1) Stacks are also used to store a stack frame each time a subroutine call is made.

State two components of a stack frame.

2) Figure 1 is a graph that shows the time it takes to travel between six locations in a warehouse. The six locations have been labeled with the numbers 1 – 6. When there is no edge between two nodes in the graph this means that it is not possible to travel directly between those two locations. When there is an edge between two nodes in the graph the edge is labeled with the time (in minutes) it takes to travel between the two locations represented by the nodes.

(a)  The graph is represented using an adjacency matrix, with the value 0 being used to indicate that there is no edge between two nodes in the graph.

A value should be written in every cell.

Complete the unshaded cells in Table 1 so that it shows the adjacency matrix for Figure 1.

(b)  Instead of using an adjacency matrix, an adjacency list could be used to represent the graph. Explain the circumstances in which it would be more appropriate to use an adjacency list instead of an adjacency matrix.

___________________________________________________________________

(c)  State one reason why the graph shown in Figure 1 is not a tree.

___________________________________________________________________

(d)  The graph in Figure 1 is a weighted graph. Explain what is meant by a weighted graph.

___________________________________________________________________

Figure 2 contains pseudo-code for a version of Djikstra’s algorithm used with the graph in Figure 1.

Q is a priority queue which stores nodes from the graph, maintained in an order based on the values in array D. The reordering of Q is performed automatically when a value in D is changed.

AM is the name given to the adjacency matrix for the graph represented in Figure 1.

e)  Complete the unshaded cells of Table 2 to show the result of tracing the algorithm shown in Figure 2. Some of the trace, including the maintenance of Q, has already been completed for you.

(f)   What does the output from the algorithm in Figure 2 represent?

___________________________________________________________________

(g)  The contents of the array P were changed by the algorithm. What is the purpose of the array P?

___________________________________________________________________

3) Write a program that checks which numbers from a series of numbers entered by the user are prime numbers.
The program should get a number from the user and then display the messages:

• •    “Not greater than 1” if the number entered is 1 or less
  •    “Is prime” if the number entered is a prime number
  •    “Is not prime” otherwise.

The user should then be asked if they want to enter another number and the program should repeat if they say that they do.

A prime number is a positive integer that will leave a remainder if it is divided by any positive integer other than 1 and itself.

You may assume that each number entered by the user is an integer.

If your program only works correctly for some prime numbers you will get some marks for this question. To get full marks for this question, your program must work correctly for any valid integer value that the user enters.

Evidence that you need to provide

(a)  Your PROGRAM SOURCE CODE.

(b)  SCREEN CAPTURE(S) showing the result of testing the program by:

• • •    entering the number 1
    •    then choosing to enter another number
    •    then entering the number 5
    •    then choosing to enter another number
    •    then entering the number 8
    •    and then choosing not to enter another number.

4) WORDS WITH AQA  is a two-player game. Each player starts with 15 randomly-selected tiles. Each tile represents a single letter; each letter has a points value as shown in Figure 1. The tiles that a player has are called their “hand”. Each player starts with a score of 50.

Players take turns to spell a two or more letter word using only the letter tiles in their hand. Each tile may only be used once in the word. If on their turn they spell a valid word then the tiles used in that word are removed from their hand and their score is increased. The amount their score increases by depends on which tiles were used and the number of tiles used in the word. Initially the score increases by the total points value of the tiles used. If a valid word is spelt that uses more than seven tiles an additional 20 points are added to the player’s score. If a valid word is spelt that uses six or seven tiles an additional five points are added to the player’s score.

The player may then choose to either get three new tiles, get a number of new tiles equal to the number of tiles used in the word they just spelt, get a number of new tiles equal to three larger than the number of tiles used in the word they just spelt or to get no new tiles. New tiles come from the tile queue.

If the word they spelt is not valid then their turn is over. No tiles are removed from their hand and they get three tiles from the tile queue.

A valid word is one in which all the tiles needed to spell the word are in their hand and it is a correctly-spelt English word.

The tile queue contains 20 randomly-selected tiles. The tiles in the queue are shown in order, the tile at the front of the queue will be the next tile given to a player who gets a new tile. When a tile is removed from the front of the queue and given to a player, a new randomly-selected tile is added to the rear of the queue. Players may look at the contents of the tile queue at any time.

The game ends when either a player has used a total of more than 50 tiles in the valid words they have spelt or when their hand contains 20 or more tiles. If Player One uses more than 50 tiles first or has a hand with 20 or more tiles then Player Two gets to have their turn before the game ends. At the end of the game each player’s score is reduced by the points value of the letters on the tiles remaining in their hand. The winner is the player with the highest score.

Figures 2 to 7 show an example game.

In the Skeleton Program there is a main menu containing three options.

The first option is to play the game with the players having a random selection of letters in their starting hands. The starting contents of the tile queue are random.

The second option is to play a training game in which the players have the same selection of letters in their starting hands as shown in Figure 2. The starting contents of the tile queue are random.

The third option is to quit the program.

When playing the game each player takes it in turn to spell a word. When a player has their turn they have five choices.

If they enter the string 1 then the point values of the 26 letters are displayed. The player’s turn continues and they can choose any of the five options.

If they enter the string 4 then the current contents of the tile queue are displayed. The player’s turn continues and they can choose any of the five options.

If they enter the string 7 then the current contents of their hand are displayed. The player’s turn continues and they can choose any of the five options.

If they enter the string 0 then the player’s hand will be given enough tiles to take them over the maximum number of tiles allowed in a hand. This will mean that the game will finish (though if Player One chooses this option, Player Two will still have their turn before the game finishes). The player’s turn then finishes.

If they enter any other string then this is treated as being an attempt at spelling a word and the program checks to see if the word is valid. The player’s turn then finishes.

To check that a word is valid the program checks if the word is:

• •    spelt using only letter tiles that are in the player’s hand
  •    in the list of allowed words. The allowed words are the words contained in the Data File aqawords.txt.

Data File

A Data File named aqawords.txt is supplied with the Skeleton Program. This stores the list of allowed English words that can be used in the game.

5) (a)  State the name of an identifier for a built-in function used in the Skeleton Program that has a string parameter and returns an integer value.

___________________________________________________________________

(b)  State the name of an identifier for a local variable in a method in the QueueOfTiles class.

___________________________________________________________________

(c)  The QueueOfTiles class implements a linear queue. A circular queue could have been used instead.

Explain why a circular queue is often a better choice of data structure than a linear queue.

___________________________________________________________________

(d)  It could be argued that the algorithms for a linear queue lead to simpler program code.

State one other reason why a linear queue is an appropriate choice in the Skeleton Program even though circular queues are normally a better choice.

___________________________________________________________________

(e)  State one additional attribute that must be added to the QueueOfTiles class if it were to be implemented as a circular queue instead of as a linear queue.

___________________________________________________________________

(f)   Describe the changes that would need to be made to the Skeleton Program so that the probability of a player getting a one point tile is the same as the probability of them getting a tile worth more than one point. The changes you describe should not result in any changes being made to the points value of any tile.

You should not change the Skeleton Program when answering this question.

___________________________________________________________________

(g)  The GetChoice subroutine uses a built-in function to convert a string to uppercase.

Describe how a string consisting of lowercase characters could be converted to uppercase using only one iterative structure if the programming language being used does not have a built-in function that can do this conversion.

You may assume that only lowercase characters are entered by the user.

You should not change the Skeleton Program when answering this question.

___________________________________________________________________

6) (a)  This question refers to the subroutine CreateTileDictionary.

The points values for the letters J and X are to be changed so that they are not worth as many points as the letters Z and Q.

Adapt the subroutine CreateTileDictionary so that the letters J and X are worth 4 points instead of 5 points.

Test that the changes you have made work:

• •    run the Skeleton Program
  •    enter 2 at the main menu
  •    enter 1 to view the letter values.

Evidence that you need to provide

(i)   Your PROGRAM SOURCE CODE for the amended subroutine CreateTileDictionary.

(ii)  SCREEN CAPTURE(S) showing the results of the requested test.

(b)  This question refers to the subroutine Main.

Currently each player starts with 15 letter tiles. In the Main subroutine StartHandSize is set to a value of 15.

Change the subroutine Main so that the user can choose what the value for StartHandSize will be.

Before the main menu is displayed and before the first iteration structure in Main the message “Enter start hand size: ” should be displayed and the user’s input should be stored in StartHandSize. This should happen repeatedly until the user enters a value for the start hand size that is between 1 and 20 inclusive.

Test that the changes you have made work:

• •    run the Skeleton Program
  •    enter 0 when asked to enter the start hand size
  •    enter 21 when asked to enter the start hand size
  •    enter 5 when asked to enter the start hand size
  •    enter 1 at the main menu.

Evidence that you need to provide

(i)   Your PROGRAM SOURCE CODE for the amended subroutine Main.

(ii)  SCREEN CAPTURE(S) showing the requested test. You must make sure that evidence for all parts of the requested test is provided in the SCREEN CAPTURE(S).

(c)  This question refers to the subroutine CheckWordIsValid.

When a player enters a word, a linear search algorithm is used to check to see if the word entered is in the list of AllowedWords. The subroutine CheckWordIsValid is to be changed so that it uses a more time-efficient search algorithm.

Change the CheckWordIsValid subroutine so that it uses a binary search algorithm instead of a linear search algorithm.

You must write your own search routine and not use any built-in search function that might be available in the programming language you are using.

Each item in AllowedWords that is compared to the word that the user entered should be displayed on the screen.

Figure 2 shows examples of how the new version of CheckWordIsValid should work if AllowedWords contained the items shown in Figure 1.

Test that the changes you have made work:

• •    run the Skeleton Program
  •    if you have answered part (b), enter 15 when asked to enter the start hand size; if you have not answered part (b) yet then skip this step
  •    enter 2 at the main menu
  •    enter the word jars.

Evidence that you need to provide

(i)   Your PROGRAM SOURCE CODE for the amended subroutine CheckWordIsValid.

(ii)  SCREEN CAPTURE(S) showing the requested test.

(d)  This question extends the functionality of the game.

After spelling a valid word the player decides which one of four options to select to determine how many tiles will be added to their hand. Before choosing they can look at the values of the tiles.

It would help the player make their decision if they were aware of how useful each letter was by knowing the frequency with which each letter appears in the list of allowed words.

The program is to be extended so that when the player chooses to view the tile values they are also shown the number of times that each letter appears in the list of allowed words.

What you need to do

Task 1

Create a new subroutine called CalculateFrequencies that looks through the list of allowed words and displays each of the 26 letters in the alphabet along with the number of times that the letter appears in the list of allowed words, which the subroutine has calculated.

Task 2

Modify the DisplayTileValues subroutine so that after displaying the tile values it also calls the CalculateFrequencies subroutine.

Task 3

Test that the changes you have made work:

• •    run the Skeleton Program
  •    if you have answered part (b), enter 15 when asked to enter the start hand size; if you have not answered part (b) yet then skip this step
  •    enter 2 at the main menu
  •    enter 1 to display the letter values.

Evidence that you need to provide

(i)   Your PROGRAM SOURCE CODE for the new subroutine CalculateFrequencies, the amended subroutine DisplayTileValues and any other subroutines you have modified when answering this question.

(ii)  SCREEN CAPTURE(S) showing the requested text.

(e)  The scoring system for the game is to be changed so that if a player spells a valid word they score points for all valid words that are a prefix of the word entered. A prefix is the first x characters of a word, where x is a whole number between one and the number of characters in the word.

In the Skeleton Program, AllowedWords contains the list of valid words that have been read in from the Data File aqawords.txt.

Example

If the user enters the word TOO they will be awarded points for the valid words TOO and TO as TO is a prefix of the word TOO. They will not be awarded points for the word OO even though it is a valid word and is a substring of TOO because it is not a prefix of TOO.

Example

If the user enters the word BETTER they will be awarded points for the words BETTER, BET and BE as these are all valid prefixes of the word entered by the user. They would not be awarded points for BETT or BETTE as these are not valid English words. They would not be awarded points for BEER as even though it is contained in the word BETTER it is not a prefix.

Example

If the user enters the word BIOGASSES they will be awarded points for the words BIOGASSES, BIOGAS, BIOG, BIO and BI as these are all valid prefixes of the word entered by the user. They would not be awarded points for BIOGA, BIOGASS or BIOGASSE as these are not valid English words. They would not be awarded points for GAS as even though it is contained in the word BIOGASSES it is not a prefix.

Example

If the user enters the word CALMIEST they will not be awarded any points as even though CALM at the start is a valid word the original word entered by the user, CALMIEST, is not.

Example

If the user enters the word AN they will be awarded points for the word AN. They would not be awarded points for A even though A at the start is a valid word as points are only awarded for words that are at least two letters long.

What you need to do

Task 1

Write a recursive subroutine called GetScoreForWordAndPrefix that, if given a valid word, returns the score of the word added to the score for any valid words that are prefixes of the word.

To get full marks for this task the GetScoreForWordAndPrefix subroutine must make use of recursion in an appropriate way to calculate the score for any prefixes that are also valid words.

If your solution uses an alternative method to recursion you will be able to get most but not all of the available marks for this question.

Task 2

Modify the UpdateAfterAllowedWord subroutine so that it calls the new GetScoreForWordAndPrefix subroutine instead of the GetScoreForWord subroutine.

Task 3

Test that the changes you have made to the program work:

• •    run the Skeleton Program
  •    if you have answered part (b), enter 15 when asked to enter the start hand size; if you have not answered part (b) yet then skip this step
  •    enter 2 at the main menu
  •    enter the word abandon
  •    enter 4 so that no tiles are replaced.

Evidence that you need to provide

(i)   Your PROGRAM SOURCE CODE for the new subroutine GetScoreForWordAndPrefix, the amended subroutine UpdateAfterAllowedWord and any other subroutines you have modified when answering this question.

(ii)  SCREEN CAPTURE(S) showing the results of the requested test.

7) Figure 1 shows the data Norbert, Phil, Judith, Mary, Caspar and Tahir entered into a binary search tree.

     Figure 2 contains pseudo-code for a recursive binary tree search algorithm.

The subroutine Exists takes two parameters – a node in the binary tree and a direction (left or right). It returns a Boolean value indicating if the node given as a parameter has a child node in the direction specified by the second parameter. For instance, Exists(Mary, left) will return a value of False as there is no node to the left of Mary in the binary tree.

node.right evaluates to the child node to the right of node, eg Judith.right is Mary.

node.left evaluates to the child node to the left of node, eg Judith.left is Caspar.

(a)     What is meant by a recursive subroutine?

___________________________________________________________________

(b)     There are two base cases for the subroutine TreeSearch. State one of the base cases.

___________________________________________________________________

(c)     Complete the unshaded cells of the table below to show the result of tracing the TreeSearch algorithm shown in Figure 2 with the function call TreeSearch(Olivia, Norbert). You may not need to use all of the rows.

8) (a)     This question refers to the subroutine InputCoordinate in the Simulation class.

The warren and fox inspection options in the Skeleton Program do not currently check if the coordinates entered by the user are on the landscape. This behaviour needs to be improved so that an error message is displayed if the user inputs coordinates for a location that is not on the landscape.

If the user runs a simulation with default settings then the landscape size is 15, so valid locations have an x coordinate between 0 and 14, inclusive.

What you need to do

Modify the InputCoordinate subroutine in the Simulation class so that, if a coordinate outside the range defined by the landscape size is input, the error message “Coordinate is outside of landscape, please try again.” is displayed and the user is forced to re-input the coordinate.

To achieve full marks for this question, the InputCoordinate subroutine should work correctly for any landscape size, not just the default size of 15.

Test

Test your changes work by running the Skeleton Program and selecting the following options:

• •    “1. Run simulation with default settings”
  •    “3. Inspect fox”

Then input these three x coordinates for the location of the fox to inspect:

• •    −1
  •    15
  •    0

Evidence that you need to provide

(i)  Your PROGRAM SOURCE CODE for the amended subroutine InputCoordinate.

(ii)  SCREEN CAPTURE(S) for the described test.

Ensure that in your SCREEN CAPTURE(S) it can be seen that the x coordinates −1 and 15 are rejected and that the x coordinate 0 is accepted, and that after the 0 is input the Skeleton Program advances to ask the user to input the y coordinate.

(b)     The simulation is to be made more realistic by increasing the probability that a rabbit will die as a result of other causes, such as disease or injury, as the rabbit ages.

The default probability of death by another cause for a rabbit is 0.05.

• •    The probability of a male rabbit dying by another cause should increase by a factor of 50% after every time period.
  •    The probability of a female rabbit dying by another cause should remain constant until the rabbit reaches the age of 2. At the age of 2, and after every time period beyond this, the probability of a female rabbit dying by another                cause should increase by 0.05.

Table 1 below summarises the probability of death by other causes for a rabbit of each gender, up to the age of 5. The probabilities will continue to increase beyond this age.

What you need to do

Create a new subroutine, CalculateNewAge, in the Rabbit class, that overrides the CalculateNewAge subroutine in the Animal class.

The new CalculateNewAge subroutine in the Rabbit class should recalculate the probability of death for a rabbit as the rabbit ages. The subroutine should also call the subroutine that it has overridden in the Animal class to ensure that the standard ageing process for a rabbit continues to be carried out as well.

Test

Check that the changes you have made work by conducting the following test:

• •    Select option “1. Run simulation with default settings” from the main menu.
  •    Then select option “2. Advance to next time period hiding detail” twice, to advance the simulation to time period 2.
  •    Then select option “4. Inspect warren” and enter the x coordinate 1 and the y coordinate 1.
  •    When asked “View individual rabbits (y/n)?” enter y.

Evidence that you need to provide

(i)  Your PROGRAM SOURCE CODE for the new subroutine CalculateNewAge from the Rabbit class.

(ii)  SCREEN CAPTURE(S) for the described test.

Your SCREEN CAPTURE(S) must clearly show the probability of death by other causes of both a male and a female rabbit of age 2. SCREEN CAPTURE(S) do not need to show the options that you have selected or the probability of death by other causes for rabbits of other ages.

(c)     The simulation is to be extended to represent the landscape that the animals live in. Most of the landscape will be land, but two rivers will run through it. The locations of the rivers are shaded in Figure 3.

Each of the individual locations, eg (12, 7), within the landscape will be assigned to be an area of either land or river.

What you need to do

Task 1

Modify the Location class so that it can store a representation of the type of terrain at the location. This representation should be as a character, with “L” representing land and “R” representing river.

Task 2

Modify the constructor subroutine of the Location class so that when a location is created, the constructor is passed the type of terrain that the location will be and this is stored appropriately.

Task 3

Modify the CreateLandscapeAndAnimals subroutine in the Simulation class so that when the landscape is created the appropriate type of terrain, as shown in Figure 3, is stored in each location. The terrain should be represented as a character, with “L” representing land and “R” representing river.

Task 4

Modify the DrawLandscape subroutine in the Simulation class so that the correct type of terrain at each location is displayed when the landscape is drawn.

Figure 4 shows one example of how the landscape could be drawn, with a letter “L” indicating that a location contains land, and a letter “R” indicating that a location contains part of a river. However, you are free to indicate the type of terrain at a location in any way that you choose, so long as this is clear to the user.

Task 5

Modify the CreateNewWarren and CreateNewFox subroutines in the Simulation class so that warrens and foxes cannot be created in locations that are part of a river.

Test

Check that the changes you have made in Tasks 1 to 4 (not Task 5) work by conducting the following test:

• •    Select option “1. Run simulation with default settings” from the main menu.

Evidence that you need to provide

(i)  Your PROGRAM SOURCE CODE for the whole of the Location class, including the constructor subroutine.

(ii)  Your PROGRAM SOURCE CODE for the amended CreateLandscapeAndAnimals subroutine from the Simulation class.

(iii)  Your PROGRAM SOURCE CODE for the amended DrawLandscape subroutine from the Simulation class.

(iv)  Your PROGRAM SOURCE CODE for the amended CreateNewWarren and CreateNewFox subroutines from the Simulation class.

(v)  SCREEN CAPTURE(S) for the described test, showing the correct type of territory in each location on the landscape.

(d)     The landscape affects the foxes’ ability to eat the rabbits. Foxes do not like to swim, so will not cross the rivers on the landscape to eat. If a river lies between a fox and a warren, the fox will not eat any rabbits in the warren, even if it is near enough for it to do so.

As the rivers only run horizontally and vertically, and extend from one side of the landscape to the other, a simple way to check if reaching a warren would require a fox to cross a river is to:

• •    Calculate the coordinates of all of the locations between the fox and the warren in a horizontal line, level with the fox.
  •    Calculate the coordinates of all of the locations between the fox and the warren in a vertical line, level with the fox.
  •    If any of the locations horizontally or vertically between the fox and the warren contain a river, then the fox will not eat any of the rabbits in the warren as the fox’s path to the warren crosses a river.

Figure 5 shows the locations that would need to be checked to see if fox F could eat any rabbits in warren W. The locations that need to be checked are shown in black and the rivers are shown in grey. As location (5, 7) contains part of a river, the fox would not eat any rabbits in this warren.

If you have not been able to fully complete part (c), you will still be able to get most of the marks for this question if you can correctly compute the coordinates of the locations that would need to be checked to see if a river was present.

To get full marks for this question, your solution must work regardless of whether a warren is above, below, to the left or to the right of a fox.

What you need to do

Task 1

Create a new subroutine CheckIfPathCrossesRiver, in the Simulation class, that takes the coordinates of two locations in the landscape and checks if there is a river between them.

Task 2

Modify the FoxesEatRabbitsInWarren subroutine in the Simulation class so that it calls the CheckIfPathCrossesRiver subroutine, and ensures that if there is a river between a fox and a warren then the fox will not eat any rabbits from the warren.

Test

Check that the changes you have made work by conducting the following test:

• •    Select option “1. Run simulation with default settings” from the main menu.
  •    Then select option “1. Advance to next time period showing detail”.

When the test is conducted, no rabbits in the warren at (1, 1) should be eaten as it is bounded by rivers on all sides.

Evidence that you need to provide

(i)  Your PROGRAM SOURCE CODE for the new subroutine CheckIfPathCrossesRiver from the Simulation class.

(ii)  Your PROGRAM SOURCE CODE for the amended subroutine FoxesEatRabbitsInWarren from the Simulation class.

(ii)  SCREEN CAPTURE(S) for the described test.

Your SCREEN CAPTURE(S) only needs to show what happens in the warren at location (1, 1) when the simulation advances to the next time period. It should contain similar information to Figure 6 below, but the exact number of rabbits killed, dying of old age and other details may differ owing to the random nature of parts of the simulation.

9) In a particular programming language, the correct syntax for four different constructs is defined by the syntax diagrams in Figure 1.

In this language an example of a valid identifier is loopCount and an example of a valid type is int.

(a)     For each row in the table below, write Yes or No in the Valid? column to identify whether or not the Example is a valid example of the listed Construct.

A student has written Backus-Naur Form (BNF) production rules that are supposed to define the same constructs as the syntax diagrams in Figure 1. Their BNF rules are shown in Figure 2.

A is any alphabetic character from “a” to “z” or “A” to “Z”.

(b)     The BNF production rules in Figure 2 contain two errors. These errors mean that the production rules do not represent the same statement types as the syntax diagrams in Figure 1.

Describe the two errors.

Error 1: ____________________________________________________________

Error 2: ____________________________________________________________

(c)     The production rule for a is recursive.

Explain why recursion has been used in this production rule.

___________________________________________________________________

10) A list data structure can be represented using a fixed-size array.

The pseudo-code algorithm in Figure 1 can be used to carry out one useful operation on a list.

The DOWNTO command causes the loop counter value to decrease by one on each iteration of the FOR loop.

The initial values of the variables for one particular execution of the algorithm are shown in the trace table opposite, labelled Table 1. Array indexing starts at 1.

(a)     Complete the trace table for the execution of the algorithm in Figure 1.

(b)     Describe the purpose of the algorithm in Figure 1.

___________________________________________________________________

(c)     A list may be implemented using a static data structure such as a fixed-length array, or using a dynamic data structure such as a linked list.

If the list were to be implemented using a dynamic data structure explain what the heap would be used for.

___________________________________________________________________

11. A computer program is being developed to play a card game on a smartphone. The game uses a standard deck of 52 playing cards, placed in a pile on top of each other.

The cards will be dealt (ie given out) to players from the top of the deck.

When a player gives up a card it is returned to the bottom of the deck.

(a)     Explain why a queue is a suitable data structure to represent the deck of cards in this game.

___________________________________________________________________

(b)     The queue representing the deck of cards will be implemented as a circular queue in a fixed-size array named DeckQueue. The array DeckQueue has indices running from 1 to 52.

The figure below shows the contents of the DeckQueue array and its associated pointers at the start of a game. The variable QueueSize indicates how many cards are currently represented in the queue.

(i)  Twelve cards are dealt from the top of the deck.

What values are now stored in the FrontPointer and RearPointer pointers and the QueueSize variable?

FrontPointer = ___________                         RearPointer = ___________

QueueSize = ___________

(ii)  Next, a player gives up three cards and these are returned to the deck.

What values are now stored in the FrontPointer and RearPointer pointers and the QueueSize variable?

FrontPointer = ___________                         RearPointer = ___________

QueueSize = ___________

(c)     Write a pseudo-code algorithm to deal a card from the deck.

Your algorithm should output the value of the card that is to be dealt and make any required modifications to the pointers and to the QueueSize variable.

It should also cope appropriately with any situation that might arise in the DeckQueue array whilst a game is being played.

___________________________________________________________________

12) A computer games programmer is writing a game. One aspect of the game involves a character who can carry various items, such as a bag of seeds, and an axe, around with her. The list of items that the character is currently carrying will be stored as a linked list of items of the String data type. The list is stored in no particular order.

The game is being developed using object-oriented programming. The LinkedList class will be used to store that list of items.

The class definition for the LinkedList class is:

(a)     Creating a class such as the LinkedList class, that can be used by other parts of a much bigger program, is a form of abstraction.

Explain why the LinkedList class is a form of abstraction.

___________________________________________________________________

(b)     Explain why the functions and procedures, such as AddItem have been declared to be Public whilst the data items such as Start have been declared as Private.

___________________________________________________________________

(c)     Write a pseudo-code algorithm for the DeleteItem operation.

You may assume that:

• • Start is a pointer to the memory location of the first item in the linked list
  • The variable DelItem, which will be passed to the DeleteItem operation as a parameter, is a String that contains the name of the item to delete, exactly as the name appears in the linked list
  • The linked list is not empty, and does contain the item to be deleted
  • For each item stored in the list, two fields are stored, which are called DataValue and Next. The DataValue is the name of the item that is stored and Next is a pointer to the memory location of the next item in the list. To access the values stored in these fields at a particular memory location, such as Current, the instructions Current. DataValue and Current. Next would be used
  • An operation called Release is provided by the operating system that will make a specified memory location that is no longer required available for re-use
  • You should make use of the data items Current and Previous, both of which are pointers, when searching the list to locate the item that is to be deleted.

___________________________________________________________________

13) A dictionary is an abstract data type that allows pairs of values to be associated with each other. For example, an English-French dictionary might associate English words with their translations into French. In such a dictionary, “Apple” would be associated with “Pomme” because “Pomme” is the French word for “Apple”.

At a lower level of abstraction, a dictionary could be implemented as a data structure using a number of different methods. Two possible implementation methods are:

• Implementation One: As an unordered list in an array.
• Implementation Two: Using hashing, with the English word being passed through a hash function to calculate the position of the correct French translation in an array.

In each implementation, a record containing the English word and the equivalent French word are stored at each index in the array that is in use.

The figure below shows how an English-French dictionary containing five words could be implemented using these two methods.

(a)     Explain why, when the French translation of an English word needs to be looked up, Implementation Two is more time efficient than Implementation One.

___________________________________________________________________

(b)     In Implementation Two, it is possible that the hash function could compute the same value for two different English words.

Explain what the effect of this would be, and how it could be dealt with.

___________________________________________________________________

(c)     In Implementation Two, both the English and French words are stored at each index in the Array. In this implementation, explain why it would not be possible to perform reliable English to French translation if only the French words were stored.

___________________________________________________________________

14) Figure 1 contains the pseudo-code for a program to output a sequence according to the ‘Fizz Buzz’ counting game.

What you need to do:

Write a program that implements the pseudo-code as shown in Figure 1.

Test the program by showing the result of entering a value of 18 when prompted by the program.

Test the program by showing the result of entering a value of -1 when prompted by the program.

Evidence that you need to provide

(a)     Your PROGRAM SOURCE CODE for the pseudo-code in Figure 1.

(b)     SCREEN CAPTURE(S) for the tests conducted when a value of 18 is entered by the user and when a value of -1 is entered by the user.

The main part of the program uses a FOR repetition structure.

(c)     Explain why a FOR repetition structure was chosen instead of a WHILE repetition structure.

___________________________________________________________________

(d)     Even though a check has been performed to make sure that the variable HowFar is greater than 1 there could be inputs that might cause the program to terminate unexpectedly (crash).

Provide an example of an input that might cause the program to terminate and describe a method that could be used to prevent this.

___________________________________________________________________

(e)     Programs written in a high level language are easier to understand and maintain than programs written in a low level language.

The use of meaningful identifier names is one way in which high level languages can be made easier to understand.

State three other features of high level languages that can make high level language programs easier to understand.

___________________________________________________________________

(f)      The finite state machine (FSM) shown in Figure 2 recognises a language with an alphabet of a and b.

Input strings of a and aabba would be accepted by this FSM.

In the table below indicate whether each input string would be accepted or not accepted by the FSM in Figure 2.

If an input string would be accepted write YES.
If an input string would not be accepted write NO.

(g)     In words, describe the language (set of strings) that would be accepted by this FSM shown in Figure 2.

___________________________________________________________________

15) State the name of an identifier for:

(a)     an array or list variable

___________________________________________________________________

(b)     a user-defined subroutine that has four parameters

___________________________________________________________________

(c)     a variable that is used to store a whole number.

___________________________________________________________________

(d)     a user-defined subroutine that returns one or more values.

___________________________________________________________________

(e)     Look at the repetition structures in the DisplayCavern subroutine.

Explain the need for a nested FOR loop and the role of the Count1 and Count2 variables.

___________________________________________________________________

(f)     Look at the ResetCavern subroutine.

Why has a named constant been used instead of the numeric value 5?

___________________________________________________________________

(g)     Look at the SetPositionOfItem subroutine.

Describe the purpose of the WHILE loop and the command within it in this subroutine.

___________________________________________________________________

(h)     Look at the MakeMonsterMove subroutine.

Describe why it is necessary to check if the monster moves into the same cell as the flask and how any problem caused by this is solved by the Skeleton Program.

___________________________________________________________________

(i)     Look at the PlayGame subroutine.

Explain why a WHILE loop has been made to complete the two moves for the monster rather than a FOR loop.

___________________________________________________________________

(j)     The subroutines in the Skeleton Program avoid the use of global variables: they use local variables and parameter passing instead.

State two reasons why subroutines should, ideally, not use global variables.

___________________________________________________________________

16) Based on the description in Statius’ journal you are sure that this must be the right place. The blue-green moss covering the rocks and the dense tree foliage combine to conceal the cave entrance; you almost walked straight past it and it was only through luck that you saw it. There isn’t any time to waste – ever since the journal was discovered, everyone has been looking for this place. The thick cobwebs across the entrance prove that you must be the first one here. You know that, if you are right, you could be the one that finds, in the cavern below the mountain, the single draft of Styxian potion contained in Statius’ flask. The journal says that there is a fearsome beast lying in wait, but the risk is worth it. Statius wrote that consuming the potion would grant the drinker invulnerability. Nothing could hurt you, cut you, graze, scratch or bruise you. Your thoughts start to drift and you imagine what you could do with such power.

“Snap out of it,” you tell yourself. Someone else could find this place and you can’t take that risk; the flask contains only enough potion for one. Quickly you shoulder your pack, then you light your torch, brush aside some cobwebs and step into the cave.

Inside, the ground is rough and you stumble several times. As you go deeper into the mountain, the cave darkens and soon the only light is coming from your torch. After you have been walking for a few minutes the cave widens and then ends abruptly. You take out your copy of the journal. You read the description of the cave again. It says that, at the end of the cave, there is a large fissure near the western part of the wall and that the cavern, where the flask is hidden, is at the bottom of the fissure. You move over to the west side of the cave. Sure enough, the fissure is there. You take off your pack and then move carefully nearer the edge. The light from the torch does not reach far enough down to reveal the bottom, but you can see that the fissure walls are too steep to get down unaided so you will need your climbing equipment. You place your torch carefully on the floor nearby and take your rope, pitons and carabiners out of your pack.

Your foot slips on some loose stones and you fall backwards into the fissure. You tumble down the hole in a shower of dust and pebbles, falling into the cavern below. You land painfully on the rocky floor.

It is dark; your torch is back in the cave and it weakly illuminates your immediate surroundings but you cannot see any farther into the cavern. You become aware of a sonorous noise around you and it takes you a few minutes to work out what it is. The monster is asleep somewhere in the cavern and is snoring loudly. The sound reverberates around you so you can’t work out in which direction the monster lies.

You can see the bottom aperture of the fissure several metres above your head and try to scramble up the wall to reach it, but the rock face is too sheer and you can’t get sufficient purchase. From what you can remember of the journal, you must be at the north-west corner of the cavern.

You make your mind up. You can’t get out of the cavern the way that you came in and the monster could wake soon. You decide to explore the cavern. Maybe you will find another way out. Maybe you will find the Styxian potion. You have no choice but to play the game of…

MONSTER!

MONSTER!

The Skeleton Program in this Preliminary Material is a program for the one-player game MONSTER!.

When playing MONSTER! the player starts in the north-west corner of a dark cavern. The cavern is represented by a 7 × 5 rectangular grid of cells. The player’s current position is indicated by an *. The player is presented with a list of five options: they can either return to the main menu (where they can save the current game if they want to) or they can move one cell in one of four possible directions. If they enter ‘N’ they will move one cell to the north, ‘S’ will move them one cell to the south, ‘E’ will move them one cell to the east and ‘W’ will move them one cell to the west. The initial position of a new game is shown in Figure 1.

Figure 2 shows a new state, resulting from the user selecting ‘E’ in the starting position.

The aim of MONSTER! is to find the hidden treasure (a flask containing a Styxian potion) that is in one of the cells of the cavern. Unfortunately, the cavern is dark and the only way that a player can find the flask is to move around until they are in the same cell as the flask. When a new game is started, the flask will be in a random position in the cavern (though it won’t be in the same cell as the player starts in). If the player moves into the cell that contains the flask, then they win the game.

The cavern is also the lair of a fearsome monster that guards the flask. At the start of a new game the monster is asleep. As the cavern is dark the player cannot see where the monster is. If the player moves into the cell that contains the monster then the monster will wake up and eat the player and the player will have lost the game.

The monster has set two traps in its cavern. The player cannot see where these traps are. If the player moves into a cell that contains a trap then the monster will wake up. When the monster is awake, it will move around the cavern until it either eats the player or the player finds the flask. The monster is twice as fast as the player and makes two moves for each player move. Each move is one cell in one of the four possible directions. When it is awake the monster’s skin glows so the player can see the position of the monster. The monster can see in the dark and so knows where the player is. The current position of the moving monster is indicated by an ‘M’ in the cavern displayed to the player.

If the monster moves into the same cell as the flask, it kicks the flask out of the way and the flask will be moved to the cell the monster came from. When the monster is awake, it does not matter if the player (or the monster) moves into a cell containing one of the traps.

Figure 3 shows part of a possible game as displayed to the player. The player moves one cell to the east, which triggers a trap that wakes the monster. The player is then shown the position of the monster in the cavern. The monster then makes its first move and the new state of the cavern is shown. It then makes its second move and the updated state of the cavern is shown. It is then the player’s turn to move.

In the Skeleton Program there is a menu containing five options: ‘Start new game’, ‘Load game’, ‘Save game’, ‘Play training game’ and ‘Quit’. If the user chooses ‘Load game’ then the contents of a user-specified file are loaded and the user will start playing MONSTER! from the game state saved in the file. If the user chooses ‘Save game’ then they will be asked to enter a name for the file and then the current state of the game will be stored in a file with the name supplied by the user. If the user chooses ‘Play training game’ then the user will start playing MONSTER! from the game state shown in Figure 4.

‘F’ denotes the position of the flask; ‘T’ denotes the position of a trap. The flask, traps and monster are not displayed to the player when the training game starts.

17) (a)     This question refers to the subroutines CheckValidMove and PlayGame.

The Skeleton Program currently does not make all the checks needed to ensure that the move entered by a player is an allowed move. It should not be possible to make a move that takes a player outside the 7×5 cavern grid.

The Skeleton Program is to be adapted so that it prevents a player from moving north if they are at the northern end of the cavern.

The subroutine CheckValidMove needs to be adapted so that it returns a value of False if a player attempts to move north when they are at the northern end of the cavern.

The subroutine PlayGame is to be adapted so that it displays an error message to the user if an illegal move is entered. The message should state “That is not a valid move, please try again.”.

Evidence that you need to provide

(i)     Your amended PROGRAM SOURCE CODE for the subroutine CheckValidMove.

(ii)     Your amended PROGRAM SOURCE CODE for the subroutine PlayGame.

(iii)     SCREEN CAPTURE(S) for a test run showing a player trying to move north when they are at the northern end of the cavern.

(b)     This question refers to the PlayGame subroutine and will extend the functionality of the game.

A scoring system is to be implemented as a game of MONSTER! is played. A variable called Score will be used to store the current score of each player.

The final score will be displayed to the user at the end of the game. At the end of the game, either the player will have found the flask or the player will have been eaten by the monster.

The final score should be displayed with the message “Your score was: Y” where Y is the value of Score.

The scoring system will be based upon the following:

• • each valid move by the player is +10 points
  • finding the flask is +50 points
  • setting off a trap is −10 points
  • being killed by the monster is −50 points.

Task 1
Adapt the Skeleton Program so that the scoring system described above is implemented, with the value of Score being updated as indicated and the required message being displayed at the end of a game.

Task 2
Test that the changes you have made work by conducting the following test:

• • play the training game
  • move south
  • move south
  • move east.

Evidence that you need to provide

(i)     Your amended PROGRAM SOURCE CODE for the subroutine PlayGame and (if relevant) the PROGRAM SOURCE CODE for any other subroutine(s) you have amended.

(ii)     SCREEN CAPTURE(S) showing the required test.

(c)     This question will extend the functionality of the game.

The player will now have access to a close-range trap detector. After making a directional move in the cavern, the trap detector will perform a sweep of the neighboring cells and report back if a trap is detected. Unfortunately, the detector can only detect the presence of a trap in a neighboring cell, and not which individual cell the trap is in.

In Figure 1 the shaded cells show the cells that would be scanned by the trap detector if the player were in the cell marked P1 or P2. The trap detector cannot scan outside the cavern.

Task 1
Create a new subroutine, TrapDetector, that, when given the current location of the player, returns True if a trap is in a neighboring cell and False if there is no trap in a neighboring cell.

When creating this subroutine you should ensure that your solution is efficiently coded.

Task 2
Modify the PlayGame subroutine so that after the player moves and the new state of the cavern is displayed:

• • the message ‘Trap detected’ is displayed if there is a trap in any neighboring cell.
  • the message ‘No trap detected’ is displayed if there are no traps in any neighboring cell.

Task 3
Test that your program works by loading the training game and showing that:

• • a trap is detected after the player’s first move, west
  • a trap is detected after the player’s second move, south
  • a trap is not detected after the player’s third move, west.

Evidence that you need to provide

(i)     Your PROGRAM SOURCE CODE for the subroutine TrapDetector.

(ii)     Your amended PROGRAM SOURCE CODE for the subroutine PlayGame.

(iii)     SCREEN CAPTURE(S) showing the required sequence of tests being carried out, with the trap detected message being displayed after each of the first two moves and the trap not detected message being displayed after the third move.

(iv)    The game of MONSTER!, as represented by the Skeleton Program, is to be extended so that the cavern generated is not rectangular. The outer cells, shaded in Figure 2, will be randomly selected to be either rock or normal space when a new game starts. A cell that contains rock cannot be entered by the monster or player.

Describe changes that could be made to the Skeleton Program to achieve this.

In your answer you should ensure that you discuss changes to the data held in the Cavern variable and how the subroutines ResetCavern and CheckValidMove will need to be altered.

You are not expected to actually make the changes.

______________________________________________________________

(v)     A request has been made that the layout of the whole cavern should be more random. It has been suggested that all of the cells should be made a random choice between rock and normal space during setup.

Identify two problems that might occur with the MONSTER! game if this suggestion was made to the program.

______________________________________________________________

18) ℝ denotes the set of real numbers, which includes the natural numbers, the rational numbers and the irrational numbers.

(a)     Give one example of a natural number.

___________________________________________________________________

(b)     Give one example of an irrational number.

___________________________________________________________________

19) (a)     What is the decimal equivalent of the hexadecimal number D6₁₆? Show your working.

___________________________________________________________________

(b)     Represent the decimal value 9.375₁₀ as an unsigned binary fixed point number, with 4 bits before and 4 bits after the binary point.

___________________________________________________________________

(c)     Represent the decimal value -67₁₀ as an 8-bit two’s complement binary integer.

___________________________________________________________________

(d)     A computer represents numbers using 8-bit two’s complement binary.

Using this representation perform the calculation:

(e)     What problem has resulted from performing the calculation using 8-bit two’s complement binary?

___________________________________________________________________

20) (a)     Complete the table below and draw the symbol for an AND gate in the box.

(b)     Using the laws of Boolean algebra, simplify the following Boolean expression.

A.B. (A + B)

___________________________________________________________________

                                                               Answer ___________________________

(c)     Using the laws of Boolean algebra, simplify the following Boolean expression.

(X + Y).(X + )

___________________________________________________________________

                                                               Answer ___________________________

21) The famous detective John Stout was called in to solve a perplexing murder mystery. He determined the following facts.

          a       Nathan, the murdered man, was killed by a blow on the head.

          b       Either Suzanne or Martin was in the dining room at the time of the murder.

          c       If Peter was in the kitchen at the time of the murder, then Ian killed Nathan using poison.

          d       If Suzanne was in the dining room at the time of the murder, then Steve killed Nathan.

          e       If Peter was not in the kitchen at the time of the murder, then Martin was not in the dining room when the murder was committed.

          f        If Martin was in the dining room at the time the murder was committed, then Paul killed Nathan.

          g       If Kevin was in the hall at the time of the murder, then Suzanne killed Nathan by a blow to the neck with a saucepan.

(a)     Who murdered Nathan?

         A        Paul

         B        Steve

         C        Suzanne

         D        Ian

         E        It is not possible for John Stout to solve the crime.

(b)     Explain how you know your answer to (a) is correct.

Use the space below for rough working.

___________________________________________________________________

___________________________________________________________________

22) A finite state machine (FSM) can be used to define a language: a string is allowed in a language if it is accepted by the FSM that represents the rules of the language.

Figure 1 shows the state transition diagram for an FSM.

An FSM can be represented as a state transition diagram or as a state transition table. The table below is an incomplete state transition table for Figure 1 .

(a)     Complete the table.

(b)     Any language that can be defined using an FSM can also be defined using a regular expression.

The FSM in Figure 1 defines the language that allows all strings containing at least, either two consecutive 1s or two consecutive 0s.

The strings 0110, 00 and 01011 are all accepted by the FSM and so are valid strings in the language.

The strings 1010 and 01 are not accepted by the FSM and so are not valid strings in the language.

Write a regular expression that is equivalent to the FSM shown in Figure 1.

___________________________________________________________________

(c)     Backus-Naur Form (BNF) can be used to define the rules of a language.

Figure 2 shows an attempt to write a set of BNF production rules to define a language of full names.

BNF can be used to define languages that are not possible to define using regular expressions. The language defined in Figure 2 could not have been defined using regular expressions.

Complete the table below by writing either a ‘Y’ for Yes or ‘N’ for No in each row.

(d)     There is an error in rule 5 in Figure 2 which means that no names are defined by the language.

Explain what is wrong with the production rule and rewrite the production rule so that the language does define some names – the names ‘BEN D JONES’, ‘JO GOLOMBEK’ and ‘ALULIM’ should all be defined.

___________________________________________________________________

23) Create a folder / directory for your new program.

One method for converting a decimal number into binary is to repeatedly divide by 2 using integer division. After each division is completed, the remainder is output and the integer result of the division is used as the input to the next iteration of the division process. The process repeats until the result of the division is 0.

Outputting the remainders in the sequence that they are calculated produces the binary digits of the equivalent binary number, but in reverse order.

For example, the decimal number 210 could be converted into binary as shown below.

The sequence 0, 1, 0, 0, 1, 0, 1, 1 which would be output by this process is the reverse of the binary equivalent of 210 which is 11010010.

What you need to do

Task 1
Write a program that will perform the conversion process described above. The program should display a suitable prompt asking the user to input a decimal number to convert and then output the bits of the binary equivalent of the decimal number in reverse order.

Task 2
Improve the program so that the bits are output in the correct order, e.g. for 210 the output would be 11010010.

Task 3
Test the program works by entering the value 210.

Save the program in your new folder / directory.

Evidence that you need to provide

(a)     Your PROGRAM SOURCE CODE after you have completed both Task 1 and Task 2.

If you complete Task 1 but do not attempt Task 2 then a maximum of 9 marks will be awarded.

(b)     SCREEN CAPTURE(S) for the test showing the output of the program when 210 is entered.

The marks for this test will be awarded whether the binary digits are output in reverse order or in the correct order.

24) Based on the description in Statius’ journal you are sure that this must be the right place. The blue-green moss covering the rocks and the dense tree foliage combine to conceal the cave entrance; you almost walked straight past it and it was only through luck that you saw it. There isn’t any time to waste – ever since the journal was discovered, everyone has been looking for this place. The thick cobwebs across the entrance prove that you must be the first one here. You know that, if you are right, you could be the one that finds, in the cavern below the mountain, the single draft of Styxian potion contained in Statius’ flask. The journal says that there is a fearsome beast lying in wait, but the risk is worth it. Statius wrote that consuming the potion would grant the drinker invulnerability. Nothing could hurt you, cut you, graze, scratch or bruise you. Your thoughts start to drift and you imagine what you could do with such power.

“Snap out of it,” you tell yourself. Someone else could find this place and you can’t take that risk; the flask contains only enough potion for one. Quickly you shoulder your pack, then you light your torch, brush aside some cobwebs and step into the cave.

Inside, the ground is rough and you stumble several times. As you go deeper into the mountain, the cave darkens and soon the only light is coming from your torch. After you have been walking for a few minutes the cave widens and then ends abruptly. You take out your copy of the journal. You read the description of the cave again. It says that, at the end of the cave, there is a large fissure near the western part of the wall and that the cavern, where the flask is hidden, is at the bottom of the fissure. You move over to the west side of the cave. Sure enough, the fissure is there. You take off your pack and then move carefully nearer the edge. The light from the torch does not reach far enough down to reveal the bottom, but you can see that the fissure walls are too steep to get down unaided so you will need your climbing equipment. You place your torch carefully on the floor nearby and take your rope, pitons and carabiners out of your pack.

Your foot slips on some loose stones and you fall backwards into the fissure. You tumble down the hole in a shower of dust and pebbles, falling into the cavern below. You land painfully on the rocky floor.

It is dark; your torch is back in the cave and it weakly illuminates your immediate surroundings but you cannot see any farther into the cavern. You become aware of a sonorous noise around you and it takes you a few minutes to work out what it is. The monster is asleep somewhere in the cavern and is snoring loudly. The sound reverberates around you so you can’t work out in which direction the monster lies.

You can see the bottom aperture of the fissure several metres above your head and try to scramble up the wall to reach it, but the rock face is too sheer and you can’t get sufficient purchase. From what you can remember of the journal, you must be at the north-west corner of the cavern.

You make your mind up. You can’t get out of the cavern the way that you came in and the monster could wake soon. You decide to explore the cavern. Maybe you will find another way out. Maybe you will find the Styxian potion. You have no choice but to play the game of…

MONSTER!

MONSTER!

The Skeleton Program in this Preliminary Material is a program for the one-player game MONSTER!.

When playing MONSTER! the player starts in the north-west corner of a dark cavern. The cavern is represented by a 7 × 5 rectangular grid of cells. The player’s current position is indicated by an *. The player is presented with a list of five options: they can either return to the main menu (where they can save the current game if they want to) or they can move one cell in one of four possible directions. If they enter ‘N’ they will move one cell to the north, ‘S’ will move them one cell to the south, ‘W’ will move them one cell to the west and ‘E’ will move them one cell to the east. The initial position of a new game is shown in Figure 1.

Figure 2 shows a new state, resulting from the user selecting ‘E’ in the starting position.

The aim of MONSTER! is to find the hidden treasure (a flask containing a Styxian potion) that is in one of the cells of the cavern. Unfortunately, the cavern is dark and the only way that a player can find the flask is to move around until they are in the same cell as the flask. When a new game is started, the flask will be in a random position in the cavern (though it won’t be in the same cell as the player starts in). If the player moves into the cell that contains the flask, then they win the game.

The cavern is also the lair of a fearsome monster that guards the flask. At the start of a new game the monster is asleep. As the cavern is dark the player cannot see where the monster is. If the player moves into the cell that contains the monster then the monster will wake up and eat the player and the player will have lost the game.

The monster has set two traps in its cavern. The player cannot see where these traps are. If the player moves into a cell that contains a trap then the monster will wake up. When the monster is awake, it will move around the cavern until it either eats the player or the player finds the flask. The monster is twice as fast as the player and makes two moves for each player move. Each move is one cell in one of the four possible directions. When it is awake the monster’s skin glows so the player can see the position of the monster. The monster can see in the dark and so knows where the player is. The current position of the moving monster is indicated by an ‘M’ in the cavern displayed to the player.

If the monster moves into the same cell as the flask, it kicks the flask out of the way and the flask will be moved to the cell the monster came from. When the monster is awake, it does not matter if the player (or the monster) moves into a cell containing one of the traps.

Figure 3 shows part of a possible game as displayed to the player. The player moves one cell to the east, which triggers a trap that wakes the monster. The player is then shown the position of the monster in the cavern. The monster then makes its first move and the new state of the cavern is shown. It then makes its second move and the updated state of the cavern is shown. It is then the player’s turn to move.

In the Skeleton Program there is a menu containing three options: ‘Start new game’, ‘Play training game’ and ‘Quit’. If the user chooses ‘Play training game’ the user will start playing MONSTER! from the game state shown in Figure 4.

In the Skeleton Program there is a menu containing three options: ‘Start new game’, ‘Play training game’ and ‘Quit’. If the user chooses ‘Play training game’ the user will start playing MONSTER! from the game state shown in Figure 4.

25) (a)     This question refers to the subroutines CheckValidMove and Play in the Game class.

The Skeleton Program currently does not make all the checks needed to ensure that the move entered by a player is an allowed move. It should not be possible to make a move that takes a player outside the 7 × 5 cavern grid.

The Skeleton Program needs to be adapted so that it prevents a player from moving west if they are at the western end of the cavern.

The subroutine CheckValidMove needs to be adapted so that it returns a value of FALSE if a player attempts to move west when they are at the western end of the cavern.

The subroutine Play needs to be adapted so that it displays an error message to the user if an illegal move is entered. The message should state “That is not a valid move, please try again”.

Evidence that you need to provide

(i)      Your amended PROGRAM SOURCE CODE for the subroutine CheckValidMove.

(ii)     Your amended PROGRAM SOURCE CODE for the subroutine Play.

(iii)    SCREEN CAPTURE(S) for a test run showing a player trying to move west when they are at the western end of the cave.

(b)     This question will extend the functionality of the game.

The game is to be altered so that there is a new type of enemy: a sleepy enemy. A sleepy enemy is exactly the same as a normal enemy, except that after making four moves it falls asleep again.

Task 1

Create a new class called SleepyEnemy that inherits from the Enemy class.

Task 2

Create a new integer attribute in the SleepyEnemy class called MovesTillSleep.

Task 3

Create a new public subroutine in the SleepyEnemy class called ChangeSleepStatus. This subroutine should override the ChangeSleepStatus subroutine from the Enemy class. The value of MovesTillSleep should be set to 4 in this subroutine.

Task 4

Create a new public subroutine in the SleepyEnemy class called MakeMove. This subroutine should override the MakeMove subroutine from the Enemy class. When called this subroutine should reduce the value of MovesTillSleep by 1 and then send the monster to sleep if MovesTillSleep has become equal to 0.

Task 5

Modify the Game class so that the Monster object is of type SleepyEnemy (instead of Enemy) .

Task 6

Check that the changes you have made work by conducting the following test:

• • play the training game
  • move east
  • move east
  • move south.

Evidence that you need to provide

(i)      Your PROGRAM SOURCE CODE for the new SleepyEnemy class.

(ii)     SCREEN CAPTURE(S) showing the requested test.

(c)     This question refers to the Game and Character classes and will extend the functionality of the game.

The game should be altered so that once per game the player can shoot an arrow instead of making a move in the cavern. The arrow travels in a straight line, in a direction of the player’s choice, from the cell the player is in to the edge of the cavern. If the arrow hits the monster then the player wins the game and a message saying that they have shot the monster should be displayed.

For this question you are only required to extend the program so that it checks if the monster is hit by the arrow when the user chooses to shoot an arrow northwards. However, the user should be able to select any of the four possible directions.

In the diagram below, the two shaded cells show the cells which, if the monster is in one of them, would result in the player winning the game, as long as the player is in the cell five to the east and three to the south and chooses to shoot an arrow northwards.

Task 1

Modify the DisplayMoveOptions subroutine in the Game class so that the option to enter A to shoot an arrow is added to the menu.

Task 2

Create a new Boolean attribute called HasArrow in the Character class.

The value of HasArrow should be set to True when a new object of class Character is instantiated.

Task 3

Create a new public subroutine called GetHasArrow in the Character class that returns the value of the HasArrow attribute to the calling routine.

Task 4

Modify the CheckValidMove subroutine in the Game class so that:

• • it is a valid move if A is selected and the player does have an arrow
  • it is not a valid move if A is selected and the player does not have an arrow.

Task 5

Create a new public subroutine called GetArrowDirection in the Character class.

This subroutine should return a character to the calling routine.

The user should be asked in which direction they would like to shoot an arrow (N, S, E or W) and the value entered by the user should be returned to the calling routine.

If an invalid direction is entered then the user should be repeatedly asked to enter a new direction, until a valid direction is entered.

The value of HasArrow should then be changed to FALSE.

Task 6

Modify the Play subroutine in the Game class so that if the move chosen by the user is not M it then checks if the move chosen is A.

If the move chosen was A, then there should be a call to the player’s GetArrowDirection subroutine. If the user chooses a direction of N then the program should check to see if the monster is in one of the squares directly north of the player’s current position. If it is then a message saying “You have shot the monster and it cannot stop you finding the flask” should be displayed. The value of FlaskFound should then be set to TRUE.

After the arrow has been shot, if the monster is still alive and awake, it is now the monster’s turn to move, the player should remain in the same cell as they were in before the arrow was shot.

There is no need to write any code that checks if the monster has been shot when the player chooses to shoot either to the east, to the west or to the south.

Task 7: test 1

Test that the changes you have made work by conducting the following test:

• • play the training game
  • shoot an arrow
  • choose a direction of N for the arrow.

Task 8: test 2

Test that the changes you have made work by conducting the following test:

• • play the training game
  • move east
  • shoot an arrow
  • choose a direction of N for the arrow
  • shoot an arrow.

Evidence that you need to provide

(i)      Your amended PROGRAM SOURCE CODE for the subroutine DisplayMoveOptions.

(ii)     Your amended PROGRAM SOURCE CODE for the subroutine CheckValidMove.

(iii)    Your amended PROGRAM SOURCE CODE for the class Character.

(iv)    Your amended PROGRAM SOURCE CODE for the subroutine Play.

(v)     SCREEN CAPTURE(S) showing the results of Test 1.

(vi)    SCREEN CAPTURE(S) showing the results of Test 2.