Algorithms — Paper 3 · A Level Computer Science 9618

4 (a) (i) Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of expressions. … … … … [2] (ii) Identify, with reasons, a data structure that could be used to evaluate an expression in RPN. … … … … [2] (b) Write the infix expression in RPN. (a – b) * (a + c) / 7 … … [1] (c) Write the RPN expression as an infix expression. a b / 4 * a b + - … … [1] (d) Evaluate the RPN expression: a b + c d / / where a = 17, b = 3, c = 48 and d = 12. Show your working. … … … … [2]

8 marks

Mark scheme: 4(a)(i) One mark for each correct marking point (Max 2) 2 • Reverse Polish Notation provides an unambiguous method of representing an expression • … reading from left to right • …without the need to use brackets • …with no need for rules of precedence / BODMAS 4(a)(ii) One mark for identification of the data structure, 2 One mark for a sensible reason Either: Structure: stack The operands are popped from the stack in the reverse order to how they were pushed Or: Structure: Binary tree A (binary) tree allows both infix and postfix to be evaluated (tree traversal) 4(b) a b - a c + * 7 / 1 4(c) a / b * 4 – (a + b) 1 4(d) 1 mark for correct structure 2 1 mark for correct substitution (a + b) / (c / d) (17 + 3) / (48 / 12)

This question in 9618/31 May/June 2021

5 (a) Calculate the shortest distance between the base and each of the other towns in the diagram using Dijkstra’s algorithm. Show your working and write your answers in the table provided. Base 4 5 Town 1 2 Town 2 1 8 Town 3 7 3 Town 6 1 5 6 Town 4 Town 5 Working … … … … … … … … Answers Town 1 Town 2 Town 3 Town 4 Town 5 Town 6 [5] (b) Explain the use of graphs to aid Artificial Intelligence (AI). … … … … … … [3]

8 marks

Mark scheme: 5(a) Working (Max 3) 5 May be seen on diagram • Initialisation: setting Base to 0 • … and the rest of the towns to ∞ • Evidence to show values at nodes being updated • Evidence to show ‘visited node(s)’ May be seen in working section of paper • Evidence to show calculation of at least one route • Evidence to show more than one route has been calculated for at least one town Correct Answer (Max 2) One mark for four correct values… … One mark for all values correct Town 1 Town 2 Town 3 Town 4 Town 5 Town 6 3 5 2 9 3 8 5(b) One mark for each correct marking point (Max 3) 3 • Artificial Neural Networks can be represented using graphs • Graphs provide structures for relationships // graphs provide relationships between nodes • AI problems can be defined/solved as finding a path in a graph • Graphs may be analysed/ingested by a range of algorithms • …e.g. A* / Dijksta’s algorithm • …used in machine learning. • Example of method e.g. Back propagation of errors / regression methods

This question in 9618/31 May/June 2021

8 (a) State two factors that may affect the performance of a sorting algorithm. … … … … [2] (b) The given algorithm is a simple bubble sort that arranges a set of scores stored in a one- dimensional array into descending order, and orders the corresponding students’ names stored into a two-dimensional array in the same order as the scores. All the arrays are indexed from 1. The contents of both arrays after sorting are shown. Name Score 1 2 1 98 1 Smithfield Tom 2 97 2 Johnson Jane … … 248 5 248 Peters Jade 249 3 249 Allen John YearSize 249 ← Flag TRUE ← WHILE Flag = TRUE Flag FALSE ← FOR Student 1 TO YearSize - 1 ← IF Score[Student] < Score[Student + 1] THEN Temp1 Score[Student] ← Temp2 Name[Student,1] ← Temp3 Name[Student,2] ← Score[Student] Score[Student + 1] ← Name[Student,1] Name[Student + 1,1] ← Name[Student,2] Name[Student + 1,2] ← Score[Student + 1] Temp1 ← Name[Student + 1,1] Temp2 ← Name[Student + 1,2] Temp3 ← Flag TRUE ← ENDIF NEXT Student ENDWHILE Write an algorithm, using pseudocode, that will perform the same task using an insertion sort. … … … … … … … … … … … … … … … … … … … … … [6]

8 marks

Mark scheme: 8(a) One mark for each correct marking point (Max 2) 2 • The initial order of the data • The number of data items to be sorted • The efficiency of the sorting algorithm 8(b) One mark for each marking point (max 6) 6 MP1 Use of FOR loop to cycle through the whole year group MP2 Temporary storage of the score being ‘inserted’ MP3 Temporary storage of the corresponding name elements MP4 Use of WHILE loop with correct exit clause MP5 Moving of all three elements of data to next array elements MP6 Correct updating of counter variable MP7 Final insertion of all three data elements Example algorithm YearSize ← 249 FOR Student ← 2 to YearSize Temp1 ← Score[Student] Temp2 ← Name[Student,1] Temp3 ← Name[Student,2] Counter ← Student WHILE Counter > 1 AND Score[Counter - 1] < Temp1 Score[Counter] ← Score[Counter - 1] Name[Counter,1] ← Name[Counter - 1,1] Name[Counter,2] ← Name[Counter - 1,2] Counter ← Counter – 1 ENDWHILE Score[Counter] ← Temp1 Name[Counter,1] ← Temp2 Name[Counter,2] ← Temp3 NEXT Student

This question in 9618/31 May/June 2021

4 (a) (i) Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of expressions. … … … … [2] (ii) Identify, with reasons, a data structure that could be used to evaluate an expression in RPN. … … … … [2] (b) Write the infix expression in RPN. (a – b) * (a + c) / 7 … … [1] (c) Write the RPN expression as an infix expression. a b / 4 * a b + - … … [1] (d) Evaluate the RPN expression: a b + c d / / where a = 17, b = 3, c = 48 and d = 12. Show your working. … … … … [2]

8 marks

Mark scheme: 4(a)(i) One mark for each correct marking point (Max 2) 2 • Reverse Polish Notation provides an unambiguous method of representing an expression • … reading from left to right • …without the need to use brackets • …with no need for rules of precedence / BODMAS 4(a)(ii) One mark for identification of the data structure, 2 One mark for a sensible reason Either: Structure: stack The operands are popped from the stack in the reverse order to how they were pushed Or: Structure: Binary tree A (binary) tree allows both infix and postfix to be evaluated (tree traversal) 4(b) a b - a c + * 7 / 1 4(c) a / b * 4 – (a + b) 1 4(d) 1 mark for correct structure 2 1 mark for correct substitution (a + b) / (c / d) (17 + 3) / (48 / 12)

This question in 9618/32 May/June 2021

5 (a) Calculate the shortest distance between the base and each of the other towns in the diagram using Dijkstra’s algorithm. Show your working and write your answers in the table provided. Base 4 5 Town 1 2 Town 2 1 8 Town 3 7 3 Town 6 1 5 6 Town 4 Town 5 Working … … … … … … … … Answers Town 1 Town 2 Town 3 Town 4 Town 5 Town 6 [5] (b) Explain the use of graphs to aid Artificial Intelligence (AI). … … … … … … [3]

8 marks

Mark scheme: 5(a) Working (Max 3) 5 May be seen on diagram • Initialisation: setting Base to 0 • … and the rest of the towns to ∞ • Evidence to show values at nodes being updated • Evidence to show ‘visited node(s)’ May be seen in working section of paper • Evidence to show calculation of at least one route • Evidence to show more than one route has been calculated for at least one town Correct Answer (Max 2) One mark for four correct values… … One mark for all values correct Town 1 Town 2 Town 3 Town 4 Town 5 Town 6 3 5 2 9 3 8 5(b) One mark for each correct marking point (Max 3) 3 • Artificial Neural Networks can be represented using graphs • Graphs provide structures for relationships // graphs provide relationships between nodes • AI problems can be defined/solved as finding a path in a graph • Graphs may be analysed/ingested by a range of algorithms • …e.g. A* / Dijksta’s algorithm • …used in machine learning. • Example of method e.g. Back propagation of errors / regression methods

This question in 9618/32 May/June 2021

8 (a) State two factors that may affect the performance of a sorting algorithm. … … … … [2] (b) The given algorithm is a simple bubble sort that arranges a set of scores stored in a one- dimensional array into descending order, and orders the corresponding students’ names stored into a two-dimensional array in the same order as the scores. All the arrays are indexed from 1. The contents of both arrays after sorting are shown. Name Score 1 2 1 98 1 Smithfield Tom 2 97 2 Johnson Jane … … 248 5 248 Peters Jade 249 3 249 Allen John YearSize 249 ← Flag TRUE ← WHILE Flag = TRUE Flag FALSE ← FOR Student 1 TO YearSize - 1 ← IF Score[Student] < Score[Student + 1] THEN Temp1 Score[Student] ← Temp2 Name[Student,1] ← Temp3 Name[Student,2] ← Score[Student] Score[Student + 1] ← Name[Student,1] Name[Student + 1,1] ← Name[Student,2] Name[Student + 1,2] ← Score[Student + 1] Temp1 ← Name[Student + 1,1] Temp2 ← Name[Student + 1,2] Temp3 ← Flag TRUE ← ENDIF NEXT Student ENDWHILE Write an algorithm, using pseudocode, that will perform the same task using an insertion sort. … … … … … … … … … … … … … … … … … … … … … [6]

8 marks

Mark scheme: 8(a) One mark for each correct marking point (Max 2) 2 • The initial order of the data • The number of data items to be sorted • The efficiency of the sorting algorithm 8(b) One mark for each marking point (max 6) 6 MP1 Use of FOR loop to cycle through the whole year group MP2 Temporary storage of the score being ‘inserted’ MP3 Temporary storage of the corresponding name elements MP4 Use of WHILE loop with correct exit clause MP5 Moving of all three elements of data to next array elements MP6 Correct updating of counter variable MP7 Final insertion of all three data elements Example algorithm YearSize ← 249 FOR Student ← 2 to YearSize Temp1 ← Score[Student] Temp2 ← Name[Student,1] Temp3 ← Name[Student,2] Counter ← Student WHILE Counter > 1 AND Score[Counter - 1] < Temp1 Score[Counter] ← Score[Counter - 1] Name[Counter,1] ← Name[Counter - 1,1] Name[Counter,2] ← Name[Counter - 1,2] Counter ← Counter – 1 ENDWHILE Score[Counter] ← Temp1 Name[Counter,1] ← Temp2 Name[Counter,2] ← Temp3 NEXT Student

This question in 9618/32 May/June 2021

4 (a) (i) Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of expressions. … … … … [2] (ii) Identify, with reasons, a data structure that could be used to evaluate an expression in RPN. … … … … [2] (b) Write the infix expression in RPN. (a – b) * (a + c) / 7 … … [1] (c) Write the RPN expression as an infix expression. a b / 4 * a b + - … … [1] (d) Evaluate the RPN expression: a b + c d / / where a = 17, b = 3, c = 48 and d = 12. Show your working. … … … … [2]

8 marks

Mark scheme: 4(a)(i) One mark for each correct marking point (Max 2) 2 • Reverse Polish Notation provides an unambiguous method of representing an expression • … reading from left to right • …without the need to use brackets • …with no need for rules of precedence / BODMAS 4(a)(ii) One mark for identification of the data structure, 2 One mark for a sensible reason Either: Structure: stack The operands are popped from the stack in the reverse order to how they were pushed Or: Structure: Binary tree A (binary) tree allows both infix and postfix to be evaluated (tree traversal) 4(b) a b - a c + * 7 / 1 4(c) a / b * 4 – (a + b) 1 4(d) 1 mark for correct structure 2 1 mark for correct substitution (a + b) / (c / d) (17 + 3) / (48 / 12)

This question in 9618/33 May/June 2021

5 (a) Calculate the shortest distance between the base and each of the other towns in the diagram using Dijkstra’s algorithm. Show your working and write your answers in the table provided. Base 4 5 Town 1 2 Town 2 1 8 Town 3 7 3 Town 6 1 5 6 Town 4 Town 5 Working … … … … … … … … Answers Town 1 Town 2 Town 3 Town 4 Town 5 Town 6 [5] (b) Explain the use of graphs to aid Artificial Intelligence (AI). … … … … … … [3]

8 marks

Mark scheme: 5(a) Working (Max 3) 5 May be seen on diagram • Initialisation: setting Base to 0 • … and the rest of the towns to ∞ • Evidence to show values at nodes being updated • Evidence to show ‘visited node(s)’ May be seen in working section of paper • Evidence to show calculation of at least one route • Evidence to show more than one route has been calculated for at least one town Correct Answer (Max 2) One mark for four correct values… … One mark for all values correct Town 1 Town 2 Town 3 Town 4 Town 5 Town 6 3 5 2 9 3 8 5(b) One mark for each correct marking point (Max 3) 3 • Artificial Neural Networks can be represented using graphs • Graphs provide structures for relationships // graphs provide relationships between nodes • AI problems can be defined/solved as finding a path in a graph • Graphs may be analysed/ingested by a range of algorithms • …e.g. A* / Dijksta’s algorithm • …used in machine learning. • Example of method e.g. Back propagation of errors / regression methods

This question in 9618/33 May/June 2021

8 (a) State two factors that may affect the performance of a sorting algorithm. … … … … [2] (b) The given algorithm is a simple bubble sort that arranges a set of scores stored in a one- dimensional array into descending order, and orders the corresponding students’ names stored into a two-dimensional array in the same order as the scores. All the arrays are indexed from 1. The contents of both arrays after sorting are shown. Name Score 1 2 1 98 1 Smithfield Tom 2 97 2 Johnson Jane … … 248 5 248 Peters Jade 249 3 249 Allen John YearSize 249 ← Flag TRUE ← WHILE Flag = TRUE Flag FALSE ← FOR Student 1 TO YearSize - 1 ← IF Score[Student] < Score[Student + 1] THEN Temp1 Score[Student] ← Temp2 Name[Student,1] ← Temp3 Name[Student,2] ← Score[Student] Score[Student + 1] ← Name[Student,1] Name[Student + 1,1] ← Name[Student,2] Name[Student + 1,2] ← Score[Student + 1] Temp1 ← Name[Student + 1,1] Temp2 ← Name[Student + 1,2] Temp3 ← Flag TRUE ← ENDIF NEXT Student ENDWHILE Write an algorithm, using pseudocode, that will perform the same task using an insertion sort. … … … … … … … … … … … … … … … … … … … … … [6]

8 marks

Mark scheme: 8(a) One mark for each correct marking point (Max 2) 2 • The initial order of the data • The number of data items to be sorted • The efficiency of the sorting algorithm 8(b) One mark for each marking point (max 6) 6 MP1 Use of FOR loop to cycle through the whole year group MP2 Temporary storage of the score being ‘inserted’ MP3 Temporary storage of the corresponding name elements MP4 Use of WHILE loop with correct exit clause MP5 Moving of all three elements of data to next array elements MP6 Correct updating of counter variable MP7 Final insertion of all three data elements Example algorithm YearSize ← 249 FOR Student ← 2 to YearSize Temp1 ← Score[Student] Temp2 ← Name[Student,1] Temp3 ← Name[Student,2] Counter ← Student WHILE Counter > 1 AND Score[Counter - 1] < Temp1 Score[Counter] ← Score[Counter - 1] Name[Counter,1] ← Name[Counter - 1,1] Name[Counter,2] ← Name[Counter - 1,2] Counter ← Counter – 1 ENDWHILE Score[Counter] ← Temp1 Name[Counter,1] ← Temp2 Name[Counter,2] ← Temp3 NEXT Student

This question in 9618/33 May/June 2021

9 (a) The diagram shown represents an artificial neural network. Output Layer Input Layer Hidden Hidden Layer 1 Hidden Layer 3 Layer 2 (i) State the reason for having multiple hidden layers in an artificial neural network. … … [1] (ii) Explain how artificial neural networks enable machine learning. … … … … … … … … … … [4] (b) Find the shortest path between the Home and School nodes using the A* algorithm. Show your working in the table provided. The first two rows in the table have been completed. 14 Home h = 10 g = 1 4 9 A 5 C 3 7 B 6 2 6 D 6 3 7 F 1 2 3 E 3 5 School Node Cost from Home node (g) Heuristic (h) Total (f = g + h) Home 0 14 14 A 1 10 11 Final path [5]

10 marks

Mark scheme: 9(a)(i) One mark for correct statement (Max 1) 1 • Enables deep learning to take place • Where the problem you are trying to solve has a higher level of complexity it requires more layers to solve • To enable the neural network to learn and make decisions on its own • To improve the accuracy of the result. 9(a)(ii) One mark for each correct marking point (Max 4) 4 • Artificial neural networks are intended to replicate the way human brains work • Weights / values are assigned for each connection between nodes • The data are input at the input layer and are passed into the system • They are analysed at each subsequent (hidden) layer where characteristics are extracted / outputs are calculated • … this process of training / learning is repeated many times to achieve optimum outputs // reinforcement learning takes place • Decisions can be made without being specifically programmed • The deep learning net will have created complex feature detectors • The output layer provides the results • Back propagation (of errors) will be used to correct any errors that have been made. 9(b) One mark for each correct calculation as follows (Max 4) 5 • Node B (from Home) (Line 3 in table) • Node C (from Home) (Line 4 in table) • Node B and Node E (from A) (Lines 5 and 6 in table) • Node F and Node School (from E) (Lines 7 and 8 in table) • Node School (from F) (Line 9 in table) One mark for correct path (Max 1): • Home  A  E  F  School Node Cost from Home Heuristic Total Node (g) (h) (f = g + h) 1 Home 0 14 14 2 A 1 10 11 3 B 5 7 12 4 C 4 9 13 5 B 1 + 3 = 4 7 11 6 E 1 + 6 = 7 3 10 7 F 7 + 1 = 8 3 11 8 School 7 + 5 = 12 0 12 9 School 8 + 3 = 11 0 11 Final Path Home  A  E  F  School

This question in 9618/31 Oct/Nov 2021

9 (a) The diagram shown represents an artificial neural network. Output Layer Input Layer Hidden Hidden Layer 1 Hidden Layer 3 Layer 2 (i) State the reason for having multiple hidden layers in an artificial neural network. … … [1] (ii) Explain how artificial neural networks enable machine learning. … … … … … … … … … … [4] (b) Find the shortest path between the Home and School nodes using the A* algorithm. Show your working in the table provided. The first two rows in the table have been completed. 14 Home h = 10 g = 1 4 9 A 5 C 3 7 B 6 2 6 D 6 3 7 F 1 2 3 E 3 5 School Node Cost from Home node (g) Heuristic (h) Total (f = g + h) Home 0 14 14 A 1 10 11 Final path [5]

10 marks

Mark scheme: 9(a)(i) One mark for correct statement (Max 1) 1 • Enables deep learning to take place • Where the problem you are trying to solve has a higher level of complexity it requires more layers to solve • To enable the neural network to learn and make decisions on its own • To improve the accuracy of the result. 9(a)(ii) One mark for each correct marking point (Max 4) 4 • Artificial neural networks are intended to replicate the way human brains work • Weights / values are assigned for each connection between nodes • The data are input at the input layer and are passed into the system • They are analysed at each subsequent (hidden) layer where characteristics are extracted / outputs are calculated • … this process of training / learning is repeated many times to achieve optimum outputs // reinforcement learning takes place • Decisions can be made without being specifically programmed • The deep learning net will have created complex feature detectors • The output layer provides the results • Back propagation (of errors) will be used to correct any errors that have been made. 9(b) One mark for each correct calculation as follows (Max 4) 5 • Node B (from Home) (Line 3 in table) • Node C (from Home) (Line 4 in table) • Node B and Node E (from A) (Lines 5 and 6 in table) • Node F and Node School (from E) (Lines 7 and 8 in table) • Node School (from F) (Line 9 in table) One mark for correct path (Max 1): • Home  A  E  F  School Node Cost from Home Heuristic Total Node (g) (h) (f = g + h) 1 Home 0 14 14 2 A 1 10 11 3 B 5 7 12 4 C 4 9 13 5 B 1 + 3 = 4 7 11 6 E 1 + 6 = 7 3 10 7 F 7 + 1 = 8 3 11 8 School 7 + 5 = 12 0 12 9 School 8 + 3 = 11 0 11 Final Path Home  A  E  F  School

This question in 9618/32 Oct/Nov 2021

8 A binary search or a linear search can be used to look for a specific value in an array. (a) Complete this pseudocode algorithm for a linear search. DECLARE MyList : ARRAY[0:9] OF INTEGER DECLARE MaxIndex : INTEGER DECLARE Index : INTEGER DECLARE Found : BOOLEAN DECLARE ValueToFind : … INPUT ValueToFind Found FALSE ← Index 0 ← … MaxIndex ← REPEAT IF MyList[Index] = ValueToFind THEN Found TRUE ← ENDIF Index … ← UNTIL Found OR Index > MaxIndex IF Found THEN OUTPUT "Value found at position ", Index ELSE OUTPUT … ENDIF [4] (b) (i) State the necessary condition for a binary search. … … [1] (ii) Describe how to perform a binary search. … … … … … … … … [4] (iii) Explain how the performance of a binary search varies according to the number of values in the array. … … … [1] (c) Compare the performance of the algorithms for a binary search and a linear search using Big O notation for order of time complexity. … … … … … … [3]

13 marks

Mark scheme: 8(a) 9 // LENGTH(MyList) - 1 Index + 1 "Value not found" (or any similar phrase) 8(b)(i) The list to be searched must be ordered/sorted 1 Question Answer Marks 8(b)(ii) Any four from MP1 Find the middle item / index MP2 Check the value of middle item in the list to be searched MP3 If equal item searched for is found MP4 If this is not equal/greater/less than the item searched for MP5 … discard the half of the list that does not contain the search item MP6 Repeat the above steps until the item searched for is found MP7 … or there is only one item left in the list and it is not the item searched for // lower bound > / = upper bound 4 8(b)(iii) As the number of items in the list increases the time to search the list increases 1 8(c) MP1 Linear search O(n) and Binary search O(log2n) / O(Log n) MP2 time to search increases linearly in relation to the number of items in the list for a linear search and logarithmically for a Binary search MP3 time to search increases less rapidly for a binary search and time to search increases more rapidly for a linear search 3

This question in 9618/32 May/June 2022

12 (a) The array Names[0:99] is in alphabetical order. Complete this pseudocode binary search algorithm. Lower 0 ← … Mid 0 ← Exit FALSE ← OUTPUT "Enter the name to be found " INPUT Target REPEAT … THEN OUTPUT Target, " does not exist" Exit TRUE ← ENDIF Mid Lower + (Upper – Lower + 1) DIV 2 ← IF Names[Mid] < Target THEN Lower … ← ENDIF IF Names[Mid] > Target THEN … ENDIF … THEN OUTPUT Target, " was found at location ", Mid Exit TRUE ← ENDIF … [6] (b) Big O notation is used to classify efficiency of algorithms. The Big O notation for time complexity in a binary search is O(log n). (i) State the Big O notation for time complexity of a linear search. … [1] (ii) Describe the meaning of O(log n) as it applies to a binary search algorithm. … … … … [2]

9 marks

Mark scheme: 12(a) One mark for each point (Max 6) 6 • Initialisation of upper bound • Test if upper bound is less than lower bound • Re-setting of mid value if current value is lower than the target • Re-setting of mid value if current value is higher than the target • Finding the value • Correct termination of loop Lower  0 Upper  99 Mid  0 Exit  FALSE OUTPUT "Enter the name to be found " INPUT Target REPEAT IF Upper < Lower THEN OUTPUT Target, " does not exist" Exit  TRUE ENDIF Mid  Lower + (Upper – Lower + 1) DIV 2 IF Names[Mid] < Target THEN Lower  Mid + 1 ENDIF IF Names[Mid] > Target THEN Upper  Mid - 1 ENDIF IF Names[Mid] = Target THEN OUTPUT Target, " was found at location ", Mid Exit  TRUE ENDIF UNTIL Exit // UNTIL Exit = TRUE 12(b)(i) O(n) 1 12(b)(ii) One mark for each point (Max 2) 2 • O(log n) is a time complexity that uses logarithmic time. • The time taken goes up linearly as the number of items rises exponentially • O(log n) is the worst case scenario (time complexity for a binary search).

This question in 9618/31 Oct/Nov 2022

11 A simplified linked list is used to store the names of flowers in alphabetical order. It is implemented using two 1D arrays: • Flower stores the names of the flowers. • NextPointer stores the pointer to the next flower name in the list. HeadPointer indicates the index of the first flower name in the linked list. HeadPointer 6 When the end of the linked list is reached, the next pointer has the value of 0. The following table shows the initial content of the arrays. Index Flower NextPointer 1 Rose 7 2 Marigold 1 3 Foxglove 10 4 Iris 9 5 Daisy 3 6 Dahlia 5 7 Saxifrage 0 8 Lupin 2 9 Lily 8 10 Hydrangea 4 (a) Several flower names have been deleted from the linked list. These are crossed out in the following table. Complete the table to show the new values of HeadPointer and NextPointer to keep the remaining flower names in alphabetical order. HeadPointer Index Flower NextPointer 1 Rose 2 Marigold 3 Foxglove 4 Iris 5 Daisy 6 Dahlia 7 Saxifrage 8 Lupin 9 Lily 10 Hydrangea [3] (b) Complete the pseudocode algorithm so that it achieves the following when applied to the arrays: • The flower name is input. • The linked list is searched, in order, for the flower name. • If the flower name is found, an appropriate message is output to indicate it has been found. • If the flower name is not found, an appropriate message is output to indicate it has not been found. • The algorithm terminates when the next pointer value is 0. Pointer HeadPointer Found 0 OUTPUT "Enter a flower name " IF Flower[Pointer] = FlowerName THEN Found Pointer Pointer 0 ELSE ENDWHILE ELSE [5] (c) Explain how you could improve the simplified linked list structure. … … … … [2]

10 marks

Mark scheme: 11(a) One mark for each point 3 • Correct HeadPointer • Any three correct NextPointer • All six NextPointer correct HeadPointer 5 Index Flower NextPointer 1 Rose 0 2 Marigold 3 Foxglove 4 4 Iris 9 5 Daisy 3 6 Dahlia 7 Saxifrage 8 Lupin 1 9 Lily 8 10 Hydrangea 11(b) One mark for each correct line 5 Pointer  HeadPointer Found  0 OUTPUT "Enter a flower name " INPUT FlowerName WHILE Pointer <> 0 IF Flower[Pointer] = FlowerName THEN Found  Pointer Pointer  0 ELSE Pointer  NextPointer[Pointer] ENDIF ENDWHILE IF Pointer = 0 THEN // IF Found <> 0 THEN OUTPUT Flower[Found], " is found" ELSE OUTPUT "The flower you wanted is not in the list" ENDIF 11(c) One mark for each point (Max 2) 2 • Include a free list pointer • …to reuse the unused space • …as a linked list of free space.

This question in 9618/32 Oct/Nov 2022

12 (a) The array Names[0:99] is in alphabetical order. Complete this pseudocode binary search algorithm. Lower 0 ← … Mid 0 ← Exit FALSE ← OUTPUT "Enter the name to be found " INPUT Target REPEAT … THEN OUTPUT Target, " does not exist" Exit TRUE ← ENDIF Mid Lower + (Upper – Lower + 1) DIV 2 ← IF Names[Mid] < Target THEN Lower … ← ENDIF IF Names[Mid] > Target THEN … ENDIF … THEN OUTPUT Target, " was found at location ", Mid Exit TRUE ← ENDIF … [6] (b) Big O notation is used to classify efficiency of algorithms. The Big O notation for time complexity in a binary search is O(log n). (i) State the Big O notation for time complexity of a linear search. … [1] (ii) Describe the meaning of O(log n) as it applies to a binary search algorithm. … … … … [2]

9 marks

Mark scheme: 12(a) One mark for each point (Max 6) 6 • Initialisation of upper bound • Test if upper bound is less than lower bound • Re-setting of mid value if current value is lower than the target • Re-setting of mid value if current value is higher than the target • Finding the value • Correct termination of loop Lower  0 Upper  99 Mid  0 Exit  FALSE OUTPUT "Enter the name to be found " INPUT Target REPEAT IF Upper < Lower THEN OUTPUT Target, " does not exist" Exit  TRUE ENDIF Mid  Lower + (Upper – Lower + 1) DIV 2 IF Names[Mid] < Target THEN Lower  Mid + 1 ENDIF IF Names[Mid] > Target THEN Upper  Mid - 1 ENDIF IF Names[Mid] = Target THEN OUTPUT Target, " was found at location ", Mid Exit  TRUE ENDIF UNTIL Exit // UNTIL Exit = TRUE 12(b)(i) O(n) 1 12(b)(ii) One mark for each point (Max 2) 2 • O(log n) is a time complexity that uses logarithmic time. • The time taken goes up linearly as the number of items rises exponentially • O(log n) is the worst case scenario (time complexity for a binary search).

This question in 9618/33 Oct/Nov 2022

2 (a) Draw one line from each machine learning category to its most appropriate description. Machine learning category Description simulates the data-processing capabilities of the human brain to make decisions Supervised learning enables learning by mapping an input to an output based on example input– output pairs Reinforcement learning enables information related to errors produced by the neural network to be transmitted Deep learning enables learning in an interactive environment by trial and error using its own experiences Unsupervised learning enables learning by allowing the process to discover patterns on its own that were previously undetected [4] (b) Describe the purpose of both the A* algorithm and Dijkstra’s algorithm. … … … … [2]

6 marks

Mark scheme: 2(a) One mark for each correct line connecting a machine learning technique to its 4 most appropriate description (Max 4). Machine learning category Description simulates the data processing capabilities of the human brain to make decisions Supervised learning enables learning by mapping an input to an output based on example input- Reinforcement output pairs learning enables information related to errors produced by the neural network to be transmitted Deep learning enables learning in an interactive environment by trial and error using its own experiences Unsupervised learning enables learning by allowing the process to discover patterns on its own that were previously undetected 2(b) One mark per mark point (Max 2) 2  to find the optimal / shortest / most cost-effective route  … between two nodes in a  … based on distance / cost / time.

This question in 9618/31 May/June 2023