Designing, creating and refining algorithms

A student is writing a program in a high-level programming language.

The student writes the program using an Integrated Development Environment (IDE).

Complete the table by identifying and describing three features of an IDE that the student can use to debug their program.

The program the student is developing includes both global and local variables.

Explain the difference between a global variable and a local variable.

Describe one drawback of using global variables in a program.

Describe one drawback of using local variables in a program.

A variable can be passed as a parameter into a function by value or by reference.

Describe what parameter passing by value means.

An algorithm is needed to count how many times each of the numbers from 1 to 9 appear in an array called myArray. Another array called checked is used to store each number found in myArray and the number of times it appears. For example, the contents of myArray are:

Based on these contents in myArray, the contents in checked would be:

–1 indicates an unused space in the array as the numbers 1, 4, 8 and 9 have not been found.

The student has written the following pseudocode for this program.

The pseudocode contains several errors.

Identify the line number of any four errors and write the corrected line for each error.

Error 1

Error 2

Error 3

Error 4

Sundip writes an algorithm to carry out addition and subtraction. The algorithm will use an initially empty stack with the identifier numbers and will take input from the user.

The action the algorithm takes depends on the value input by the user. These actions are listed in

Complete the pseudocode here to implement Sundip’s algorithm.

Complete the following table to give the output from this algorithm when the following set of inputs are entered by the user. The letters will complete an action stated in Fig. 2

If the user enters 4 2 S A E, the algorithm will not work correctly.

Explain what problem this input data will cause and why the problem occurs.

A stack is one data structure that is available for Sundip to use. She could also use a queue, list, linked list, array or tuple.

Describe one difference between a stack and a queue.

Describe one difference between an array and a list.

State how a tuple is different to a list.

Describe how the second item in a linked list would be accessed using pointer values.

A doCheck() function takes an integer value as a parameter, carries out a series of calculations and returns an integer value.

The function is shown here.

State the value returned from the function when doCheck(3178) is called.

Write an algorithm that will:

• allow the user to enter an integer value

• pass the value entered into the doCheck() function as a parameter

• store both the value input and the value returned from the function in a text file with name "storedvalues.txt"

You should write your algorithm using either pseudocode or program code.

A programmer creates this function shown in Fig. 5 using a high-level language.

State the value output by the line print(mystery(10,20))

State the value output by the line print(mystery(0,70))

State the value output by the line print(mystery(45,55))

Before the code in Fig. 5 can be executed, a translator must be used.

State the purpose of a translator.

Explain two differences between a compiler and an interpreter.

For each statement shown in Table 5, tick (✓) one box in each row to indicate which stage of compilation each action takes place at.

Describe the purpose of code optimisation.

The programmer creates another function to count and return how many capital letters are in a string that is passed into the function as a parameter.

The asc() function takes in a character and returns its ASCII value. For example asc("A") returns 65. Capital letters have ASCII values between 65 and 90 inclusive.

Give one similarity between ASCII and Unicode.

Give two differences between ASCII and Unicode.

* The programmer has been asked by a client to create a complex computer program. Compare the spiral model and waterfall lifecycle methodologies for this task.

You should include the following in your answer:

• how both methodologies could be used to develop a complex computer program

• the benefits of each methodology for this task

• the drawbacks of each methodology for this task.

A program written using the Little Man Computer instruction set is shown in Fig. 1.

Various registers are used when the program above is executed.

State what is meant by the term ‘register’.

Explain how the accumulator is used when the line BRP pos is executed.

Complete the table below to show the output(s) from this program given the inputs.

Write an algorithm using pseudocode that has the same functionality as the code in Fig. 1

* In assembly language, different modes of addressing memory can be used.

Discuss the different modes used. You should include:

• How the operand value is determined

• What an operand of 27 would refer to in that mode

• The reasons for requiring multiple modes of addressing

Juan is creating a structure diagram to design the game.

A structure diagram is one method of showing the decomposition of a problem.

Explain why decomposing a problem can help a developer design a solution.

Identify one input, one process and one output required for the game.

Juan uses the structure diagram to create a modular program with a number of subroutines. The program will use two integer 2-dimensional arrays to store the puzzles:

• puzzle(5,5) stores the solution

• answerGrid(5,5) stores the user’s current grid.

A 0 represents a white box and a 1 represents a black box.

Explain the purpose of line 03 in the function countRow.

Describe the purpose of branching and iteration in the function countRow.

The function checkWon() takes answerGrid and puzzle as parameters and compares each element in the grids. If they are identical, it returns true, otherwise returns false.

There are three logic errors in the function checkWon.

State the line number of each error and give the corrected line.

Error 1 line number........

Error 1 correction........

Error 2 line number........

Error 2 correction........

Error 3 line number........

Error 3 correction........

* Juan passed the two arrays as parameters, but he did consider making them globally accessible.

Compare the use of global and local variables and data structures in this program. Include the use of parameters and program efficiency in your answer.

Juan wants to create a program that will generate new Nonograms with different grid sizes. For example a Nonogram with a 10 × 10 grid or a 5 × 20 grid.

Describe how the program could be written to automatically generate a new Nonogram.

Two people play a counting game. The rules of the game are as follows:

• The first player starts at 1

• Each player may choose one, two or three numbers on their turn and the numbers must be in ascending order

• Players take it in turns to choose

• The player who chooses “15” loses the game.

For example, if the first player chooses three numbers (1, 2, 3) then the second player could choose one number (4), two numbers (4, 5) or three numbers (4, 5, 6). The first player then takes another go.

Write an algorithm using pseudocode that allows two players to play this game. The algorithm should:

• Alternate between player 1 and player 2

• Ask the player how many numbers they would like to choose, ensuring that this is between 1 and 3

• Display the numbers that the player has chosen

• Display a suitable message to say which player has won once the number 15 has been displayed.

A survey is carried out to look at the types of vehicle that travel down a stretch of motorway.

For each vehicle that passes by, a letter is entered into the system.

For a car ‘C’ is entered.

For a motorbike ‘M’ is entered.

For a lorry ‘L’ is entered.

For any other vehicle ‘O’ is entered.

It is decided to compress the data that has been generated.

State what is meant by the term ‘compression’.

It is decided that Run Length Encoding will be used.

The following sequence has been compressed using Run Length Encoding.

3C3M4C

Show the result of decompressing the sequence.

Show the result of using Run Length Encoding to compress the sequence:

CCCCOLLLCCCCCMOCCCCC

The survey takers want to find out the longest continuous sequence of cars in any given chunk of data. For example, in the data

CCMCCCCLLCCC

the longest sequence would be 4.

Write the function longest which takes in a string of characters as an argument and returns an integer representing the longest continuous sequence of Cs.

A programmer is writing software for a firewall. She is writing code so that it keeps a track of websites that users are permitted to visit. The software stores the websites’ addresses along with details about who can view them and when.

The following data is also stored about each website:

• Access level needed (1-4) • If it is available all the time (true) or just lunch times and out of work hours (false).

So a website which is available to users of access level 2 and above, all the time, would have the details [2, true] stored.

A website accessible to users of access level 3 and above, only outside of work hours, would have the details [3, false] stored.

State the name of a data structure that could be used to store a single site’s details.

A flaw with the current hash function is it tends to generate lots of collisions (addresses that compute to the same hash). Below is a diagram of part of the hash table. The address www.rnd.com with details [2, true] is being added to the hash table.

Explain how a hash table can be used to handle collisions, referring to the example below.

The hash function is changed so there are no longer high numbers of collisions.

During busy periods the firewall is expected to check several addresses a second. It is anticipated that roughly 10 new addresses will be added to a whitelist (list of acceptable addresses) each day.

There is a debate as to whether a hash table (with the new hash function) is the best approach, or if the whitelist would be better stored in a linked list.

*Discuss whether a hash table or linked list is better to store acceptable websites. You should compare how each structure can be searched and has data added and come to a

recommendation as to which is better for the whitelist.

State the output of the program when the number 30 is entered.

State the most suitable data type of the variable count

State the data type of the result of the expression (count*num)<=100

State the data type of the result of the expression

str(num) + " goes into 100 " + str(count) + " times."

Write extra code so the program also displays the remainder.

The program is compiled. The first stage is Lexical Analysis.

Referring to examples in the code in Fig. 8.1, explain what happens in Lexical Analysis.

State the name of the stage of compilation that directly follows Lexical Analysis.

The temperatures of an ocean are input into a computer system. They are recorded, and will be accessed, in the order in which they arrive. The data for one week is shown:

5, 5.5, 5, 6, 7, 6.5, 6

The data is to be stored in a data structure. The programmer stores the data in a queue.

Explain why a queue is used instead of a stack.

The data is processed. After processing, the value for the first day is stored as 0. The value for each following day is stored as an increase, or decrease, from the first day.

For example: if the first day was 7, the second was 6 and the third was 9, after processing it would be stored as 0, –1, 2.

The queue uses dequeue() to return the first element of the queue.

dequeue() is a function.

Explain why dequeue() is a function, not a procedure.

The contents of processedData are shown.

The data needs to be sorted into ascending order.

Explain how a bubble sort algorithm sorts data. Use the current contents of processedData in your explanation.

A student writes a program to apply a symmetric encryption algorithm to work on messages of up to 25 ASCII characters.

Describe what is meant by the term ‘ASCII’.

The encryption algorithm works in the following way. A message of up to 25 characters (spaces and punctuation are not included) is placed in a 5×5 array. Any leftover spaces are filled with random letters. The message I LOVE COMPUTER SCIENCE becomes:

The key is a sequence of ten numbers. In this example we will use 1 2 3 4 5 1 2 3 4 5. The first 5 numbers state how many spaces the rows 0 to 4 must be rotated right.

A key with the first 5 digits 1 2 3 4 5 would result in

The next 5 digits state how many spaces down the columns 0 to 4 should be rotated.

Applying the last 5 digits 1 2 3 4 5 to the grid above would give

Part of the pseudocode for the algorithm is written below.

Show the result of running the algorithm on the grid and key below.

KEY: 3 3 3 3 3 1 1 1 1 1

Grid after only the rows are shifted:

Grid after columns have also been shifted:

Write the procedure shiftRow.

*Modern encryption is much stronger than the method described in the first part of this question. Discuss the impact of modern encryption on society. You should refer to:

• The importance of asymmetric encryption and how it differs from symmetric encryption.

• Different circumstances in which symmetric and asymmetric encryption may be used.

A web forum stores all its content in a database.

The forum stores details of its users in the table called Users. An extract of Users is shown

Describe what is meant by the term ‘primary key’, giving an example from the table above.

The user’s password is passed to a function that generates a hash and the result is stored in passwordHash.

Describe what is meant by the term ‘hash’.

Describe one advantage to storing the password as a hash.

Write an SQL statement to get just the passwordHash and locked values of the user Apollo.

Sometimes users can have their accounts locked if they behave inappropriately. When this is the case the locked field is set to 1 rather than 0.

Write an SQL statement that locks the account of the user Hades

The function checkAccess takes in the password the user has entered (givenPassword along with the password hash (passwordHash) and locked value (locked).

passwordHash and locked have already been extracted from the database before being passed to the function. It should return the value true if a user should be allowed access to a system and false if they aren’t.

Your function should make use of the pre-written function hash() which takes in a string and returns the hash of that string.

e.g.

hash("Hello") returns f7ff9e8b7bb2e09b70935a5d785e0cc5d9d0abf0

Complete the function checkAccess.

function checkAccess(givenPassword, passwordHash, locked)

endfunction

A software development team is writing a word game.

The team is using Rapid Application Development.

Players are given 10 random letters and asked to find the largest word they can make from those letters. Each letter can only be used once. The length of the word determines the number of points awarded. e.g. a word with 6 letters would mean 6 points are awarded.

The function validateAnswer takes in the randomLetters as an array of letters and the player’s as a string. It then checks if the word the player has entered only contains letters from the 10 random letters with each letter being used only once. (At this stage the program doesn’t check if the answer provided is an actual word.) It then returns a score, out of 10, for a valid word or 0 for an invalid word.

Example

If the random letters are

OPXCMURETN

The word COMPUTER returns 8

Whereas

The word POST returns 0 (there is no S in the random letters).

And

The word RETURN returns 0 (there is only one R in the random letters).

Complete the function validateAnswer

function validateAnswer(answer, randomLetters[])

endFunction

Code is to be added to check if the word is an actual English word. All English words are stored in a binary search tree.

Give one advantage of storing the words in a binary search tree over an array.

The software team use a prebuilt library to create the Graphical User Interface.

Give two advantages to the software team of using a library.

* The program is compiled. Explain the process of compilation including how code from the library becomes part of the finished program, justifying why each stage is necessary.