Fundamentals of algorithms

Figure 1 shows an algorithm, represented using pseudo-code, which assigns a different value to four variables. **Figure 1** country ← 'United States of America' state ← 'California' city ← 'San Francisco' landmark ← 'Alcatraz Island' Define the term **algorithm**.

Figure 2 shows an algorithm that uses integer division which has been represented using pseudo-code. Line numbers are included but are not part of the algorithm. **Figure 2** 1 again ← True 2 WHILE again = True 3 a ← USERINPUT 4 IF a > 0 THEN 5 counter ← 0 6 WHILE a > 0 7 a ← a DIV 3 8 counter ← counter + 1 9 ENDWHILE 10 ELSE 11 again ← False 12 ENDIF 13 OUTPUT a 14 ENDWHILE Where is iteration **first** used in the algorithm in Figure 2?

In the algorithm in Figure 2, what will be output when the user input is 10?

In the algorithm in Figure 2, what is the largest possible value of the variable `counter` when the user input is 36?

Figure 4 shows an algorithm presented as a flowchart. Complete the trace table for the algorithm. You may not need to use all the rows in the table.

Figure 5 shows an algorithm for a simple authentication routine. Parts of the algorithm are missing and have been replaced with the labels L1 to L4. **Figure 5** login ← False REPEAT username ← "" WHILE username = "" OUTPUT 'Enter username: ' username ← L1 ENDWHILE password ← "" WHILE password = "" OUTPUT 'Enter password: ' password ← USERINPUT ENDWHILE storedPassword ← getPassword(L2) IF storedPassword = L3 THEN OUTPUT L4 ELSE IF password = storedPassword THEN login ← True ELSE OUTPUT 'Try again.' ENDIF ENDIF UNTIL login = True OUTPUT 'You are now logged in.' State the items from Figure 6 that should be written in place of the labels in the algorithm in Figure 5. You will not need to use all the items. **Figure 6** | -1 | OUTPUT | 0 | |---|---|---| | username | True | SUBROUTINE | | 1 | User not found | "" | | USERINPUT | password | Wrong password |

A list of numbers `[5, 2, 8, 1, 9, 4]` needs to be sorted using the merge sort algorithm. Explain how the merge sort algorithm works by describing the 'divide' and 'conquer' (merge) steps for this list.

What should the label L1 in Figure 8 be replaced by?

Figure 9 shows an algorithm, represented in pseudo-code, used to display students' test scores. The algorithm does not work as expected and the teacher wants to find the error. The algorithm should display three test scores for each student: - Natalie has results of 78, 81 and 72 - Alex has results of 27, 51 and 54 - Roshana has results of 52, 55 and 59. **Figure 9** 1 names ← ['Natalie', 'Alex', 'Roshana'] 2 scores ← [78, 81, 72, 27, 51, 54, 52, 55, 59] 3 count ← 0 4 FOR i ← 0 TO 2 5 person ← names[i] 6 OUTPUT 'Student: ', person 7 FOR j ← 0 TO 1 8 OUTPUT j + 1 9 result ← scores[i * 3 + j] 10 OUTPUT result 11 count ← count + 1 12 ENDFOR 13 ENDFOR Complete the trace table for the algorithm shown in Figure 9. You may not need to use all the rows in the table.

How could the error in the algorithm in Figure 9 be corrected?

Figure 10 shows part of an algorithm that has been written in pseudo-code. There is an error in the algorithm. The algorithm should: - get the start year and end year from the user - check that the start year is before the end year - check that the start year is before 2000 - calculate the difference between the two years after a valid start year has been entered. **Figure 10** 1 validChoice ← False 2 REPEAT 3 difference ← -1 4 OUTPUT 'Enter a start year ' 5 startYear ← USERINPUT 6 OUTPUT 'Enter an end year ' 7 endYear ← USERINPUT 8 IF startYear >= endYear THEN 9 OUTPUT 'Start year must be before end year' 10 ELSE 11 IF startYear < 2000 THEN 12 OUTPUT 'Start year must be before 2000' 13 ELSE 14 validChoice ← True 15 ENDIF 16 ENDIF 17 UNTIL validChoice = True 18 difference ← endYear - startYear 19 OUTPUT difference Complete the table to show what the values of the `validChoice` and `difference` variables would be for the given test data after the program finishes.

The algorithm in Figure 10 contains a logic error on line 11. Describe how the error on line 11 can be corrected.

Figure 11 shows a binary search algorithm that has been programmed in Python. **Figure 11** python animals = ["cat", "dog", "hippo", "llama", "ox", "rat", "tiger", "wolf"] animalToFind = input("What animal would you like to find? ") validAnimal = False start = 0 finish = len(animals) - 1 while validAnimal == False and start <= finish: mid = (start + finish) // 2 if animals[mid] == animalToFind: validAnimal = True elif animalToFind > animals[mid]: start = mid + 1 else: finish = mid - 1 print(validAnimal) Complete the trace table for the program in Figure 11 if the user input is `wolf`. Part of the table has already been filled in.

State why a binary search cannot be used on the list `fruits`.

Figure 13 shows an algorithm, represented using pseudo-code, that should display currency names in reverse alphabetical order, starting with yen. There are errors in the logic of the algorithm. **Figure 13** 1 SUBROUTINE diffCurrencies(currencies) 2 currencies ← ['baht', 'dollar', 'euro', 'koruna', 'lira', 'rand', 'rupee', 'yen'] 3 RETURN currencies[x] 4 ENDSUBROUTINE 5 6 FOR i ← 8 TO 0 STEP 1 7 OUTPUT(diffCurrencies(i)) 8 ENDFOR Rewrite line 1 and line 6 from Figure 13 to make the algorithm work as intended.

Figure 16 shows an incomplete algorithm, represented using pseudo-code, designed to output the highest or lowest results of a vote. The programmer has used a two-dimensional array called `results` to store the genre and the number of votes for each genre. Parts of the algorithm are missing and have been replaced with the labels L1 to L3. **Figure 16** SUBROUTINE showResults(method, numberOfGenres) results ← [['Pop', 'Post-Punk', 'Techno', 'Metal', 'Dance'], ['7', '19', '14', '1', '9']] pos ← 0 high ← -1 IF method = 'HIGHEST' THEN FOR i ← 0 TO numberOfGenres - 1 Votes ← STRING_TO_INT(results[L1][i]) IF votes > high THEN high ← votes pos ← L2 ENDIF ENDFOR ELSE OUTPUT 'not yet working' ENDIF IF high ≠ -1 THEN OUTPUT results[0][pos], ' with ', results[1][pos] ENDIF ENDSUBROUTINE OUTPUT 'Show the genre with the HIGHEST or LOWEST number of votes? ' method ← USERINPUT showResults(L3, 5) State what should be written in place of the labels L1 to L3 in the algorithm.