Algorithm Design and Standard Methods: Computer Science 0478 (Cambridge O Level / IGCSE)

A gym stores the number of visits made by each of its members during the last month in a one-dimensional (1D) array called Visits, which has 8 elements. The pseudocode algorithm below is run on this array.

DECLARE Visits : ARRAY[1:8] OF INTEGER
DECLARE Index : INTEGER
DECLARE Reward : INTEGER
Reward ← 0
FOR Index ← 1 TO 8
    IF Visits[Index] > 10 THEN
        Reward ← Reward + 1
    ENDIF
NEXT Index
OUTPUT Reward

What is the purpose of this algorithm?

An allotment society is having a new system developed so that members can reserve one of the society's garden plots for the coming season and order bags of compost to be delivered to that plot.

(a) State what is meant by decomposition, as used in the analysis stage of the program development life cycle. [2]

(b) The systems analyst decomposes the plot-reservation problem into inputs, processes, outputs and storage. Identify one example of each of these four for this system. [4]

(c) Explain one benefit, other than making the problem easier to understand, of decomposing a problem in this way before an algorithm is designed. [2]

A community makerspace keeps a one-dimensional (1D) array called ToolID, with 10 elements, listing the ID numbers of tools that are currently checked out. Before letting a member borrow tool number 7749, the system must search ToolID to see if it is already checked out.

The array currently holds these values:

(a) Write an algorithm, in pseudocode, that uses a linear search to search ToolID for the value stored in SearchValue. If the value is found, your algorithm should output the index position at which it was found. If it is not found after every element has been checked, your algorithm should output the message "Not checked out". [4]

(b) SearchValue is set to 7749. Trace your algorithm, showing the value of Index and the value of ToolID[Index] compared at each step, until the algorithm ends. [3]

(c) State the number of comparisons your algorithm makes before it ends, and explain why the number of comparisons a linear search needs to make can vary considerably each time it searches this array. [2]

A go-kart track records the finishing times, in seconds, of the 5 karts in one heat, stored in a one-dimensional (1D) array called RaceTimes, in the order the karts crossed the start line:

RaceTimes: 52.3, 48.7, 55.1, 50.4, 47.6

The track marshal wants RaceTimes sorted into ascending order (fastest time first) so that trophies can be awarded correctly.

(a) Write an algorithm, in pseudocode, that uses a bubble sort to sort RaceTimes into ascending order. Your algorithm must use a Boolean variable, Swapped, so that it stops repeating passes as soon as a complete pass makes no swaps. [5]

(b) Trace your algorithm for the data given, showing the contents of RaceTimes after each pass, until the array is fully sorted into ascending order. [4]

(c) Explain how including the variable Swapped in your algorithm in (a) makes it more efficient than a bubble sort that always repeats a fixed number of passes. [2]

A fitness app records the number of steps a user walks on each of the 30 days of a month, stored in a one-dimensional (1D) array called Steps. The pseudocode algorithm below processes this data.

DECLARE Steps : ARRAY[1:30] OF INTEGER
DECLARE Day : INTEGER
DECLARE Total : INTEGER
Total ← 0
FOR Day ← 1 TO 30
    Total ← Total + Steps[Day]
NEXT Day
OUTPUT Total / 30

What does this algorithm calculate?

A school library is having a new system designed to manage book loans. During the analysis stage, the systems analyst uses both decomposition and abstraction before any algorithm is designed.

(a) State what is meant by abstraction, as used in the analysis stage of the program development life cycle. [2]

(b) The library's loan record for one book currently stores: the book's ISBN, its title, its author, the shelf it is kept on, the borrower's name, the borrower's library card number, the borrower's home address, and the date the book is due back. The analyst is designing the part of the system that checks whether a book is overdue. Identify two of these stored details that abstraction would remove from this part of the system, and explain why each is not needed for it. [3]

A parcel delivery company charges a surcharge on any parcel that weighs more than 20 kg. A flowchart algorithm reads the weight of each parcel in turn, in kilograms, and counts how many parcels need the surcharge. The weights are entered one at a time; entering -1 signals that there are no more parcels to process.

The flowchart is shown below as a numbered sequence of shapes:

Step 1 [Terminator]      START
Step 2 [Process]         Count ← 0
Step 3 [Input/Output]    INPUT Weight
Step 4 [Decision]        Weight = -1 ?
                            Yes → go to Step 8
                            No  → go to Step 5
Step 5 [Decision]        Weight > 20 ?
                            Yes → go to Step 6
                            No  → go to Step 7
Step 6 [Process]         Count ← Count + 1
Step 7 [Process]         go to Step 3
Step 8 [Input/Output]    OUTPUT Count
Step 9 [Terminator]      STOP

(a) Identify the flowchart shape used for Step 4 and Step 5, and state what type of instruction this shape represents. [2]

(b) State what this algorithm calculates, and explain how the algorithm knows when to stop reading parcel weights. [2]

(c) The company enters these parcel weights, in this order: 15, 22, 9, 30, -1. Trace the algorithm, showing the value of Weight and Count after each value is entered. [4]

(d) Rewrite this flowchart as pseudocode, using a REPEAT ... UNTIL loop. [3]

A weather station records the temperature, in degrees Celsius, at 6 equally spaced times during one day, stored in a one-dimensional (1D) array called Temp with 6 elements:

(a) Write an algorithm, in pseudocode, that finds the maximum temperature in Temp and the index at which it occurs, storing the results in MaxTemp and MaxIndex. [5]

(b) Trace your algorithm for the data given, showing the values of Index, Temp[Index], MaxTemp and MaxIndex at each step of the loop. [4]

(c) State the number of comparisons your algorithm makes, and explain why this standard method always makes the same number of comparisons no matter where in the array the maximum value is actually located. [2]

An online store keeps the prices, in dollars, of 5 items in a one-dimensional (1D) array called Prices. The pseudocode algorithm below is run on this array.

DECLARE Prices : ARRAY[1:5] OF REAL
DECLARE Index : INTEGER
DECLARE Cheapest : REAL
Cheapest ← Prices[1]
FOR Index ← 2 TO 5
    IF Prices[Index] < Cheapest THEN
        Cheapest ← Prices[Index]
    ENDIF
NEXT Index
OUTPUT Cheapest

What does this algorithm calculate?

A developer is designing a new quiz app called QuizMaster. The app must let a user register, then run a quiz, in which the app asks a series of questions, marks each typed answer, and keeps a running score, and finally show a leaderboard of the top scores from all users.

(a) Decompose QuizMaster into a structure diagram. Your diagram must show a single top-level module for the whole app, at least three second-level modules, and at least two third-level modules nested underneath one of the second-level modules. Represent your structure diagram as an indented hierarchy, clearly showing which module each one belongs under. [5]

(b) State one difference between what a structure diagram shows and what a flowchart shows. [2]

(c) Explain one advantage, other than making the problem easier to understand, of decomposing QuizMaster into the modules shown in your structure diagram before any coding begins. [2]