# 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
endif
____________________________??????
if (A[mid] > value)then
return S(A, value, low, mid-1)
elseif (A[mid] < value)then
return S(A, value, mid+1, high)
else
return mid
endif
endfunction```

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). bubble

insertion

quick

merge

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.

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```

6

9

7

8

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

pipelining

pathfinding

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.
```Context
=======
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.