CS121 lecture note.pdf

ABUBAKAR TAFAWA BALEWA UNIVERSITY BAUCHI, BAUCHI STATE FACULTY OF SCIENCE MATHEMATICAL SCIENCE DEPARTMENT CS 121 Introduction to Computer Science 11 Lecture note Lecture...

ABUBAKAR TAFAWA BALEWA UNIVERSITY BAUCHI, BAUCHI STATE FACULTY OF SCIENCE MATHEMATICAL SCIENCE DEPARTMENT CS 121 Introduction to Computer Science 11 Lecture note Lecture note Page 1 CS121 – INTRODUCTION TO COMPUTER SCIENCE II Overview of fundamental concept of Computer Science. Problem solving using computer; Algorithm, Flowchart, Pseudo code. Program program Control/Logic structure, Programming paradigms (Unstructured, structured and OO programming). Definition of the following terms: bits, bytes, word, word length, data, information, records, fields, files, and database. Basic data Structure: Meaning of data structure. Brief discussion on: Array, linked lists, stacks and queues, tree and their applications; tree traversal. BASIC Programming Language.. Lecture note Page 2 1.0 INTRODUCTION A computer is a programmable device machine that accepts data, stores and manipulates data, and provides output in a useful format. At the early stage of its development, computer was seen as just a mere tool to assist in computation. However, computer has now grown to be a sophisticated tool that can be programmed to do variety of tasks. In fact, it‘ll be hard to think of any field or area of human endeavour where computer is not employed and heavily relied upon. Most of the computers that we see and used today are based on Von Neumann Architecture. The basic idea behind the Von Neumann architecture is the concept of ‗stored program‘. That is, computer works under the control of some instructions called program/software stored in its memory.The CPU fetch (read) both the data and the instructions from the main memory, decode (interpret)the instructions and finally execute it. This constitute what is called fetch-execute cycle, based on which the CPU speed measured. Computer is organized as a system comprising of two major components: hardware and software. It is these two components that work together to achieve the task of transforming input data into meaningful information. Our focus as students Computer Science is notonly limited toknowing the principles behind how computer operate, but to be able to create and analyse computational procedures that when implemented will cause computer to carryout meaningful tasks. The fields of Computer Science and Software Engineering primarily focus on the design and implementation of software 2.0 PROBLEM SOLVING The goalComputer Scientist is to solve problems using computers.The problems that Computer Scientist solves areusually real-world problem involving some computations – eg, students‘ results computation, payroll computation etc. Problems are formulated as computational processes called algorithms.Recall that computer is a programmable, which means it follow instructions or computational steps to accomplish any task. Computer scientist create, study, analyse those computational steps with theultimate view of implementation on the machine. In fact this is the reason why Computer Science is sometimes regarded as the study of algorithms. There are many definitions for ―problem solving‖. Here is one: Problem Solvingis the process of analysing a given situation and generating appropriate response or solution. In the context Computer Science, problem solving can be defined as the process of analysinga given problem and producing its solution in form of algorithm that can be implemented using a programming language on the computer. Lecture note Page 3 In essence, problem solving using computer is all about producing/developingsolution to a problem in form of program that can be executed on a computer. There is need to have a standard and systematic approach to solving problems. Program is a sequence of instructions that can be executed by a computer to solve some problem or perform a specified task. Producing/developing program is a systematic task. Some steps needs to be followed. If you opt to do it any how, you‘d certainly get rubbish at the end! 2.1 Problem Solving Steps The following are problem solving steps are expected to be adhere strictly. As you progress in studying Computer Science, you would see that it is these steps that mutate into what is called Software Development Life Cycle (SDLC), or Software process models such as Water fall model, V-model, Agile etc i. Understand the Problem ii. Problem analysis & specification Problem analysis deals with determining how the solution is going to be by identifying:  Inputs (the data to be processed),  Output (the desired result; in what format is it required), and  Any additional constraint on the solution. Having known the input and the kind of output needed, it is hope that you will gain an idea of the approach to use in solving the problem. Broadly speaking, program specification defines the input, the processing and the output required. A good specification specifies what processing is needed by given the exact relationship between input and output rather than prescribing how the program should be written. iii. Program design& algorithm development Design phase establishes overall system architecture. Software design involves breaking the problem into small manageable units/components, and identify their relationships. Software Design is about modelling software systems – producing structure or model based on which the software is built. The end-product of Software design provides road map for implementation. At the end of this step/phase, computational steps or algorithm is expected to be produced. iv. Coding Coding means transforming the algorithm into an executable computer program. It is task of converting the steps in the algorithm (pseudo code or flowchart) using the syntax of a programming language.This is where the knowledge of programming language comes in. Lecture note Page 4  Coding is also called implementation. Because programmer is actually implementing algorithm using a Programming Language v. Testing Testing is the process of running program with different set of input with the intension of revealing error. The essence of running it with different sets of data is to test whether it produces the expected result and ultimately meet its specification or not. When a program is run, if all is well, you should see correct output. However, it is possible for the program to produce wrong results (output) or failed to run at all. In that case, the algorithm is not properly converted into a program. We say the program has bugs or errors. Thus, the program must be debugged. Debugging is the process of finding and fixing errors in programs. It is often a very time – consuming task, since the programmer must read the code line by line in an attempt to uncover error. During testing, the programmer will be looking for both syntax errors and logic errors, as well as exploring other section that may cause the program to either not work properly or not run at all. Syntax error occurswhen rule of programming language is violated. Logic error occur when formulas of algebraic expressions were not correctly implemented thereby leading to wrong answer. A program that has logic error does not produce correct result/output.Logic errors are hard to find. vi. Document the program Documentation involves writing explanations of the problem being solved and the organization of the solution, comments embedded within the program itself, and user manuals that describe how to use the program. Documentation is a task that should be done right from the first stage of program development. Many different people are likely to work on a program over a long period of time. Good documentation will simplify the work for them. vii. Maintenance Once a program has been put into use, it is often necessary to modify it. Modification may involve fixing an error that didn‘t show up during development but appear during usage, or changing the program in response to changes in the user‘s requirements. Each time the program is modified, it is necessary to repeat the problem-solving steps. This phase of the programming process is known as maintenance and actually accounts for the majority of the effort expended on most programs. 2.2 Algorithm An algorithm is a precise and unambiguous sequence of instructions for solving a problem. Algorithm can also be defined as a finite and unambiguous set of procedures to accomplish a task. The term algorithm applies to any method of solving a problem, and it is not restricted to the field computer science alone. When we write computer program, we are implementing algorithm. Lecture note Page 5 When you start your car, you follow a step-by-step procedure – i.e, the algorithm might look something like this: 1. Insert the key. 2. Make sure the transmission is in Park (or Neutral). 3. Turn the key to the start position. 4. If the engine starts within six seconds, release the key to the ignition position. 5. If the engine doesn‘t start in six seconds, release the key and gas pedal, wait ten seconds, and repeat Steps 3 through 5, but not more than five times. 6. If the car doesn‘t start, call the garage. Attributes of Algorithm i. Precision – algorithm must be clear and give correct solution in all case. ii. Unambiguity – ambiguity in algorithm means having more than one step performing the same task. An algorithm is unambiguous if it doesn‘t have series of steps performing the same task. iii. Finite – an algorithm should not be run forever. It must have an end. iv. Efficiency – efficiency of algorithm has to do with how much of various types of resources it consumes. For example, processing time, memory. Some algorithms consume much memory and time when executed. In computer science, we are interested in algorithms that are time and space (memory) efficient. As far as problem solving using computer is concern, the aim is to implement algorithm using a programming language. To have a better understanding of the steps in algorithm so as to make implementation easier, algorithm can be represented in two forms (1) Pseudocode (2) flowchart. 2.3 Pseudo code Pseudo code is used as a way of describing a computer program without completely following the syntax of programming language. Alternatively, a pseudo code can be seen as an informal set of instructions that imitate the structure of a program but does not adhere completely to the syntax of programming language. Lecture note Page 6 When learning to program, it is important to write pseudocode because it helps you clearly understand the problem that you are trying to solve. It also helps you avoid getting bogged down with syntax details (i.e., like spelling mistakes) when you write your program. Although flowcharts can be visually appealing, pseudocode is often the preferred choicefor algorithm development because of the following reasons: i. Pseudocode fits more easily on a page of paper. ii. Pseudocodeis written in a way that is very close to real program code, thus making it easier when writing the program (coding). iii. Pseudocode takes less time to write than drawing a flowchart. iv. Pseudocode easily accommodate changes/alteration than flowchart which is difficult to be redrawn when mistakes are made. Pseudocode will vary according to whoever writes it. That is, one person‘s pseudocodeis often quite different from that of another person. However, there are some commoncontrol structures (i.e., features) that appear whenever we write pseudocode. Control structures Description Example Sequence Sequence of executable age = 20 statements without branching input gradelevel or loops pay = neyPay + bonus print pay Decision Selecting one option from if lamp is not plugged in several other options. then plug it in Example, Doing taskA or ………OR………….. taskB depending on if bulb is burned out condition. then replace bulb otherwise buy new lamp Repetition/loop Repeatedly doing some tasks repeat several times until a get a new light bulb condition is satisfied.. put it in the lamp until lamp works or no more bulbs left Lecture note Page 7 The above are the control structures that are used to control flow of control in computer programs. There every programming language its own syntax of these control structures. The point is that there are a variety of ways to write pseudocode. The important thing to remember is that your algorithm should be clearly explained with no ambiguity as to what order your steps are performed in 2.4 Flowchart A flowchart is used to represent algorithm ina diagrammatic form. Flow chart uses symbols to show the operations and decisions to be followed by a computer in solving problem. A flowchart is a convenient technique to show the flow of control in a program.Flowchart is one of the programming tools that help programmers understand algorithm better In fact, flowcharts are the plan to be followed when the program is written. Expert programmers may write programs without drawing the flowcharts. But for a beginner it is recommended that a flowchart should be drawn before writing a program. This reduces the number of errors and omissions that might occur during coding/program creation. The flowchart symbols are as follows: Symbol Symbol name Meaning Start/Stop symbol. Denotes the beginning and end of a program. There must be two set of this symbol in your flowchart Flow line This symbol is used to indicate the direction of the flow of control in a flowchart. This means the flow lines indicate the next statement to be executed. Input/output symbol It is used to denote entering data through keyboard or Displaying output. Processing symbol It is used to denote processing activity to be carried out such as assignment and data-movement instructions. Therefore, all arithmetic Lecture note Page 8  processing of adding, subtracting, multiplying, and dividing are represented with a processing symbol. Decision symbol It is used to denote a decision.This symbol must be used whenever decision has to be taken. Decision symbol has one entry point and at least two exit points (paths) depending upon the decision taken inside the symbol. When a condition is tested, if the condition is true, the path marked ―true or yes‖ is followed. If the condition is false, the path for ―false or no‖ is followed. Connector symbol It is used to connect one part of the flowchart to another. If a flowchart is too big to be accommodated on a page, a connector symbol can be used to indicate the continuation in another page. It is a circle with a number written inside it. If a flowchart is discontinued at some point, a circle is drawn pointing away from the chart. Another circle with the same number inside is placed where the flowchart is continued Rules/Guidelines for drawing flowchart The following are some guidelines or rules that are very important when drawing flowcharts  Only conventional flowchart symbols should be used. Lecture note Page 9   Arrows can be used to indicate the flow of control in the problem. However, flow lines should not cross each other.  Processing logic should flow from top to bottom and from left to right.  Words in the flowchart symbols should be common statements and easy to understand. These should be independent of programming languages.  Be consistent in using names and variables in the flowchart.  If the flowchart becomes large and complex then connector symbols should be used to avoid crossing of flow lines.  Properly labelled connectors should be used to link the portions of the flowchart on different pages.  Flowcharts should have start and stop points. Advantages of Flowchart i. Flowcharts guide or help programmer in writing the actual code in a high level language. ii. A flowchart is an excellent communication technique that explains the logic of a program to other programmers/people. iii. A flowchart is an important tool in the hands of a programmer, which helps him in designing the test data for systematic testing of programs iv. Flowcharts are used as working models in designing new programs and software systems Disadvantages Some of the disadvantages of flowchart include: i. The drawing of flowcharts is a very time-consuming process and laborious especially for large and complex problems. ii. It is very difficult to include any new step in the existing flowchart; redrawing of the flowchart is the only solution and it is even more difficult and time consuming. iii. If an algorithm has complex branches and loops, flowcharts become very difficult to draw. Whether using a flow chart of pseudocode, you should test your algorithm by manually going through the steps in your head to make sure that you did not forget a step or a special Lecture note Page 10 situation. Often, you will find a flaw in your algorithm because you forgot about a special situation that could arise. Only when you are convinced that your algorithm will solve your problem, should you go ahead to the next step. Example 1 Write an algorithm/pseudocode to calculate the area of rectangle. Represent the algorithm in a flowchart. Problem analysis This problem requires the length and breadth of the rectangle to be specified. Hence it requires input. The length and breadth can be integer or floating point numbers. So the output (area of the rectangle)should be floating point number (to generalize the case). Algorithm Pseudo code 1. Start Start 2. Print ―please enter the length and breadth of the Print “please enter the length, and breadth” rectangle ‖ length = number entered by user breadth = number entered by user 3. input a number and assign it to a variable length IFlength >0 and breadth >0THEN 4. input a number and assign it to a variable breadth area = length * breadth 5. Iflength is greater than 0 and breadth is greater than 0 Print area. then do step 7, 8 and 9, ELSEPrint “invalid input” and ELSE gotostep 2. Print “invalid input” and goto step 2. 6. Multiply length by breadth and assign the result to a endIF variable area Stop 7. Print area. 8. Stop Lecture note Page 11  start print“enter length” inputlength print“enter breadth” inputbreadth print“invalid input. Please length> 0 and F try again” breadth>0 T area = length * breadth print area Example 2 stop Write an algorithm/pseudocode to find the average of positive integers from 1 to 20. (ie, 1,2,3,4,….., 20). Represent the algorithm in aflowchart. Problem analysis This problem does not require any input.All that is needed is to have a variable initialized to 1 and then continuously incrementthe variableuntil it reaches 20 while accumulating the sum.Theoutput should be a floating point number. Algorithm 1. Start 2. Declare a variable n and initialize it to 1(ie, n = 1) 3. Declare a variable sum and initialize it to 0 (ie, sum = 0) 4. Repeat steps 5 and 6 while n is less than or equal to 20, otherwise goto step 7 5. Add n to sum (sum = sum + n) 6. Increment n by 1 (ie, add 1 to n so that n will point to the next integer in the sequence) 7. Divide sum by 20 and assign the result to average. 8. Print average 9. Stop Lecture note Page 12  start Pseudo code start n=1 n=1 sum = 0 sum = 0 average REPEATwhile n ≤ 20 F sum = sum + n n= 0 THEN PRINT "The square root is:", SQR( NUMBER ) ELSE PRINT "There is no square root" PRINT "Run the program again." END IF ' PRINT "Bye" END Answer: No. The ELSE statement must be alone on its line. Keeping Branches Separate The IF, THEN, ELSE, and END IF are like brackets that emphasize the parts of the two-way branch. The QBasic system requires that you put the ELSE and END IF on their own lines to keep the true and false branches clear. PRINT "Enter a Number" INPUT NUMBER ' IF NUMBER >= 0 THEN PRINT "The square root is:", SQR( NUMBER ) ELSE PRINT "There is no square root" = 0 THEN Lecture note Page 55  PRINT "The square root is:", SQR( NUMBER ) ELSE PRINT "There is no square root" PRINT "Run the program again." END IF ' PRINT "Bye" END In this program there are a different number of statements in the true branch than in the false branch. This is fine. Lecture note Page 56