Representing Algorithms (AQA GCSE Computer Science)

Four separate subroutines have been written to control a robot.

• Forward(n) moves the robot n squares forward.

• TurnLeft() turns the robot 90 degrees left.

• TurnRight() turns the robot 90 degrees right.

• ObjectAhead() returns true if the robot is facing an object in the next square or returns false if this square is empty.

Draw the path of the robot through the grid below if the following program is executed (the robot starts in the square marked by the ↑ facing in the direction of the arrow). If a square is black then it contains an object

WHILE ObjectAhead() = true
TurnLeft()
IF ObjectAhead() = true THEN
TurnRight()
TurnRight()
ENDIF
Forward(1)
ENDWHILE
Forward(1)

A developer is developing a program for a client. The developer is given the following instructions.

“Many of my friends ask me to walk their dogs for them. All of these friends pay me to do this and the amount I get paid depends on how long I walk their dogs for. If they have more than one dog then I don’t charge the owner any extra. I like to walk the dogs in the afternoon when the weather is normally best because I often get colds. I need you to help me keep track of how much I’m owed – fortunately for me all of my friends have different first names so it is really easy to tell them apart. I charge £10 for every 30 minutes of the walk (and I always round this up so 47 minutes would be two half-hour charges or £20)."

The developer has decided that the following two points are the only important details from the client’s request.

• The charge is based on time and not how many dogs are walked.

• The charge is £10 every 30 minutes.

State two other relevant details that the developer has missed.

The following subroutines control the way that labelled blocks are placed in box different columns.

This is how the blocks A, B and C are arranged at the start.

Draw the final arrangement of the blocks after the following algorithm has run.

MOVE(0, 1)
MOVE(0, 2)
MOVE(0, 2)

Figure 3 box shows a program written in Python that calculates the area of a rectangle or the volume of a box from the user inputs.

Figure 3

def calculate(width, length, height): 
   if height == -1: 
      return width  length 
   else:
      return width  length * height

numOne = int(input("Enter width: ")) 
numTwo = int(input("Enter length: ")) 
numThree = int(input("Enter height, –1 to ignore: ")) 

answer = calculate(numOne, numTwo, numThree) 

if numThree == -1: 
   print(f"Area {answer}") 
else: 
   print(f"Volume {answer}")

Complete the trace table using the program in Figure 3

Figure 4 shows an algorithm presented as a flowchart.

Figure 4

Complete the trace table for the algorithm in Figure 4.

You may not need to use all the rows in the table.

Figure 8 box shows an algorithm, written using pseudo-code, that uses a RECORD data structure for storing information about a film.

Each record stores four pieces of information about a film:

• film title

• certificate (eg 12A, PG)

• year the film was made

• if the film is currently being shown at a cinema.

There are records for three films and these films are stored alphabetically in an array called filmCollection.

The pseudo-code outputs the title of the newest of the three films.

Part of the algorithm has been replaced by the label ①.

Figure 8

RECORD Film 
  title : String 
  certificate : String 
  year : Integer 
  beingShown : Boolean 
ENDRECORD

hulk ←  Film('Hulk', '12A', 2005, False)
ironMan ← Film('Iron Man', '12A', 2008, False) 
antMan ← Film('Ant-Man', '12A', 2015, False) 
filmCollection [antMan, hulk, ironMan] 
year← 0 
position ← 0 
FOR i ← 0 TO ①
    IF filmCollection[i].year > year THEN 
       year← filmCollection[i].year 
       position ← i 
    ENDIF 
ENDFOR

OUTPUT filmCollection[position].title, ' is the newest film'

Select how many different values can the field beingShown have?

Figure 11 shows a binary search algorithm that has been programmed in Python.

Figure 11

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.

You may not need to use all the rows in the table.

A program is being developed that allows users to rate and review movies. A user will box enter their rating (out of 10) and a written review for each movie they have watched.

Computational thinking skills are used during the development of the program

2 A user will be able to register, log in and log out of the program. When registering, a new user will enter their details, before confirming their email address.

Decomposition has been used to break the problem down into smaller sub-problems.

Figure 7 represents the design of the program

Complete the decomposition of this program by stating what should be written in boxes A and B.

A subroutine is represented using pseudo-code.

SUBROUTINE calculate(n) 
     a  n 
     b  0 
     REPEAT 
            a  a DIV 2 
             b  b + 1 
      UNTIL a ≤ 1 
      OUTPUT b 
ENDSUBROUTINE

The DIV operator is used for integer division

Complete the trace table for the subroutine call calculate(50)

You may not need to use all the rows in the table.

Figure 13 shows an algorithm represented in pseudo-code. A developer wants to check the algorithm works correctly.

• Line numbers are included but are not part of the algorithm

Figure 13

1 arr[0]   'c' 
2 arr[1]  'b' 
3 arr[2]  'a' 
4 FOR i  0 TO 1 
5    FOR j  0 TO 1 
6        IF arr[j + 1] < arr[j] THEN 
7           temp  arr[j] 
8           arr[j]  arr[j + 1] 
9           arr[j + 1]  temp 
10        ENDIF 
11     ENDFOR 
12 ENDFOR

Complete the trace table for the algorithm shown in Figure 13.

Some values have already been entered.

You may not need to use all the rows in the table

The algorithm shown in Figure 1 is designed to help an athlete with their training. It uses two subroutines getBPM and wait:

• getBPM() returns the athlete’s heart rate in beats per minute from an external input device

• wait(n) pauses the execution of the algorithm for n seconds, so wait(60) would pause the algorithm for 60 seconds.

Line numbers have been included but are not part of the algorithm.

Figure 1

1 seconds ← 0 
2 rest ← 50 
3 REPEAT 
4   bpm ← getBPM() 
5   effort ← bpm – rest 
6   IF effort ≤ 30 THEN 
7      OUTPUT 'faster' 
8   ELSE 
9      IF effort ≤ 50 THEN 
10        OUTPUT 'steady' 
11     ELSE 
12        OUTPUT 'slower' 
13     ENDIF 
14   ENDIF 
15   wait(60) 
16   seconds ← seconds + 60 
17 UNTIL seconds > 200

Complete the trace table for the algorithm shown in Figure 1.

Some values have already been entered in the trace table:

• the first value of seconds

• the values returned by the subroutine getBPM that are assigned to the variable bpm.

You may not need to use all rows of the trace table

This is one row of a bitmap image that uses different shades of grey:

This row is stored using the following numbers to represent the different shades of grey:

The algorithm shown in Figure 4 uses this row.

Figure 4

row ← [56, 34, 0, 99, 72, 23] 
newRow ← [0, 0, 0, 0, 0, 0] 
FOR i ← 0 TO 5 
    IF row[i] > 50 THEN 
       newRow[i] ← 99 
    ENDIF 
ENDFOR

State the purpose of the algorithm shown in Figure 4

The algorithm in Figure 5 is a new search algorithm.

Figure 5

arr ← [3, 4, 6, 7, 11, 14, 17, 18, 34, 42]
value ← 21
found ← False
finished ← False
i ← 0
down ← False
WHILE (found = False) AND (finished = False)
   IF arr[i] = value THEN
      found ← True
   ELSE
      IF arr[i] > value THEN
         down ← True
                       i ← i – 1
      ELSE
        IF (arr[i] < value) AND (down = True) THEN
           finished ← True
        ELSE
           i ← i + 4
        ENDIF
       ENDIF
      ENDIF
ENDWHILE 

Complete the trace table for the algorithm in Figure 5. The first row has been completed for you. You may not need to use all rows of the trace table.

Figure 8 shows an algorithm

Figure 8

x ← True 
y ← False
IF NOT (x AND y) THEN 
   OUTPUT 'A'
   IF NOT((NOT x) OR (NOT y)) THEN 
       OUTPUT 'B' 
   ELSE 
       OUTPUT 'C' 
   ENDIF 
ELSE 
   OUTPUT 'D' 
   IF (NOT x) AND (NOT y) THEN 
      OUTPUT 'E' 
   ELSE 
      OUTPUT 'F' 
   ENDIF 
ENDIF

State the output from the algorithm shown in Figure 8.

Develop an algorithm, using either pseudo-code or a flowchart, that prompts the user to enter three values. It should output 'duplicate' if at least two of these values are the same.

The start of the algorithm has been written for you.

v1 ← USERINPUT

v2 ← USERINPUT

v3 ← USERINPUT

Number the following lines of code in order (1–4) so that they create an algorithm where the final value of the variable n is 13.

The LEFTSHIFT operator performs a binary left shift.
For example, 4 LEFTSHIFT 2 would left shift the value 4 twice.

The algorithm in Figure 4 is a sorting algorithm.

• Array indexing starts at 0.

• Line numbers are included but are not part of the algorithm

Figure 4

1 arr  [4, 1, 6]
2 swapsMade  false
3 WHILE swapsMade = false
4   swapsMade  true
5   i  0
6   WHILE i < 2
7     IF arr[i+1] < arr[i] THEN
8       t  arr[i]
9       arr[i]  arr[i+1]
10      arr[i+1]  t
11      swapsMade  false
12    ENDIF
13    i  i + 1
14   ENDWHILE
15 ENDWHILE

Complete the trace table for the algorithm shown in Figure 4. Some values have already been entered.

The following subroutines control the way that labelled blocks are placed in box different columns.

This is how the blocks A, B and C are arranged at the start.

Draw the final arrangement of the blocks after the following algorithm has run.

MOVE(0, 1)
MOVE(0, 2)
MOVE(0, 2)

Develop an algorithm using either pseudo-code or a flowchart that will move box every block from column 0 to column 1.

Your algorithm should work however many blocks start in column 0. You may assume there will always be at least one block in column 0 at the start and that the other columns are empty.

The order of the blocks must be preserved.

The MOVE subroutine must be used to move a block from one column to another. You should also use the HEIGHT subroutine in your answer.

For example, if the starting arrangement of the blocks is:

Then the final arrangement should have block B above block A:

Figure 8 shows a Python program that is being developed.

It is supposed to calculate and display the highest common factor of two numbers entered by the user.

The highest common factor of two numbers is the largest number that both numbers can be divided by without leaving a remainder.

Examples:

• the highest common factor of the numbers 6 and 9 is 3

• the highest common factor of the numbers 2 and 5 is 1

Line numbers are shown but are not part of the program code.

Figure 8

1 num1 = int(input())
2 num2 = int(input())
3 hcf = 1
4 count = 1
5 while count < num1:
6   if (num1 % count == 0 and num2 % count == 0):
7     hcf = count
8   count = count + 1
9 print(hcf)

The program in Figure 8 works correctly sometimes but not always. When the user enters the numbers 4 and 6 it correctly outputs 2, but when the user enters the numbers 4 and 4 it should output 4 but it does not.

Describe how the code on line 5 should be changed so that the program in Figure 8 will work correctly.

Figure 5 shows an algorithm represented using pseudocode.

The algorithm is for a simple authentication routine.

The pseudocode uses a subroutine getPassword to check a username:

• If the username exists, the subroutine returns the password stored for that user.

• If the username does not exist, the subroutine returns an empty string.

Parts of the algorithm are missing and have been replaced with the labels ① to ④.

Figure 5

login  False
REPEAT
   username  ''
   WHILE username = ''
     OUTPUT 'Enter username: '
     username ← ① 
   ENDWHILE
   password  ''
   WHILE password = ''
      OUTPUT 'Enter password: '
      password  USERINPUT
   ENDWHILE
   storedPassword  getPassword(②)
   IF storedPassword = ③ THEN
     OUTPUT '④'
   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 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 9 shows an algorithm, represented in pseudocode, 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.

Line numbers are included but are not part of the algorithm.

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.

50 students have voted for the music genre they like best.

Figure 16 shows an incomplete algorithm, represented using pseudocode, designed to output the highest or lowest results of the 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[][i])
IF votes > high THEN
high votes
pos
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(, 5)

State what should be written in place of the labels L1 to L3 in the algorithm in Figure 16.

A group of people have booked a meal in a restaurant. Instead of one person paying for the whole meal, each person will pay for what they eat.

Write a Python program that asks each person in the group how much they are paying towards the meal and works out when the bill is fully paid. Each person can pay a different amount.

The program should:

• get the user to enter the total amount of the bill

• get a person to enter how much they are paying towards the bill

• subtract the amount entered from the bill:

  • if the amount left to pay is more than 0, output how much is left to pay and repeat until the amount left to pay is 0 or less

  • if the amount left to pay is 0, then output the message Bill paid

  • if the amount left to pay is less than 0, then output the message Tip is and the difference between the amount left to pay and 0

You should use indentation as appropriate, meaningful variable name(s) and Python syntax in your answer.

A user wants to create a dice game played against a computer.

The aim of the game is to get as close to a score of 21 as you can, without going over 21. If your score goes over 21 then you lose.

The player’s score starts at 0.

For each turn:

• two dice (each numbered from 1 to 6) are rolled

• the total of the two dice rolls is added to the player’s score

• the value of each dice and the player’s new total is output

• if the current score is less than 21, the player is asked if they would like to roll the dice again: if the player says yes, they get another turn; otherwise, the game ends.

At the end of the game, the program should work as follows:

• if the final score is 21, output a message to say the player has won

• if the final score is greater than 21, output a message to say the player has lost

• if the final score is less than 21, the program generates a random number between 15 and 21 inclusive:

  • if this random number is greater than the player’s final score, output a message to say the player has lost

  • otherwise, output a message to say the player has won.

Figure 17 shows the output of a program that plays this dice game.

Figure 17

Roll 1: 1
Roll 2: 4
Current score: 5
Would you like to roll again? yes

Roll 1: 1
Roll 2: 6
Current score: 12
Would you like to roll again? yes

Roll 1: 1
Roll 2: 2
Current score: 15
Would you like to roll again? yes

Roll 1: 6
Roll 2: 1
Current score: 22
You lost!

Write a Python program to simulate this game.

The first line has been written for you in the answer grid

The dice rolls are carried out by the program generating random numbers between box 1 and 6. You will need to use the Python function random.randrange(a, b) which generates a random integer in the range a to b starting at a but finishing one before b.

You should use indentation as appropriate, meaningful variable name(s) and Python syntax in your answer.

This is one row of a bitmap image that uses different shades of grey:

This row is stored using the following numbers to represent the different shades of grey:

The algorithm shown in Figure 4 uses this row.

Figure 4

row ← [56, 34, 0, 99, 72, 23] 
newRow ← [0, 0, 0, 0, 0, 0] 
FOR i ← 0 TO 5 
    IF row[i] > 50 THEN 
       newRow[i] ← 99 
    ENDIF 
ENDFOR

Complete the trace table for the algorithm shown in Figure 4.

The first values have already been entered. You may not need to use all rows of the trace table.

Develop an algorithm, using either pseudocode or a flowchart, that checks if a user has entered a string that represents a valid machine code instruction.

The machine code instruction is valid if it contains exactly eight characters and all of those characters are either '0' or '1'.

The algorithm should:

• prompt the user to enter an 8-bit machine code instruction and store it in a variable

• check that the instruction only contains the characters '0' or '1'

• check that the instruction is exactly eight characters long

• output 'ok' when the instruction is valid, otherwise it should output 'wrong'.

For example:

• if the user enters the string '00101110' it should output 'ok'

• if the user enters the string '11110' it should output 'wrong'

• if the user enters the string '1x011001' it should output 'wrong'.

Draw the final pattern after the following algorithm has executed.

gotoRow(0)
WHILE atEnd() = False
   shape('square')
   move(1)
ENDWHILE
gotoRow(1)
shape('circle')
move(1)
IF atEnd() = True THEN
   gotoRow(2)
ELSE
   move(1)
ENDIF
shape('square')

You should draw your answer on the following grid.

You do not need to show the position(s) of the needle in your answer.

Draw the final pattern after the following algorithm has executed.

This question uses the MOD operator. MOD calculates the remainder after integer division, for example 7 MOD 5 = 2.

patterns ← ['circle', 'square', 'square', 'circle']
r ← 2
FOR k ← 0 TO 3
 gotoRow(k MOD r)
 move(k + 1)
 shape(patterns[k])
ENDFOR 

You should draw your answer on the following grid.

You do not need to show the position(s) of the needle in your answer.

Develop an algorithm, using either pseudocode or a flowchart, to produce the pattern shown in Figure 9.

To gain full marks your answer must make appropriate use of iteration.

Figure 9