Computational methods

Data in a computer program needs to be sorted.

Describe the steps a bubble sort will take to sort items into ascending order.

Darcie and Felix have both written a program that will perform a bubble sort to put these numbers into ascending order.

Darcie’s version will complete six passes. However, Felix’s version will only need to complete two passes.

Explain how Felix may have made his version more efficient than Darcie’s version.

A second type of sorting algorithm is an insertion sort.

Describe how an insertion sort can be used to put the following data into ascending order.

A third type of sorting algorithm is a quick sort.

The following quick sort algorithm is made up of two functions called partition() and quickSort(). The algorithm will sort an integer array into ascending numerical order.

Identify which of the two functions is recursive and give all of the line numbers where recursive calls are made.

Recursive function name........

Recursive call line numbers........

Identify the type of iteration used in the function partition().

Describe the role of the function partition() in the quick sort algorithm.

The algorithm needs to be changed to sort the integer array into descending numerical order.

Identify the line number that needs to be changed and write the amended line of code.

Amended line of code........

The quick sort is an example of a divide-and-conquer algorithm.

Describe what divide-and-conquer means.

2* A shopping website requires customers to create a username and password.

The usernames and passwords are stored securely in a file. The file contains the username and passwords for 50 million users which are sorted in alphabetical order by username.

The file can be searched using a linear search or a binary search.

The big-O complexities for a linear search and a binary search are given in the table:

Compare the use of a linear search and a binary search in this scenario.

You should include the following in your answer:

• the features and preconditions of a linear and binary search

• the benefits and drawbacks of each search in this scenario

• a conclusion justifying which search algorithm should be used in this scenario.

You should make reference to the big-O complexities in your answer.

The website collects data from customers’ activities once they log on. For example, the items they view and purchase. The company that owns the website would like to use data mining to improve their website and customer experience.

Describe what data mining means.

Explain how the company can make use of data mining to improve their website and customer experience.

Explain why this graph is a visualisation of the problem.

A user needs to travel from planet A to planet H. They need to travel the least expensive route.

Show how Dijkstra’s algorithm can be used on the directed graph shown in Fig. 5 to find the shortest path from start planet A to the end planet H.

You must state the nodes on the final path and the distance of this path. Show your working.

You may use the table to give your answer.

The A* algorithm can also be used to find the shortest path in a graph.

Describe how an A* algorithm uses heuristics to be an efficient algorithm.

A linked list data structure is designed using object-oriented programming.

The design includes two classes called node and linkedList.

Describe the features of a linked list data structure.

The class design for node is shown here.

new() is the constructor method. The constructor method takes a parameter and assigns this to the value attribute.

The method getNextNode() returns the attribute nextNode.

Write the method getNextNode() using pseudocode or program code.

The method setValue() takes an integer as a parameter and assigns this to the attribute value

Write the method setValue() using pseudocode or program code.

The class design for linkedList is shown here.

new() is the constructor method. The constructor initialises the attribute headNode to a null value.

Write the constructor method using pseudocode or program code.

The class design for node and linkedList are shown again here for your reference.

The method getValue() will return the value of a node. The method getNextNode() will return the next node to be accessed in the linked list.

The method outputList() traverses the linked list starting at the node headNode. The method joins the data in each node and returns it.

Complete the method outputList() using pseudocode or program code.

The method insertNode() will insert a new node into the linked list.

The method accepts an integer as a parameter, creates a new node with that data and inserts it into the linked list, e.g. insertNode(8) creates a node object with the data 8 and adds it to the linked list.

The program needs to store the following data items in the linked list in the order they are given: 10 25 39

The program then needs to output all of the data in the list using the appropriate method.

Write an algorithm using pseudocode or program code to:

• create a new linkedList object with the identifier createList

• insert each of the data items into the linked list (10, 25, 39)

• output the content of the linked list.

A new method is needed to remove a node from the linked list. The method needs to take the data to remove as a parameter and then find this data in the linked list before removing the node.

Describe the steps that this method will need to follow and the decisions that need to be made in the method to remove the correct node.

The program developer made use of computational methods when designing the object-oriented programming solution. One computational method is divide-and-conquer.

Identify three other computational methods that the program developer could have used.

* This program uses classes and objects to create a linked list.

An alternative method is creating a 2-dimensional array. In this design the first index stores the data and the second element stores the index of the next data item. Array elements not currently used are also linked together to form a chain of empty values to identify where the next data item can be inserted.

Compare the two different methods of creating a linked list that have been described.

You should include the following in your answer:

• the features of both methods including the reusability of program components

• benefits and drawbacks of both methods in this program

• a conclusion evaluating the efficiency of both methods when designing a program that needs

a linked list.

2* A company runs a Virtual Learning Environment (VLE). Schools can register students to use the VLE. The students get their own account and the school can view and monitor their students who are registered. There are currently over 10 000 schools registered, each with up to 1000 students.

The students can watch videos, take quizzes and communicate using forums and online chat tools.

The company gathers a large amount of data and wants to use data mining to help them decide how to improve the VLE in the future.

Discuss how the company can use data mining to decide how to improve the VLE.

You should include the following in your answer:

• the characteristics of data mining

• the benefits of data mining in this scenario

• the drawbacks of data mining in this scenario.

A computer game has a building containing 7 rooms. There are secret passages between each room. Fig. 3 shows the rooms and the passages between the rooms represented as a graph data structure.

The number in bold below each node in Fig. 3 is the heuristic value.

Perform an A* algorithm on the graph shown in Fig. 3 to find the shortest path from A to G.

Show your working, the nodes visited and the distance.

You may use the table below to give your answer.

State four ways that a graph data structure is different from a tree data structure.

* The final game will involve multiple computer-controlled characters and interactive elements that make use of artificial intelligence to determine the moves they will make.

The artificial intelligence will use heuristics to determine where the computer-controlled characters will move in the game.

Discuss how heuristics can be used in algorithms.

You should include the following in your answer:

• the purpose of heuristics

• the benefits and drawbacks of heuristics

• the suitability of heuristics in algorithms within a computer game.

A group of students are designing a racing car game. The game will allow players to enter their name and then a choice of vehicle. They will then race against other vehicles that will be controlled by the program. Players will use the arrow keys to control their vehicle.

The students are identifying the inputs and outputs for the game.

Complete the table by identifying two inputs and two outputs for the game.

The students use abstraction during the design process.

State what is meant by abstraction and describe how it can be used to design the racing car game.

Explain why it is beneficial to use abstraction when designing a computer program such as a game.

The group of students also use decomposition.

State what is meant by decomposition.

Describe one benefit of using decomposition when designing a computer program such as a game.

2* A company needs a new computer program that will create schedules for delivery drivers. It will need to identify a possible order that the drivers can deliver items and possible routes they could take.

Discuss how programmers could make use of problem recognition and problem decomposition when designing this system.

You should include the following in your answer:

• a description of both problem recognition and decomposition

• how each method can be used when designing the solution

• the benefits of using each method when designing the solution.

A programmer is developing an aeroplane simulator. The user will sit in a cockpit and the simulated environment will be displayed on screens around them.

The programmer uses computational methods to design a solution for the program.

Complete the table by writing a definition for each computational method.

Give three potential differences between the abstracted aeroplane simulator and reality.

Identify two reasons why abstraction is used when designing a solution to the problem.

Describe how caching can be used in the aeroplane simulator.

State one way a directed graph is different to an undirected graph.

State one way a graph data structure is different to a tree data structure.

Give one reason why the graph is a visualisation of the problem.

Give a similarity and difference between the performance of Dijkstra’s algorithm and the performance of A* algorithm.

State why performance modelling is used to test a system.

Describe how performance modelling can be used in the delivery system.

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.

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.

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.

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.

OCR-Tickets wants to sell tickets for their concerts, plays and other events online. A customer should be able to create an account and then be able to log into their account. Once logged in, customers should be able to carry out actions such as setting their preferences and purchase tickets.

OCR-Tickets have hired a software development company to create the system for them.

The system requirements have a number of features that mean they are solvable by computational methods, such as decomposition.

Explain why decomposition can help the development of the program.

* Discuss the need for concurrent processing in OCR-Ticket’s system and the benefits and drawbacks of using this.

A program needs to store the names of plants that are in a garden, so they can be easily found and accessed in alphabetical order.

The data is stored in a tree structure. Part of the tree is shown.

State the type of tree shown in Fig. 2.1.

Show the output of a breadth-first traversal of the tree shown in Fig. 2.1.

Explain how backtracking is used in a depth-first (post-order) traversal. Use the tree in Fig. 2.1 in your explanation.

The elements in the tree in Fig. 2.1 are read into a linked list producing an alphabetised list.

Complete the following table to show the linked list for the data.

A new plant, Lavender, needs adding to the linked list. The linked list needs to retain its alphabetical order.

Complete the table to show the linked list after Lavender is added.

Hosta needs removing from the linked list.

Explain how a data item is removed from a linked list. Use the removal of Hosta in your answer.

The linked list is stored as a 2D array with the identifier plantList. The index of the first element of the linked list is stored in the identifier firstElement.

All contents of the linked list need to be output in alphabetical order.

Write an algorithm to follow the pointers to output the contents of the linked list in alphabetical order.

Add comments to explain your code.

Mabel is a software engineer. She is writing a computer game for a client. In the game the main character has to avoid their enemies. This becomes more difficult as the levels of the game increase.

Mabel uses decomposition to design the program.

Explain how decomposition can aid the design of this program.

The computer game allows a user to select a character (e.g. name, gender). They can then choose a level for the game (easy, normal, challenging). The user controls their character by moving it left or right. The character can jump using space bar as an input. If the character touches one of the enemies then it loses a life. The character has to make it to the end of the level without losing all their lives.

The game is designed in a modular way.

One sub-procedure will handle the user input.

Describe three other sub-procedures Mabel could create for the given game description.

Describe the decision that the program will need to make within the user input sub- procedure and the result of this decision.

Define pipelining and give an example of how it could be applied in the program.

*Mabel has been told that true programmers write programs in a text editor, and do not use IDEs. Mabel does not agree with this statement.

Discuss the use of an IDE in the development of this program.

6* Benedict runs a social networking website. He has been told he should use data mining to help him enhance and improve his website.

Evaluate the use of data mining to help Benedict enhance and improve his social networking website.

A company merger is joining five e-commerce retailers under one company, OCRRetail. Each retailer has a different sales system and OCRRetail wants to develop one computer system that can be used by all the retailers.

Mary’s software development company has been employed to analyse and design a solution for the company.

Two computational methods (techniques used to solve a problem using computational thinking) that Mary will use are problem recognition and decomposition.

State what is meant by problem recognition and decomposition.

State one additional computational method.

Mary plans to use data mining to generate information about OCRRetail’s customers. Mary will use this information to benefit the company.

Define the term ‘data mining’.

Identify two pieces of information that data mining could provide OCRRetail about sales, and state how OCRRetail could make use of this information.

Mary has developed the program and is considering using performance modelling before installing the system.

Define the term ‘performance modelling’.

Identify one way performance modelling could be used to test the new system.

Mary created the program as a series of sub-programs that can be reused.

Describe one benefit of Mary creating reusable program components.

The graph in Fig. 3 is a visualisation of the problem.

Identify one difference between a graph and a tree.

Explain how the graph is an abstraction of the problem.

Identify two advantages of using a visualisation such as the one shown in Fig. 3.

Demonstrate how Dijkstra’s algorithm would find the shortest path to the solution in Fig. 3.

* The creator of the puzzle has been told that the A* algorithm is more efficient at finding the shortest path because it uses heuristics.

Compare the performance of Dijkstra’s algorithm and the A* search algorithm, making reference to heuristics, to find the shortest path to the problem.

Identify the data structure shown in Fig. 4.1.

The programmer is considering using a depth-first (post-order) traversal, or a breadth-first traversal to find the path between node A and node X.

Explain the difference between a depth-first (post-order) and breadth-first traversal.

Show how a depth-first (post-order) traversal would find the path between node A and node X for the structure shown in Fig. 4.1.

Explain how you used backtracking in your answer to part (b)(ii).

A software developer is creating a Virtual Pet game.

The user can choose the type of animal they would like as their pet, give it a name and then they are responsible for caring for that animal. The user will need to feed, play with, and educate their pet.

The aim is to keep the animal alive and happy, for example if the animal is not fed over a set period of time then the pet will die.

• The game tells the user how hungry or bored the animal is as a percentage (%) and the animal’s intelligence is ranked as a number between 0 and 150 (inclusive).

• Hunger and boredom increase by 1% with every tick of a timer.

• When the feed option is selected, hunger is reduced to 0.

• When the play option is selected, bored is reduced to 0.

• When the read option is selected, the intelligence is increased by 0.6% of its current value.

An example of the game is shown:

Fig. 1.1

Identify three inputs that the user will have to enter to start, and/or play the game.

The developer is using decomposition to design the game.

Describe the process of decomposition.

The developer needs to write procedures for the options play and read. Each of the options changes its corresponding value, and outputs the results to the screen.

Write a procedure, using pseudocode, to reset bored and output the new value in an appropriate message.

Write a procedure, using pseudocode, to increase intelligence by 0.6% and output the new intelligence in an appropriate message.

The developer is extending the game to allow users to have multiple pets of different types. The developer has written a class, Pet.

The attributes and methods in the class are described in the table:

Part of the class declaration is given:

Write a line of code that creates a new instance of Pet for a Tiger called “Springy”.

The method outputGreeting for the superclass is written as follows:

A class is needed for Tiger. The class needs to:

• inherit the methods and attributes from pet

• in the constructor, set type to Tiger, intelligence to 10, hunger to 50 and bored to 10

• extend the method outputGreeting, by outputting an additional line that says “I like to eat meat and roar”

Write, using pseudocode, the class Tiger.

(e*) The developer made use of abstraction when creating the Virtual Pet game.

Discuss the need for and purpose of abstraction and how abstraction will be used in the

development of the game.

The developer is storing the user’s pets in a 1-dimensional array. At each timer interval, the array is searched, using a linear search, to check if any pets’ hunger or bored values are greater than 90%. If they are, an alert is displayed to the user.

State the complexity of searching the pets in Big-O notation.

A given computer takes 4 milliseconds (ms) to search an array of 20 pets. Calculate an estimate of how long the computer will take to search an array of 100 pets.

Show your working.