CS201 Introduction to Programming Handouts PDF

Introduction to Programming CS201 CS201 – Introduction to Programming Lecture No. 1.................................................................................................................3 Lecture No. 2..........................................................................................

Introduction to Programming CS201 CS201 – Introduction to Programming Lecture No. 1.................................................................................................................3 Lecture No. 2.................................................................................................................9 Lecture No. 3...............................................................................................................15 Lecture No. 4...............................................................................................................24 Lecture No. 5...............................................................................................................33 Lecture No. 6...............................................................................................................45 Lecture No. 7...............................................................................................................55 Lecture No. 8...............................................................................................................66 Lecture No. 9...............................................................................................................77 Lecture No. 10.............................................................................................................88 Lecture No. 11.............................................................................................................99 Lecture No. 12...........................................................................................................112 Lecture No. 13...........................................................................................................124 Lecture No. 14...........................................................................................................143 Lecture No. 15...........................................................................................................158 Lecture No. 16...........................................................................................................171 Lecture No. 17...........................................................................................................186 Lecture No. 18...........................................................................................................198 Lecture No. 19...........................................................................................................211 Lecture No. 20...........................................................................................................228 Lecture No. 21...........................................................................................................245 Lecture No. 22...........................................................................................................255 Lecture No. 23...........................................................................................................268 Lecture No. 24...........................................................................................................278 Lecture No. 25...........................................................................................................291 Lecture No. 26...........................................................................................................304 Lecture No. 27...........................................................................................................318 Lecture No. 28...........................................................................................................328 Lecture No. 29...........................................................................................................344 Lecture No. 30...........................................................................................................358 Lecture No. 31...........................................................................................................368 Lecture No. 32...........................................................................................................381 Lecture No. 33...........................................................................................................394 Lecture No. 34...........................................................................................................407 Lecture No. 35...........................................................................................................421 Lecture No. 36...........................................................................................................432 Lecture No. 37...........................................................................................................443 Lecture No. 38...........................................................................................................453 Lecture No. 39...........................................................................................................468 Lecture No. 40...........................................................................................................481 Lecture No. 41...........................................................................................................496 Lecture No. 42...........................................................................................................509 Lecture No. 43...........................................................................................................519 Lecture No. 44...........................................................................................................528 Lecture No. 45...........................................................................................................552 2 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming Lecture No. 1 Summary o What is programming o Why programming is important o What skills are needed o Develop a basic recipe for writing programs o Points to remember What is programming As this course is titled “Introduction to programming”, therefore it is most essential and appropriate to understand what programming really means. Let us first see a widely known definition of programming. Definition: "A program is a precise sequence of steps to solve a particular problem.” It means that when we say that we have a program, it actually means that we know about a complete set activities to be performed in a particular order. The purpose of these activities is to solve a given problem. Alan Perlis, a professor at Yale University, says: "It goes against the grain of modern education to teach children to program. What fun is there in making plans, acquiring discipline in organizing thoughts, devoting attention to detail and learning to be self-critical? " It is a sarcastic statement about modern education, and it means that the modern education is not developing critical skills like planning, organizing and paying attention to detail. Practically, in our day to day lives we are constantly planning, organizing and paying attention to fine details (if we want our plans to succeed). And it is also fun to do these activities. For example, for a picnic trip we plan where to go, what to wear, what to take for lunch, organize travel details and have a good time while doing so. When we talk about computer programming then as Mr. Steve Summit puts it “At its most basic level, programming a computer simply means telling it what to do, and this vapid-sounding definition is not even a joke. There are no other truly fundamental aspects of computer programming; everything else we talk about will simply be the details of a particular, usually artificial, mechanism for telling a computer what to do. Sometimes these mechanisms are chosen because they have been found to be convenient for programmers (people) to use; other times they have been chosen because they're easy for the computer to understand. The first hard thing about programming is to learn, become comfortable with, and accept these artificial mechanisms, whether they make ``sense'' to you or not. “ 3 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming Why Programming is important The question most of the people ask is why should we learn to program when there are so many application software and code generators available to do the task for us. Well the answer is as give by the Matthias Felleisen in the book ‘How to design programs’ “The answer consists of two parts. First, it is indeed true that traditional forms of programming are useful for just a few people. But, programming as we the authors understand it is useful for everyone: the administrative secretary who uses spreadsheets as well as the high-tech programmer. In other words, we have a broader notion of programming in mind than the traditional one. We explain our notion in a moment. Second, we teach our idea of programming with a technology that is based on the principle of minimal intrusion. Hence, our notion of programming teaches problem-analysis and problem-solving skills without imposing the overhead of traditional programming notations and tools.” Hence learning to program is important because it develops analytical and problem solving abilities. It is a creative activity and provides us a mean to express abstract ideas. Thus programming is fun and is much more than a vocational skill. By designing programs, we learn many skills that are important for all professions. These skills can be summarized as: o Critical reading o Analytical thinking o Creative synthesis What skills are needed Programming is an important activity as people life and living depends on the programs one make. Hence while programming one should o Paying attention to detail o Think about the reusability. o Think about user interface o Understand the fact the computers are stupid o Comment the code liberally Paying attention to detail In programming, the details matter. This is a very important skill. A good programmer always analyzes the problem statement very carefully and in detail. You should pay attention to all the aspects of the problem. You can't be vague. You can't describe your program 3/4th of the way, then say, "You know what I mean?'', and have the compiler figure out the rest. Furthermore you should pay attention to the calculations involved in the program, its flow, and most importantly, the logic of the program. Sometimes, a grammatically correct sentence does not make any sense. For example, here is a verse from poem "Through the Looking Glass" written by Lewis Carol: 4 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming “Twas brillig, and the slithy toves Did gyre and gimble in the wabe “ The grammar is correct but there is no meaning. Similarly, the sentence, "Mr. ABC sleeps thirty hours every day", is grammatically correct but it is illogical. So it may happen that a program is grammatically correct. It compiles and runs but produces incorrect or absurd results and does not solve the problem. It is very important to pay attention to the logic of the program. Think about the reusability When ever you are writing a program, always keep in mind that it could be reused at some other time. Also, try to write in a way that it can be used to solve some other related problem. A classic example of this is: Suppose we have to calculate the area of a given circle. We know the area of a circle is (Pi * r2). Now we have written a program which calculates the area of a circle with given radius. At some later time we are given a problem to find out the area of a ring. The area of the ring can be calculated by subtracting the area of outer circle from the area of the inner circle. Hence we can use the program that calculates the area of a circle to calculate the area of the ring. Think about Good user interface As programmers, we assume that computer users know a lot of things, this is a big mistake. So never assume that the user of your program is computer literate. Always provide an easy to understand and easy to use interface that is self explanatory. 5 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming Understand the fact that computers are stupid Computers are incredibly stupid. They do exactly what you tell them to do: no more, no less-- unlike human beings. Computers can't think by themselves. In this sense, they differ from human beings. For example, if someone asks you, “What is the time?”, “Time please?” or just, “Time?” you understand anyway that he is asking the time but computer is different. Instructions to the computer should be explicitly stated. Computer will tell you the time only if you ask it in the way you have programmed it. When you're programming, it helps to be able to "think'' as stupidly as the computer does, so that you are in the right frame of mind for specifying everything in minute detail, and not assuming that the right thing will happen by itself. Comment the code liberally Always comment the code liberally. The comment statements do not affect the performance of the program as these are ignored by the compiler and do not take any memory in the computer. Comments are used to explain the functioning of the programs. It helps the other programmers as well as the creator of the program to understand the code. Program design recipe In order to design a program effectively and properly we must have a recipe to follow. In the book name ‘How to design programs’ by Matthias Felleisen.and the co-worker, the idea of design recipe has been stated very elegenlty as “Learning to design programs is like learning to play soccer. A player must learn to trap a ball, to dribble with a ball, to pass, and to shoot a ball. Once the player knows those basic skills, the next goals are to learn to play a position, to play certain strategies, to choose among feasible strategies, and, on occasion, to create variations of a strategy because none fits. “ The author then continue to say that: “A programmer is also very much like an architect, a composers, or a writer. They are creative people who start with ideas in their heads and blank pieces of paper. They conceive of an idea, form a mental outline, and refine it on paper until their writings reflect their mental image as much as possible. As they bring their ideas to paper, they employ basic drawing, writing, and playing music to express certain style elements of a building, to describe a person's character, or to formulate portions of a melody. They can practice their trade because they have honed their basic skills for a long time and can use them on an instinctive level. Programmers also form outlines, translate them into first designs, and iteratively refine them until they truly match the initial idea. Indeed, the best programmers edit and rewrite their programs many times until they meet certain aesthetic standards. And just like soccer players, architects, composers, or writers, programmers must practice the basic skills of their trade for a long time before they can be truly creative. Design recipes are the equivalent of soccer ball handling techniques, writing techniques, arrangements, and drawing skills. “ 6 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming Hence to design a program properly, we must: o Analyze a problem statement, typically expressed as a word problem. o Express its essence, abstractly and with examples. o Formulate statements and comments in a precise language. o Evaluate and revise the activities in light of checks and tests and o Pay attention to detail. All of these are activities that are useful, not only for a programmer but also for a businessman, a lawyer, a journalist, a scientist, an engineer, and many others. Let us take an example to demonstrate the use of design recipe: Suppose we have to develop a payroll system of a company. The company has permanent staff, contractual staff, hourly based employees and per unit making employees. Moreover, there are different deductions and benefits for permanent employees and there is a bonus for per unit making employees and overtime for contractual employees. We need to analyze the above problem statement. The company has four categories of employees; i.e.; Permanent staff, Contractual staff, hourly based employees and per unit making employees. Further, permanent staff has benefits and deductions depending upon their designation. Bonus will be given to per unit making employees if they make more than 10 pieces a day. Contractual employee will get overtime if they stay after office hours. Now divide the problem into small segments and calculations. Also include examples in all segments. In this problem, we should take an employee with his details from each category. Let’s say, Mr. Ahmad is a permanent employee working as Finance Manager. His salary is Rs.20000 and benefits of medical, car allowance and house rent are Rs.4000 and there is a deduction of Rs.1200. Similarly, we should consider employees from other categories. This will help us in checking and testing the program later on. The next step is to formulate these statements in a precise language, i.e. we can use the pseudo code and flowcharting. which will be then used to develop the program using computer language. Then the program should be evaluated by testing and checking. If there are some changes identified, we revise the activities and repeat the process. Thus repeating the cycle, we achieve a refined solution. Points to remember Hence the major points to keep in mind are: o Don’t assume on the part of the users 7 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming o User Interface should be friendly o Don’t forget to comment the code o PAY ATTENTION TO DETAIL o Program, program and program, not just writing code, but the whole process of design and development 8 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming Lecture No. 2 Reading Material Deitel & Deitel – C++ How to Program chapter 1 1.2, 1.3, 1.4, 1.6, 1.7 1.11, 1.12, 1.13 Summary o Software Categories o System Software o Application Software o History of C language o Development Environment of ‘C’ Software Categories Software is categorized into two main categories o System Software o Application Software 9 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming System Software The system software controls the computer. It communicates with computer’s hardware (key board, mouse, modem, sound card etc) and controls different aspects of operations. Sub categories of system software are: o Operating system o Device drivers o Utilities Operating system An operating system (sometimes abbreviated as "OS") is the program that manages all the other programs in a computer. It is a integrated collection of routines that service the sequencing and processing of programs by a computer. Note: An operating system may provide many services, such as resource allocation, scheduling, input/output control, and data management. Definition “Operating system is the software responsible for controlling the allocation and usage of hardware resources such as memory, central processing unit (CPU) time, disk space, and peripheral devices. The operating system is the foundation on which applications, such as word processing and spreadsheet programs, are built. (Microsoft)” 10 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming Device drivers The device driver software is used to communicate between the devices and the computer. We have monitor, keyboard and mouse attached to almost all PC’s; if we look at the properties of these devices we will see that the operating system has installed special software to control these devices. This piece of software is called device driver software. When we attach a new device with the computer, we need software to communicate with this device. These kinds of software are known as device drivers e.g. CD Rom driver, Sound Card driver and Modem driver. Normally manufacturer of the device provide the device driver software with the device. For scanners to work properly with the computers we install the device driver of the scanner. Nowadays if you have seen a scanner, it comes with TWAIN Drivers. TWAIN stands for Technology Without An Interesting Name. Utility Software Utility software is a program that performs a very specific task, usually related to managing system resources. You would have noticed a utility of Disk Compression. Whenever you write a file and save it to the disk, Compression Utility compresses the file (reduce the file size) and write it to the disk and when you request this file from the disk, the compression utility uncompressed the file and shows its contents. Similarly there is another utility, Disk Defragmentation which is used to defragment the disk. The data is stored on the disks in chunks, so if we are using several files and are making changes to these files then the different portions of file are saved on different locations on the disk. These chunks are linked and the operating system knows how to read the contents of file from the disk combining all the chunks. Similarly when we delete a file then the place where that file was stored on the disk is emptied and is available now to store other files. As the time goes on, we have a lot of empty and used pieces on the disk. In such situation we say that the disk is fragmented now. If we remove this fragmentation the chunks of data on the disk will be stored close to each other and thus reading of data will be faster. For the purpose of removing fragmentation on the disk the Defragmentation utility is used. The compilers and interpreters also belong to the System Software category. Application software A program or group of programs designed for end users. For example a program for Accounting, Payroll, Inventory Control System, and guided system for planes. GPS (global positioning system), another application software, is being used in vehicles, which through satellite determines the geographical position of the vehicle History of C language The C language was developed in late 60’s and early 70’s, in Bell Laboratories. In those days BCPL and B languages were developed there. The BCPL language was developed in 1967 by Martin Richards as a language for writing operating systems software and compilers. In 1970 Ken Thompson used B language to create early 11 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming versions of the UNIX operating system at Bell Laboratories. Thus both the languages were being used to develop various system software even compilers. Both BCPL and B were ‘type less’ languages, every data item occupied one ‘word’ in memory and the burden of treating a data item as a whole number or real number, for example was the responsibility of the programmer. Dennis Ritchie developed a general purpose language, called C language, by using different features of BCPL and B languages. C uses many important concepts of BCPL and B while adding data typing and other features. In the start C became widely known as the development language of the UNIX operating system, and the UNIX operating system was written by using this C language. The C language is so powerful that the compiler of C and other various operating systems are written in C. C language has almost unlimited powers to do with computers. You can program to turn on or off any device of computer. You can do a lot to hard disk and other peripherals. It is very easy to write a program in C that stops the running of computer. So be careful while programming in C. The C language and UNIX operating system widely spread in educational and research institutions. There was C and UNIX everywhere. Due to the wide spread of C, different researchers started to add their features in the language. And thus different variations in C came into existence. Many universities developed their own C by adding different features to the C language developed by Ritchie. These variations led to the need of a standard version of C. In 1983 a technical committee was created under the American National Standards Committee on Computer and Information Processing to provide an unambiguous and machine-independent definition of the language. In 1989 the standard was approved. ANSI cooperated with the International Standard Organization (ISO) to standardize C worldwide. Tools of the trade As programmer we need different tools to develop a program. These tools are needed for the life cycle of programs Editors First of all we need a tool for writing the code of a program. For this purpose we used Editors in which we write our code. We can use word processor too for this, but word processors have many other features like bold the text, italic, coloring the text etc, so when we save a file written in a word processor, lot of other information including the text is saved on the disk. For programming purposes we don’t need these things we only need simple text. Text editors are such editors which save only the text which we type. So for programming we will be using a text editor Compiler and Interpreter As we write the code in English and we know that computers can understand only 0s and 1s. So we need a translator which translates the code of our program into machine language. There are two kinds of translators which are known as Interpreter and Compilers. These translators translate our program which is written in C-Language into Machine language. Interpreters translates the program line by line meaning it reads one line of program and translates it, then it reads second line, translate it and so on. The benefit of it is that we get the errors as we go along and it is very easy to correct the errors. The drawback of the interpreter is that the program executes slowly 12 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming as the interpreter translates the program line by line. Another drawback is that as interpreters are reading the program line by line so they cannot get the overall picture of the program hence cannot optimize the program making it efficient. Compilers also translate the English like language (Code written in C) into a language (Machine language) which computers can understand. The Compiler read the whole program and translates it into machine language completely. The difference between interpreter and compiler is that compiler will stop translating if it finds an error and there will be no executable code generated whereas Interpreter will execute all the lines before error and will stop at the line which contains the error. So Compiler needs syntactically correct program to produce an executable code. We will be using compiler in our course Debugger Another important tool is Debugger. Every programmer should be familiar with it. Debugger is used to debug the program i.e. to correct the logical errors. Using debugger we can control our program while it is running. We can stop the execution of our program at some point and can check the values in different variables, can change these values etc. In this way we can trace the logical errors in our program and can see whether our program is producing the correct results. This tool is very powerful, so it is complex too Linker Most of the time our program is using different routines and functions that are located in different files, hence it needs the executable code of those routines/functions. Linker is a tool which performs this job, it checks our program and includes all those routines or functions which we are using in our program to make a standalone executable code and this process is called Linking Loader After a executable program is linked and saved on the disk and it is ready for execution. We need another process which loads the program into memory and then instruct the processor to start the execution of the program from the first instruction (the starting point of every C program is from the main function). This processor is known as loader. Linker and loaders are the part of development environment. These are part of system software. The following figure represents a graphical explanation of all the steps involved in writing and executing a program. 13 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming Editor Disk Preprocessor program Preprocessor Disk processes the code. Compiler creates object Compiler Disk code and stores it on disk. Linker Disk Linker links the object code with the libraries Primary Memory Loader Loader puts program in memory. Disk...... Primary Memory CPU takes each instruction and CPU executes it, possibly storing new data values as the...... program executes. 14 © Copyright Virtual University of Pakistan CS201 – Introduction to Programming Lecture No. 3 Reading Material Deitel & Deitel – C++ How to Program chapter 1 1.19, 1.20, 1.21, 1.22 Summary First C program Variables Data Types Arithmetic Operators Precedence of Operators Tips First C program The best way to learn C is to start coding right away. So here is our very first program in C. # include main() { cout