Developing Algorithms: Study Guide (Computer Science Principles 3.9)

An algorithm is a finite set of instructions that accomplish a specific task. A recipe is an algorithm for a meal, and the steps for long division are an algorithm for dividing. Almost everything you have met in this unit, from assignments to loops, is a way of writing algorithms precisely enough for a computer to follow. In this topic you step back and look at algorithms themselves: how to create one, how to combine and modify algorithms you already know, and how to compare two algorithms to decide whether they produce the same result.

Notation. The exam uses its own pseudocode, not a real programming language. The code in this pack is Marlbridge’s rendering of that reference notation, not a copy of the official sheet: ← is assignment, = tests equality, lists start at index 1, DISPLAY shows a value, and braces mark blocks. Use the Exam Reference Sheet from your teacher for the official wording.

What an algorithm is, and how it can be written

An algorithm must be finite (it ends) and must accomplish a task (it solves a problem). It does not belong to any language. The same algorithm can be expressed as:

• natural language: “Look at each score and remember the biggest one”;
• a diagram: a flowchart with boxes and diamonds;
• pseudocode: structured text like the notation in this pack;
• a program in a visual or text-based programming language, which a computer can run.

Whatever the form, every algorithm can be constructed from three kinds of step, as you have seen in Topics 3.6 and 3.8: sequencing (steps in order), selection (choosing a path with a condition) and iteration (repeating). Clarity matters as much as correctness: an algorithm another person cannot read is hard to test and to fix.

Three ways to create an algorithm

Algorithms rarely start from nothing. The course names three sources:

1. From an idea. You invent the steps to solve a new problem.
2. By combining existing algorithms. You use two known solutions as parts of a bigger one.
3. By modifying an existing algorithm. You change a known solution slightly to solve a related problem.

Knowing a stock of standard algorithms is a big advantage. The ones named in the course include: finding the maximum or minimum of two or more numbers, computing the sum or average of two or more numbers, testing whether one integer is evenly divisible by another, and determining a robot’s path through a maze. Using an existing, already-correct algorithm as a building block has real benefits: it reduces development time, reduces testing (the part is already trusted) and simplifies finding errors (if the answer is wrong, the fault is probably in the new part).

Comparing algorithms

Two algorithms can be written in different ways and still accomplish the same task. Two algorithms can also look almost identical and produce different results. To decide, you cannot rely on how they look: you must test them with inputs (including boundaries and special cases) or reason about every path.

Two kinds of equivalence are especially important:

• Some conditional statements can be written as equivalent Boolean expressions. IF(n MOD 2 = 0) { r ← true } ELSE { r ← false } stores in r the same value as r ← (n MOD 2 = 0).
• Some Boolean expressions can be written as equivalent conditionals (the reverse), often with nested IF statements, as in the leap-year example in Topic 3.7.

When algorithms are equivalent, you may choose the one that is clearer or, later in the unit, the one that runs faster.

Worked example 1: same task, or look-alike?

Part A. Two ways to test “n is even”.

Algorithm A uses a conditional; Algorithm B uses a Boolean expression directly.

A:
IF(n MOD 2 = 0)
{
  result ← true
}
ELSE
{
  result ← false
}

B:
result ← (n MOD 2 = 0)

n	0	1	2	3	4	5
A and B store	true	false	true	false	true	false

They agree for every value in the table. They always agree, because the conditional’s two branches simply copy the value of the condition into result. B is shorter, so it is often preferred.

Part B. Two look-alike algorithms. Both aim to store the larger of x and y in big.

C:
IF(x > y)
{
  big ← x
}
ELSE
{
  big ← y
}

D:
IF(x > y)
{
  big ← x
}
IF(y > x)
{
  big ← y
}

Test them with big starting at 0:

x	y	C gives	D gives
7	3	7	7
3	7	7	7
4	4	4	0 (neither IF is true, so big is never changed)

C and D agree on every input except when x equals y. When the two numbers are equal neither condition in D is true, so big keeps its old value. The algorithms look alike but are not equivalent. The lesson: always test the special case where the values are equal.

Worked example 2: combining and modifying

Task. For three numbers a, b, c find the largest, the smallest, the range (largest − smallest) and the average.

Step 1. Start from a known algorithm. To find the larger of two numbers we remember one and replace it if the other is bigger. Extend that idea to three: set big to a, then replace it by b if b is bigger, then by c if c is bigger.

a ← 7
b ← 12
c ← 5
big ← a
IF(b > big)
{
  big ← b
}
IF(c > big)
{
  big ← c
}
small ← a
IF(b < small)
{
  small ← b
}
IF(c < small)
{
  small ← c
}
DISPLAY(big)
DISPLAY(small)
DISPLAY(big - small)
DISPLAY((a + b + c) / 3)

Output: 12 5 7 8

Step 2. Modify to get the smallest. The code for small is the code for big with > changed to <. Modifying an existing algorithm is faster and safer than writing a new one.

Step 3. Combine. The range is the difference of the two results, so no new searching is needed: big - small.

Step 4. Trace.

Step	Variable change	Value
big ← a	big	7
b > big? 12 > 7 true	big	12
c > big? 5 > 12 false	big	12
small ← a	small	7
b < small? 12 < 7 false	small	7
c < small? 5 < 7 true	small	5

So the largest is 12, the smallest is 5, the range is 12 − 5 = 7, and the average is (7 + 12 + 5) / 3 = 24 / 3 = 8. Output 12 5 7 8.

Step 5. Test the special cases. What if the largest number is the first one (a = 9, b = 2, c = 4)? Then neither IF changes big and it stays 9, which is right. What if two numbers tie (a = 6, b = 6, c = 6)? Every comparison is false, big and small are both 6, the range is 0 and the average is 6, which is correct. Cases that exercise “no change” and “ties” are worth a test each.

Choosing between algorithms

Different algorithms can be developed to solve the same problem. When you compare options, consider: correctness on all inputs (including edge cases), clarity (can someone else read it?), reuse (can existing tested parts help?) and, as Topic 3.17 explains, efficiency. A correct but unreadable algorithm is a poor choice if a clear one is equally correct.

Common misconceptions

• “An algorithm has to be written in a programming language.” It can be natural language, a diagram, pseudocode or code.
• “If two algorithms look similar, they are equivalent.” Small differences such as > versus ≥, or two IFs versus IF/ELSE, change behaviour on boundary and tie cases.
• “If two algorithms agree on a few tests, they are equivalent.” Tests can show that they differ, but only reasoning about every input (or every case) proves they agree.
• “There is one correct algorithm for each problem.” Many different algorithms can solve the same problem.
• “Reusing an existing algorithm means copying without understanding.” You must still understand what it does and test how it behaves in your program.
• “A conditional and a Boolean expression are unrelated.” Some conditionals can be written as an equivalent Boolean expression and vice versa.

Where this leads

Algorithms are the cargo that procedures carry: in Topics 3.12 and 3.13 you will wrap algorithms such as “largest of three” in procedures with parameters, and in Topic 3.17 you will ask not just whether an algorithm is correct but how long it takes.

Next steps: try the practice questions, skim the revision notes the night before, and tick off the topic checklist. The next topic is Topic 3.10, Lists.