S4 ICT Practice Paper: Programming and Algorithm Fundamentals

A program uses integer variables a and b, where a = 87 and b = 12.

(a) State the results of the Python expressions a // b, a % b and a / b, giving a / b correct to 2 decimal places. (3 marks)
(b) Evaluate 4 + 3 * 2 ** 3 – 20 // 6 and state the order of operations. (2 marks)
(c) A student tests 0.1 + 0.2 == 0.3 and gets False. Explain why. (2 marks)

(a) 87 // 12 = 7 (integer quotient); 87 % 12 = 3 (remainder, since 12 x 7 = 84); 87 / 12 = 7.25 (true division). (3 marks)
(b) Evaluate 2 ** 3 = 8 first, then 3 x 8 = 24 and 20 // 6 = 3, giving 4 + 24 – 3 = 25. (2 marks)
(c) 0.1 and 0.2 cannot be stored exactly in binary floating point, so their sum differs from the stored value of 0.3 by about 5 x 10^-17 and == returns False. Compare with a tolerance such as abs(a – b) less than 1e-9 instead. (2 marks)

Consider the following Python code:

total = 0;
i = 1;
while i <= 8:
    total = total + i * i
    i = i + 2

(a) Complete a trace table showing i and total after each iteration. (4 marks)
(b) State the final value of total and the number of iterations. (2 marks)
(c) If i = i + 2 is changed to i = i + 1, what is the value of total? (1 mark)

(a) Trace: i = 1 gives total = 1; i = 3 gives total = 10; i = 5 gives total = 35; i = 7 gives total = 84; then i = 9, the condition 9 is not at most 8, so the loop ends. (4 marks)
(b) total = 84 (1 + 9 + 25 + 49), and the loop body runs 4 times. (2 marks)
(c) With i = i + 1 the program adds the squares from 1 to 8, so total = 204. (1 mark)

The following code prints a grade for a score:

if score >= 85:
    grade = "A"
elif score >= 70:
    grade = "B"
elif score >= 50:
    grade = "C"
else:
    grade = "F"

(a) State the output when score is 85, 84, 70 and 49. (4 marks)
(b) If the first condition becomes score > 85, what is printed for score = 85, and what type of error is this? (2 marks)
(c) Explain why the order of the conditions affects the result. (1 mark)

(a) 85 gives A; 84 gives B; 70 gives B; 49 gives F. (4 marks)
(b) With the first test changed to score greater than 85, the value 85 fails it and falls into the second branch (85 is not less than 70), so the output is B. The program runs but disagrees with the specification: a logic error. (2 marks)
(c) elif chains are tested top to bottom and the first true branch is executed, skipping the rest; if a looser test (for example 50 or above gives C) comes first, high scores would be graded C and the stricter branches would never be reached. (1 mark)

A telephone directory has 2,000 records sorted by name. A program may use linear search or binary search.

(a) State the number of comparisons for linear search in the worst case and in the average case. (2 marks)
(b) State the worst-case number of comparisons for binary search and show the working. (2 marks)
(c) What precondition does binary search require, and what extra cost arises if the data must first be sorted? (3 marks)

(a) Linear search needs 2000 comparisons in the worst case (item last or absent) and about 1000.5 on average, i.e. (n + 1) / 2. (2 marks)
(b) Binary search halves the range each time, so the worst case is ceil(log2(n + 1)) = ceil(log2 2001) which is about ceil(10.97) = 11 comparisons. (2 marks)
(c) The data must already be sorted and randomly accessible. If not, sorting first costs about O(n log n) with merge sort, which may exceed the comparisons saved, so for a single lookup linear search can be cheaper in practice. (3 marks)

The following code sorts a list in ascending order using bubble sort:

data = [45, 12, 78, 33, 56, 90]

(a) Write the list after the first pass. (4 marks)
(b) Without an early-exit optimisation, how many comparisons does the whole sort need? Give the formula in terms of n. (2 marks)
(c) What is the minimum number of passes needed for this list? (1 mark)
(d) What does it mean if a pass makes no swap, and how can this end the sort early? (1 mark)

(a) Compare adjacent items left to right: 45 and 12 swap; 45 and 78 stay; 78 and 33 swap; 78 and 56 swap; 78 and 90 stay. Result [12, 45, 33, 56, 78, 90], with the largest value 90 now last. (4 marks)
(b) Comparisons = (n – 1) + (n – 2) + … + 1 = n(n – 1) / 2; for n = 6 this is 6 x 5 / 2 = 15. (2 marks)
(c) At least 3 passes are needed, since each pass fixes one item in place. (1 mark)
(d) A pass with no swap means the list is already sorted; a swapped flag can break out at the end of that pass, so the best case takes 1 pass and n – 1 comparisons, improving O(n^2) to O(n). (1 mark)

A function computes a tutorial fee of 120 per hour with a cap of 1,000 per session:

def lesson_fee(hours, rate=120, cap=1000):
    amount = hours * rate
    if amount > cap:
        amount = cap
    return amount

(a) State the values returned by lesson_fee(6), lesson_fee(10) and lesson_fee(8.5). (3 marks)
(b) Explain the benefit of rate and cap as default parameters. (2 marks)
(c) What does the function return for hours = -3? Identify the problem and suggest a fix. (3 marks)

(a) lesson_fee(6) = 6 x 120 = 720; lesson_fee(10) = 1,200 which exceeds the cap, so 1000; lesson_fee(8.5) = 1,020, also capped to 1000. (3 marks)
(b) Default parameters let common values (120 per hour, 1,000 cap) be omitted at the call site, keeping calls short, while still allowing overrides such as lesson_fee(6, 150) without editing the function body. (2 marks)
(c) hours = -3 returns -360, an impossible negative fee. Validate the input at the start, for example if hours less than 0: raise ValueError(“hours must be non-negative”), or return 0 or a null value for the caller to handle. (3 marks)

The test marks of 7 students are:

marks = [72, 58, 91, 64, 85, 47, 79]

(a) State the total, the highest mark and the lowest mark. (3 marks)
(b) Calculate the mean mark correct to 1 decimal place. (2 marks)
(c) State how many students scored above the mean. (2 marks)
(d) Write a code fragment that counts the students above the mean. (1 mark)

(a) Total = 72 + 58 + 91 + 64 + 85 + 47 + 79 = 496; highest 91; lowest 47. (3 marks)
(b) Mean = 496 / 7 = 70.857…, i.e. 70.9. (2 marks)
(c) Marks above 70.857 are 72, 91, 85 and 79, so 4 students. (2 marks)
(d) avg = sum(marks) / len(marks); count = 0; for m in marks:; if m greater than avg: count += 1; (or sum(1 for m in marks if m greater than avg)). (1 mark)

A string variable s holds “Programming”.

(a) State the values of len(s), s[0:4] and s[-3:]. (3 marks)
(b) State the values of s.count(“m”) and s.count(“g”). (2 marks)
(c) State the result of s[::-1]. (1 mark)
(d) Explain how slicing can test whether s is a palindrome, and state whether s is one. (2 marks)

(a) len(s) = 11; s[0:4] = Prog (indexes 0 to 3); s[-3:] = ing (last three characters). (3 marks)
(b) s.count(“m”) = 2 and s.count(“g”) = 2; counting is case sensitive, and both letters here are lower case. (2 marks)
(c) s[::-1] = gnimmargorP. (1 mark)
(d) Test s == s[::-1]: reverse the string and compare; equality means a palindrome. Here gnimmargorP differs from Programming, so it is not a palindrome. (2 marks)

The following code counts the work done by nested loops:

total = 0
for i in range(n):
    for j in range(i):
        total = total + 1

(a) What is total when n = 120? (3 marks)
(b) Express total in terms of n and show the derivation. (2 marks)
(c) State the time complexity of this code. What is the time complexity of a single loop for k in range(3 * n)? (3 marks)
(d) If n grows from 120 to 1,200, by roughly what factor does the work increase? (2 marks)

(a) The outer loop runs i = 0 to 119 and the inner loop runs i times, so total = 0 + 1 + … + 119 = 119 x 120 / 2 = 7140. (3 marks)
(b) In general total = n(n – 1) / 2, the sum of the arithmetic series 0 + 1 + … + (n – 1). (2 marks)
(c) The nested loops are O(n^2); a single loop for k in range(3 * n) runs 3n times, which is O(n) (constant factors are ignored). (3 marks)
(d) For n = 1,200 the count is 1,199 x 1,200 / 2 = 719400, a factor of about 101, so a tenfold increase in n means about a hundredfold increase in work. (2 marks)

The following program should sum all even numbers from 2 to 20 inclusive, but it is faulty:

total = 0
i = 1
while i <= 20:
    if i % 2 == 1:
        total = total + i
    i = i + 1
print(total)

(a) State the value the program actually prints. (2 marks)
(b) State the correct answer. (2 marks)
(c) Identify the fault and write the corrected line. (3 marks)
(d) What goes wrong if the line i = i + 1 is deleted? (3 marks)

(a) The test keeps odd values (i % 2 == 1), so the program sums 1 + 3 + … + 19 = 100. (2 marks)
(b) The even numbers from 2 to 20 sum to 110. (2 marks)
(c) The fault is the condition, which should be if i % 2 == 0: because an even number leaves remainder 0. Corrected line: if i % 2 == 0:. (3 marks)
(d) Without i = i + 1 the value of i stays 1, the condition is always true and the loop never ends: an infinite loop that hangs the program. It is a run-time logic error the compiler cannot detect. (3 marks)

The list below is sorted in ascending order; the program searches for key with binary search:

ids = [12, 18, 23, 27, 31, 38, 44, 50, 56, 62, 69, 75, 81, 88, 94]

(a) For key = 75, write low, high, mid and the comparison at each step, and give the final index. (5 marks)
(b) How many comparisons were made? (2 marks)
(c) For key = 70 (absent), write the final low and high and explain how the loop terminates. (3 marks)

(a) low = 0, high = 14, mid = 7 gives ids[7] = 50, which is less than 75, so low = 8; then low = 8, high = 14, mid = 11 gives ids[11] = 75, a match at index 11. (5 marks)
(b) 2 comparisons were made. (2 marks)
(c) For key = 70: mid = 7 (50 less than 70) so low = 8; mid = 11 (75 greater than 70) so high = 10; mid = 9 (62 less than 70) so low = 10; mid = 10 (69 less than 70) so low = 11; now low = 11 exceeds high = 10, the while condition fails, the loop ends and reports not found after 4 comparisons. (3 marks)

A program takes the marks of 8 students:

scores = [48, 67, 55, 90, 73, 38, 81, 59]

(a) Calculate the mean, correct to 1 decimal place. (3 marks)
(b) Count the students who pass (50 or above). (2 marks)
(c) Count the students above the mean. (2 marks)
(d) Write the complete program to output the mean (1 decimal place), the number of passes and the number above the mean. (3 marks)

(a) Total = 48 + 67 + 55 + 90 + 73 + 38 + 81 + 59 = 511; mean = 511 / 8 = 63.875, i.e. 63.9. (3 marks)
(b) Scoring 50 or above: 67, 55, 90, 73, 81 and 59, so 6 students pass. (2 marks)
(c) Above 63.875: 67, 90, 73 and 81, so 4 students. (2 marks)
(d) scores = […]; avg = sum(scores) / len(scores); passes = 0; above = 0; for s in scores:; if s not less than 50: passes += 1; if s greater than avg: above += 1; print(round(avg, 1), passes, above), which outputs 63.9 6 4. (3 marks)