IGCSE Computer Science - Chapter 7: Algorithm Design and Problem Solving PDF

# Chapter 7: Algorithm Design and Problem Solving ## C7.1 Program Development Life Cycle - **Analysis:** A magnifying glass with the word “Analysis” below it. - **Design:** A paint palette with the word “Design” below it. - **Coding:** A computer with a person coding on it. - **Testing:** A cog...

# Chapter 7: Algorithm Design and Problem Solving ## C7.1 Program Development Life Cycle - **Analysis:** A magnifying glass with the word “Analysis” below it. - **Design:** A paint palette with the word “Design” below it. - **Coding:** A computer with a person coding on it. - **Testing:** A cog in a circle with an arrow around it with "testing" below it. These four elements are displayed in a clockwise circle around an arrow pointing up, with “C7.1” and “Program Development Life Cycle” below it. The text "IGCSE Computer Science" is displayed within the circle at the bottom of the image ## C7.4 Algorithm & Pseudocode A person with a laptop sitting at a desk is illustrated. There are several objects around them including: Headphones, a tablet, a cactus, a power bank, a coffee mug, and a router with binary code displayed near it. There is a purple and blue patterned background beneath the desk. - The text "C7.4 Algorithm and Pseudocode" is displayed in the upper left corner of the image, with "IGCSE Computer Science" displayed at the bottom. ## Pseudocode ### Pseudocode Definition - **A conventional way to represent an algorithm (a sequence of steps and instructions to complete a task).** - **It employs English keywords that closely resemble those in a high-level programming language and is not constrained by the strict syntax rules of programming languages.** ### Why We Need Pseudocode - **A person reading pseudocode does not need programming language knowledge to understand the algorithm, making it commonly used in computer science research papers.** ## Elements Of Pseudocode - **Assignment statement:** A yellow square containing the text "Assignment statement". - **Input and Output:** A purple square containing the text "Input and Output". - **Conditional statement:** A red square containing the text "Conditional statement". - **Iterative statement:** A green square containing the text "Iterative statement". These four squares are arranged side by side in a horizontal line. ## Assignment Statement - **Definition:** A value is assigned to item/variable. A box with an arrow pointing left is displayed with the word “Variable” on the left side of the arrow, and the word “Value” on the right side of the arrow pointing towards the variable. - **Description:** A variable is a container for storing a value. An open box with the word “Value” inside it is displayed. - **How to combine values:** The values on the right can have one value or multiple values combined with mathematical operators. ### One Value - **Example:** An illustration of an arrow pointing left, with the word "x" on the left side of the arrow and the number "5" on the right side of the arrow. There is another illustration with an arrow pointing left, with the word "name" on the left side of the arrow and the word "Adam" on the right side of the arrow. ### Multiple Values - **Example:** An illustration of an arrow pointing left, with the word "x" on the left side of the arrow, and the equation "5 * 6" on the right side of the arrow. There is another illustration with an arrow pointing left, with the word "name" on the left side of the arrow and the equation “"Hello" + "Adam"” on the right side of the arrow. ## Mathematical Operators | Operator | Action | |---|---| | + | Addition | | - | Subtraction | | * | Multiply | | / | Divide | | ^ | Raise to the power of | | ( ) | Group | ## Assignment Statement: Instead of doing - **Instead of doing:** A table with a column on the left containing the words "Output "adadjjdwajdajw"" repeated seven times. - **We can do:** A table with a column on the right containing the word "name" on the first row and "adadjjdwajdajw" below it. The rest of the rows in the second column contain "Output name". The text **Keyword: REFER** is displayed with a yellow background, and the text “We need to declare variables so that we can refer to them whenever we need to” is displayed below it. ## Assignment Statement: Array - **Assigning an array to a variable:** A blue rectangle with the text "DECLARE MyClass: ARRAY[1:10] OF STRING" is displayed. - **Description:** An illustration of a horizontal line with ten equally sized squares to represent an array. An arrow pointing left is drawn above the array pointing to the text “Store value”. - **We can also assign an array to a variable.** An arrow pointing left with the text "Array = A container that can store multiple items" below it. ## Accessing Elements in An Array - **To access a particular element of an array, we can put a [position] after the variable name. ** A blue rectangle with the text "DECLARE MyClass: ARRAY[1:10] OF STRING" is displayed. - **Example:** An illustration of ten equally sized squares in a horizontal line. The numbers "1" to "10" are displayed above these squares. The words "Peter" and "Jane" are displayed inside the 3rd and 8th squares respectively, with the text "MyClass[3] -> Peter" and "MyClass[8] -> Jane" displayed below the array. ## Input and Output - **Input:** A light green square containing text that explains input, “Used for data entry; It is usually followed by a variable where the data input is stored." - **Output:** A pink square containing text that explains output, "Used to display information on a screen." The words “Input variable” and "Output variable" are displayed below these squares. ## Input and Output: Application - **Illustrative Example:** The words "INPUT cost" are displayed followed by the following equations: - `Price <- Cost * 2` - `Tax <- Price * 0.12` - `Selling price <- Price + Tax` - **Output:** The words “OUTPUT selling price” are displayed. ## Conditional Statement - **Definition:** An element of pseudocode which allows the algorithm to do different things depending on the input/scenario. - **Keywords:** Two rectangles are displayed. - A yellow rectangle with the text “IF ... THEN ... ELSE ... ENDIF” inside of it. - A green rectangle with the text “CASE OF … OTHERWISE … ENDCASE” inside of it. ## IF ... THEN ... ELSE ... ENDIF - **Illustrative Example:** A light blue rectangle with the following text inside it: - `INPUT Age` - `IF Age < 18` - `THEN` - `OUTPUT "Child"` - `ELSE` - `OUTPUT “Adult”` - `ENDIF` ## CASE OF … OTHERWISE … ENDCASE - **Definition:** A CASE statement uses the value of the variable to decide the path to be taken. Several values are usually specified. - **Illustrative Example:** A light blue rectangle with the following text inside it: - `INPUT FoodToBuy` - `CASE OF FoodToBuy` - `Milo: OUTPUT “Here’s your milo”` - `Biscuit : OUTPUT "Here’s your biscuit"` - `OTHERWISE: OUTPUT “The canteen does not have this food”` - `ENDCASE` ## Iterative Statement - **Definition:** An element of pseudocode which allows the algorithm to repeat certain actions. - **Illustrative Example:** Three squares are displayed with a description below each: - A purple square with the text "FOR... TO... NEXT..." inside. - A yellow square with the text "REPEAT... UNTIL..." inside. - A green square with the text "WHILE... DO... ENDWHILE" inside. - **FOR... TO... NEXT...** A set number of repetitions are executed. - **REPEAT... UNTIL...** A repetition, where the number of repeats is not known, but the loop is completed at least once. - **WHILE... DO... ENDWHILE** A repetition, where the number of repeats is not known, that may never be completed. ### FOR... TO... NEXT... - **Illustrative Example:** A light blue rectangle with the following text inside: - `FOR Counter <- 1 TO 10` - `OUTPUT Counter` - `NEXT Counter` - **Explanation:** The text “Beginning value” and “Ending value” are displayed with arrows pointing to the statement `FOR Counter <- 1 TO 10`. The text "Counter+1" is displayed with an arrow pointing to "NEXT Counter". ### REPEAT... UNTIL... - **Illustrative Example:** A light blue rectangle with the following text inside it: - `REPEAT` - `OUTPUT "Hello"` - `INPUT Option` - `Until Option = -1` - **Explanation:** The text “Condition to determine whether we want to continue our program” is displayed with an arrow pointing to “Until Option = -1” in the pseudocode. ### WHILE... DO... ENDWHILE - **Illustrative Example:** A light blue rectangle with the following text inside it: - `Total <- 0` - `OUTPUT "Enter value for mark, -1 to finish" ` - `INPUT Mark` - `WHILE Mark <> -1 DO` - `Total <- Total + Mark` - `OUTPUT "Enter value for mark, -1 to finish"` - `INPUT Mark` - `ENDWHILE` - **Explanation:** The text “Block that will be executed by the DO keyword” is displayed above the WHILE loop. An arrow points to the bottom part of WHILE loop with text “Signify the end of the while loop” displayed below it. The text "Condition to decide whether the DO block will be run" is displayed with an arrow pointing to the WHILE condition. ## C7.5 Standard Methods of Solutions - **Totalling:** A person is displayed sitting at a computer coding with several screens next to each other. The text "C7.5 Standard Methods of Solutions" is displayed at the top right corner of the image. - **Definition:** Totalling in pseudocode refers to accumulating a sum of values over a sequence. - **Concept:** An array with ten squares is illustrated. The numbers "70", “75”, “80”, “60”, “70”, “ 65”, “75”, “90”, “95”, and “100” are displayed inside of them. - **Pseudocode to find the total mark:** A light blue rectangle with the following text inside it: - `Total <- 0` - `ClassSize <- 10` - `FOR Counter <- 1 TO ClassSize` - `Total <- Total + StudentMark[Counter]` - `NEXT Counter ` - **Counting:** - **Definition:** Counting involves incrementing a numerical variable to track occurrences or iterations within a process. For example, calculate the number of students who got 100%. - **Concept:** An array with ten squares is illustrated. The numbers "70", “75”, “80”, “60”, “7”, “ 65”, “75”, “25”, “95”, and “100” are displayed inside of them. - **Pseudocode to count**: - `PerfectCount <- 0` - `ClassSize <- 10` - `FOR Counter <- 1 TO ClassSize` - `IF StudentMark[Counter] = 100` - `THEN` - `PerfectCount <- PerfectCount + 1` - `ENDIF` - `NEXT Counter ` - **Maximum and Minimum:** - **Definition:** Finding the maximum and minimum of a given array. Eg. Find the highest and lowest mark awarded to a class of students. - **Concept:** An array with ten squares is illustrated. The numbers "70", “75”, “80”, “60”, “7”, “ 65”, “75”, “25”, “95”, and “100” are displayed inside of them. - **Method 1:** - **Setup:** - `MaximumMark <- 0 ` - `MinimumMark <- 100 ` - `ClassSize <- 10` - **Algorithm:** - `FOR Counter <- 1 TO ClassSize` - `IF StudentMark[Counter] > MaximumMark ` - `THEN ` - `MaximumMark <- StudentMark[Counter]` - `ENDIF` - `IF StudentMark[Counter] < MinimumMark ` - `THEN ` - `MinimumMark <- StudentMark[Counter]` - `ENDIF` - `NEXT Counter ` - **Method 2:** - **Setup:** - `MaximumMark <- StudentMark[1]` - `MinimumMark <- StudentMark[1]` - `ClassSize <- 10` - **Algorithm:** - `FOR Counter <- 1 TO ClassSize` - `IF StudentMark[Counter] > MaximumMark ` - `THEN ` - `MaximumMark <- StudentMark[Counter]` - `ENDIF` - `IF StudentMark[Counter] < MinimumMark ` - `THEN ` - `MinimumMark <- StudentMark[Counter]` - `ENDIF` - `NEXT Counter ` - **Average** - **Definition:** Finding the average value of a given array. Eg. Find the average mark awarded to a class of students. - **Concept:** An array with ten squares is illustrated. The numbers "70", “75”, “80”, “60”, “7”, “ 65”, “75”, “25”, “95”, and “100” are displayed inside of them. - **Pseudocode to find the average:** - `Total <- 0` - `FOR Counter <- 1 TO ClassSize` - `Total <- Total + StudentMark[Counter]` - `NEXT Counter ` - `Average <- Total / ClassSize` - (This pseudocode is based on the "TOTALLING" concept) - **Linear Search:** - **Definition:** A type of search that is used to check if a value is stored in a list, performed by going through the items in the list one at a time. Eg. Searching for a name in a class list of students' names, where all the names stored are different. - **Concept:** - An array with seven squares is illustrated. The letters "ZK", "Lyn", "Tam", "YW", "Dan", "Joh", and "Abd" are displayed inside of them. - The text "Say, we want to search for a student called Lyn" is displayed below the array. - **Explanation:** An arrow is pointing to the second box in the array, which contains "Lyn". The text "Found!" is displayed below the second box. - **Algorithm:** The algorithm will go through the value in the array one by one until it finds the target OR it reaches the end of the list. - **Pseudocode to find the average:** - `OUTPUT "Please enter name to find"` - `INPUT Name` - `Found <- FALSE` - `Counter <- 1` - `REPEAT` - `IF Name = StudentName[Counter]` - `THEN` - `Found <- TRUE` - `ELSE` - `Counter <- Counter + 1` - `ENDIF` - `UNTIL Found <- TRUE OR Counter > ClassSize` - `IF Found` - `THEN` - `OUTPUT Name, " found at position ", Counter, " in the list."` - `ELSE` - `OUTPUT Name, " not found."` - `ENDIF` - **Bubble Sort:** - **Definition:** Lists become more valuable when their items are arranged in a logical sequence. For instance, names can be organized alphabetically, and numbers can be arranged in either ascending or descending order to enhance usability. - **Concept:** - **Sorting Names:** - An array with seven squares is illustrated. The letters "ZK", "Lyn", "Tam", "YW", "Dan", "Joh", and "Abd" are displayed inside of them. - An arrow pointing down is displayed between the first and second row of squares. - Another array with seven squares is illustrated. The letters "Abd", "Dan", "Joh", "Lyn", "Tam", "YW", and "ZK" are displayed inside of them. - **Sorting Numbers:** - An array with seven squares is illustrated. The numbers “7”, “6”, “5”, “4”, “3”, “2”, and “1” are displayed inside of them. - An arrow pointing down is displayed between the first and second row of squares. - Another array with seven squares is illustrated. The numbers “1”, “2”, “3”, “4”, “5”, “6”, and “7” are displayed inside of them. - **Pseudocode for Bubble Sort:** - `First <- 1` - `Last <- 10` - `REPEAT` - `Swap <- FALSE` - `FOR Counter <- First TO Last - 1` - `IF StudentMark[Counter] > StudentMark[Counter + 1]` - `THEN` - `Temp <- StudentMark[Counter]` - `StudentMark[Counter] <- StudentMark[Counter + 1]` - `StudentMark[Counter + 1] <- Temp` - `Swap <- TRUE` - `ENDIF` - `NEXT Counter` - `Last <- Last - 1` - `UNTIL (NOT Swap) OR Last = 1`