Algorithms and Programming: Mixed Unit Review (Computer Science Principles Unit 3)

(a)

PROCEDURE aboveAverage(aList)
{
  total ← 0
  FOR EACH item IN aList
  {
    total ← total + item
  }
  average ← total / LENGTH(aList)
  count ← 0
  FOR EACH item IN aList
  {
    IF(item > average)
    {
      count ← count + 1
    }
  }
  RETURN(count)
}

(b) The total is 20 + 25 + 31 + 22 + 30 + 28 = 156 and LENGTH(aList) is 6, so the average is 156 / 6 = 26. Elements greater than 26: 31, 30 and 28. The procedure returns 3.

(c) The average is 4 and no element is greater than 4, so it returns 0. Using > (not ≥) counts only elements strictly above the average.

(d) For [], LENGTH(aList) is 0 so the division total / LENGTH(aList) divides by zero, which is undefined and would cause an error. Guard with IF(LENGTH(aList) > 0) before dividing, and return 0 (or another agreed value) otherwise.

Suggested Marlbridge rubric (7 marks)

PROCEDURE digitSum(n)
{
  total ← 0
  REPEAT UNTIL(n = 0)
  {
    total ← total + n MOD 10
    n ← (n - n MOD 10) / 10
  }
  RETURN(total)
}

(a)

The loop stops when n is 0, so digitSum(4826) returns 20.

(b) n is already 0, so the REPEAT UNTIL(n = 0) loop runs zero times and the procedure returns the starting total, 0.

(c)

PROCEDURE divisibleBy3(n)
{
  RETURN(digitSum(n) MOD 3 = 0)
}

For example divisibleBy3(4827) is true (digit sum 21) and divisibleBy3(4826) is false (digit sum 20). (We checked that this agrees with n MOD 3 = 0 for every whole number from 0 to 2,000.)

(d) The digit-adding code is already written and tested, so reusing it reduces development time and testing, keeps divisibleBy3 short and readable, and means a correction to digitSum improves both.

Suggested Marlbridge rubric (7 marks)

PROCEDURE price1(age, isMember)
{
  IF(age < 13)
  {
    RETURN(5)
  }
  ELSE
  {
    IF(isMember)
    {
      RETURN(8)
    }
    ELSE
    {
      RETURN(10)
    }
  }
}

PROCEDURE price2(age, isMember)
{
  IF(age < 13)
  {
    RETURN(5)
  }
  IF(isMember)
  {
    RETURN(8)
  }
  RETURN(10)
}

PROCEDURE price3(age, isMember)
{
  IF(isMember)
  {
    RETURN(8)
  }
  IF(age < 13)
  {
    RETURN(5)
  }
  RETURN(10)
}

(a)

(b) price1 and price2 match the requirement. price3 does not: for a 9-year-old member it returns 8, but under-13s should pay 5. It tests membership before age.

(c) In price2 the first RETURN leaves the procedure immediately, so the later tests are only reached when age < 13 was false. That is exactly what the ELSE of price1 achieved, so the two procedures give the same result for every input (we confirmed this for ages 0 to 39 with both membership values).

Suggested Marlbridge rubric (6 marks)

(a) Linear search: up to 1,000 elements. Binary search: halving 1,000 repeatedly gives 500, 250, 125, 62, 31, 15, 7, 3, 1, nine halvings plus the final check, so up to 10 (2¹⁰ = 1,024 is the first power of two above 1,000).

(b)

Two checks.

(c) 2,000 items: the first power of two above 2,000 is 2,048 = 2¹¹, so 11 checks, only one more than before.

(d) Linear search. Binary search needs the data to be sorted: it discards half the list after each comparison, which is valid only if the order guarantees the target is not in the discarded half. In an unsorted list the target could be discarded.

Suggested Marlbridge rubric (7 marks)

PROCEDURE banner(word)
{
  RETURN(concat(toUpper(word), "!"))
}

(a) toUpper("go") returns "GO", then concat("GO", "!") is "GO!", so GO! is displayed.

(b) The parameter is word; the argument is "go"; the value returned is "GO!".

(c) The library supplies a tested capitalising procedure, so the student does not have to write or test it, and the API documentation says what it does without showing how. banner wraps the steps under one name with a parameter, so any word can be turned into a shout with a single call, and the details are hidden from the callers. Together they reduce development time and keep the program short and readable.

(d) No. Callers depend on what banner does (returns the word in capitals followed by an exclamation mark), not how. Because that is unchanged, the internals can change without notifying users.

Suggested Marlbridge rubric (5 marks)

wins ← 0
REPEAT 5 TIMES
{
  total ← RANDOM(1, 6) + RANDOM(1, 6)
  IF(total ≥ 10)
  {
    wins ← wins + 1
  }
}
DISPLAY(wins)

(a) The totals are 6 + 5 = 11 (win), 2 + 3 = 5, 4 + 6 = 10 (win), 1 + 1 = 2, 5 + 5 = 10 (win). Three totals are at least 10, so 3 is displayed.

(b) There are 36 equally likely pairs and six of them total at least 10: (4,6), (5,5), (6,4), (5,6), (6,5), (6,6). So the probability is 6/36 = 1/6 (about 17%).

(c) Each RANDOM call is random, so every run uses a new set of values and the count of wins can differ. One run is a single possible outcome; many runs (or counting the possible pairs, as in part (b)) are needed to judge the game.

(d) The simulation assumes the dice are fair (each face equally likely). Real dice may be slightly weighted, and the model also ignores things such as dice landing off the table. If the assumption is wrong, the results are biased.

Suggested Marlbridge rubric (7 marks)

(a) Task 1: decidable and solvable in reasonable time. Exploring the map from one depot (an algorithm exists) takes a number of steps that grows slowly with the size of the map, and it gives the correct answer for every map.

Task 2: decidable but not in reasonable time. Trying every order is an algorithm that always gives the best route, but 49! orders is far too many for a computer to check.

Task 3: undecidable. It is the halting problem: no algorithm can correctly decide, for every script and input, whether it will ever finish.

(b) Use a heuristic, such as always travelling to the nearest unvisited depot. It finds a good route quickly but is not guaranteed to be the shortest.

(c) For Task 2 an algorithm exists that always works; it just takes an unreasonable amount of time, so a faster method or approximation helps. For Task 3 no algorithm exists that is always correct, so no amount of time or speed would solve the general problem (though some scripts can be checked individually).

Suggested Marlbridge rubric (6 marks)