OCR A Level Computer Science Algorithms and programming November 2021 question paper H446/02

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.

Taylor uses computational methods to analyse the problem including abstraction.

Describe how Taylor could use abstraction in the design of his online circus game.

Taylor will make use of concurrent processing within his circus game.

Describe what is meant by the term ‘concurrent processing’.

Explain why concurrent processing is needed to allow multiple users to log in and interact with game elements at the same time.

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.

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.

Define the term heuristic in relation to the A* algorithm.

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.

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.

* 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.

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.

The pseudocode binary search algorithm is incomplete.

Complete the algorithm by filling in the missing statements.

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.

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.

Tick the best-case space complexity for a binary and linear search.

Tick the average time complexity for a binary and linear search.

Identify one situation where a linear search is more appropriate than a binary search.

A one dimensional array holds data that needs to be sorted.

Describe how a quicksort would sort data into ascending order.

Explain why a quicksort is known as a divide and conquer algorithm.

4* Anna currently writes her program code in a text editor and then runs the compiler.

She has been told that using an Integrated Development Environment (IDE) would be more helpful.

Discuss the benefits of Anna using an IDE to write and test her program rather than using a text editor.

The method new is used to denote the constructor for each class.

State the purpose of the constructor.

The classes office and house inherit from building.

Describe what is meant by inheritance with reference to these classes.

Part of the declaration for the class building is shown.

Complete the pseudocode declaration by filling in the missing statements.

Write program code or pseudocode to declare the class house.

Define the attributes and constructor method in your answer. You do not need to write the get or set methods.

Christoff develops a new class to store the houses in one road. His class design is shown:

The method newbuilding() takes a new building as a parameter, and stores this in the next free space in the array buildings.

Write pseudocode or program code for the method newbuilding().

Christoff wants to create a new house called houseOne. It has the properties: 2 floors, 8(m) width, 10(m) height, 3 bedrooms and 2 bathrooms.

The house is located on a road with the identifier limeAvenue of type houseRoad houseOne is the first house in this road.

Write pseudocode or program code to declare the house houseOne, road limeAvenue and assign houseOne to the first array position in the road.

Amy’s processor makes use of pipelining during the fetch-decode-execute cycle.

The processor’s pipeline consists of the following stages:

• Fetching the instruction from memory

• Decoding the instruction

• Executing the instruction.

Instructions A, B, C and D need to be processed.

Identify the stage(s) and instruction(s) run during each pipeline below.

Explain why pipelining can improve the performance of the processor.

Lucas writes a program that makes use of a circular queue. The queue stores the data entered into the program. An array is used to represent the queue.

The program needs two pointers to access and manipulate the data in the queue.

State the purpose of the two pointers and give an appropriate identifier for each.

Pointer 1 purpose........

Pointer 1 identifier........

Pointer 2 purpose........

Pointer 2 identifier........

Lucas wants a procedure, enqueue(), that will add the parameter it is passed to the queue.

Describe the steps the procedure enqueue() will follow when adding new items to the queue.

Juan is creating a structure diagram to design the game.

A structure diagram is one method of showing the decomposition of a problem.

Explain why decomposing a problem can help a developer design a solution.

Identify one input, one process and one output required for the game.

Juan uses the structure diagram to create a modular program with a number of subroutines. The program will use two integer 2-dimensional arrays to store the puzzles:

• puzzle(5,5) stores the solution

• answerGrid(5,5) stores the user’s current grid.

A 0 represents a white box and a 1 represents a black box.

Explain the purpose of line 03 in the function countRow.

Describe the purpose of branching and iteration in the function countRow.

The function checkWon() takes answerGrid and puzzle as parameters and compares each element in the grids. If they are identical, it returns true, otherwise returns false.

There are three logic errors in the function checkWon.

State the line number of each error and give the corrected line.

Error 1 line number........

Error 1 correction........

Error 2 line number........

Error 2 correction........

Error 3 line number........

Error 3 correction........

* Juan passed the two arrays as parameters, but he did consider making them globally accessible.

Compare the use of global and local variables and data structures in this program. Include the use of parameters and program efficiency in your answer.

Juan wants to create a program that will generate new Nonograms with different grid sizes. For example a Nonogram with a 10 × 10 grid or a 5 × 20 grid.

Describe how the program could be written to automatically generate a new Nonogram.