An algorithm has been written in pseudocode to input some numbers. It only outputs any numbers that are greater than or equal to 100. The number 999 is not output and stops the algorithm. INPUT Number WHILE Numbers <> 999 DO IF Number > 100 THEN OUTPUT Number ENDIF ENDWHILE OUTPUT Number (a) Identify the four errors in the pseudocode and suggest corrections. Error 1 (b) Write a pseudocode statement to change the corrected algorithm to output all numbers between 100 and 200 inclusive. You do not need to rewrite the whole algorithm

Question 2:

The 1D array StudentName[] contains the names of students in a class. The 2D array StudentMark[] contains the mark for each subject, for each student. The position of each student's data in the two arrays is the same, for example, the student in position 10 in StudentName[] and StudentMark[] is the same. The variable ClassSize contains the number of students in the class. The variable SubjectNo contains the number of subjects studied. All students study the same number of subjects. The arrays and variables have already been set up and the data stored. Students are awarded a grade based on their average mark. Average mark Grade awarded greater than or equal to 70 distinction greater than or equal to 55 and less than 70 merit greater than or equal to 40 and less than 55 p

ass less than 40 fail Write a program that meets the following requirements: calculates the combined total mark for each student for all their subjects calculates the average mark for each student for all their subjects, rounded to the nearest whole number outputs for each student: - name - combined total mark - average mark - grade awarded calculates, stores and outputs the number of distinctions, merits, passes and fails for the whole class. You must use pseudocode or program code and add comments to explain how your code works. You do not need to initialise the data in the array.

Question 3:

A function, FormOut(), takes an integer parameter in the range 0 to 999999 and returns a formatted string depending on two other parameter values. Formatting may incorporate the use of: A prefix string to be added before the integer value (e.g. '$' or "Total: ") A comma as a thousand-separator (e.g. "1,000") The function will be called as follows: MyString FormOut(Number, Prefix, AddComma) Parameter Data type Description Number INTEGER The positive integer value to be formatted. Prefix STRING A string that will appear in front of the numeric value. Set to an empty string if no prefix is required. AddComma BOOLEAN TRUE if a comma is required in the formatted string. FALSE if a comma is not required in the formatted string. (a) Fill in the tables to show two tests that could be carried out to test different aspects of the function. Give the expected result for each test. TEST 1 Parameter Value Expected return string: Number Prefix ............................................................... AddComma TEST 2 Parameter Value Expected return string: Number Prefix ............................................................... AddComma

(b) Write pseudocode for the function FormOut(). Refer to the Appendix on pages 18-19 for the list of built-in functions and operators.

Question 4:

A message may contain several hashtags. A hashtag is a string consisting of a hash character '#', followed by one or more alphanumeric characters. A hashtag may be terminated by a space character, the start of the next hashtag, any other non-alphanumeric character, or by the end of the message. For example, the following message contains three hashtags: "#Error27 is the result of #PoorPlanning by the #Designer" The hashtags in the message are "#Error27", "#PoorPlanning" and "#Designer". A program is being developed to process a message and extract each hashtag. A global 1D array of strings, TagString, will store each hashtag in a single element. Unused array elements will contain an empty string. The array will contain 10000 elements. A developer has started to define the modules as follows: Module Description GetStart() Called with two parameters: a message string an integer giving the number of the required hashtag. For example, GetStart(Message, 3) would search for the third hashtag in the string Message Returns an integer value representing the start position of the hashtag in the message string, or value 1 if that hashtag does not exist GetTag() Called with two parameters: a message string an integer giving the hashtag start position within the message Returns the hashtag or an empty string if the character in the message at the hashtag start position is not '#' GetIndex() Called with a hashtag as a parameter Returns the index position of the hashtag in array TagString Returns the value 1 if the hashtag is not present in the array 13

a) Write pseudocode for the module GetIndex().

b) Create pseudocode for the module GetStart(). The module description is repeated here for reference. Module Description GetStart() Called with two parameters: a message string an integer giving the number of the required hashtag. For example, GetStart(Message, 3) would search for the third hashtag in the string Message Returns an integer value representing the start position of the hashtag in the message string, or value 1 if that hashtag does not exist

(c) Form a program code for the module GetTag(). The module description is repeated here for reference. Module Description GetTag() Called with two parameters: a message string an integer giving the hashtag start position within the message Returns the hashtag or an empty string if the character in the message at the hashtag start position is not '#' Visual Basic and Pascal: You should include the declaration statements for variables. Python: You should show a comment statement for each variable used with its data type. Programming language ............................................................................................................ Program code

Question 5:

(a) Algorithms usually consist of three different stages. One stage is INPUT. Name the other stages. 1

(b) An algorithm may be documented using different methods. These include structured English, a program flowchart, and pseudocode. State what a program designer represents using one or more of these methods.

(c) Programming languages support different data types. Complete the table by giving four different data types together with an example data value for each. Data type Example data value

Question 6:

(a) The following pseudocode is an attempt to define an algorithm that takes two numbers as input and outputs the larger of the two numbers. DECLARE A, B : INTEGER INPUT A INPUT B IF A > B THEN OUTPUT A ELSE OUTPUT B ENDIF The algorithm needs to be amended to include the following changes: 1. Input three values, ensuring that each value input is unique. 2. Output the average. 3. Output the largest value. Write the pseudocode for the amended algorithm.

Question 7:

A car has the ability to detect a skid by monitoring the rate of rotation (the rotational speed) of each wheel. If the rate of rotation of any wheel is not within 10% of the average of all four wheels, the car skids. A function, CheckSkid(), is being developed. The function will: simulate real-time data acquisition, by prompting for the input of four integer values in the range 0 to 1000 inclusive, representing the rate of rotation of each wheel calculate the average value check whether any individual value is more than 10% greater than the average or more than 10% less than the average return TRUE if any individual value is more than 10% greater than the average or more than 10% less than the average and FALSE otherwise output a suitable warning message. (a) Write program code for the function CheckSkid(). Visual Basic and Pascal: You should include the declaration statements for variables. Python: You should show a comment statement for each variable used with its data type. Programming language ............................................................................................................ Program code

Question 8:

(a) The following structured English describes an algorithm used to count the number of odd and even digits in an input sequence. 1. Initialise variables OddCount and EvenCount to zero. 2. Prompt and input an integer. 3. If the integer is not in the range 0 to 9 then go to step 7. 4. If the integer is an even number then add 1 to EvenCount. 5. Otherwise add 1 to OddCount. 6. Repeat from step 2. 7. Output "Same" if there are the same number of odd and even integers. 8. Output "Odd" if there are more odd than even integers. 9. Output "Even" if there are more even than odd integers. Draw a flowchart on the following page to represent the algorithm

(b) The following pseudocode is an attempt to check whether two equal-length strings consist of identical characters. Refer to the Appendix on pages 18-19 for the list of built-in functions and operators. FUNCTION Compare(String1, String2 : STRING) RETURNS BOOLEAN DECLARE x, y, Len1, Len2 : INTEGER DECLARE RetFlag : BOOLEAN DECLARE NextChar : CHAR DECLARE New : STRING Len1 LENGTH(String1) RetFlag TRUE FOR x 1 TO Len1 // for each char in String1 Len2 LENGTH(String2) NextChar MID(String1, x, 1) // get NextChar from String1 New "" FOR y 1 TO Len2 // for each char in String2 IF NextChar <> MID(String2, y, 1) // no match THEN New New & MID(String2, y, 1) // save this char from String2 ENDIF ENDFOR String2 New // replace String2 with New ENDFOR

IF LENGTH(String2) <> 0 // anything left in String2 ? THEN RetFlag FALSE ENDIF RETURN RetFlag ENDFUNCTION

Question 9:

A hashtag is used on a social media network. A hashtag is a string consisting of a hash character '#' followed by one or more alphanumeric characters. A program is being developed to monitor the use of hashtags. The program will include two global arrays each containing 10 000 elements: A 1D array, TagString, of type STRING stores each hashtag in a single element. All unused array elements contain an empty string (""). A 1D array, TagCount, of type INTEGER stores a count of the number of times each hashtag is used. The count value at a given index relates to the element stored at the corresponding index in the TagString array. The contents of the two arrays will be stored in a text file Backup.txt. The format of each line of the file is: <','> For example: "#ComputerScienceClass,978" A developer has started to define the modules as follows: Module Description InitArrays() Initialise the arrays SaveArrays() The contents of the two arrays are stored in the text file Backup.txt Existing file contents will be overwritten Each hashtag and count are stored in one line of the file, as in the example above Unused TagString elements are not added to the file Returns the total number of unused TagString elements LoadArrays() Values from the text file Backup.txt are stored in the two arrays The number of elements stored is returned (a) Write pseudocode for the module InitArrays().

Algorithms (a) Explain the greedy strategy in algorithm design. To what problems does it apply? [3 marks] (b) If a problem can be solved with both dynamic programming and a greedy algorithm, what are the advantages of using one or the other? [2 marks] (c) An imaginary post office machine must issue decorative stamps adding up to a given amount of p pence. Its goal is to minimize the number of postage stamps issued, and the machine always has as many stamps as needed. (i) Let the set of available denominations for the stamps be D = {1p, 5p, 25p, 50p, 1, 2}. Can this problem be solved using bottom-up dynamic programming? If so, clearly describe your algorithm and determine its complexity. If not, prove that it cannot be done. [5 marks] (ii) Let c1 < c2 < < cn be n stamp denominations. Prove that if each ci (a positive integer) is a multiple of ci1 for every i = 2, . . . , n then the greedy strategy applied to the set D = {c1, c2, , cn} finds the optimal solution for any amount p that is a multiple of c1. (iii) Provide a set of denominations for stamps D and an amount of pence p for which the greedy strategy fails to give an optimal solution, p being a multiple of the smallest denomination in D. Show what solution the greedy strategy would find and what the optimal solution is. [3 djacency-list representation and the adjacency-matrix representation. Find a problem that can be solved more efficiently in the adjacency-list representation than in the adjacency-matrix representation, and another problem that can be solved more efficiently in the adjacency-matrix representation than in the adjacency-list representation. [4 marks] (b) Prove or disprove (by giving a counter-example) the following claim: If a directed graph G contains a path from a vertex u to a vertex v, then any depth-first search must result in v.d u.f, where .d is the discovery time and .f the finishing time. [4 marks] (c) We are given an undirected, connected graph G = (V, E) with edge-weights w : E R + and a minimum spanning tree T of G. How would you update your minimum spanning tree T in each of the following three cases? Specify the runtime of your algorithm and give a proof that the returned tree is indeed a minimum spanning tree. (i) We increase the weight of an edge e which is not in T. [3 marks] (ii) We decrease the weight of an edge e which is in T. [3 marks] (iii) We add a new edge e with weight w(e) to G. The weight w(e) is arbitrary, but for simplicity you may assume that after adding the edge e no two edges in G have the same weight.