Computer Grade 9-1 (1) PDF

# Unit 2: Computational Thinking & Algorithms ## Unit Introduction * A computer is a machine that is used to solve problems by accepting inputs, performing operations, and presenting outputs. * Computers can't think but can perform those operations that are written by us in the form of algorithms...

# Unit 2: Computational Thinking & Algorithms ## Unit Introduction * A computer is a machine that is used to solve problems by accepting inputs, performing operations, and presenting outputs. * Computers can't think but can perform those operations that are written by us in the form of algorithms and fed into the computer in the form of programs. * You can't program a computer to do something that you don't know how to solve. Therefore, you need to understand the real-world problem, make some solution, and instruct the computer to behave accordingly when it is asked to solve that problem. * Although computers are of various types depending upon their size and capacity but computation is primarily based on processor and main memory. * We use computers because they work at a much faster speed and perform operations more accurately than humans. ## 2.1 Problems * A problem is a challenge or situation that needs to be overcome using some action. * The problems are present in all fields such as economic, healthcare, education, transportation, internet, biology and many more. ### Examples * **Economic:** What to produce? How to manage limited budgets? * **Healthcare:** How to expand access to medicines? How to stop infectious diseases? * **Education:** How to increase literacy rate in Pakistan? What subject areas of education should be focused on more? ## 2.2 Identifying a Computing Problem * In computer science a problem is a challenge or situation that needs to be overcome using some action. * In computer science, a computing problem is a problem that is solved step-by-step using computation. * It can include any type of calculation such as arithmetical or logical. * These problems usually have a well-defined input and some desired properties that output must be satisfied. * Following are some of the computing problems: * Decision Problems * Search Problems * Counting Problems ### Decision Problems * A decision problem occurs when a given input requires a binary response, either Yes or No. * Responses may take various forms, such as true or false. * In complex cases, answers extend beyond a straightforward Yes-or-No, involving multiple decision factors and criteria. #### Examples: * The problem whether a given number is odd (or even). * The problem whether a given number is a prime number. * The problem that is there any occurrence of "aa"?" in a sequence x of English alphabets. ## 2.3 Problem Solving * Problem solving defines the process of analyzing some situation and accordingly behaving to generate some response. * For simple problems the following 4 steps are used: * Define and analyze a problem: What is the problem and why it is happening. * Design a plan: What we are going to do (Algorithm) * Implement the plan: Code it by using some programming language. * Evaluate: did our plan work? * However, for complex problems, the 6 step problem solving process could be used * Define and analyze a problem * Decompose the problem: make sub-problems that are manageable * Identify potential plans for each sub-problem: such as plan A, plan B and plan C * Select and design best plan * Implement that plan * Evaluate * Before jumping into an action for a problem, it must be thoroughly investigated to capture all the relevant aspects of the problem. * For this purpose, we properly define and analyze a problem. * In defining a problem, there must be clarity and the objectives of the problem must be specified. ## 2.4 Input-Processing-Output (I-P-O) Model * The computer systems work on the input-Process-Output model. * The analyzing of problem allows us to break the problem down into three components: Input, Output and Processing. * It requires us to have correct identification of: * input that needs to be given to the system, * operations the system would perform and * the output to be presented. * Input refers to the requirements from the environment, are the computation operations that is dependent upon the requirement while output is the thing that is presented to the environment. ## 2.5 Input-Processing-Output (I-P-O) Chart * To visually represent the IPO model, we use IPO charts that represent the Inputs, Process and Output in tabular form. * IPO charts are considered a handy tool that software designers use to solve problems. ### Example * An IPO chart to compute the area of rectangle would be: | Input | Process | Output | | :----- | :------------------------------------ | :----- | | Length | Area = Length \* Width | Area | | Width | | | ## 2.6 Computational Thinking * Using computation to solve problems requires the ability to think in a certain way, which is often referred to as 'computational thinking'. ### 2.6.1 Importance of Computational Thinking * Computational thinking encourages not only to reflect clearly on a problem they're solving but also to define a repeatable solution for it. * While solving a problem, we don't just want to solve one instance of a problem, we want an automized system that can solve all instances of similar problem. * Computational thinking can be thought of as an extension of logical thinking. ### 2.6.2 Properties of Computational Thinking * **Decomposition:** Breaking down the larger problems into smaller/ manageable ones and working on them one by one. * These smaller problems are referred as sub-problems. * This way we simplify the problem and solve it easily. * **Abstraction:** by removing the unnecessary details to solution, so you could be able to identify essential information. * **Pattern Recognition:** Examine the problem for a pattern or similarities between previously solved problems. * **Algorithm Design:** This is actual designing of solution. This involves creating step-by-step plan of the problem solution. ### Example * If you want to create your own computer game, these properties of computational thinking would apply: | | Description | | :---- | :------------------ | | Time | 00:45 | | Items | Key, ladder, skull | | Enemy | Skull | | | Exit | **Decomposition:** where to go, how to complete the level **Abstraction:** * **Necessary Information:** location of exit, where is enemy, etc * **Unnecessary Information:** weather **Pattern recognition:** Six enemies should be handled like a single enemy. **Algorithm Design:** step by step plan of action e.g. movement ## 2.7 Principles of Computational Thinking ### 2.7.1 Logical thinking * Logical thinking refers to analyzing a particular situation or problem using reason and accordingly reaching up to one or more decisions that are sensible. * The situation analysis requires gathering of relevant facts and then deciding the best way based on the reasons. * **Example:** You enter your home and see water on the floor. What do you think has happened? * **To solve such problems, you need reasoning skills that are based on evidence and facts.** #### Example * **Fact:** Islamabad is a city * **Fact:** Cities have a mayor (or some equivalent) * **Inferred:** Islamabad has a mayor (or some equivalent) * **One of the fundamental parts of computational thinking is to think logically. ** * The computers use logic in their computation but it does not mean that they think logically. * The computers themselves can't perform logical thinking unless they are programmed to do so. * **By developing the ability to align problem-solving with technology and focusing on the process as well as the solution** ### 2.7.2 Algorithmic Thinking * **Algorithmic thinking is about problem-solving.** * Computers do nothing by magic, algorithmic thinking is a way of getting to a solution. * It is a process that involves identifying the steps needed and then implementing those steps in a logical and efficient manner. * **It is a way of thinking that involves breaking down complex problems into smaller, manageable parts and then solving those parts one at a time.** #### Example * Find the largest of three unequal numbers. | Input | Process | Output | | :------------ | :-------------------------------------------------------- | :----------------- | | Three numbers | Find largest among the three numbers | Display largest number | * **Step 1:** Let three number be A=10, B=20 and C=30 * **Step 2:** Check if A is the largest? * **Step 2.1:** Check if A > B and A > C then A is the largest. * **Step 3:** If A is largest then Stop the process, otherwise proceed to next step. * **Step 4:** Check if B is largest? * **Step 4.1:** Check if B > A and B > C then B is the largest. * **Step 5:** If B is largest then Stop the process, otherwise proceed to next step. * **Step 6:** C is largest. ## 2.8 Methods to Design a Solution * Once you have completely understood the problem, the next stage is to design a solution. * In solution design, you define how a software will meet the requirements and objectives of a problem. * There are two methods that are used to design a solution: * Flowcharts * Concept Maps * Let's discuss both in detail and solve some examples. ### 2.8.1 Flowcharts * Flowchart is a diagrammatic representation of an algorithm. It describes what operations are required to solve a given problem. #### Importance of flowchart in solving a problem * Flowchart illustrates the sequence of operations to be performed to solve a problem in the form of a diagram. * Computers programmers draw flowcharts before writing computer programs. * It provides an easy way to analyze and find solutions to problems. * Once the flowchart is drawn, it becomes very easy to write the program in any computer language. * It is very helpful in communicating the problem-solving method to other people. * It also helps in finding and removing logical errors. #### Steps for drawing flowchart * The flowchart developer must determine the following requirements for the given problem or algorithm before drawing a flowchart. * Start of the flowchart * Input to the flowchart * Type of processing required * Decision to be taken * Output of the operation * End of the flowchart **Start of the flowchart:** Every flowchart should start with a trigger. The graphical representation of start of flowchart is oval shape. **Input to the flowchart:** The flowchart designer must know what exactly the input to the flowchart is. The input is determined from the problem statement. For example, the given problem is to convert temperature from Fahrenheit to Celsius. Here, the input will be the temperature in Fahrenheit. The graphical representation of input is parallelogram. **Processing in the flowchart:** The flowchart designer must decide what type of calculation is to be performed or what formula is applied to obtain the required result. For example, to find the area of a triangle. The following formula is to be used: Area = (Base x Height) / 2 The graphical representation of processing symbol is rectangle. **Decision making in flowchart:** The flowchart designer must decide which control structure (sequence, repetition, or selection) are to be applied for the solution of the problem. For example, selection structure must be applied to print letter grade of a student based on the marks obtained. The selection structure will check in which range the marks fall and accordingly print the grade. Graphically the decision is represented with diamond. **Output:** The flowchart must provide the required output. The output is represented with a parallelogram symbol as well. **End of flowchart:** The flowchart should have a defined end, and because of the possibility of multiple decision points, it may have multiple ends. For end of flowchart the oval symbol is used. #### Flowchart to solve problems: ##### Flowchart 1: Flowchart to find sum, product, and average of five numbers. * From the statement of the flowchart, it is clear that sum, product and average are to be calculated and given are five numbers. * The flowchart is shown below for this. [Diagram describing Flowchart 1] ##### Flowchart 2: Flowchart to find the largest of three unequal numbers. [Diagram describing Flowchart 2] ##### Flowchart 3: Flowchart to find the area of triangle when the lengths of height and base are given. [Diagram describing Flowchart 3] #### Software Tools for Flowchart Designing * For flowchart designing, different software tools are available to design the flowcharts. * Some of the famous tools are Microsoft Visio and LARP software. **Microsoft Visio** * Microsoft Visio is a tool for drawing various types of diagrams such as flowcharts, building plans, data flow diagrams, network diagrams, etc. **How to create flowchart in Microsoft Visio** * Start Microsoft Visio * Click on the category of Flowchart * Double-click the Basic Flowchart * For each step, you wish to design in the process, drag a relevant flowchart symbol and place it onto your drawing. * Connect the flowchart shapes by holding the mouse pointer over the first symbol, and then releasing it on the to the other symbol you wish to connect to. * To place text into a shape, select it, and then type. * The Figure 2.16 shows a screenshot of flowchart designing in Microsoft Visio. **LARP** * Logics of Algorithms and Resolution of Problems (LARP) is a programming language for rapid development of prototypes. * Unlike C++, Java and other programming languages, LARP uses semi-natural syntax. * Therefore, it is very easy for non-programmers to understand. * LARP also allows algorithms to be expressed as flowcharts. * A screenshot of flowchart designing is shown in Figure 2.17. ### 2.8.2 Concept Maps * Like a flowchart, a concept map is another way of representing knowledge. * A concept map is a graphical tool that represents concepts and relationships between them. * The concepts in these maps are represented as boxes or circles, which relate to lines or arrows. * These lines are labeled with linking words and phrases to represent the connections between concepts. * There are different software tools for concept mapping, for example CmapTools, Mind Manager. * (Fig 2.18 shows an example concept of map) * **Example:** Consider the below given sample diagram representing concept map of electricity [Diagram describing Concept Map] ## Summary * **Abstraction:** Identifying essential information and Removal of the unnecessary details to solution. * **Algorithm Design:** This is actual designing of solution. This involves creating step-by-step plan of the problem solution. * **Algorithmic Thinking** is a way of getting to a solution. * **Computing Problem** is a problem that is solved step-by-step using computation. * **Computational Thinking** is a problem-solving method that computer scientists use as a skill to solve complex problems in a logical and systematic manner. * **Concept Map** is another way of representing knowledge. * **Counting Problems:** These problems work on the principle that if an event/decision has A number of choices and another decision/event has B number of choices then the total number of possible unique combinations would be A x B. * **Decision Problems:** A decision problem is the situation for a given input that has Yes-or-No Answer. * **Decomposition:** Breaking down the larger problems into smaller/ manageable ones and working on them one by one. These smaller problems are referred as sub-problems. This way we simplify the problem and solve it easily. * **Flowchart** is a diagrammatic representation of an algorithm. * **IPO charts** are considered a handy tool that software designers use to solve problems. * **LARP:** Logics of Algorithms and Resolution of Problems is a programming language for rapid development of prototypes * **Logical Thinking** refers to analyzing a particular situation or problem using reason and accordingly reaching up to one or more decisions that are sensible. * **Pattern Recognition:** Examine the problem for a pattern or similarities between previously solved problems. * **Problem** is a challenge or situation that needs to be overcome using some action. * **Problem Solving** defines the process of analyzing some situation and accordingly behaving to generate some response.