Computer Science - Class XI - Problem Solving PDF

# Computer Science - Class XI ## 4.2 Steps for Problem Solving **GIGO (Garbage In Garbage Out)** The correctness of the output that a computer gives depends upon the correctness of input provided. ### Problem Solving Steps * Testing and Debugging * Coding * Analysing the Problem * Developing an A...

# Computer Science - Class XI ## 4.2 Steps for Problem Solving **GIGO (Garbage In Garbage Out)** The correctness of the output that a computer gives depends upon the correctness of input provided. ### Problem Solving Steps * Testing and Debugging * Coding * Analysing the Problem * Developing an Algorithm **Figure 4.1: Steps for problem solving** ### 4.2.1 Analysing the Problem It is important to clearly understand a problem before we begin to find the solution for it. If we are not clear **as** to what is to be solved, we may end up developing a program which may **not** solve our purpose. **Thus,** we need to read and analyse the problem statement carefully in order to list the principal components of the problem and decide **the** core functionalities that our solution should have. By analysing a problem, we would be able to figure out what are the inputs that our program should accept and the outputs that it should produce. ### 4.2.2 Developing an Algorithm It is essential to devise a solution before writing a program code **for** a given problem. The solution is represented in natural language and is called an algorithm. We can imagine an algorithm **like** a very well-written recipe for a dish, with clearly defined steps that, **if** followed, one will end up preparing the dish. We start with a tentative solution plan and keep on refining the algorithm until the algorithm **is** able to capture all the aspects of the desired solution. For a given problem, more than one algorithm is possible and we have to select the most suitable solution. The algorithm is discussed in section 4.3. ### 4.2.3 Coding After finalising the algorithm, we need to convert the algorithm into the format which can be understood by the computer to generate the desired solution. Different high level programming languages can be used for writing a program. It is equally important to record the details of the coding procedures followed and document the solution. This is helpful when revisiting the programs at a later stage. Coding is explained in detail in section 4.8. ### 4.2.4 Testing and Debugging The program created should be tested on various parameters. The program should meet the requirements of the user. It must respond within the expected time. It should generate correct output for all possible inputs. In the presence of syntactical errors, no output will be obtained. In case the output generated **is** incorrect, then the program should be checked for logical errors, if any. Software industry follows standardised testing methods like unit or component testing, integration testing, system testing, and acceptance testing while developing complex applications. **This** is to ensure that the software meets all the business and technical requirements and works as expected. The errors or defects found in the testing phases **are** debugged or rectified and the program **is** again tested. This continues till all the errors are removed from the program. Once the software application has **been** developed, tested and delivered to the user, still problems in terms of functioning can come up and need to be resolved from time to time. The maintenance of the solution, thus, involves fixing the problems faced by the user, answering the queries of the user and even serving the request for addition **or** modification of features. ## 4.3 Algorithm In our day-to-day life we perform activities by following a certain sequence of steps. Examples of activities include getting ready for school, making breakfast, riding a bicycle, wearing a tie, solving a puzzle and so on. To complete each activity, we follow a sequence of steps. Suppose following are the steps required for an activity 'riding a bicycle': 1. remove the bicycle from the stand, 2. sit on the seat of the bicycle, 3. start peddling, 4. use breaks whenever needed and 5. stop on reaching the destination. Let us now find Greatest Common Divisor (GCD) of two numbers 45 and 54. **Note:** GCD is the largest number that divides both the given numbers. **Step 1:** Find the numbers (divisors) which can divide the given numbers * Divisors of 45 are: 1, 3, 5, 9, 15, and 45 * Divisors of 54 are: 1, 2, 3, 6, 9, 18, 27, and 54 **Step 2:** Then find the largest common number from these two lists. Therefore, GCD of 45 and 54 **is** 9. Hence, it is clear that we need to follow a sequence of steps to accomplish the task. Such a finite sequence of steps required to get the desired output **is** called an algorithm. It will lead to the desired result in a finite amount of time, **if** followed correctly. Algorithm has a definite beginning and a definite end, and consists of a finite number of steps. ### 4.3.1 Why do we need an Algorithm? A programmer writes a program to instruct the computer to do certain tasks as desired. The computer then follows the steps written in the program code. Therefore, the programmer first prepares a roadmap of the program to be written, before actually writing the code. Without a roadmap, the programmer may not be able to clearly visualise the instructions to be written and may end up developing a program which may not work **as** expected. Such a roadmap is nothing but the algorithm which **is** the building block of a computer program. For example, searching using a search engine, sending a message, finding a word in a document, booking a taxi through an app, performing online banking, playing computer games, all are based on algorithms. Writing an algorithm **is** mostly considered as a first step to programming. Once we have an algorithm to solve a problem, we can write the computer program for giving instructions to the computer in high level language. If the algorithm is correct, the computer will run the program correctly, every time. So, the purpose of using an algorithm is to increase the reliability, accuracy and efficiency of obtaining solutions. #### (A) Characteristics of a good algorithm * **Precision** - the steps are precisely stated or defined. * **Uniqueness** - results of each step are uniquely defined and only depend on the input and the result of the preceding steps. * **Finiteness** - the algorithm always stops after a finite number of steps. * **Input** - the algorithm receives some input. * **Output** - the algorithm produces some output. #### (B) While writing an algorithm, it is required to clearly identify the following: * The input to be taken from the user * Processing or computation to be performed to get the desired result * The output desired by the user ## 4.4 Representation of Algorithms Using their algorithmic thinking skills, the software designers or programmers analyse the problem and identify the logical steps that need to be followed to reach a solution. Once the steps are identified, the need is to write down these steps along with the required input and desired output. There are two common methods of representing an algorithm - flowchart and pseudocode. Either of the methods can be used to represent an algorithm while keeping in mind the following: * It showcases the logic of the problem solution, excluding any implementational details * It clearly reveals the flow of control during execution of the program ### 4.4.1 Flowchart - Visual Representation of Algorithms A flowchart is a visual representation of an algorithm. A flowchart is a diagram made up of boxes, diamonds and other shapes, connected by arrows. Each shape represents a step of the solution process and the arrow represents the order or link among the steps. There are standardised symbols to draw flowcharts. Some are given in Table 4.1. | Flowchart symbol | Function | Description | |---|---|---| | | Start/End | Also called "Terminator" symbol. It indicates where the flow starts and ends. | | | Process | Also called "Action Symbol,” it represents a process, action, or a single step. | | | Decision | A decision or branching point, usually a yes/no or true/false question is asked, and based on the answer, the path gets split into two branches. | | | Input/Output | Also called data symbol, this parallelogram shape is used to input or output data | | | Arrow | Connector to show order of flow between shapes. | **Example 4.1:** Write an algorithm to find the square of a number. Before developing the algorithm, let us first identify the input, process and output: * **Input:** Number whose square is required * **Process:** Multiply the number by itself to get its square * **Output:** Square of the number **Algorithm to find square of a number.** **Step 1:** Input a number and store it to num **Step 2:** Compute _num_ * _num_ and store it in _square_ **Step 3:** Print _square_ The algorithm to find square of a number can be represented pictorially using flowchart as shown in Figure 4.2. **Figure 4.2: Flowchart to calculate square of a number** **Example 4.2:** Draw a flowchart to solve the problem of a non-functioning light bulb **Figure 4.3: Flowchart to solve the problem of a non-functioning light bulb** **Think and Reflect** What will happen if an algorithm does not stop after a finite number of steps? **Activity 4.2** Draw a flowchart that represents the attainment of your career goal. ### 4.4.2 Pseudocode A pseudocode (pronounced Soo-doh-kohd) is another way of representing an algorithm. It is considered as a non-formal language that helps programmers to write algorithm. It is a detailed description of instructions that a computer must follow in a particular order. It is intended for human reading and cannot be executed directly by the computer. No specific standard for writing a pseudocode exists. The word "pseudo” means “not real," so "pseudocode” means “not real code”. Following are some of the frequently used keywords while writing pseudocode: * INPUT * COMPUTE * PRINT * INCREMENT * DECREMENT * IF/ELSE * WHILE * TRUE/FALSE **Example 4.3:** Write an algorithm to display the sum of two numbers entered by user, using both pseudocode and flowchart. **Pseudocode for the sum of two numbers will be:** INPUT num1 INPUT num2 COMPUTE Result = num1 + num2 PRINT Result The flowchart for this algorithms is given in Figure 4.4. **Figure 4.4: Flowchart to display sum of two numbers** **Example 4.4:** Write an algorithm to calculate area and perimeter of a rectangle, using both pseudocode and flowchart. **Pseudocode for calculating area and perimeter of a rectangle.** INPUT length INPUT breadth COMPUTE Area = length * breadth PRINT Area COMPUTE Perim = 2 * (length + breadth) PRINT Perim The flowchart for this algorithm is given in Figure 4.5. **Figure 4.5: Flowchart to calculate area and perimeter of a rectangle** #### (A) Benefits of Pseudocode Before writing codes in a high level language, a pseudocode of a program helps in representing the basic functionality of the intended program. By writing the code first in a human readable language, the programmer safeguards against leaving out any important step. Besides, for non-programmers, actual programs are difficult to read and understand, but pseudocode helps them to review the steps to confirm that the proposed implementation is going to achieve the desire output. ## 4.5 Flow of Control The flow of control depicts the flow of events as represented in the flow chart. The events can flow in a sequence, or on branch based on a decision or even repeat some part for a finite number of times. ### 4.5.1 Sequence If we look at the examples 4.3 and 4.4, the statements are executed one after another, i.e., in a sequence. Such algorithms where all the steps are executed one after the other are said to execute in sequence. However, statements in an algorithm may not always execute in a sequence. We may sometimes require the algorithm to either do some routine tasks in a repeated manner or behave differently depending on the outcomes of previous steps. In this section, we are going to learn how to write algorithms for such situations. ### 4.5.2 Selection Consider the map of a neighbourhood as shown in Figure 4.6. Let us assume that the pink building with the red roof is the school; the yellow painted house at the far end of the map is a house. With reference to Figure 4.6, let us answer the following questions : * Is there a predefined route for walking from home to school? * Can we have a different route while coming back? As seen from the map, there can be multiple routes between home and school. We might take the shortest route in the morning. But while coming back home in the afternoon, the shortest route might have heavy traffic. Therefore, we could take another route with less traffic. Hence, the above problem involves some decision-making based on certain conditions. Let us look at some other examples where decision making is dependent on certain conditions. For example, **(i) Checking eligibility for voting.** Depending on their age, a person will either be allowed to vote or not allowed to vote: * If age is greater than or equal to 18, the person is eligible to vote * If age is less than 18, the person is not eligible to vote **(ii) Let us consider another example** If a student is 8 years old and the student likes Maths put the student in Group A Otherwise Put the student in Group B In which group will these students go as per the above condition? | Outcome | |---|---| | 8-year-old Ravi who does not like Maths: | Group B | | 8-year-old Priti who likes Maths: | Group A | | 7-year-old Anish who likes Maths: | Group B | In these examples, any one of the alternatives is selected based on the outcome of a condition. Conditionals are used to check possibilities. The program checks one or more conditions and perform operations (sequence of actions) depending on true or false value of the condition. These true or false values are called binary values. **Example 4.6:** Let us write a pseudocode and draw a flowchart where multiple conditions are checked to categorise a person as either child (<13), teenager (>=13 but <20) or adult (>=20), based on age specified: * Input: Age * Process: Check Age as per the given criteria * Output: Print either "Child", "Teenager", "Adult" **Pseudocode is as follows:** INPUT Age IF Age < 13 THEN PRINT "Child" ELSE IF Age < 20 THEN PRINT "Teenager" ELSE PRINT "Adult" The flowchart representation of the algorithm in shown in Figure 4.9 **Figure 4.9: Flowchart to check multiple conditions** **Example 4.7:** Algorithm for a card game called "Dragons and Wizards". Make two teams DRAGONS and WIZARDS The rules for the game are as follows: * If the card drawn is a diamond or a club, Team DRAGONS gets a point * If the card drawn is a heart which is a number, Team WIZARDS gets a point