OCR A Level Computer Science H446/02 Algorithms and programming. QUESTIONS AND MARKING SCHEME

Answer all the questions. 1 Taylor is creating an online multiplayer game where users can create accounts and build their own circus. Each circus will contain characters such as clowns, animals, magicians and dancers. ...

Answer all the questions. 1 Taylor is creating an online multiplayer game where users can create accounts and build their own circus. Each circus will contain characters such as clowns, animals, magicians and dancers. Users can set up a new circus in the online world, purchase new characters and visit other users’ circuses. (a) Taylor uses computational methods to analyse the problem including abstraction. Describe how Taylor could use abstraction in the design of his online circus game. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... .............................................................................................................................................. [3] (b) Taylor will make use of concurrent processing within his circus game. (i) Describe what is meant by the term ‘concurrent processing’. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ...................................................................................................................................... [2] (ii) Explain why concurrent processing is needed to allow multiple users to log in and interact with game elements at the same time. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ...................................................................................................................................... [3] 4 © OCR 2021 (c) Some of the characters in the game will move and interact independently. Taylor is going to use graphs to plan the movements that each character can take within the game. DancerGold is one character. The graph shown in Fig. 1 shows the possible movements that DancerGold can make. A B D E G C F 40 38 21 42 12 23 33 55 90 65 50 80 50 0 30 Fig. 1 DancerGold’s starting state is represented by node A. DancerGold can take any of the paths to reach the end state represented by node G. The number on each path represents the number of seconds each movement takes. The number in bold below each node is the heuristic value from A. (i) Define the term heuristic in relation to the A* algorithm. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ...................................................................................................................................... [2] 5 © OCR 2021 Turn over (ii) Perform an A* algorithm on the graph shown in Fig. 1 to find the shortest path from the starting node to the end node. Show your working, the nodes visited and the distance. You may choose to use the table below to give your answer. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... Node Distance travelled Heuristic Distance travelled + Heuristic Previous node Final path: ..................................................... Distance: ....................................................... [8] 6 © OCR 2021 (d) A breadth-first traversal can be performed on both a tree and a graph. Show how a breadth-first traversal is performed on the following binary tree. M E C J G K L P V S ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... .............................................................................................................................................. [6] (e)* The game will have thousands of users. Taylor will store data about the users and their actions while playing the game in a large database. Evaluate how Taylor can use data mining to inform future changes to improve his circus game. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... 7 © OCR 2021 Turn over ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... .............................................................................................................................................. [9] 8 © OCR 2021 2 The pseudocode function binarySearch() performs a binary search on the array dataArray that is passed as a parameter. The function returns the array index of searchValue within the array, and -1 if it is not in the array. (a) The pseudocode binary search algorithm is incomplete. (i) Complete the algorithm by filling in the missing statements. function binarySearch(dataArray:byref, upperbound, lowerbound, ………………………………) while true middle = lowerbound + ((upperbound – lowerbound) ………………………………) if upperbound < lowerbound then return …………………………………………… else if dataArray[middle] < searchValue then lowerbound = ……………………………………………………………………………………………………………………… elseif dataArray[middle] > searchValue then upperbound = ……………………………………………………………………………………………………………………… else return …………………………………………………………………………………………… endif endif endwhile endfunction [6] (ii) The algorithm uses a while loop. State a different type of loop that could be used instead of the while loop in the given algorithm. ........................................................................................................................................... ...................................................................................................................................... [1] 9 © OCR 2021 Turn over (b) The tables below show possible Big O complexities for the worst-case space, best-case space and average time for search algorithms. Tick the worst-case space complexity for a binary and linear search. Binary search Linear search O(log(n)) O(1) O(n) Tick the best-case space complexity for a binary and linear search. Binary search Linear search O(log(n)) O(1) O(n) Tick the average time complexity for a binary and linear search. Binary search Linear search O(log(n)) O(1) O(n) [6] (c) Identify one situation where a linear search is more appropriate than a binary search.