Cambridge IGCSE™ and O Level Computer Science Answers to Algorithms, Programming and Logic Workbook 7 Algorithm design and problem solving 1. Three from: ‘© analysis —a process of investigation, leading to the specification of what a program is required to do + design —uses the program specification from the analysis stage to show how the program shiould be developed «coding — the writing ofthe program or suite of programs ‘© testing —the completed program is run with test data to make sure that all of the modules interact correctly, and the program as a whole works as intended in all circumstances 2 Abstraction Stage Analysis ‘Use to identify the key elements required, discarding any unnecessary details and information ‘that is not required Decomposition Stage Analysis ‘Use to break down a complex problem into smaller parts, repeating this until each part can be solved easily, Structure diagram, Stage Design ‘Use a hierarchical diagram thal shows bow a computer system can be repeatedly divided into sub-systems 2 2 data hardware ‘comnminications b Three from: + input © process = output storage 4 Structure diagrams are used to show top-down design in a diagrammatic form. Flowcharts show diagrammatically the steps required to complete a task and the order that they sre to he performed Pseudocode describes what an algorithm does by using English key words that are very similar 10 those used in a high-level programming language. Cambridge IGCSE and O Level Computer Science Teacher's Guide 1 ‘© David Watson and Helen Williams 2021Answers to Algorithms, Programming and Logic Warkbook ‘5. Structure diagrams are used to show the top-down design of a computer program in 2 diagrammatic form. A structure diagram shows the design of a computer program in a hierarchical way with each level giving a more detailed breakdown of the system into sub-systems Terminator flowchart symbols are used at the beginning and end of each flowchart. Process flowchart symbols are used to show actions. Input and output symbols — the same flowchart symbol is used to show input of data snd ‘output of information, <> Decision flowchart symbols are used to decide wiiich action is to be taken next; these can be used for selection and repetition iteration. Flowchart flow lines use arrows to show the direction of flow through the chart, which is usually, but not alway’, top to bottom and left to right. 7 Assignment: The single variable on the left of the < is assigned the value of the expression on the right. For example: Total « Total + Total Conditional: When different actions are performed by an algorithin according to the values of ‘the variables, conditional statements can be used to decide which action should be taken. IF Age > 70 ‘THEN OUTPUT "sel RISE, oureur "A gun, ENDIE ‘rerative: When some actions pecformed as part of an algorithm need repeating this is called iteration, Loop structures are used to perform the iteration. ater © 170 Cambridge IGCSE and O Level Computer Science Teacher's Guide 2 © David Watson and Helen Williams 2021Answers to Algorithms, Programming and Logic Warkbook 8 a Loopl:FOR .. TO .. NEXT: FOR Counter « 0 TO 19 OUTPUT Student NEXT Counter unter] Loop2: REPEAT .. UNTIL Counter — REPEAT OUTPUT student [Counter] +1 counter ~ Counter UNTIL Counter > 19 Loop 3:7 Counter ~ 0 Eu. DO. WHILE Counter < 20 Do student [counter] Counter € Counter ENDWHILE +1 b T Conditional Statements 1: 1F statements oureur “Please ente! r your name " INPUT Name IF Name = "Alice" THEW OUTPUT “Welcome Alice " ENDIF IF Name = "Abid" THEN OUTPUT “welcome Abid “ ENDTF IF Name = “Dinesh” THEN OUTPUT “Welcome Dinesh " ENDIF IF Name = "Daisy" THEN OUTPUT “Welcome Daisy ” ENDIF IF Name = "Zak" ‘THEN OUTPUT “Welcome Zak * ENDIF Cambridge IGCSE and O Level Computer Science Teacher's Guide 3 ‘© David Watson and Helen Williams 2021Answers to Algorithms, Programming and Logic Warkbook “Alice” AND Name <> “Abid” AND Name <> “Dinesh” AND Name <> "Daisy" <> AND Name <> "Zak" come " eNULe Conditional Statements 2: CASE statements OUTEUI “Flease enter name" INPUT Name CASE OF Name Abia" Dinesh " ENDCASE 1 ¢ The most suitable conditional statement to use is CASE. as the code is considerably shorter to waite. ‘©. and clearer to read and understand. € i Pre-condition loop 1 counter © 0 yes oureur Student [Counter| Cambridge IGCSE and O Level Computer Science Teacher's Guide © David Watson and Helen Williams 2021Answers to Algorithms, Programming and Logic Warkbook Post-condition loop oureu? Student (Counter] Fes STOP ii Pre-condition loop WHILE .. DO... ENDWHILE Post-condition loop REPEAT... UNTIL Loop 4 ris", "May", "Bao"} HOR «4 70 +4 NEXT 0 To 19 eLine (Student (C Cambridge IGCSE and O Level Computer Science Teacher's Guide 5 © David Watson and Helen Williams 2021Answers to Algorithms, Programming and Logic Warkbook Java String[] Student Tim", “tony”, int ©: untert W BOR .. NEXT for (Counter janter +4) { Sytem, out printin (Student [Counter] ) 7 stem. out.printin() 7 Loop 2 WHILE .. DO .. ENDWHILE Python Student - ["Alice", "Jan", "Lint, "Dee", "Avril", "Ron", "Fred", bom", red", "Davy", “Chen”, while Counter < 2 print (student [counter]) Counter print () Counter +1 Visual Basic Bim Student = New string() ("Al Sue", "Tim", "Dee", "Avril", vsusié", "Tony", "Dom", "Ted", "Davy", Dim Counter As Integer "WHILE .. DO .. ENDWHILE Console. WriteLine (Student (Counter) ) Counter — counter + 1 End While Coneole.writeLine() Cambridge IGCSE and O Level Computer Science Teacher's Guide 6 © David Watson and Helen Williams 2021Answers to Algorithms, Programming and Logic Warkbook Java String[] Student *Tim", “tony”, J/ WEILE . DO .. ENDWEILE counter = 0) while (Counter < 19){ stem. out print 1n (Student (Coun unter +1 } System.out.printin(); Loop 3 REPEAT .. UNTIL Python Not available Visual Basic dent New string() ("AL Console. WriteLine (Student (Coun Counter = Counter + 1 Loop Until Counter = 19 console. meLlezLae () Student ea", Saved Tan", "Mi dria”, "May", vrony", “Don”, "Ted", 44 REPEAT .. UNTIL Counter dot System. out .printin (Student (Cou Counter +47 } while (Counter <= 19)7 System. out.printin(); Cambridge IGCSE and O Level Computer Science Teacher's Guide 7 © David Watson and Helen Williams 2021Answers to Algorithms, Programming and Logic Warkbook Total OurevT “Pl INPUT Nunbe se enter next Number" Total « Total + Number NEXT Counter j © David Watson and Helen Williams 2021Answers to Algorithms, Programming and Logic Warkbook 20 2 input—the number of guesses allowed input —a guess for a word check — checks if a guess is comreet check — checks how many guesses are left output — Message(s) to show if] guess is correct or not b * To playa word guessing game «allowing the player to decide how many guesses to take, © // The code below x presents the guessing algori to guess, W, has // Assume that the wo! // declared and defined. eady been DECLARE N : INTEGER DECLARE G : STRING DECLARE Finish : B00! Finish © FALSE OUTPUT "How many guesses INEUT 0 TEDEAT OUTPUT “Please enter INPUT 6 IFG=0 THEM OUTPUT "He: ne you guessed the word!" Fintan 2 oRne ELSE oureur ailed to guess the wi NeN-1 ENnTE UNTIL Finish OR N = 0 111 Standard methods of solution are used in the design of algorithms. These include adding in 2 new vahie every time an action occurs, for example, awarding a mark to each student ~ this is called totalling. When divided by the number of times this occurs, this gives the average. ‘Keeping a record of the number of times an action occurs is called counting, Finding the Jaggest, maximum, and smallest, minimum, ate also standard methods, In order to look for an item in. lista search is used, The method you need to know for IGCSE, Computer Science is to inspect each item in the list in turn to see if itis the one required, This is called a linear search, To puta list in order a sort is used. The method you need to know for IGCSE Computer Science is called # bubble sort. Cambridge IGCSE and O Level Computer Science Teacher's Guide 9 © David Watson and Helen Williams 2021Answers to Algorithms, Programming and Logic Warkbook 22 2 * Enchelement ina list is compared with the next element and swapped if the elements are in the wrong order... ©. starting from the first element and finishing with the next-to-last element, irst 1 Last < 10 REPEAT Swap < FALSE FOR Index « Firet 0 Last - 1 IF Names [Index] > Names [Index + 1] THEN © Names [index] Names[index] « Names[index + 1] Names[index + 1] © Temp Swap © TRUE ENDIF EXT Index Last © Last - 1 UNTIL (NOT Swap) OR (Last = 1) 13 2 | Validation is appropriate to check that only reasonable data is accepted when data is entered. ii Verification is appropriate to check that the data does not change as it is being emtered, b 1 range check presence check i double entry visual check 14 a + Testdata is. set of values used to determine whether a solution is working as itshould ... © the values are chosen to testa full range of operating conditions b 1 normal data a set of test data used thatthe program would normally be expected to work with abnormaVerroneous data — test data chosen to be rejected by the solution as not suitable, if the solution is working properly ‘extreme data~ the largest and smallest values that normal data can take li 99 inside the boundary 100 outside the boundary Cambridge IGCSE and O Level Computer Science Teacher's Guide 10 © David Watson and Helen Williams 2021Answers to Algorithms, Programming and Logic Warkbook w x Y z Mark ourpur 0 100 0 2 34 7 2 5 16 16 b © selects the maximum and minimum values input between 0 and 100 ©... calculates the total of these valid input values = «+; and outputs the maximum, minimum and the total VE Cambridge IGCSE and O Level Computer Science Teacher's Guide 11 © David Watson and Helen Williams 2021Answers to Algorithms, Programming and Logic Warkbook d NumberOfMarks < 0 HighMark © LowMark < 100 Total < 0 REPEAT OUTPUT “Enter 999 to finish” OUTPUT "Marks mast be in the range 0-100, enter next mark” INPUT Mark IF Mark <> 999 THEN REPEAT IF Mark <0 OK Mark >100 THEN OUTEUT "Your mark is out of range, please re-enter the mark" Inrur Mark ENDIF UNTIL Mark >=0 AND Maz IF Mark > HighMark HighMark © Mark ENDIF IF Mark < LowMark THEN LowMark © Mark Total © Total + Mark NunberofMarks « NumberofMarke + 1 ENDIF UONPIL Mark - 999 OUTPUT "The highest mark is ", Hight Opi Tha Taueat mark fe", Tountarl OUTPUT "The total of all the marks is ", Total rk Cambridge IGCSE and O Level Computer Science Teacher's Guide 12 ‘© David Watson and Helen Williams 2021Answers to Algorithms, Programming and Logic Warkbook Example test data could be: Test data: -1, 0, 100, 10 This has been chosen so that there is mixture of normal, abnormal, extreme and boundary data. In this case: ‘Normal data: 21, 999 : 999 has been chosen to ensure that the method used to stop the program Works and should be included in test data; but aay other value in the range 1 99 could also be used. Abnormal data: -§ : but any other data larger than 101. less than -1. or of the wrong data type (eg. twenty one) could be used Extreme data: 0, 100 : these are the only choice of extreme data for this example Boundary data: ~1. 0, 100, 101 : these are the only choice of boundary data for tie main data range (although some students might also want to test the boundary for the ‘quit’ option, Le, 998, 999, 1000). 21,999 Trace table: Nunberof Low TemeetOF | nighmark | EON, | total | mark | ovrpur ° 0 100 Jo 2 101 | range, please re-enter the mark aza daa Cambridge IGCSE and O Level Computer Science Teacher's Guide 13 © David Watson and Helen Williams 202116 2 Answers to Algorithms, Programming and Logic Warkbook OUTEUT T should be IN2% T < 30 should bet < a No flowline out of the OUTEUT "Too Low" box. T > 20shouldbeT > 30 Flowlines from the decision box are not labelled. The arrow on the horizontal flowline is at the wrong end and points in the wrong direction ‘No flowline out of the OUTEUT "Too High" box. Cc 8 Programming 1 Three from: integer: a positive or negarive whole number that can be used with mathematical operators, real: a positive or negative number with a fractional part that can be used with mathematical operators or EAL Boolean: a variable or constant that can have only two values 7: char: a single alphanumeric character string: multiple alphanumeric characters Cambridge IGCSE and O Level Computer Science Teacher's Guide 14 © David Watson and Helen Williams 2021