02 - Prog&Algorithms Part 1 (Exam Simulation)

 1. A games company is developing a flight simulation program. State three pieces of information that would need to be researched in order to design this simulator. (3 marks)

 2. Explain what is meant by "concurrent processing" and describe one example of how the simulator could make use of it. (2 marks)

 3. The following tube map of London is an abstraction made up of component parts. Using this example, explain the term abstraction (2 marks)

 4. A simulation games company is re-creating the London tube for a game. Program development requires the use of re-usable components. State three examples of how reusable components are used in the above example (3 marks)

 5. Another term for the use of re-usable components is modular programming. Why is this necessary for large programs? (3 marks)

 6. State two advantages to using re-usable parts while developing programs (2 marks)

 7. Explain why good programming practice generally avoids the use of global variables.(2 marks)

 8. The following algorithm shows the outworking of a binary search. Fill in the blanks on line 5.
function S(A[0..N-1], value, low, high) 
          if (high < low)then                
		return error_message   
	  if (A[mid] > value)then             
		return S(A, value, low, mid-1)               
	  elseif (A[mid] < value)then              
                return S(A, value, mid+1, high)           
                return mid      

  mid = (low + high) / 2

  low = (mid + high) / 2

  high = (low + mid) / 2

  mid = (high / 2)

 9. Part of the data held by the programmers for the search is shown below. State two reasons that suggest it would be best NOT to use a binary search on this data. (2 marks)
(42, 83, 27, 18, 52)

 10. Fill in the blanks on line 1 for the linear search that could be carried out on the data set above (to find the value 27 in the list)
Compare 83 (second value) and discard
Compare 27 (third value)
Display result / search stops

  Compare 27 to 83 (second value) and discard if smaller

  Compare 42 (first item) to be searched with 27

  Compare 83 (second value) with the first value and discard

  Compare 42 (first item) to be searched with 83 (second value)

 11. The following diagram shows the steps needed for a _______ on these values: (42, 83, 27, 18, 52).





 12. When comparing linear and binary search it is possible to look at the best, worst and average number of items in the array that need to be checked to find the item being searched for. The assumption here is that:

  every item in the array is equal to or less than 526 (or the equivalent size of RAM).

  only the first half of the list in the array is likely to be searched.

  not every item in the array is equally likely to be searched for.

  every item in the array is equally likely to be searched for.

 13. As the size of an array increases the average number of checks grows logarithmically. State what is meant by logarithmic growth.

  It can be thought of as the inverse of exponential growth.

  All the listed answers are valid answers.

  As x (or the size of the array) increases, the rate at which y (or the number of checks needed) increases more slowly.

  The rate of increase is a logarithmic function of the size of the array.

 14. A binary search tree is one example of a type of tree. State the main features of a tree. (3 marks)

 15. The following function is recursive. State the line in which recursion is occuring.
01 function generateObstacle(diceNumber) 
02 if diceNumber == 0 then 
03 return true 
04 else 
05 x = randomNumber(0, 7) 
06 y = randomNumber(0, 7) 
07 board(x, y) = new obstacle() 
08 generateObstacle(diceNumber-1) 
09 endif 
10 endfunction





 16. State two things that are occuring on line 01 of the algorithm above (2 marks)

 17. State three advantages of recursion (3 marks)

 18. State four drawbacks of recursion (4 marks)

 19. The following code re-writes the code above (recursive function) in an iterative manner. Which of the following would correctly fit in with this algorithm on line 02?
function generateobstacle(diceNumber)
	x = randomNumber(0,7)
	y = randonNumber(0,7)
	board(x,y) = new obstacle()
    next count
    return true
End Function

Context of the game given below
This game involves a board.
The board is to be stored as a 2-dimensional array.

Game play: The game is played by rolling two 6-sided dice 
and moving that number of spaces. 

Both players start on the START space. 

If a player lands on a space occupied by the other player, 
they move to the next available space.

Each time a player moves, a series of obstacles are to be added
to the board.

On their turn, each player rolls two dice. The smaller number from
the two dice is taken, and that many obstacles will appear on the
board in random locations.

For example, if a 3 and 6 are rolled, then 3 obstacles will appear.

  while count > 0 and diceNumber <7

  for count = 1 to 6

  for count = 0 to diceNumber

  while diceNumber <7 and count > 0

 20. Lisa wants to create an app and does some market research first. State four items of data that she could obtain in order to make a sensible choice of an app development project. (4 marks)

 21. A cafe manager is reorganising the layout of the cafeteria in order to speed up the service to customers. Explain how computational methods could be used in order to improve the layout of this cafeteria. (3 marks)

 22. Describe what is meant by a heuristic approach to problem-solving? (2 marks)

 23. In which of the following are heuristic methods likely to be used?

  Insertion of a leaf node into a binary tree data structure

  The powering on of a robot

  Insertion of a RAM chip into a desktop PC

  A human crossing a busy road

 24. Connect 4 is a popular game in which players must place four 'coins' in a row to win. Explain how a programmer could make use of a tree structure, using a heuristic approach in the development of the computer player for Connect 4? (4 marks)

 25. Virus checkers work by looking for _________________________. They also use ___________ approaches.

  patterns in the program code / heuristic

  instances of machine failure or illegal file deltion / file fragmentation

  viruses in the RAM / advantageous

  computational failure / computational method

 26. The following answer explains how _________________ principles can be used to ensure that a house is built as quickly as possible.
Look for processes that can be processed at the same time (1) 
processes that must be sequential (1). Example of possible parallel 
processes, e.g. windows installed at same time as electrics / plumbing 
(1). Example of an obligatory sequence e.g. rafters installed before 
tiles put on / walls before roof (1).

  modular programming




 27. How is the above used in any computer system? (3 marks)

 28. Read the context below and fill in the blanks for the following algorithm.
It is possible to use XOR together with a key to encrypt a plain text message.

For example, to encrypt the bit pattern 111100001111 using the number 5 as a key, 
the key is repeated as often as necessary to match the length of the message. 
An XOR operation is performed to generate the encoded message.

111100001111 <- Message to be encrypted

101101101101 <- Key: repeated as necessary

010001100010 <- Encrypted message

Fill in the blanks for the following algorithm to accept a text message
and a key that would  use the method above to generate an encoded message.

  asc_msg=encryptmsg+complete_key(1,i) XOR

  encryptmsg=asc_msg+complete_key(0,i) XOR

  encryptmsg=encryptmsg+complete_key(1,i) XOR

  encryptmsg=encryptmsg - complete_key(i) XOR

 29. In reference to the table below, assume every item in the array is equally likely to be searched for. Fill in the blanks for A.

 30. Refer to the table above. Fill in the blanks for B.

 31. Refer to the table above. Fill in the blanks for C.

 32. Refer to the table above. Fill in the blanks for D.

 33. State the purpose of Big O notation.(2 marks)

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

 35. Read the context below and describe why a queue is a suitable structure for this program. (3 marks)
A program stores a queue of mathematical questions to be asked to a user. 
The questions are asked in the order they are added. 

Once a question has been asked it cannot be asked again. 
New questions are continually added to the end of the queue.

The program will use a non-circular queue, questions, (implemented using an array)
to store the questions.

The pointer, head, stores the index of the first element in the queue.
The pointer, tail, stores the index of the last element in the queue.