AQA A Level Computer Science Paper 1: On-screen exam June 2018 question paper 7517/1

labelled. One is labelled "onions", one is labelled "carrots" and the other is labelled "onions and carrots". You know that all three have been labelled incorrectly.

Describe how you can work out what each box actually contains by taking just one vegetable out of one box, without looking inside any of the boxes.

How would the infix expression 5 - 3 be represented in Reverse Polish notation?

How would the infix expression 3 + 4 * 2 - 1 be represented in Reverse Polish notation?

Use the space below for rough working then copy your answer into your Electronic Answer Document.

Explain why Reverse Polish notation is sometimes used instead of infix notation.

To evaluate an expression in Reverse Polish notation, you start from the left hand side of the expression and look at each item until you find an operator (eg + or -).

This operator is then applied to the two values immediately preceding it in the expression. The result obtained from this process replaces the operator and the two values used to calculate it. This process continues until there is only one value in the expression, which is the final result of the evaluation.

For example 5 2 7 + + would change to 5 9 + after the first replacement.

Explain how a stack could be used in the process of evaluating an expression in Reverse Polish notation.

Stacks are also used to store a stack frame each time a subroutine call is made. State two components of a stack frame.

possible to travel directly between those two locations. When there is an edge between two nodes in the graph the edge is labelled with the time (in minutes) it takes to travel between the two locations represented by the nodes.

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.

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

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

What does the output from the algorithm in Figure 2 represent?

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

Describe the Halting problem.

Why is it not possible to create a Turing machine that solves the Halting problem?

To define a Turing machine the finite alphabet of symbols that it can use needs to be specified and there needs to be a tape.

State two other components of a Turing machine.

Explain what a Universal Turing Machine is.

Why can a Universal Turing Machine be considered to be more powerful than any computer that you can purchase?

You are advised to spend no more than 20 minutes on this section.

Enter your answers to Section B in your Electronic Answer Document. You must save this document at regular intervals.

The question in this section asks you to write program code starting from a new program/project/file.

You are advised to save your program at regular intervals.

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 Include the following in your Electronic Answer Document.

Your PROGRAM SOURCE CODE.

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.

You are advised to spend no more than 15 minutes on this section.

Type your answers to Section C into your Electronic Answer Document. You must save this document at regular intervals.

These questions refer to the Preliminary Material and the Skeleton Program, but do not require any additional programming.

Refer either to the Preliminary Material issued with this question paper or your electronic copy.

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.

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

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.

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.

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.

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.

You are advised to spend no more than 70 minutes on this section.

Type your answers to Section D in your Electronic Answer Document. You must save this document at regular intervals.

These questions require you to load the Skeleton Program and to make programming changes to it.

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.

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.

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 4 shows examples of how the new version of CheckWordIsValid should work if AllowedWords contained the items shown in Figure 3.

1) If the user enters the word BIG then a value of True should be returned and the words GET, BUG, BIG should be displayed, in that order. 2) If the user enters the word JET then a value of True should be returned and the words GET, NOT, JET should be displayed, in that order. 3) If the user enters the word ZOO then a value of False should be returned and the words GET, NOT, SIP, WON should be displayed, in that order.

Test that the changes you have made work:

run the Skeleton Program

if you have answered Question 8, enter 15 when asked to enter the start hand size; if you have not answered Question 8 yet then skip this step

enter 2 at the main menu

enter the word jars.

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 Question 8, enter 15 when asked to enter the start hand size; if you have not answered Question 8 yet then skip this step

• enter 2 at the main menu

• enter 1 to display the letter values.

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 Question 8, enter 15 when asked to enter the start hand size; if you have not answered Question 8 yet then skip this step

enter 2 at the main menu

enter the word abandon

enter 4 so that no tiles are replaced.