CS101 Introduction to Computing Handouts PDF

Introduction to Computing – CS101 VU 1. Introduction to Computer Science 1.1. What is Computer Science? Computer Science is the discipline that seeks to build a scientific foundation for such topics as: Hardware Computer...

Introduction to Computing – CS101 VU 1. Introduction to Computer Science 1.1. What is Computer Science? Computer Science is the discipline that seeks to build a scientific foundation for such topics as: Hardware Computer hardware is the collection of physical parts of a computer system. This includes the computer case, monitor, keyboard, and mouse. It also includes all the parts inside the computer case, such as the hard disk drive, motherboard, video card, and many others. Computer hardware is what you can physically touch. Software Computer software, also called software, is a set of instructions and its documentations that tells a computer what to do or how to perform a task. Software includes all different software programs on a computer, such as applications and the operating system. Programing Computer programming is the process of designing and building an executable computer program for accomplishing a specific computing task. Networks A computer network is a set of computers connected for the purpose of sharing resources. The most common resource shared today is connection to the Internet. Other shared resources can include a printer or a file server. The Internet itself can be considered a computer network. Graphics Computer graphics is the discipline of generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer display, and many specialized applications. Robots A robot is a machine—especially one programmable by a computer— capable of carrying out a complex series of actions automatically. Robots can be guided by an external control device or the control may be embedded within Database Database, also called electronic database, any collection of data, or information, that is specially organized for rapid search and retrieval by a computer. Databases are structured to facilitate the storage, retrieval, modification, and deletion of data in conjunction with various data-processing operations. A database management system (DBMS) extracts information from the database in response to queries. Security Security are those controls that are put in place to provide confidentiality, integrity, and availability for all components of computer systems. These components include data, software, hardware, and firmware. Algorithmic Solutions Page 26 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU An algorithm is a set of instructions designed to perform a specific task. Information Processing Information processing refers to the manipulation of digitized information by computers and other digital electronic equipment, known collectively as information technology (IT). Information processing systems include business software, operating systems, computers, networks and mainframes. We will be learning the details of these terms throughout the courses in different modules. 1.2. Computer Science Applications Furthermore, Computer Science has applications in almost all domains such as:  Telecom  Banks  Hospitals  Software Development  Service Industry  Pak Army  Freelancing  and many more 1.3. Local Job Market According to famous Job market website in Pakistan, most of the jobs are available in Computer Science, for example Figure 1 shows job opportunities when filtered using “By Function”, and Figure 2 represents job opportunities when filtered using “By Industry”. In both cases, the job opportunities in Computer Science are higher than rest of the fields. Figure 1: Job Opportunities in Pakistan when classified as “By Function” Page 27 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Figure 2: Job Opportunities in Pakistan when classified as “By Industry” 1.4. International Job Market Similarly, internationally, jobs related to Computer Science are ranked on the top. For example, forbes magazine1, one of the acclaimed agencies in US claims that Software Developer has been ranked as Number 1 job in the US. In Computer Science, the following areas have been ranked by the Forbes magazine.  Artificial Intelligence and Machine Learning  Data Science  Virtual Reality  IoT  Back-End Developer  Front-End Developer  UI Designer  Full-Stack Engineer  IT Manager  Quality Assurance Expert All of this discussion would be helpful to make you motivated all the time and to be happy with the decision you have made to choose Computer Science and a career. 1.5. Are you not a student of Computer Science? Those who are not studying CS, even then this course will be helpful for them too. As this course covers all basic concepts of Computer Science which you would require in whatever field of study you are working. You know studying basics of Computer Science is compulsory for everyone even you are studying Business, Engineering, or Sciences. This course has been made very easy and interactive to make sure that you learn properly the basics of Computer Science and can apply them in your own studies. 1 https://www.forbes.com/sites/richardgano/2018/01/29/the-best-jobs-for-2018-and-beyond/#1940306742c4 accessed on 16th July Page 28 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 2 2. Breadth First Learning This course will give basic introduction to almost all courses of Computer Science. Such strategy of learning is known as Breadth First Learning. The other strategy is called Depth First Learning in which one particular course is first covered in details and then next course is covered. The Breadth First Learning helps students to first know what they will be learning in the whole degree program. We will cover: 1. Abstract view of all major courses in CS 2. Understanding what will be studied in CS 3. Why each course is important 4. Clarifying the bigger Picture Introduction to the topics will be covered in this course: 2.1. Search Engine Usage Techniques We will cover the searching techniques in this topic. How can you effectively search over the internet using popular search engine? 2.2. History of Computing We will cover in this topic that how todays computer evolved from the basic idea. 2.3. Data Storage Whatever data you enter the computer, this data need to be stored somewhere in the hardware, such storage science will be understood in this topic. 2.4. Data Manipulation Then the next thing is to study how data is manipulated. For example, how basic arithmetic operations (+,- ,*, /) are performed in computer and how some advance operators are performed. 2.5. Operating System We will study about Operating System which is the overall in-charge of the computer system. 2.6. Networking and the Internet We will also study how different computers communicate over the internet. 2.7. Algorithms We will then study the fundamental concept of algorithm in Computer Science. We define algorithm as: “Set of Steps in a sequence to perform a certain task”. 2.8. Programming Languages Then we will study programming tools. How algorithm can be written to achieve the said goal in a computer programming. We will cover just basics of C++. 2.9. Software Engineering Here we will cover that how a complete software is developed starting from the requirement gathering phase to designing, implementation and testing 2.10. Data Abstraction In Computer Science, designing a complex and large system becomes a challenge when we discuss design at a great depth, data abstraction hides complexities from the designer and helps to comprehend things with more ease. Such things will be discussed in data abstraction like Arrays, Stack, Queue, and trees. Page 29 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU 2.11. Database Systems In Computer Science, we store and link data in an organized way using state-of-the-art Database Management Systems (DBMS). We will discuss database design, DBMS functionalities in these modules. 2.12. Artificial Intelligence You know Computer is a dump device, cannot think of take inferential decisions. However, Artificial Intelligence (AI) is a specialized field of Computer Science that aims at building such Computer Systems which can act intelligently. 2.13. CS impact on society We will also learn the impact of Computer Science on society, social setups and on humans. 2.14. Content Filtering, Spam, International laws Here we will cover content filtering, dealing with the spams and international laws related to Computer Science in terms of data and privacy. 2.15. Word Processing Word processor like Microsoft Word is an application software which helps to build editable word documents, we will cover all major functionalities of Microsoft Word. 2.16. Presentations Development Presentation are built in specialized tools like Microsoft Power point. We will cover Microsoft PowerPoint tool in details to design and animate the presentation slides. 2.17. Spreadsheet To perform certain types of calculations on data, there are some specialized software like Spreadsheet. One of such software is Microsoft Excel which will be covered in such modules. 2.18. Database MS Access Database learnt above will be implemented using DBMS tool like Microsoft Access. 2.19. Web Page Development We will also learn that how a web page can be made easily using built-in tools like Dreamweaver. Page 30 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 3 3. Search Engines Search Engine like Google index web pages and helps you to retrieve the relevant web pages based on your queries. Starting from today, in next few modules, we will focus on techniques and short-cuts to retrieve most relevant information from Google. There are many search engines like Google, Yahoo, and MSN etc. However, we will focus on Google because it is most widely used search engine and has most of the market share of searching over the internet as illustrated from the Figure 3. Figure 3: Market share of Search Engines [gs.statcounter.com/search-engine-market-share] To search on Google, type: https://www.google.com/ on the web browser, you will be shown the screen like shown in the Figure 4. Figure 4: Google Search Engine home page 3.1. Query Query is the set of words given to the search engine for searching for example, if you are interested to find “Virtual University” on the internet, you will provide this the text box available in the Figure 4 and you will be given the relevant results. 3.2. How Google Works When you search in the Google by typing any query in the text box shown in the Figure 4, Google finds all those pages which contains all the terms given in the query. Try the following queries and see the results: Page 31 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU 3.3. Try Searching on Google 1. “Airport” 2. “Where is the closest airport” 3. “Virtual University in Islamabad” [Note: If you find any query with double quotations like “”, you should not give this query in double quotations on Google, I am attaching double quotations just to make sure that you can understand it is a query not a running text. Otherwise posting a query in double quotations has a particular meaning in Google which you will learn in next modules.] 3.4. Use of Microphone There is another option of microphone as can be seen in the Figure 4 on the right side. If you click on you can search by speaking. 3.5. Flip a Coin If you want to flip a coin and you do not have the coin to flip, you can use Google to do that. To achieve this just type the following on Google: “Flip a Coin” 3.6. Query Formulation Always remember, when you search, Google will try to identify the pages on which the provided term is available. For example, if your head is in pain and you type: “Head Hurts” It might not give you relevant results as when head is in pain, then its medical name is headache. So, your query should be: “Headache “ Similarly, if you are interested to search the name of the head of the virtual university and type the query as: “Head of the virtual university” Google can give you wrong result for example the web page which contains the term “head” and “virtual university” that might be the head office of virtual university. The right query could be: “Rector of virtual university” As the head of virtual university is called rector, therefore in this way it will give you more chance to search the right person effectively. 3.7. Capitalization Google does not distinguish the capital letters or small letters. This is called case-insensitive in computer science. For example, search “COMPUTER SCIENCE” or “computer science” Will not make a difference. Page 32 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 4 4. Searching Tricks In this module we will learn about searching tricks while searching on Google. 4.1. Weather Searching You can simply add the location with the word “Weather” to form such query for example: Query “Weather Lahore” will give you a screen shown in the Figure 5. Figure 5: Weather searching on Google 4.2. Performing Calculations on Google To perform calculations on Google, just type whatever you want to perform like if we want to multiply 12 with 391, we will type the query like: 12*391 and you can see in the screen shown in the Figure 6 that the Google has automatically started the calculator, have understood our query, have translated our query and given this query to calculator application and have shown the result as well. Figure 6: Calculations on Google Page 33 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Perform the following queries on your computer: 1. 12-5 2. Sin 90 3. Tan 80 4. 80/100*200 5. Subtract 10 from 30 4.3. Currency Conversion You can also see latest currency conversion on Google. For example, you want to see how much 100 Euros will be when converted to Pakistani rupees. Here is the query and result are shown in the Figure 7. Figure 7: Currency conversion on Google Try the following queries and see the results: 1. Kph in Mph 2. m in cm 3. Pakistan Cricket team 4. Baadshahi Mosque 5. Minar e Pakistan Page 34 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 5 5. Search Operators (1) In this module, we will further learn about different search operators that can be used on the Google to retrieve more relevant and focused results. 5.1. Search on Social Media When you want to use Google and want to search the query on a particular social media, you can add “@” symbol. For example, when we give queries: “Fifa World cup @facebook” and “Fifa World Cup @Twitter”, the results can be seen in the Figure 8. Figure 8: Searching in Social media over Google 5.2. Search for a price Put pkr in front of a number. For example, give a query like: “Laptop pkr 50000” it will give you laptops whose price is around 50000 as shown in the Figure 9. Figure 9: searching for a price at Google Page 35 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU 5.3. Searching Hash tags On Social media, sometimes, a hash tag is very popular, if you are interested to identify such pages using hash tag, you can use the query like: “#education” You will get result like shown in the Figure 10. Figure 10: Searching Hash tag 5.4. Exclude words from Query One term could mean more than one thing for example word: “Jaguar” is used in two meanings such as: animal and car. If you want to exclude all pages containing pages of cars, you can write the query like “Jaguar -cars”. 5.5. Exact Match If you want to search for an exact phrase enclose it in double quotes, in this case, the search engine will search where it can find the exact phrase as it is. For example, searching “Tallest Building in Pakistan” will give only those pages which contains exact this phrase, however, if you give the query like: Tallest Building in Pakistan Google will give you all those pages which contains all or any of these words. 5.6. Wild Card based Searching You can search a phrase when even you do not know what word would be there at a particular location for example, you want to search all those pages which contains any word in the start and then contains the exact phrase “is thicker than water”. You can write: “* is thicker than water” This query will give you all those pages which contains any word in the start and then have the exact phrase “is thicker than water” Please note if you search “is thicker than water”, it might give you those pages where such question has been posed or there is no word in the start, but the phrase is written like “is thicker than water”. Page 36 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 6 6. Search Operators (2) This module will further explore more search operators. 6.1. Searching within the range If you want to search within the range of number, you can use two dots. For example: “laptop pkr25000. pkr35000” will try to give those pages which contains laptop options between the specified ranges. 6.2. Boolean Operators We can use Boolean operators specially “And” “Or” to find relevant pages. For example, writing a query: Computer and Science Will give you all those pages which have both words but not necessarily they occur together. Similarly writing a query: Computer Or science Will give you those pages in which either the term “computer” is written, or “science” is written. Off course, it will also return those pages in which both terms are also written. 6.3. Search with a Specific Site If you are interested to search the query in a website, we can write like:  “virtual university site: youtube.com” This will give us those pages of virtual university which are contained within the youtube.com website. 6.4. Searching Related Websites For example, you like the videos on YouTube and interested to know are there some more websites like YouTube? you can type the query:  “related:youtube.com” Furthermore, you can also search information for a particular website like if you write:  “info:youtube.com” It will provide the information about this website. 6.5. Searching a cached version If the website is down and you are interested to see the cached version of the website, you can use the following query:  cache:youtube.com Searching on a file type If you are interested to search a query for a specific file type, you can include such file type in the query. For example, we are interested to search for “virtual university” but all those pages having file type PDF, so you can write a query:  “Virtual University” filetype:pdf  “Virtual University” ext:pdf Page 37 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 7 7. Search Operators (3) In this module we will further learn about some remaining search operators. 7.1. Stocks Operator Using this operator, we can find the trend of the stock market for a particular company for example, if we want to see what the stock market trend for the company “Apple” is, we can write the following query:  stocks:aapl 7.2. Map Operator If we are interested to see the map of some location, we can use map operator in the following way:  map:Lahore 7.3. Movie Operator Using movie operator, we can find information about any movie. For example, try:  movie:steve jobs 7.4. Compare Food If you want to compare two foods based on their nutrient values, you can go and explore the following website:  https://www.myfooddata.com/ 7.5. Define Operator If you are interested to find the definition of a particular term, type:  Define:Computer 7.6. Image Search There is a dedicated web link at Google: https://images.google.com/ Using this link, you can search images even by giving a query of another image. Google will provide you other images which look quite similar to the queried image. 7.7. Tilt This is an interesting option available at Google. Using this option, you can perform number of funny things with the shown screen of the Google. For example, you can rotate the Google screen to 360 degree etc. To do it type the following query:  Tilt On the show results, select the appropriate link like: https://elgoog.im/tilt/ and then perform the interesting tricks with the Google screen. Page 38 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 8 8. Advanced Search Operators In this module, we will learn some advanced search operators. 8.1. Intitle This operator will give us only those web pages in which the searched term appears in the title of the web pages. For example, if we are interested to search web pages in which the phrase “iPhone vs. android” appears in the title, we can write the following query.  Intitle:“iPhone vs. android” 8.2. Allintitle The next similar operator is allintitle without double quotation. This will find all those web pages in which any of the word “IPhone” or “android” is found. The query would be:  allintitle:iphone vs. android 8.3. inurl and allinurl The “inurl” operator finds all those web pages which contains the mentioned query in the url of the web pages. For example, if we try the following query:  inurl:2018 “virtual university” This will give us all those web pages in which 2018 is written and the phrase “virtual university” is written. As we had allintitle above, here again we have allinurl which means it will find any of the those mentioned terms within the url and will fetch all those pages in which any of the mentioned query terms are present. 8.4. Intext and allintext If we are interested to search anywhere in the body of the document, we can use intext operator, for example:  intext:“virtual university admissions 2018” this will give all those pages in which the whole phrase is present as it is. Furthermore, we can try:  allintext:virtual university admissions 2018 Which will return all those pages in which any of those terms are available. 8.5. Proximity Search Suppose we are interested to search two words:  Education  Virtual university But both words should be collocated on the web page within the margin of three words. To achieve this, we can use the operator around.  education AROUND(3) "virtual university" This query will give all those web pages on which both words are available within the margin of three words. 8.6. Let’s solve a complex Query As we have learnt many operators, now let’s solve a bit complex query. The query is: “We are interested to see how many of pages of a website are not secured?”  site:youtube.com –inurl:https Page 39 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 9 9. What we should not search on Internet We have learnt different tricks and operators to ease the task of searching on the Google. However, there are many things which we should not search on Google. But Why? There are three main reasons: 1) Google Adds: Google give you advertisements based on your search queries, history, geographical location etc. 2) Security Agencies: law and enforcement agencies might see your queries and can enquire you or can reach at your location if they see a sensitive term searching again and again. 3) Sometimes, when we search like free music, we can be trapped to provide a virus which might be harmful for our computer. By keeping in view, the above three points, the followings and related things must not be searched over the internet: 9.1. Avoiding Ads: Searching the followings can avoid un-necessary ads from the search engines.  Your email  Medical issues and drugs  Your name  Your location  Your favorite things 9.2. Dangerous to Search Searching the followings can alert the law enforcement agencies or any organization who is keeping eye on the security threats. There is one typical such Pressure Cooker bomb story. When someone searched this term and the security agency representatives reached to the particular location from where such searching was performed. Therefore, avoid searching the followings:  pressure cooker bomb story  Attacks  Suicide bomb  Killers/Underworld  Terrifying insects  Killing animals  Poisons  Murder  Medical Symptoms  How to make computer Virus  Hacking  About Religion  About Politics 9.3. Avoid Cyber-security attacks Avoid searching the followings:  Free Music The hackers normally add many viruses to such websites as the information seeker of free music etc. Page 40 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU 9.4. Unpleasant Results You might search the followings or similar thing and might get unpleasant results which might depress you.  Smokers Lungs  Skin Condition Page 41 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 10 10. Roots of Computing Here we will see how we moved from mechanical driven machines to electronics driven machine (Computer). 10.1. Abacus One of the earlier computing devices was the abacus. History tells us that it probably had its roots in ancient China and was used in the early Greek and Roman civilizations. The machine is quite simple, consisting of beads strung on rods that are in turn mounted in a rectangular frame as shown in the Figure 11. Figure 11: Abacus 10.2. Technology of Gears In the time period after the Middle Ages and before the Modern Era, the quest for more sophisticated computing machines was seeded. A few inventors began to experiment with the technology of gears. Among these were Blaise Pascal (1623–1662) of France, Gottfried Wilhelm Leibniz (1646–1716) of Germany, and Charles Babbage (1792–1871) of England. These machines represented data through gear positioning, with data being entered mechanically by establishing initial gear positions. Output from Pascal’s and Leibniz’s machines was achieved by observing the final gear positions. Babbage, on the other hand, envisioned machines that would print results of computations on paper so that the possibility of transcription errors would be eliminated. One typical diagram is shown in the Figure 12. Page 42 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Figure 12: Gear Technology 10.3. Punch Cards Herman Hollerith (1860–1929), who applied the concept of representing information as holes in paper cards to speed up the tabulation process in the 1890 U.S. census. (It was this work by Hollerith that led to the creation of IBM.) Such cards ultimately came to be known as punched cards and survived as a popular means of communicating with computers well into the 1970s. One typical punch card machine is illustrated in the Figure 13. Figure 13: Punch Cards Mechanical-driven to Electronics-driven machines Nineteenth-century technology was unable to produce the complex gear-driven machines of Pascal, Leibniz, and Babbage cost-effectively. But with the advances in electronics in the early 1900s, this barrier Page 43 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU was overcome. Examples of this progress include the electromechanical machine of George Stibitz, completed in 1940 at Bell Laboratories, and the Mark I, completed in 1944 at Harvard University by Howard Aiken and a group of IBM engineers. These machines made heavy use of electronically controlled mechanical relays. In this sense they were obsolete almost as soon as they were built, because other researchers were applying the technology of vacuum tubes to construct totally electronic computers. 10.4. ENIAC More flexible machines, such as the ENIAC (electronic numerical integrator and calculator) developed by John Mauchly and J. Presper Eckert at the Moore School of Electrical Engineering, University of Pennsylvania, soon followed as shown in the Figure 14. Figure 14: ENIAC 10.5. Factsheet of ENIAC  Occupied 1800 square feet  20, 000 vacuum tubes  1500 relays  10, 000 capacitors  70, 000 registers  200 Kilo Watt electricity  Weight 30tons  Cost = $487, 000  PKR = 62.5 millions [https://www.computerhope.com/jargon/e/eniac.htm] 10.6. Rapid Advancement Since the invention of ENIAC, there was a rapid advancement. Some key milestones are listed below:  Transistor  Integrated Circuits  Size reduction  Processing Power doubling in 2 years  Desktop computer by Steve Jobs and Stephen Wozniak in 1976  IBM launched PC in 1981 Page 44 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU  Web  Smart Phones Page 45 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 11 11. Bits In Computer, all kind of information is stored in bits. Bit is the basic unit of storage. 11.1. Basics  Information is coded as pattern of 0 or 1  Short form of Binary Digits  One bit can contain only one value 0 or 1 11.2. What Bits can represent:  Representing numbers, text, audio, video, image etc.  In Chip electric Charge 0/1 11.3. Bits units Table 1 shows the bits and their equivalent units. Table 1: Bits Units Unit Equivalent 1 Byte 8 bits 1 Kilo Byte (KB) 1024 Bytes 1 Mega Byte (MB) 1024 KB 1 Giga Byte (GB) 1024 MB 1 Tear Byte (TB) 1024 GB 11.4. Patterns Using Bits In one bit we can represent two patterns either 0 or 1, if we have 2 bits then 4 different patterns can be representing as shown in the Table 2. Table 2: bits patterns for two bits 00 01 10 11 Let’s comprehend all bit patterns, we will have the Table 3. Table 3: Bits and their number of patterns Bits Number of Patterns 1 2 2 4 3 8 4 16 5 32 6 64 7 128 8 = 1 byte 256 Page 46 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU At page 577 of your book2, you can find ASCII codes, using which we can represent different characters. For example, representing character “A” we need to represent it using digit 65. The bit pattern of 65 would be: 01000001. How did we get this, we will learn in details, at the moment you can just try to learn very basic method of converting decimal to binary. As the binary is represented using base 2. To represent any number, please form the representation as shown in the Table 4. Table 4: representing decimal to Binary 27 26 25 24 23 22 21 20 128 64 32 16 8 4 2 1 Now whatever number you want to represent, put 1 the respective bit. For example if you want to represent the decimal 2, just put 1 on the second bit from the right side and put zeros otherwise, you will get the number 2 in binary as shown in the Table 5. Table 5: Representing Decimal 2 in Binary 27 26 25 24 23 22 21 20 128 64 32 16 8 4 2 1 0 0 0 0 0 0 1 0 Similarly, 8 will be represented as: 00001000, 65 will be represented as: 01000001 2 Computer Science – An Overview by J. Glenn Brookshear and Dennis Brylow Page 47 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 12 12. Boolean Operations To understand how individual bits are stored and manipulated inside a computer, it is convenient to imagine that the bit 0 represents the value false and the bit 1 represents the value true. Operations that manipulate true/false values are called Boolean operations, in honor of the mathematician George Boole (1815–1864), who was a pioneer in the field of mathematics called logic. Three of the basic Boolean operations are AND, OR, and XOR (exclusive or). The “AND” operation and “OR” are summarized in the Figure 15. 12.1. AND Boolean Operation It produces the output as 1 when both of the inputs are 1. Otherwise, it gives output as 0 as shown in the Figure 15. 12.2. OR Boolean Operation It produces output of 1 when any of the inputs are 1, otherwise 0 as shown in the Figure 15. Figure 15: AND, OR Boolean operation 12.3. XOR Boolean Operation XOR (Exclusive or) is another Boolean operation which produces the output of 1 when both inputs are different. It produces 0 when both inputs are same as shown in the Figure 16. 12.4. Not Operation Not operation takes one input, produces 1 when input is 0 and produces 0, when the input is 1 as shown in the Figure 16. Page 48 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Figure 16: XoR, Not operation 12.5. Boolean Operation Example To demonstrate the working of the Boolean operations, an example has been shown in the Table 6. First two rows represent the bit patterns as “A” and “B” and next rows are self-explanatory to perform “AND”, “OR”, “XOR”, “Not” on both “A” and “B”. Table 6: Example of Boolean operation Page 49 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 13 13. Hexadecimal Notation 13.1. Why we need Hexadecimal Notation When considering the internal activities of a computer, we must deal with patterns of bits, which we will refer to as a string of bits, some of which can be quite long. A long string of bits is often called a stream. Unfortunately, streams are difficult for the human mind to comprehend. Merely transcribing the pattern 101101010011 is tedious and error prone. To simplify the representation of such bit patterns, therefore, we usually use a shorthand notation called hexadecimal notation, which takes advantage of the fact that bit patterns within a machine tend to have lengths in multiples of four. In particular, hexadecimal notation uses a single symbol to represent a pattern of four bits. For example, a string of twelve bits can be represented by three hexadecimal symbols. 13.2. Hexadecimal Representation Table 7 presents the hexadecimal notation. Table 7: Hexadecimal Notation 13.3. Hexadecimal Example Let’s solve an example from the book, on page 38, Q#5 (b), we want to represent the following bit pattern in hexadecimal. 111010000101010100010111 Our strategy would be to divide it in four bit pattern as shown in the Table 8. Table 8: hexadecimal example 1110 1000 0101 0101 0001 0111 E 8 5 5 1 7 So the hexadecimal notation for: 111010000101010100010111 Is E85517. Page 50 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 14 14. Storing a Bit 14.1. Main Memory For the purpose of storing data, a computer contains a large collection of circuits (such as flip-flops), each capable of storing a single bit. This bit reservoir is known as the machine’s main memory. A typical Flip- flop is shown in the Figure 17 Figure 17: Flip flop 14.2. Main Memory Organization  Manageable unit Cells – 8 bits  Household devices have few hundreds of cells  Large computer may have billions of cells 14.3. Byte Size Organization In Computer Science, there is no left or right, however, to understand the significance of bits, we represent most significant bits on left side while least significant bits on the right size as shown the Figure 18. Figure 18: Byte organization in memory 14.4. Memory Address To identify individual cells in a Computer’s main memory, each cell is assigned a unique “name,” called its address. It has been shown in the Figure 19. Page 51 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Figure 19: Memory arranged with respect to addresses 14.5. RAM The cells (represented in Figure 19) can be accessed independently as required. To reflect the ability to access cells in any order, a computer’s main memory is often called random access memory (RAM). 14.6. DRAM Dynamic ram – Stores bits as tiny electric Charge, refreshes many times a second. 14.7. SDRAM Synchronous DRAM is used in reference to DRAM that applies additional techniques to decrease the time needed to retrieve the contents from its memory cells. Page 52 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 15 15. Magnetic Systems 15.1. Mass Storage Due to the volatility and limited size of a computer’s main memory, most computers have additional memory devices called mass storage (or secondary storage) systems, including magnetic disks, CDs, DVDs, magnetic tapes, flash drives, and solid-state disks (all of which we will discuss shortly). The advantages of mass storage systems over main memory include less volatility, large storage capacities, low cost, and in many cases, the ability to remove the storage medium from the machine for archival purposes. 15.2. How it works One typical device has been shown in the Figure 19.  Thin spinning disk with magnetic coating to hold data  Read/Write Heads placed above or below disk  Each head traverses a circle called track.  Normally, each track is divided into equal sectors  Sectors have equal number of bits: 512 bytes to few KBs.  Outer tracks contain more information. Figure 20: Disk Storage System 15.3. Zoned-bit recording  Adjacent tracks form Zones.  A typical disk contains 10 zones  All tracks within a zone have equal number of sectors. 15.4. Seek Time Time required to move the read/write heads from one track to another. 15.5. Rotation Delay Average amount of time required for the desired data to rotate around to the read/write head once the head has been positioned over the desired track. 15.6. Access Time The sum of seek time and rotation delay Page 53 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU 15.7. Transfer rate The rate at which data can be transferred to or from the disk. Page 54 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 16 16. Optical System Another class of mass storage system applies optical technology. An example is the compact disk (CD). Digital Versatile Disks (DVDs) and Blu-ray Disks (BDs) are also popular examples of optical systems. 16.1. Compact Disk Data storage in terms of tracks has been shown in the Figure 21. The characteristics of a CD are:  12 centimeter in diameter  Consists of reflective material  Information is recorded on them by creating variations in their reflective surfaces.  Data is stored on a single-track spiral from inside outside.  Each track is divided into sectors,  Capacity of a sector is 2KB of data, 1/75 of a second audio music.  Retrieval using a Laser that detects the irregularities on the reflective surface of the CD as it spins  Initially applied on audio recording using format CD-DA (compact disk-digital audio)  Format is being used even today to store computer data  Single Track  As all sectors are not individually accessible in Optical system having one track, therefore, the data retrieval is faster in magnetic systems than optical systems.  Optical System is best suited for long continuous string of data. Figure 21: Data storage in CD 16.2. DVD (Digital Versatile Disks) CDs capacity is 600 to 700 MB; however, DVD has space in GBs as have multiple semi-transparent layers, which can be viewed by precise focused laser. Its shape is like CD. 16.3. BDs (Blue Ray Disks) BDs use a blue-violet spectrum of light (instead of red), which is able to focus its laser beam with very fine precision. BDs provide five-time capacity than DVDs. Module 17 17. Flash Drives 17.1. Issues in Magnetic and Optical Systems  Physical motion is required Page 55 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU  Moving Read/Write heads  Aiming Laser beams  All this takes lot of time in comparison with electronic circuitry 17.2. Flash Drive Technology  Bits are stored by sending electronic signals directly to the storage medium where they cause electrons to be trapped in tiny chambers of silicon dioxide  Chambers are able to store data for years without external power.  Repeated erasing slowly damages the silicon dioxide chambers  Not suitable in place of Main memory  Suitable where alterations can be controlled like cameras, smart phones, portable devices  Not reliable as optical disks for long term 17.3. SSDs (Solid State Disks)  Larger Flash memory devices designed to take place of magnetic disks  Quite operations and low access time  However, costly than magnetic systems 17.4. SDs (Secure Digital Memory Cards)  Provide up to few GBs of storage  Available in smaller, mini, and micro sizes  SDHC (High Capacity) can provide 32 GBs  SDXC (Extendable Capacity) may exceed to TB.  Compact physical size, suitable for car navigation, cameras etc. Page 56 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 18 18. Representing Text This module highlights that how a text is stored with the computer memory. 18.1. Representation as Code  Each Textual Symbol is represented with a unique bit pattern  Normally 8 bits for each character  “Virtual University”  18 characters = 18*8 (144) bits or 18 bytes  In 1940’s and 1950’s many such codes were designed  American National Standards Institute (ANSI)  American Standard Code for Information Interchange (ASCII) 18.2. ASCII Codes  7 bits for information and most significant bit has zero  27combinations= 128  Uppercase, lower case, punctuation marks, digits 0 to 9, line feed, carriage returns, and tabs  Available at page 577 of your book. 18.3. ASCII code example Suppose we want to represent “Hello”, by looking at the ASCII table available in your book, the solution is represented in the Figure 22: Figure 22: ASCII code example 18.4. Limitation of ASCII codes  Only 128 characters  International Organization for Standardization (ISO) come-up with many extensions to ASCII  One to support western language symbols. 18.5. Limitations of ASCII-extensions  256 are still insufficient to denote all language symbols  Document having multiple languages could not be read as it should follow a one standard 18.6. Unicode  Internationalization of codes by manufacturers of hardware and software  Unique patterns of 21 bits  Compliance with ASCII  Supporting thousands of character sets of Chinese, Hebrew, Japanese 18.7. UTF-8  Uses 24 to 32 bits having large possibilities for expansion  224= 16,777,216 unique symbols  File consisting of long symbols encoded with ASCII or Unicode is called text file. Page 57 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 19 19. Representing Numeric Values This module explains how the numeric values can be represented. 19.1. Issues in storing numeric as Unicode  Inefficient suppose you want to store 12, you would need 16 bits to do that  99 could be stored in 16 bits  We will learn 16 bits can store 65,535 numeric values 19.2. Binary Notation Binary notation is a way of representing numeric values using only the digits 0 and 1 rather than the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Let’s represent numeric values using three bits as shown in the Table 9. Table 9: Three-bit representation of Numeric values If we add another bit and takes 4 bits then you can observe in the Table 10, we can represent 16 values [ranging from 0 to 15] Table 10: 4 bits representation of Numeric Values If we closely look into the representation, we can represent 2 n numbers if we have n bits. Therefore, if we have 16 bits, we can represent 216 = 65536 numeric values. 19.3. Binary Notation Variations Binary notation has two following representations, we will learn them in detail in the upcoming modules.  Two’s complement for storing whole numbers  Floating point notation for fractional numbers Page 58 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 20 20. Representing Images In this module, we will learn how images are stored in the memory. 20.1. Pixel  Collection of dots – Pixel short for Picture Element.  Appearance of each pixel is encoded to form bit map.  Many display devices, printers work on Pixel concept. 20.2. Encoding Method: Pixel to Bitmap  In black and white images, each pixel is represented as one bit – e.g. 0 for black and 1 for white  Often used in Facsimile 20.3. Encoding Method: Handling shades  8 bits are used instead of 1 bit to store the shades of grayness. 20.4. Encoding Method: Colorful Images  RGB encoding  One byte for Red, one byte for Green, and one-byte Blue – Three bytes to represent one pixel. 20.5. Brightness Chrominance  One brightness component and two-color components.  Brightness component= Pixel’s luminance (sum of red, green, and blue)  Blue Chrominance and Red Chrominance  Difference between luminance and amount of blue or red. 20.6. Image Scaling  Scaling to a larger size needs more pixels  Digital Zoom 20.7. Geometric Structures for Image Scaling  Collection of lines and curves  Using Analytical Geometry  Technique: How geometric structures should be displayed rather Pixel reproduction 20.8. Scalable Fonts  TrueType by Microsoft and Apple  PostScript by Adobe  Also popular in Computer Aided Design (CAD) Page 59 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 21 21. Representing Sound 21.1. Sound Amplitude It is the extent to which air particles are displaced, and this amplitude of sound or sound amplitude is experienced as the loudness of sound. 21.2. How to encode the Sound  Sample the amplitude of sound at regular intervals and record the values as shown in the Figure 23.  8000 samples per second for long distance telephone communication Figure 23: Encoding the amplitude of the sound 21.3. How Sound data communication takes place  At one end, it stores amplitude numeric values for each eight thousand of a second  Transmitted over the network  Received on other end and sound is produced using amplitude. 21.4. Sample Intervals After how long we should take the sample depends on how accurate and high definition sound recordings are required.  8000 is not enough for high fidelity music recordings  44, 100 samples per second are recorded in today’s CD’s.  Data from each sample is recorded in 16 bits (32 bits for Stereo)  32*44100 = million bits/sec 21.5. Alternative Method: MIDI  Musical Instrument Digital Interface.  Used in music synthesizers found in electronic keyboards.  Encode directions for producing music rather than storing music itself.  2 seconds sound can be stored in 3 bytes rather than 2 million bits.  Encoding the "Sheet music" read by performer rather than the performance itself.  MIDI recordings could be significantly different when performed on different synthesizer. Page 60 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 22 22. Binary Notation Quantity associated with each position is twice the quantity associated with the position to its right. 22.1. Power Method To understand binary notation first recall decimal numbers we use in our daily life, when we say 375. The representation of 375 in decimal system is available in the Table 11. Table 11: Decimal System representation Hundreds Tens Units 102 = 100 101 = 10 100 = 1 3 7 5 In each of the position we can use any number from 0 to 9. However, in binary system we can use only 0 or 1 at each position and from right side it represents 2 0 and onwards as illustrated in the Table 12. For example, if we want to represent 32, we will just put 1 in that particular location and rest are 0s. Table 12: Binary System Representation 27 26 25 24 23 22 21 20 128 64 32 16 8 4 2 1 0 0 1 0 0 0 0 0 Similarly, if we want to represent 255, we will put 1 in all locations as: 11111111 If you count (128+64+32+16+8+4+2+1 = 255). 22.2. Algorithm for Finding Binary Representation of a Positive Decimal Number Remember, algorithm was a set of steps to perform a certain task. To convert a positive decimal number, the set of steps are shown in the Figure 24. Figure 24: Algorithm for converting positive decimal to binary number Let’s apply this algorithm, suppose we have the number 13 and wants to convert it to the equivalent binary, the working of this algorithm is shown in the Figure 25. Page 61 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Figure 25: Algorithm working for converting positive decimal to binary Page 62 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 23 23. Binary Addition In this module, you will learn the binary addition. As we are dealing with two bits while adding them, there could be 4 possibilities, firstly whether both bits are zero, secondly first bit is one and second is zero, thirdly first bit is zero and second bit is one, fourthly both are one. All four cases and their sum is illustrated in the Figure 26. Figure 26: Binary Addition basics We will apply these rules from right to left as we do the addition of decimal numbers, when we come across 10, we will place 0 and takes 1 as a carry. Different examples have been shown in the Figures 27 to 29. Figure 27: Example 1 of Binary Addition Figure 28: Example 2 of Binary Addition Page 63 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Figure 29: Example 3 of Binary Addition Page 64 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 24 24. Fraction in Binary 24.1. Radix Point  As we have decimal point  Digits on left side represent the whole number  Digits on right side represent the fractional part 24.2. Example of Radix Point The example has been shown in the Figure 30. Figure 30: Radix point example How to read the data represented in the Figure 30, consider the Figure 31. Figure 31: Understanding Fraction represented in Binary 24.3. Addition in fraction It is same as the addition in decimal system, you need to align the radix point and perform the addition as we did in simple binary or decimal system illustrated in the previous modules. For example, 10.011 added to 100.11 produces 111.001, as shown in the Figure 32. Figure 32: Binary addition Page 65 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 25 25. 2’s Complement Notation to Store Numbers The most popular system for representing integers within today’s computers is two’s complement notation. Integer Representation in 2’s Complement 25.1.  Fixed number of bits to represent each value  Normally 32 bits are used  We will discuss smaller examples for demonstration purpose.  For +ve integers, starting from zero going upward until a single zero is reached followed by all 1’s  For -ve integers, starting from all 1's going downwards until a single 1 is reached followed by all 0's.  Left most bit = sign bit. Integers are represented in the pattern of three lengths in the Figure 33 and patterns of four lengths have been represented in the Figure 34. Figure 33: 2's complement Figure 34: 2's complement notation for three bits notation for four bits patterns patterns 25.2. Conversion between positive and negative representations One trick to convert between positive and negative numbers represented in 2’s complement is as follows: 1. Start from right most bit. 2. Start copying until first 1 arrives 3. After first 1 is found, complement all numbers i.e 0 to 1 and 1 to 0 For example, you know the binary of 7 in 2’s complement notation which is 0111, now if you want to find the binary form of -7, apply the above rule and you will get 1001. 25.3. Addition in 2’s complement notation The beauty of 2’s complement notation is that it works perfectly fine by using the same method of addition as we studied earlier, for more understanding carefully look at the Figure 35. Page 66 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Figure 35: Addition in 2's complement notation 25.4. Problem of Overflow  Using 4 bits, maximum positive number 7 can be represented and -8 on the negative side.  5+4 = 9 which cannot be stored in four bits  Result would be as -7.  Can be deducted using sign bit.  Today’s computer have longer bit pattern normally 32 bits  Maximum positive value = 2,147,483,647  If still overflow occurs, we can use even more bits, or changing the units like calculating answer in Kilometer than meter.  Previously 16 bits were used to store 2’s complement notation, maximum number represented was 32,768  On “September 19, 1989”, Hospital system malfunctioned as 32, 768 days had been passed after “January 1, 1900”, and thus it produced negative value. Page 67 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 26 26. Excess Notation This is another method of representing integer values. 26.1. Integer Representations in Excess Notation  Fixed number of bits to represent each value  Write down all bit patterns of the same length  First bit pattern having 1 in the most significant bit is used to represent Zero  Following values used to represent positive numbers and Preceding values to represent negative numbers.  Each value in Excess notation is Excess of its original value in Binary  1011 represent 11 in Binary but here it is representing 3 (excess of 8).  Excess 16 to represent 10000 as Zero  Excess 4 to represent 100 as Zero Excess 8 notation is shown in the Figure 36. Figure 36: Excess eight notation 26.2. Excess Four Notation  Excess 4 to represent 100 as Zero  Values are Excess of 4 as shown in the Figure 37. Figure 37: Excess Four notation 26.3. Excess Four Notation Comparisons Let’s see the differences of bits patterns represented in Binary, Excess 4, and 2’s complement. Such comparison is shown in the Figure 38. Page 68 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Figure 38: Excess four notation comparisons Page 69 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 27 27. Floating Point Notation In contrast to the storage of integers, the storage of a value with a fractional part requires that we store not only the pattern of 0s and 1s representing its binary representation but also the position of the radix point. A popular way of doing this is based on scientific notation and is called floating-point notation. 27.1. Storing Radix  Numbers with fractional part have a radix, so its important to store the position of Radix  One popular way is floating-point notation  For demonstration purpose we will use examples of 8 bits storage system. 27.2. Storing Fractions We first designate the high-order bit of the byte as the sign bit. Once again, a in the sign bit will mean that the value stored is nonnegative, and a 1 will mean that the value is negative. Next, we divide the remaining 7 bits of the byte into two groups, or fields: the exponent field and the mantissa field. Let us designate the 3 bits following the sign bit as the exponent field and the remaining 4 bits as the mantissa field. Figure 39 illustrates how the byte is divided. We can explain the meaning of the fields by considering the following example. Suppose a byte consists of the bit pattern 01101011. Analyzing this pattern with the preceding format, we see that the sign bit is 0, the exponent is 110, and the mantissa is 1011. To decode the byte, we first extract the mantissa and place a radix point on its left side, obtaining.1011 Figure 39: Floating-point notation components Next, we extract the contents of the exponent field (110) and interpret it as an integer stored using the 3-bit excess method (see again Figure 39). Thus the pattern in the exponent field in our example represents a positive 2. This tells us to move the radix in our solution to the right by 2 bits. (A negative exponent would mean to move the radix to the left.) Consequently, we obtain: 10.11 Which is the binary representation for 23⁄4. (Recall the representation of binary fractions from Figure 1.18.) Next, we note that the sign bit in our example is 0; the value represented is thus nonnegative. We conclude that the byte 01101011 represents 23⁄4. Had the pattern been 11101011 (which is the same as before except for the sign bit), the value represented would have been 23⁄4. As another example, consider the byte 00111100. We extract the mantissa to obtain.1100 and move the radix 1 bit to the left, since the exponent field (011) represents the value -1. We therefore have.01100 Page 70 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Which represents 3/8. Since the sign bit in the original pattern is 0, the value stored is nonnegative. We conclude that the pattern 00111100 represents 3⁄8. To store a value using floating-point notation, we reverse the preceding process. For example, to encode 11⁄8, first we express it in binary notation and obtain 1.001. Next, we copy the bit pattern into the mantissa field from left to right, starting with the leftmost 1 in the binary representation. At this point, the byte looks like this: - - - - 1 0 0 1 We must now fill in the exponent field. To this end, we imagine the contents of the mantissa field with a radix point at its left and determine the number of bits and the direction the radix must be moved to obtain the original binary number. In our example, we see that the radix in.1001 must be moved 1 bit to the right to obtain 1.001. The exponent should therefore be a positive one, so we place 101 (which is positive one in excess four notation as shown in Figure 1.23) in the exponent field. Finally, we fill the sign bit with 0 because the value being stored is nonnegative. The finished byte looks like this: 01011001 There is a subtle point you may have missed when filling in the mantissa field. The rule is to copy the bit pattern appearing in the binary representation from left to right, starting with the leftmost 1. To clarify, consider the process of storing the value 3⁄8, which is.011 in binary notation. In this case the mantissa will be - - - - 1 1 0 0 It will not be - - - - 0 1 1 0 This is because we fill in the mantissa field starting with the leftmost 1 that appears in the binary representation. Representations that conform to this rule are said to be in normalized form. Using normalized form eliminates the possibility of multiple representations for the same value. For example, both 00111100 and 01000110 would decode to the value 3⁄8, but only the first pattern is in normalized form. Complying with normalized form also means that the representation for all nonzero values will have a mantissa that starts with 1. The value zero, however, is a special case; its floating-point representation is a bit pattern of all 0s. Module 28 28. Truncation Errors in Floating Point Notation Let us consider the annoying problem that occurs if we try to store the value 25⁄8 with our one-byte floating- point system. We first write 25⁄8 in binary, which gives us 10.101. But when we copy this into the mantissa field, we run out of room, and the rightmost 1 (which represents the last 1⁄8) is lost (Figure 40). If we ignore this problem for now and continue by filling in the exponent field and the sign bit, we end up with the bit pattern 01101010, which represents 21⁄2 instead of 25⁄8. What has occurred is called a truncation error, or round- off error—meaning that part of the value being stored is lost because the mantissa field is not large enough. Page 71 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Figure 40: Encoding the value 25⁄8 28.1. Primitive Methods for Handling Truncation Errors The significance of such errors can be reduced by using a longer mantissa field. In fact, most computers manufactured today use at least 32 bits for storing values in floating-point notation instead of the 8 bits we have used here. This also allows for a longer exponent field at the same time. Even with these longer formats, however, there are still times when more accuracy is required. Another source of truncation errors is a phenomenon that you are already accustomed to in base 10 notation: the problem of nonterminating expansions, such as those found when trying to express 1⁄3 in decimal form. Some values cannot be accurately expressed regardless of how many digits we use. The difference between our traditional base 10 notation and binary notation is that more values have nonterminating representations in binary than in decimal notation. For example, the value 1/10 is nonterminating when expressed in binary. Imagine the problems this might cause the unwary person using floating-point notation to store and manipulate dollars and cents. In particular, if the dollar is used as the unit of measure, the value of a dime could not be stored accurately. A solution in this case is to manipulate the data in units of pennies so that all values are integers that can be accurately stored using a method such as two’s complement. 28.2. Intelligent Processing for Handling Truncation Errors  Lets suppose we want to store  2½ + 1/8 + 1/8  If we add 2½ to 1/8 we ends up with 25/8 which is 10.101 which cannot be stored in 4 bit mantissa.  The result 10.10 would be 2½ this means the 1/8 is truncated In this situation, the following can be done:  Lets add first 1/8 to 1/8 which is ¼ or.01, can be stored and result would be 00111000  Now add this to 2½ now we got 2¾ = 01101011 which is accurate.  Order is important, adding small quantities together first might give significant quantity to be added to large quantity. Page 72 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 29 29. Data Compression: Generic Techniques Data compression schemes fall into two categories. Some are lossless, others are lossy. Lossless schemes are those that do not lose information in the compression process. Lossy schemes are those that may lead to the loss of information. Lossy techniques often provide more compression than lossless ones and are therefore popular in settings in which minor errors can be tolerated, as in the case of images and audio. In cases where the data being compressed consist of long sequences of the same value, the compression technique called run-length encoding, which is a lossless method, is popular. It is the process of replacing sequences of identical data elements with a code indicating the element that is repeated and the number of times it occurs in the sequence. For example, less space is required to indicate that a bit pattern consists of 253 ones, followed by 118 zeros, followed by 87 ones than to actually list all 458 bits. Another lossless data compression technique is frequency-dependent encoding, a system in which the length of the bit pattern used to represent a data item is inversely related to the frequency of the item’s use. Such codes are examples of variable-length codes, meaning that items are represented by patterns of different lengths. David Huffman is credited with discovering an algorithm that is commonly used for developing frequency-dependent codes, and it is common practice to refer to codes developed in this manner as Huffman codes. In turn, most frequency-dependent codes in use today are Huffman codes. As an example of frequency-dependent encoding, consider the task of encoded English language text. In the English language the letters e, t, a, and I are used more frequently than the letters z, q, and x. So, when constructing a code for text in the English language, space can be saved by using short bit patterns to represent the former letters and longer bit patterns to represent the latter ones. The result would be a code in which English text would have shorter representations than would be obtained with uniform-length codes. In some cases, the stream of data to be compressed consists of units, each of which differs only slightly from the preceding one. An example would be consecutive frames of a motion picture. In these cases, techniques using relative encoding, also known as differential encoding, are helpful. These techniques record the differences between consecutive data units rather than entire units; that is, each unit is encoded in terms of its relationship to the previous unit. Relative encoding can be implemented in either lossless or lossy form depending on whether the differences between consecutive data units are encoded precisely or approximated. Still other popular compression systems are based on dictionary encoding techniques. Here the term dictionary refers to a collection of building blocks from which the message being compressed is constructed, and the message itself is encoded as a sequence of references to the dictionary. We normally think of dictionary encoding systems as lossless systems, but as we will see in our discussion of image compression, there are times when the entries in the dictionary are only approximations of the correct data elements, resulting in a lossy compression system. Dictionary encoding can be used by word processors to compress text documents because the dictionaries already contained in these processors for the purpose of spell checking make excellent compression dictionaries. In particular, an entire word can be encoded as a single reference to this dictionary rather than as a sequence of individual characters encoded using a system such as UTF-8. A typical dictionary in a word processor contains approximately 25,000 entries, which means an individual entry can be identified by an integer in the range of 0 to 24,999. This means that a particular entry in the dictionary can be identified by a pattern of only 15 bits. In contrast, if the word being referenced consisted of six letters, its character-by-character encoding would require 48 bits using UTF-8. Page 73 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU A variation of dictionary encoding is adaptive dictionary encoding (also known as dynamic dictionary encoding). In an adaptive dictionary encoding system, the dictionary is allowed to change during the encoding process. A popular example is Lempel-Ziv-Welsh (LZW) encoding (named after its creators, Abraham Lempel, Jacob Ziv, and Terry Welsh). To encode a message using LZW, one starts with a dictionary containing the basic building blocks from which the message is constructed, but as larger units are found in the message, they are added to the dictionary –meaning that future occurrences of those units can be encoded as single, rather than multiple, dictionary references. For example, when encoding English text, one could start with a dictionary containing individual characters, digits, and punctuation marks. But as words in the message are identified, they could be added to the dictionary. Thus, the dictionary would grow as the message is encoded, and as the dictionary grows, more words (or recurring patterns of words) in the message could be encoded as single references to the dictionary. The result would be a message encoded in terms of a rather large dictionary that is unique to that particular message. But this large dictionary would not have to be present to decode the message. Only the original small dictionary would be needed. Indeed, the decoding process could begin with the same small dictionary with which the encoding process started. Then, as the decoding process continues, it would encounter the same units found during the encoding process, and thus be able to add them to the dictionary for future reference just as in the encoding process. To clarify, consider applying LZW encoding to the message xyx xyx xyx xyx starting with a dictionary with three entries, the first being x, the second being y, and the third being a space. We would begin by encoding xyx as 121, meaning that the message starts with the pattern consisting of the first dictionary entry, followed by the second, followed by the first. Then the space is encoded to produce 1213. But, having reached a space, we know that the preceding string of characters forms a word, and so we add the pattern xyx to the dictionary as the fourth entry. Continuing in this manner, the entire message would be encoded as 121343434. If we were now asked to decode this message, starting with the original three entry dictionary, we would begin by decoding the initial string 1213 as xyx followed by a space. At this point we would recognize that the string xyx forms a word and add it to the dictionary as the fourth entry, just as we did during the encoding process. We would then continue decoding the message by recognizing that the 4 in the message refers to this new fourth entry and decode it as the word xyx, producing the pattern xyx xyx Continuing in this manner we would ultimately decode the string 121343434 as xyx xyx xyx xyx Which is the original message. Page 74 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 30 30. Data Compression: Compressing Images Numerous compression schemes have been developed specifically for image representations. One system known as GIF (short for Graphic Interchange Format and pronounced “Giff” by some and “Jiff” by others) is a dictionary encoding system that was developed by CompuServe. It approaches the compression problem by reducing the number of colors that can be assigned to a pixel to only 256. The red-green-blue combination for each of these colors is encoded using three bytes, and these 256 encodings are stored in a table (a dictionary) called the palette. Each pixel in an image can then be represented by a single byte whose value indicates which of the 256 palette entries represents the pixel’s color. (Recall that a single byte can contain any one of 256 different bit patterns.) Note that GIF is a lossy compression system when applied to arbitrary images because the colors in the palette may not be identical to the colors in the original image. GIF can obtain additional compression by extending this simple dictionary system to an adaptive dictionary system using LZW techniques. In particular, as patterns of pixels are encountered during the encoding process, they are added to the dictionary so that future occurrences of these patterns can be encoded more efficiently. Thus, the final dictionary consists of the original palette and a collection of pixel patterns. One of the colors in a GIF palette is normally assigned the value “transpar- ent,” which means that the background is allowed to show through each region assigned that “color.” This option, combined with the relative simplicity of the GIF system, makes GIF a logical choice in simple animation applications in which multiple images must move around on a computer screen. On the other hand, its ability to encode only 256 colors renders it unsuitable for applications in which higher precision is required, as in the field of photography. Another popular compression system for images is JPEG (pronounced “JAY-peg”). It is a standard developed by the Joint Photographic Experts Group (hence the standard’s name) within ISO. JPEG has proved to be an effective stan- dard for compressing color photographs and is widely used in the photography industry, as witnessed by the fact that most digital cameras use JPEG as their default compression technique. The JPEG standard actually encompasses several methods of image compression, each with its own goals. In those situations that require the utmost in precision, JPEG provides a lossless mode. However, JPEG’s lossless mode does not produce high levels of compression when compared to other JPEG options. Moreover, other JPEG options have proven very successful, meaning that JPEG’s lossless mode is rarely used. Instead, the option known as JPEG’s baseline standard (also known as JPEG’s lossy sequential mode) has become the standard of choice in many applications. Image compression using the JPEG baseline standard requires a sequence of steps, some of which are designed to take advantage of a human eye’s limitations. In particular, the human eye is more sensitive to changes in brightness than to changes in color. So, starting from an image that is encoded in terms of luminance and chrominance components, the first step is to average the chrominance values over two-by- two-pixel squares. This reduces the size of the chrominance information by a factor of four while preserving all the original brightness information. The result is a significant degree of compression without a noticeable loss of image quality. The next step is to divide the image into eight-by-eight-pixel blocks and to compress the information in each block as a unit. This is done by applying a mathematical technique known as the discrete cosine transform, whose details need not concern us here. The important point is that this transformation converts the original eight-by-eight block into another block whose entries reflect how the pixels in the original block relate to each other rather than the actual pixel values. Within this new block, values below a predetermined threshold are then replaced by zeros, reflecting the fact that the changes represented by these values are too subtle to be detected by the human eye. For example, if the original block contained a checkerboard pattern, the new block might reflect a uniform average color. (A typical eight-by-eight-pixel Page 75 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU block would represent a very small square within the image so the human eye would not identify the checkerboard appearance anyway.) At this point, more traditional run-length encoding, relative encoding, and variable-length encoding techniques are applied to obtain additional compression. Altogether, JPEG’s baseline standard normally compresses color images by a factor of at least 10, and often by as much as 30, without noticeable loss of quality. Still another data compression system associated with images is TIFF (short for Tagged Image File Format). However, the most popular use of TIFF is not as a means of data compression but instead as a standardized format for storing photographs along with related information such as date, time, and camera set- tings. In this context, the image itself is normally stored as red, green, and blue pixel components without compression. The TIFF collection of standards does include data compression techniques, most of which are designed for compressing images of text documents in facsimile applications. These use variations of run-length encoding to take advantage of the fact that text documents consist of long strings of white pixels. The color image compression option included in the TIFF standards is based on techniques similar to those used by GIF and are therefore not widely used in the photography community. Page 76 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 31 31. Data Compression: Compressing Audio and Videos The most commonly used standards for encoding and compressing audio and video were developed by the Motion Picture Experts Group (MPEG) under the leadership of ISO. In turn, these standards themselves are called MPEG. MPEG encompasses a variety of standards for different applications. For example, the demands for high definition television (HDTV) broadcast are distinct from those for video conferencing, in which the broadcast signal must find its way over a variety of communication paths that may have limited capabilities. Both of these applications differ from that of storing video in such a manner that sections can be replayed or skipped over. The techniques employed by MPEG are well beyond the scope of this text, but in general, video compression techniques are based on video being constructed as a sequence of pictures in much the same way that motion pictures are recorded on film. To compress such sequences, only some of the pictures, called I-frames, are encoded in their entirety. The pictures between the I-frames are encoded using relative encoding techniques. That is, rather than encode the entire picture, only its distinctions from the prior image are recorded. The I-frames themselves are usually compressed with techniques similar to JPEG. The best-known system for compressing audio is MP3, which was developed within the MPEG standards. In fact, the acronym MP3 is short for MPEG layer 3. Among other compression techniques, MP3 takes advantage of the properties of the human ear, removing those details that the human ear can- not perceive. One such property, called temporal masking, is that for a short period after a loud sound, the human ear cannot detect softer sounds that would otherwise be audible. Another, called frequency masking, is that a sound at one frequency tends to mask softer sounds at nearby frequencies. By taking advantage of such characteristics, MP3 can be used to obtain significant compression of audio while maintaining near CD quality sound. Using MPEG and MP3 compression techniques, video cameras are able to record as much as an hour’s worth of video within 128MB of storage, and portable music players can store as many as 400 popular songs in a single GB. But, in contrast to the goals of compression in other settings, the goal of compressing audio and video is not necessarily to save storage space. Just as important is the goal of obtaining encodings that allow information to be transmitted over today’s communication systems fast enough to provide timely presentation. If each video frame required a MB of storage and the frames had to be transmitted over a communication path that could relay only one KB per second, there would be no hope of successful video conferencing. Thus, in addition to the quality of reproduction allowed, audio and video compression systems are often judged by the transmission speeds required for timely data communication. These speeds are normally measured in bits per second (bps). Common units include Kbps (kilo-bps, equal to one thousand bps), Mbps (mega-bps, equal to one million bps), and Gbps (giga-bps, equal to one billion bps). Using MPEG techniques, video presentations can be successfully relayed over communication paths that provide transfer rates of 40 Mbps. MP3 recordings generally require transfer rates of no more than 64 Kbps. Page 77 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 32 32. Data Manipulation: CPU Basic A CPU consists of three parts (Figure 41): the arithmetic/logic unit, which contains the circuitry that performs operations on data (such as addition and subtraction); the control unit, which contains the circuitry for coordinating the machine’s activities; and the register unit, which contains data storage cells (similar to main memory cells), called registers, that are used for temporary storage of information within the CPU. Some of the registers within the register unit are considered general-purpose registers, whereas others are special-purpose registers. For now, we are concerned only with the general purpose registers. Figure 41: CPU and main memory connected via a bus General-purpose registers serve as temporary holding places for data being manipulated by the CPU. These registers hold the inputs to the arithmetic/logic unit’s circuitry and provide storage space for results produced by that unit. To per- form an operation on data stored in main memory, the control unit transfers the data from memory into the general purpose registers, informs the arithmetic/ logic unit which registers hold the data, activates the appropriate circuitry within the arithmetic/logic unit, and tells the arithmetic/logic unit which register should receive the result. For the purpose of transferring bit patterns, a machine’s CPU and main memory are connected by a collection of wires called a bus (see again Figure 41). Through this bus, the CPU extracts (reads) data from main memory by supplying the address of the pertinent memory cell along with an electronic signal telling the memory circuitry that it is supposed to retrieve the data in the indicated cell. In a similar manner, the CPU places (writes) data in memory by providing the address of the destination cell and the data to be stored together with the appropriate electronic signal telling main memory that it is supposed to store the data being sent to it. Based on this design, the task of adding two values stored in main memory involves more than the mere execution of the addition operation. The data must be transferred from main memory to registers within the CPU, the values must be added with the result being placed in a register, and the result must then be stored in a memory cell. The entire process is summarized by the five steps listed in Figure 42. Page 78 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Figure 42: Adding values stored in memory Page 79 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 33 33. Data Manipulation: Stored Program Early computers were not known for their flexibility—the steps that each device executed were built into the control unit as a part of the machine. To gain more flexibility, some of the early electronic computers were designed so that the CPU could be conveniently rewired. This flexibility was accomplished by means of a pegboard arrangement similar to old telephone switchboards in which the ends of jumper wires were plugged into holes. A breakthrough (credited, apparently incorrectly, to John von Neumann) came with the realization that a program, just like data, can be encoded and stored in main memory. If the control unit is designed to extract the program from memory, decode the instructions, and execute them, the program that the machine follows can be changed merely by changing the contents of the computer’s memory instead of rewiring the CPU. The idea of storing a computer’s program in its main memory is called the stored-program concept and has become the standard approach used today—so standard, in fact, that it seems obvious. What made it difficult originally was that everyone thought of programs and data as different entities: