Thinking concurrently

7* (a) A program designer needs to decide on an algorithm to use from a choice of three. The table shows the worst-case Big O complexities for each algorithm.

The program will be used to analyse data that can range from 2 items to 2 billion items.

Compare the use of all three algorithms and suggest which the programmer should use.

You should include the following in your answer:

• the meaning of constant, logarithmic, linear and exponential complexity

• how well each algorithm scales as the amount of data increases

• which algorithm is the most suitable for the given task.

The program designer is investigating the use of concurrent processing.

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

Give two benefits of using concurrent processing.

The programmer needs to use a merge sort in one part of the problem to sort items in ascending order.

Describe how a merge sort works.

Give one benefit and one drawback of the programmer using a merge sort instead of a bubble sort.

The programmer uses an Integrated Development Environment (IDE).

Complete the table by identifying and describing three IDE features that can help the programmer to develop, or debug a program.

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.

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.

Kamran is writing a program to manipulate the data for a set of items.

For each item, the program needs to store:

• Item name (e.g. Box)

• Cost (e.g. 22.58)

• Date of arrival (e.g. 1/5/2018)

• Transferred (e.g. true)

The items are added to a queue for processing.

The queue is defined as a class, itemQueue.

The head attribute points to the first element in the queue. The tail attribute points to the next available space in the queue. The numItems attribute states how many items are currently in the queue.

The data about the items can be stored using either a record structure, or as objects of a class.

Explain the similarities and differences between a record and a class.

Kamran chooses to use a record structure to store the data about the items.

Record structures may be declared using the following syntax:

Complete the pseudocode to declare a record called items.

New records may be created using the following syntax:

Write a programming statement to create a new item, using the identifier ‘box1’, with the item name “Box”, the cost 22.58, date of arrival 1/5/2018 and transferred true.

The array, theItems, stores the items in the queue. When the tail of the queue exceeds the last element in the array, it adds a new item to the first element if it is vacant.

For example, in the following queue, the next item to be added would be placed at index 0.

Define the term ‘queue’.

The attributes in itemQueue are all declared as private.

Explain how a private attribute improves the integrity of the data.

The constructor method creates a new instance of itemQueue and sets the head, tail and numItems attributes to 0.

Write an algorithm, using pseudocode or program code, for the constructor including the initialisation for all attributes.

The enqueue method:

takes as a parameter the item to insert in the queue

checks if the queue is full

reports an error and returns false if the queue is full

does the following if the queue is not full: o adds the item to the array at the tail position and adjusts the pointer(s) o returns true

The attribute numItems stores the number of items currently in the queue.

Write an algorithm, using pseudocode or program code, for the enqueue method.

Write a programming statement to declare an instance of itemQueue called myItems

Write a procedure, insertItems(), to ask the user to input the data for an item. The item is then added to the queue myItems. The user is continually asked to input data items until the queue is full.

When the main program ends, the items and the queue no longer exist.

Describe how Kamran could amend the program to make sure the items and queue still exist and are used the next time the program is run.

* Kamran wants to expand the program to allow it to handle up to 100,000,000 items and to allow him to search for data about items. Kamran is worried that the increase in the number of items will cause a decrease in the performance of the program. He decides to investigate the benefits of caching and concurrent processing.

Evaluate the use of caching and concurrent processing in this scenario and make a recommendation to Kamran.

A programmer is developing an ordering system for a fast food restaurant. When a member of staff inputs an order, it is added to a linked list for completion by the chefs.

Explain why a linked list is being used for the ordering system.

Order 158 has been made, and needs adding to the end of the linked list.

Add the order, 158, to the linked list as shown in Fig. 2.1. Show the contents of the linked list in the following table.

Order 159 has been made. This order has a high priority and needs to be the second order in the linked list. Add the order, 159, to the original linked list as shown in Fig. 2.1. Show the contents of the linked list in the following table.

The linked list is implemented using a 2D array, theOrders:

• Row 0 stores orderNo

• Row 1 stores next

The data now stored in theOrders is shown in Fig. 2.2.

The following algorithm is written:

Outline why nodeNo does not need to be stored in the array.

Complete the trace table for procedure x, for the data shown in Fig. 2.2.

Describe the purpose of procedure x.

A new order, 190, is to be added to theOrders. It needs to be the third element in the list. The current contents of the array are repeated here for reference:

Describe how the new order, 190, can be added to the array, so the linked list is read in the correct order, without rearranging the array elements.

The user needs to be able to search for, and find, a specific order number.

State an appropriate search algorithm that could be used, and justify your choice against an alternative Search algorithm.

Appropriate Search Algorithm........

The programmer is writing the program using an IDE.

Identify three features of an IDE that the programmer would use when writing the code and describe how the features benefit the programmer.

(f*) The programmer is considering using concurrent programming.

Discuss how concurrent programming can be applied to the food ordering system and the

benefits and limitations of doing so.