AS & A Level Computer Science (9618)
Algorithm design and problem-solving Banker
31 questions · about 10% of the marks we indexed · examined in 9 of 9 sessions.
Practice questions
Original questions written by HomiLabs in the style of the exam, with answers and mark schemes. They are not
Cambridge past paper questions and have not been reviewed by Cambridge. Try each one before opening the answer.
Q1Writing pseudocode algorithms · Core · Paper 2 style · 5 marksA language-learning app for children in Malaysia counts vowels in words.
- (a) Write pseudocode for the function CountVowels(Word : STRING) RETURNS INTEGER. The function returns the number of vowels (a, e, i, o, u) in Word. Vowels may be upper or lower case. [5]
Show answer
- (a) FUNCTION CountVowels(Word : STRING) RETURNS INTEGER DECLARE Count, Index : INTEGER DECLARE Ch : CHAR Count ← 0 FOR Index ← 1 TO LENGTH(Word) Ch ← LCASE(MID(Word, Index, 1)) IF Ch = 'a' OR Ch = 'e' OR Ch = 'i' OR Ch = 'o' OR Ch = 'u' THEN Count ← Count + 1 ENDIF NEXT Index RETURN CountENDFUNCTION
1 mark each: function header and ENDFUNCTION with Count initialised to 0; loop from 1 to LENGTH(Word); extract each character with MID; correct test for all five vowels in both cases (e.g. using LCASE); increment count and RETURN Count (not OUTPUT).
A cinema in Lahore sells tickets through a kiosk.
- (a) Write pseudocode that asks the user for the number of tickets, repeats the input until it is a whole number from 1 to 8 inclusive, then outputs the total cost. Each ticket costs Rs 750. Assume the input is always an integer. [4]
- (b) State the output when the user enters 0, then 9, then 3. [1]
Show answer
- (a) DECLARE Tickets : INTEGERREPEAT OUTPUT "Enter number of tickets (1 to 8)" INPUT TicketsUNTIL Tickets >= 1 AND Tickets <= 8OUTPUT "Total cost: Rs ", Tickets * 750
1 mark prompt and INPUT inside a loop; 1 mark loop repeats while invalid (REPEAT…UNTIL or WHILE with pre-input); 1 mark correct range condition 1 to 8 inclusive; 1 mark output of Tickets × 750 after the loop.
- (b) Total cost: Rs 2250 (0 and 9 are rejected).
B1: 2250.
A weather station in Murree stores the rainfall, in mm, for each day of a 30-day month in the global array Rainfall[1:30] OF REAL.
- (a) Write pseudocode for a procedure WettestDay() that finds the largest value in Rainfall and outputs the day number and the rainfall on that day. If two days have the same largest value, output the first one. [5]
Show answer
- (a) PROCEDURE WettestDay() DECLARE Day, MaxDay : INTEGER MaxDay ← 1 FOR Day ← 2 TO 30 IF Rainfall[Day] > Rainfall[MaxDay] THEN MaxDay ← Day ENDIF NEXT Day OUTPUT "Day ", MaxDay, " had ", Rainfall[MaxDay], " mm"ENDPROCEDURE
1 mark procedure header/end; 1 mark initialise max (to first element, or index 1); 1 mark loop through all 30 elements; 1 mark compare with strict > so that the first is kept, updating index; 1 mark output day number and rainfall after the loop.
A science club in Kampala records temperatures from a classroom thermometer.
- (a) Write pseudocode that inputs temperatures until the value −999 is entered. −999 is not a temperature. The program then outputs the average temperature, or the message "No data" if no temperatures were entered. [5]
Show answer
- (a) DECLARE Temp, Total : REALDECLARE Count : INTEGERTotal ← 0Count ← 0INPUT TempWHILE Temp <> -999 Total ← Total + Temp Count ← Count + 1 INPUT TempENDWHILEIF Count = 0 THEN OUTPUT "No data"ELSE OUTPUT Total / CountENDIF
1 mark initialise Total and Count before the loop; 1 mark first INPUT before a WHILE loop (or equivalent so −999 is not added); 1 mark correct loop condition and second INPUT inside the loop; 1 mark add to total and count inside the loop; 1 mark IF Count = 0 then 'No data' else output Total / Count.
A courier company in Lahore gives each parcel a tracking code.
- (a) Write pseudocode for the function IsValidCode(Code : STRING) RETURNS BOOLEAN. A valid code has exactly 8 characters: three upper-case letters, a hyphen, then four digits, for example "LHR-2041". The function returns TRUE if Code is valid and FALSE otherwise. [7]
Show answer
- (a) FUNCTION IsValidCode(Code : STRING) RETURNS BOOLEAN DECLARE Index : INTEGER DECLARE Ch : CHAR IF LENGTH(Code) <> 8 THEN RETURN FALSE ENDIF FOR Index ← 1 TO 3 Ch ← MID(Code, Index, 1) IF Ch < 'A' OR Ch > 'Z' THEN RETURN FALSE ENDIF NEXT Index IF MID(Code, 4, 1) <> '-' THEN RETURN FALSE ENDIF FOR Index ← 5 TO 8 Ch ← MID(Code, Index, 1) IF Ch < '0' OR Ch > '9' THEN RETURN FALSE ENDIF NEXT Index RETURN TRUEENDFUNCTION
1 mark each: header/ENDFUNCTION returning BOOLEAN; length check of 8; loop over characters 1 to 3; test each is 'A'–'Z' (or UCASE/ASC range); check character 4 is '-'; loop over characters 5 to 8 testing '0'–'9' (or IS_NUM); RETURN TRUE only after all tests pass and FALSE otherwise. Accept a flag variable instead of early returns.
A water-quality sensor at a treatment plant in Johannesburg logs pH readings to a text file.
- (a) Write pseudocode for the function CopyHigh(Limit : REAL) RETURNS INTEGER. The function reads every line of the text file "Readings.txt". Each line holds one reading as a string. Every reading greater than Limit is written to a new text file "High.txt". The function returns the number of readings written. [7]
Show answer
- (a) FUNCTION CopyHigh(Limit : REAL) RETURNS INTEGER DECLARE Line : STRING DECLARE Count : INTEGER Count ← 0 OPENFILE "Readings.txt" FOR READ OPENFILE "High.txt" FOR WRITE WHILE NOT EOF("Readings.txt") READFILE "Readings.txt", Line IF STR_TO_NUM(Line) > Limit THEN WRITEFILE "High.txt", Line Count ← Count + 1 ENDIF ENDWHILE CLOSEFILE "Readings.txt" CLOSEFILE "High.txt" RETURN CountENDFUNCTION
1 mark each: open Readings.txt FOR READ; open High.txt FOR WRITE; loop WHILE NOT EOF("Readings.txt"); READFILE each line into a variable; convert with STR_TO_NUM and compare with the parameter Limit; WRITEFILE and increment counter (initialised to 0); close both files and RETURN Count. Do not credit INPUT of Limit.
An electricity company charges for each month: the first 100 units at Rs 10 per unit, the next 200 units (units 101 to 300) at Rs 15 per unit, and every unit above 300 at Rs 22 per unit.
- (a) Write pseudocode for the function BillAmount(Units : INTEGER) RETURNS INTEGER that returns the bill in rupees. [6]
- (b) Calculate the values returned for 80 units and for 350 units. [2]
Show answer
- (a) FUNCTION BillAmount(Units : INTEGER) RETURNS INTEGER DECLARE Cost : INTEGER IF Units <= 100 THEN Cost ← Units * 10 ELSE IF Units <= 300 THEN Cost ← 1000 + (Units - 100) * 15 ELSE Cost ← 1000 + 3000 + (Units - 300) * 22 ENDIF ENDIF RETURN CostENDFUNCTION
1 mark header/end with RETURN; 1 mark first band Units × 10; 1 mark correct boundary tests (≤ 100, ≤ 300); 1 mark second band 1000 + (Units − 100) × 15; 1 mark third band 4000 + (Units − 300) × 22; 1 mark nested IF / CASE structure correct.
- (b) 80 units: Rs 800; 350 units: Rs 5100.
1 mark each (350: 100×10 + 200×15 + 50×22 = 1000 + 3000 + 1100).
An auditorium in Kuala Lumpur has 10 rows of 20 seats. The global 2D array Booked[1:10, 1:20] OF BOOLEAN stores TRUE if a seat is booked and FALSE if it is free.
- (a) Write pseudocode for a procedure BestRow() that outputs the number of the row with the most free seats and how many free seats it has. If several rows have the same number, output the lowest row number. [7]
Show answer
- (a) PROCEDURE BestRow() DECLARE Row, Seat, Free, BestRowNo, BestFree : INTEGER BestFree ← -1 BestRowNo ← 0 FOR Row ← 1 TO 10 Free ← 0 FOR Seat ← 1 TO 20 IF Booked[Row, Seat] = FALSE THEN Free ← Free + 1 ENDIF NEXT Seat IF Free > BestFree THEN BestFree ← Free BestRowNo ← Row ENDIF NEXT Row OUTPUT "Row ", BestRowNo, " has ", BestFree, " free seats"ENDPROCEDURE
1 mark each: outer loop 1 to 10 for rows; reset count of free seats for each row; inner loop 1 to 20 for seats; test Booked[Row, Seat] = FALSE and increment; compare with best so far using > (lowest row kept); store best row and count; output after both loops.
A text-analysis tool for a newspaper in Dhaka counts words typed by reporters.
- (a) Write pseudocode for the function CountWords(Sentence : STRING) RETURNS INTEGER. Words are separated by one or more spaces, and the sentence may begin or end with spaces. For example " the cat sat " contains 3 words. [6]
Show answer
- (a) FUNCTION CountWords(Sentence : STRING) RETURNS INTEGER DECLARE Index, Count : INTEGER DECLARE InWord : BOOLEAN DECLARE Ch : CHAR Count ← 0 InWord ← FALSE FOR Index ← 1 TO LENGTH(Sentence) Ch ← MID(Sentence, Index, 1) IF Ch = ' ' THEN InWord ← FALSE ELSE IF InWord = FALSE THEN Count ← Count + 1 InWord ← TRUE ENDIF ENDIF NEXT Index RETURN CountENDFUNCTION
1 mark each: initialise count and flag; loop through every character; extract with MID; space sets 'not in word'; non-space after space (start of a word) increments count; RETURN Count. Accept counting positions where a non-space follows a space or is at position 1.
A teacher in Karachi wants a small tool that shows how denary numbers are stored in binary.
- (a) Write a program function DenaryToBinary(Number) that takes a non-negative integer and returns its binary representation as a string, using repeated division by 2. Do not use a built-in conversion function. Then write a main program that calls the function with 45, 0, 255 and 130 and outputs each result. Give the outputs of your test run. (Python shown; Java or VB.NET solutions are equally acceptable.) [7]
Show answer
- (a) def DenaryToBinary(Number): # Number is a non-negative integer if Number == 0: return "0" Result = "" while Number > 0: Remainder = Number % 2 Result = str(Remainder) + Result Number = Number // 2 return Resultfor Value in [45, 0, 255, 130]: print(Value, DenaryToBinary(Value))Test output:45 1011010 0255 11111111130 10000010
1 mark each: function header with one parameter; special case 0 returns "0"; loop while Number > 0; remainder with MOD (%) prepended to the result string; integer division by 2; returns the string (not printed inside the function); main program calls with all four values and evidence of output 101101, 0, 11111111, 10000010.
A security club at a school in Rawalpindi is learning about simple ciphers.
- (a) Write pseudocode for the function Encrypt(Message : STRING, Shift : INTEGER) RETURNS STRING. Each upper-case letter is replaced by the letter Shift places later in the alphabet, wrapping from Z back to A. Shift is from 1 to 25. All other characters are copied unchanged. [7]
- (b) State the value returned by Encrypt("ZEBRA 9", 3). [1]
Show answer
- (a) FUNCTION Encrypt(Message : STRING, Shift : INTEGER) RETURNS STRING DECLARE Result : STRING DECLARE Index, Code : INTEGER DECLARE Ch : CHAR Result ← "" FOR Index ← 1 TO LENGTH(Message) Ch ← MID(Message, Index, 1) IF Ch >= 'A' AND Ch <= 'Z' THEN Code ← ASC(Ch) - ASC('A') Code ← MOD(Code + Shift, 26) Ch ← CHR(Code + ASC('A')) ENDIF Result ← Result & Ch NEXT Index RETURN ResultENDFUNCTION
1 mark each: initialise result to empty string; loop through each character with MID; test for upper-case letter; convert to 0–25 using ASC; add Shift and wrap with MOD 26 (or IF > 'Z' subtract 26); convert back with CHR; concatenate every character (changed or not) and RETURN the result.
- (b) "CHEUD 9"
B1.
A warehouse in Gwadar keeps sorted lists of product codes.
- (a) Write pseudocode for the function RemoveDuplicates(Size : INTEGER) RETURNS INTEGER. The first Size elements of the global array Codes[1:500] OF INTEGER are in ascending order and may contain repeated values. The function moves the elements so that each value appears once, at the start of the array, keeping ascending order, and returns the number of distinct values. For example, if Size is 7 and the elements are 3, 3, 5, 8, 8, 8, 9, then afterwards the first four elements are 3, 5, 8, 9 and 4 is returned. [7]
Show answer
- (a) FUNCTION RemoveDuplicates(Size : INTEGER) RETURNS INTEGER DECLARE ReadPos, WritePos : INTEGER IF Size = 0 THEN RETURN 0 ENDIF WritePos ← 1 FOR ReadPos ← 2 TO Size IF Codes[ReadPos] <> Codes[WritePos] THEN WritePos ← WritePos + 1 Codes[WritePos] ← Codes[ReadPos] ENDIF NEXT ReadPos RETURN WritePosENDFUNCTION
1 mark each: header/ENDFUNCTION; handle Size = 0 (or Size < 2); write position starts at 1; loop from 2 to Size; compare current element with the last kept element; increment write position and copy the element; RETURN the number of distinct values.
A teacher in Mombasa keeps test scores in a text file.
- (a) Write pseudocode for the procedure AboveAverage(). The text file "Scores.txt" has one line per student in the form StudentID,Score, for example "S0412,67". Score is an integer from 0 to 100 and StudentID is always 5 characters. The procedure must calculate the average score, then write the StudentID of every student whose score is above the average to the file "Above.txt", and finally output the average. Assume the file contains at least one line. [8]
Show answer
- (a) PROCEDURE AboveAverage() DECLARE Line : STRING DECLARE Total, Count, Score : INTEGER DECLARE Average : REAL Total ← 0 Count ← 0 OPENFILE "Scores.txt" FOR READ WHILE NOT EOF("Scores.txt") READFILE "Scores.txt", Line Score ← STR_TO_NUM(MID(Line, 7, LENGTH(Line) - 6)) Total ← Total + Score Count ← Count + 1 ENDWHILE CLOSEFILE "Scores.txt" Average ← Total / Count OPENFILE "Scores.txt" FOR READ OPENFILE "Above.txt" FOR WRITE WHILE NOT EOF("Scores.txt") READFILE "Scores.txt", Line Score ← STR_TO_NUM(MID(Line, 7, LENGTH(Line) - 6)) IF Score > Average THEN WRITEFILE "Above.txt", LEFT(Line, 5) ENDIF ENDWHILE CLOSEFILE "Scores.txt" CLOSEFILE "Above.txt" OUTPUT "Average score: ", AverageENDPROCEDURE
Level-style marking, 1 mark each to max 8: open Scores.txt for READ; loop until EOF; READFILE each line; extract the score after the comma (MID/RIGHT and STR_TO_NUM); total and count, then average calculated after the first pass; close and reopen the file (second pass) or store the data in arrays; open Above.txt for WRITE and write LEFT(Line, 5) when Score > Average; close all files and output the average.
A word-game app in Egypt checks phrases entered by players.
- (a) Write pseudocode for the function IsPalindrome(Phrase : STRING) RETURNS BOOLEAN. It returns TRUE if the phrase reads the same forwards and backwards when spaces are ignored and upper and lower case are treated as the same. For example "Never odd or even" is a palindrome. [6]
Show answer
- (a) FUNCTION IsPalindrome(Phrase : STRING) RETURNS BOOLEAN DECLARE Clean : STRING DECLARE Index, LeftPos, RightPos : INTEGER DECLARE Ch : CHAR Clean ← "" FOR Index ← 1 TO LENGTH(Phrase) Ch ← MID(Phrase, Index, 1) IF Ch <> ' ' THEN Clean ← Clean & LCASE(Ch) ENDIF NEXT Index LeftPos ← 1 RightPos ← LENGTH(Clean) WHILE LeftPos < RightPos IF MID(Clean, LeftPos, 1) <> MID(Clean, RightPos, 1) THEN RETURN FALSE ENDIF LeftPos ← LeftPos + 1 RightPos ← RightPos - 1 ENDWHILE RETURN TRUEENDFUNCTION
1 mark each: build a string without spaces; convert to one case; set pointers to both ends (or build reversed string); compare matching characters; move pointers inwards / loop to the middle; RETURN FALSE on a mismatch and TRUE otherwise.
A satellite-imaging start-up in Bengaluru compresses rows of a black-and-white image using run-length encoding.
- (a) Write a function Encode(Text) that returns the run-length encoding of Text: each run of the same character is replaced by the run length followed by the character, so "AAABCCDDDD" becomes "3A1B2C4D". Text contains only letters. Write a function Decode(Code) that reverses the process; run lengths may have more than one digit. Write a main program that encodes and then decodes "AAABCCDDDD", "WWWWWWWWWWWWB" and "XYZ", outputting the original, encoded and decoded strings. Give the test output. (Python shown; Java or VB.NET solutions are equally acceptable.) [10]
Show answer
- (a) def Encode(Text): if Text == "": return "" Result = "" Count = 1 for Index in range(1, len(Text)): if Text[Index] == Text[Index - 1]: Count = Count + 1 else: Result = Result + str(Count) + Text[Index - 1] Count = 1 Result = Result + str(Count) + Text[-1] return Resultdef Decode(Code): Result = "" Digits = "" for Ch in Code: if Ch.isdigit(): Digits = Digits + Ch else: Result = Result + Ch * int(Digits) Digits = "" return Resultfor Test in ["AAABCCDDDD", "WWWWWWWWWWWWB", "XYZ"]: Coded = Encode(Test) print(Test, Coded, Decode(Coded))Test output:AAABCCDDDD 3A1B2C4D AAABCCDDDDWWWWWWWWWWWWB 12W1B WWWWWWWWWWWWBXYZ 1X1Y1Z XYZ
Encode (5): handles empty string or first character; loop comparing each character with the previous; counter incremented for a repeat; on change, append count and character and reset count; final run appended after the loop. Decode (3): collect digit characters into a number string (multi-digit lengths, e.g. 12); on a letter, append it int(count) times; reset the digit string. Main and testing (2): calls for all three strings; screenshot/evidence of the correct three output lines.
A volunteer register for a flood-relief camp in Sindh stores 50 names.
- (a) Write pseudocode for the function FindName(SearchName : STRING) RETURNS INTEGER that performs a linear search of the global array Names[1:50] OF STRING and returns the index of the first element equal to SearchName, or −1 if it is not found. [5]
- (b) State one condition that must be true before a binary search could be used on Names instead. [1]
Show answer
- (a) FUNCTION FindName(SearchName : STRING) RETURNS INTEGER DECLARE Index : INTEGER Index ← 1 WHILE Index <= 50 IF Names[Index] = SearchName THEN RETURN Index ENDIF Index ← Index + 1 ENDWHILE RETURN -1ENDFUNCTION
1 mark each: header/ENDFUNCTION; loop through indices 1 to 50; compare element with the parameter; return index when found (stopping the search); return −1 only after the whole array has been checked.
- (b) The array must be sorted (in alphabetical order).
B1.
A quiz website in Turkey ranks the scores of 100 players.
- (a) Write pseudocode for the procedure SortScores() which uses an efficient bubble sort to put the global array Scores[1:100] OF INTEGER into descending order (highest first). The sort must stop as soon as a complete pass makes no swaps. [7]
- (b) Explain why reducing the upper bound of the inner loop after each pass makes the algorithm more efficient. [2]
Show answer
- (a) PROCEDURE SortScores() DECLARE Index, Temp, Last : INTEGER DECLARE Swapped : BOOLEAN Last ← 99 REPEAT Swapped ← FALSE FOR Index ← 1 TO Last IF Scores[Index] < Scores[Index + 1] THEN Temp ← Scores[Index] Scores[Index] ← Scores[Index + 1] Scores[Index + 1] ← Temp Swapped ← TRUE ENDIF NEXT Index Last ← Last - 1 UNTIL Swapped = FALSE OR Last = 0ENDPROCEDURE
1 mark each: outer conditional loop; flag reset to FALSE at the start of each pass; inner loop 1 to 99 (or reducing upper bound); compare adjacent elements with < for descending order; swap using a temporary variable; set flag TRUE when a swap happens; outer loop ends when no swaps (reducing the bound is credit-worthy but not required).
- (b) After each pass the smallest remaining value has moved to its final position at the end, so it does not need to be compared again; fewer comparisons are made.
1 mark last element is in its correct place after each pass; 1 mark so fewer comparisons/iterations are needed.
An array holds the six values 29, 12, 45, 7, 33, 18 (in index order).
- (a) An insertion sort is used to put the array into ascending order. Complete the contents of the array after each pass of the outer loop (each pass inserts one more element into the sorted part). [5]
- (b) Describe the order of the data that gives the best-case performance for an insertion sort, and explain why. [2]
- (c) Give one reason why an insertion sort is usually faster than a bubble sort on the same data. [1]
Show answer
- (a) After pass 1: 12, 29, 45, 7, 33, 18After pass 2: 12, 29, 45, 7, 33, 18After pass 3: 7, 12, 29, 45, 33, 18After pass 4: 7, 12, 29, 33, 45, 18After pass 5: 7, 12, 18, 29, 33, 45
1 mark for each correct row.
- (b) Data already in ascending order: each new element is compared once with the element before it and never moved, so only n − 1 comparisons are needed.
1 mark already sorted; 1 mark only one comparison per element / no shifting, so time grows linearly.
- (c) Insertion sort shifts elements along and stops comparing as soon as the correct position is found, so it does fewer comparisons and swaps (especially on nearly sorted data).
B1.
A music-streaming company keeps sorted lists of song IDs.
- (a) Write a recursive function BinarySearch(Data, Target, Low, High) that returns the index of Target in the sorted list Data, or −1 if it is not present. Use a global variable Calls to count how many times the function is called. Write a main program that searches the list [3, 8, 15, 21, 30, 42, 57, 66, 79, 88] (indices 0 to 9) for 57 and then for 10, resetting Calls before each search, and outputs the item, the returned index and the number of calls. Give the test output. (Python shown; Java or VB.NET solutions are equally acceptable.) [8]
- (b) State the maximum number of items that are compared with Target when searching a sorted list of 1000 items with a binary search. [1]
Show answer
- (a) Calls = 0def BinarySearch(Data, Target, Low, High): global Calls Calls = Calls + 1 if Low > High: return -1 Mid = (Low + High) // 2 if Data[Mid] == Target: return Mid elif Data[Mid] < Target: return BinarySearch(Data, Target, Mid + 1, High) else: return BinarySearch(Data, Target, Low, Mid - 1)Numbers = [3, 8, 15, 21, 30, 42, 57, 66, 79, 88]for Item in [57, 10]: Calls = 0 print(Item, BinarySearch(Numbers, Item, 0, len(Numbers) - 1), Calls)Test output:57 6 410 -1 4
1 mark each: function with four parameters; base case Low > High returns −1; mid-point using integer division; returns Mid when found; recursive call on upper half (Mid + 1) when Data[Mid] < Target; recursive call on lower half (Mid − 1) otherwise, returning the result of each recursive call; global call counter incremented; evidence of outputs 6 with 4 calls and −1 with 4 calls.
- (b) 10
B1: 10 (2¹⁰ = 1024 ≥ 1000).
A developer is writing a journey-planner app for the Lahore Metrobus and Orange Line.
- (a) Explain what is meant by abstraction, using the journey-planner app as an example. [2]
- (b) Explain what is meant by decomposition, and identify two sub-problems that the journey-planner problem could be decomposed into. [3]
Show answer
- (a) Abstraction removes unnecessary detail to keep only what is needed; e.g. the app shows stations, routes and journey times but leaves out the buildings and the exact shape of the roads.
1 mark removing unnecessary details / keeping only essential features; 1 mark suitable example from the app.
- (b) Breaking a problem into smaller sub-problems that are easier to solve. Sub-problems e.g. finding the nearest station to the user; calculating the fastest route; calculating the fare; displaying live arrival times.
1 mark definition; 1 mark each for two suitable sub-problems.
A public library in Accra is writing a program to calculate fines for books returned late.
- (a) Identify three items of data that the program needs and two items of real-world detail that can be ignored. Justify one item you would ignore. [4]
- (b) Describe how decomposition can help a team of three programmers produce this system. [2]
Show answer
- (a) Needed (any three): book ID; member ID; date due back; date returned; fine rate per day; maximum fine. Ignored (any two): book's cover colour, number of pages, author's biography, the member's height. Justification: e.g. the colour of the cover has no effect on how much fine is owed.
1 mark for three needed items; 1 mark each for two ignored items; 1 mark justification.
- (b) The system is split into modules (e.g. issue books, return books, calculate fines) that can be given to different programmers and written and tested separately at the same time, then combined.
1 mark split into independent modules/sub-tasks; 1 mark developed and tested in parallel by different programmers / easier to maintain.
An online shop in Dubai has three procedures:BookSale() – reduces the price of every product in category "Books" by 10 %ToySale() – reduces the price of every product in category "Toys" by 15 %StationerySale() – reduces the price of every product in category "Stationery" by 5 %Each procedure loops through the same global array of product records.
- (a) Use the idea of generalisation (pattern recognition) to replace these three procedures with one module. Write the pseudocode header for the module and explain how it would be called to produce the same three results. [4]
- (b) Give two advantages of using the single module instead of three procedures. [2]
Show answer
- (a) PROCEDURE ApplyDiscount(Percent : INTEGER, Category : STRING)Calls: ApplyDiscount(10, "Books"); ApplyDiscount(15, "Toys"); ApplyDiscount(5, "Stationery"). The common pattern (loop through products, reduce price of a category by a percentage) is written once and the differences become parameters.
1 mark spotting the common pattern; 1 mark one module with parameters for percentage and category; 1 mark correct header syntax; 1 mark three calls with correct arguments.
- (b) Less code to write/test; a change or bug fix is made in only one place; can easily handle new categories or discounts without new code.
1 mark each for any two.
Total ← 0Count ← 0Max ← 0INPUT ValueWHILE Value <> -1 IF Value > 10 THEN Total ← Total + Value Count ← Count + 1 ENDIF IF Value > Max THEN Max ← Value ENDIF INPUT ValueENDWHILEOUTPUT Total, Count, Max
- (a) Complete a trace table for the algorithm with columns Value, Total, Count, Max, when the inputs are 12, 7, 20, 5, 15, −1. [4]
- (b) State the values output. [1]
- (c) State the purpose of the algorithm. [1]
Show answer
- (a) Value | Total | Count | Max12 | 12 | 1 | 127 | 12 | 1 | 1220 | 32 | 2 | 205 | 32 | 2 | 2015 | 47 | 3 | 20−1 (loop ends)
Initial row 0, 0, 0. 1 mark Total column; 1 mark Count column; 1 mark Max column; 1 mark loop ends at −1 without processing it.
- (b) 47 3 20
B1.
- (c) It finds the total and number of values greater than 10, and the largest value entered.
B1.
PROCEDURE Process(Text : STRING) DECLARE Index, Count : INTEGER DECLARE Ch : CHAR DECLARE Result : STRING Count ← 0 Result ← "" FOR Index ← 1 TO LENGTH(Text) Ch ← MID(Text, Index, 1) IF Ch = 'A' THEN Count ← Count + 1 ELSE Result ← Ch & Result ENDIF NEXT Index OUTPUT Count, " ", ResultENDPROCEDURE
- (a) Complete a trace table with columns Index, Ch, Count, Result for the call Process("KARAKORAM"). [5]
- (b) State what the procedure outputs. [1]
- (c) Describe the purpose of the procedure. [2]
Show answer
- (a) Index | Ch | Count | Result1 | K | 0 | K2 | A | 1 | K3 | R | 1 | RK4 | A | 2 | RK5 | K | 2 | KRK6 | O | 2 | OKRK7 | R | 2 | ROKRK8 | A | 3 | ROKRK9 | M | 3 | MROKRK
1 mark Index and Ch columns; 1 mark Count column; 2 marks Result column (1 mark if one error); 1 mark final output.
- (b) 3 MROKRK
B1: 3 and MROKRK.
- (c) It counts the letter A in the text and outputs the other letters in reverse order.
1 mark counts 'A's; 1 mark outputs the remaining characters reversed.
FUNCTION Mystery(N : INTEGER) RETURNS INTEGER DECLARE Steps : INTEGER Steps ← 0 WHILE N <> 1 IF MOD(N, 2) = 0 THEN N ← DIV(N, 2) ELSE N ← 3 * N + 1 ENDIF Steps ← Steps + 1 ENDWHILE RETURN StepsENDFUNCTION
- (a) Complete a trace table with columns N and Steps for the call Mystery(6). State the value returned. [4]
- (b) State the value returned by Mystery(7). [1]
- (c) Explain what happens when Mystery(0) is called, and suggest a change to the function to prevent this. [2]
Show answer
- (a) N: 6, 3, 10, 5, 16, 8, 4, 2, 1Steps: 0, 1, 2, 3, 4, 5, 6, 7, 8Value returned: 8
2 marks N column (1 mark if one error); 1 mark Steps column; 1 mark returns 8.
- (b) 16
B1: 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 is 16 steps.
- (c) 0 is even, DIV(0, 2) = 0, so N never becomes 1 and the loop never ends (infinite loop). Change: validate N, e.g. IF N < 1 THEN RETURN -1 ENDIF before the loop.
1 mark infinite loop with reason; 1 mark suitable validation/guard.
A water park in Murree is drawing flowcharts for its ticket machine.
- (a) State the flowchart symbol used for each of: (i) START and STOP, (ii) INPUT Age, (iii) Price ← Price × 0.8, (iv) Is Age < 12? [4]
- (b) A flowchart contains: START → INPUT Age → decision 'Age < 12?' → Yes: OUTPUT "Child ticket"; No: OUTPUT "Adult ticket" → both join → STOP. Write equivalent pseudocode. [2]
Show answer
- (a) (i) terminator – rounded rectangle; (ii) input/output – parallelogram; (iii) process – rectangle; (iv) decision – diamond.
1 mark each.
- (b) INPUT AgeIF Age < 12 THEN OUTPUT "Child ticket"ELSE OUTPUT "Adult ticket"ENDIF
1 mark INPUT and IF condition; 1 mark both outputs in correct branches with ENDIF.
A flowchart for a savings-box counter is described:1. START2. Process: Balance ← 03. Input: INPUT Amount4. Decision: 'Amount = 0?' – Yes goes to step 8; No goes to step 55. Decision: 'Amount > 0?' – Yes goes to step 6; No goes to step 76. Process: Balance ← Balance + Amount, then go to step 37. Output: OUTPUT "Invalid", then go to step 38. Output: OUTPUT Balance9. STOP
- (a) Write pseudocode for the algorithm shown by the flowchart. Use a pre-condition loop. [5]
- (b) State the output if the inputs are 500, −20, 250, 0. [2]
Show answer
- (a) Balance ← 0INPUT AmountWHILE Amount <> 0 IF Amount > 0 THEN Balance ← Balance + Amount ELSE OUTPUT "Invalid" ENDIF INPUT AmountENDWHILEOUTPUT Balance
1 mark Balance initialised; 1 mark first INPUT before the loop; 1 mark WHILE Amount <> 0 with INPUT at end of loop body; 1 mark IF/ELSE inside the loop with correct actions; 1 mark OUTPUT Balance after the loop.
- (b) Invalid, then 750
1 mark 'Invalid' output once; 1 mark 750.
A flowchart is described:1. START2. Process: Count ← 0, Total ← 03. Input: INPUT Mark4. Decision: 'Mark = −1?' – Yes goes to step 8; No goes to step 55. Decision: 'Mark >= 50?' – Yes goes to step 6; No goes to step 76. Process: Count ← Count + 17. Process: Total ← Total + Mark, then go to step 38. Process: Mean ← Total / Count9. Output: OUTPUT Count, Total, Mean10. STOP
- (a) Dry-run the flowchart with the inputs 45, 72, 50, 38, 91, −1. State the final values of Count and Total and the output. [3]
- (b) The output in step 9 is meant to be the mean of all the marks. Identify the logic error and state how to correct it. [3]
- (c) Write pseudocode for the corrected algorithm, including a check that prevents division by zero. [4]
Show answer
- (a) Count = 3, Total = 296, output: 3 296 98.67 (to 2 d.p.)
1 mark Count 3 (72, 50, 91); 1 mark Total 296 (all marks except −1); 1 mark average 296 ÷ 3 = 98.67 shown in output.
- (b) The mean is calculated as Total ÷ Count but Count only counts marks of 50 or more (passes), while Total includes every mark. Correct by adding a second counter for all marks (incremented in step 7) and dividing Total by it – giving 296 ÷ 5 = 59.2.
1 mark identifies Total ÷ Count mismatch; 1 mark explains Count counts passes only; 1 mark correction (new counter of all marks) / correct value 59.2.
- (c) Count ← 0NumMarks ← 0Total ← 0INPUT MarkWHILE Mark <> -1 IF Mark >= 50 THEN Count ← Count + 1 ENDIF Total ← Total + Mark NumMarks ← NumMarks + 1 INPUT MarkENDWHILEIF NumMarks > 0 THEN OUTPUT Count, Total, Total / NumMarksENDIF
1 mark initialisation; 1 mark loop with sentinel −1 and input in correct places; 1 mark pass count and totals in loop; 1 mark division guarded by NumMarks > 0.
A car park at a shopping mall in Karachi calculates the charge when a vehicle leaves. The program reads the vehicle's registration number and entry time, calculates the number of whole or part hours parked, applies Rs 100 per hour, and halves the charge if the driver has a membership card.
- (a) Complete an identifier table (identifier, data type, description) for four variables needed by this algorithm. [4]
- (b) Explain why meaningful identifier names should be used. [2]
Show answer
- (a) PlateNo | STRING | registration number of the vehicleEntryTime | TIME (or INTEGER minutes) | time the vehicle enteredHours | INTEGER | number of hours charged (part hours rounded up)Charge | REAL (or INTEGER rupees) | amount to payAlso accept IsMember : BOOLEAN – whether the driver has a membership card.
1 mark per row with a meaningful identifier, a suitable data type and a clear description (max 4).
- (b) They make the code self-documenting, so it is easier for other programmers to read, understand and maintain (debug) the program.
1 mark easier to read/understand; 1 mark easier to maintain/debug, especially by others.
A mobile network in Pakistan needs a billing program.
- (a) Use stepwise refinement to break the task 'Produce a monthly mobile-phone bill' into at least four steps, and refine two of those steps into more detailed sub-steps. [6]
- (b) State one benefit of stepwise refinement. [1]
Show answer
- (a) 1 Read customer details2 Calculate call charges 2.1 For each call record, find its duration in minutes (round up part minutes) 2.2 Multiply by the rate (on-network or off-network) 2.3 Add to call total3 Calculate data charges 3.1 Total the MB used 3.2 Subtract the free allowance (minimum 0) 3.3 Multiply the excess by the rate per MB4 Add line rental and tax5 Output the bill
1 mark each to max 6: at least four sensible top-level steps (2 marks); first step refined into ordered, more detailed sub-steps (2 marks); second step refined (2 marks). Sub-steps must be more detailed than the parent step.
- (b) Each sub-step is small enough to be turned directly into code/modules, making the program easier to write, test and share between programmers.
B1.
