Aim for FiveComputer Science Principles

Unit 3 · Topic 3.9

3.9 Developing Algorithms

There's usually more than one way to solve a problem, and code that looks almost the same can behave differently. This topic covers comparing algorithms, building new ones from standard building blocks (maximum, minimum, sum, average, divisibility, robot paths) and why reusing tested algorithms saves time.

Key terms

  • algorithm
  • equivalent algorithms
  • existing algorithms as building blocks
  • maximum and minimum
  • sum and average

Same result, different code

Algorithms can be written in different ways and still do the same task. Some conditionals can be replaced by a single Boolean expression, and the reverse is also true. These two segments always give isEven the same value:

IF (n MOD 2 = 0) { isEven ← true } ELSE { isEven ← false }

isEven ← (n MOD 2 = 0)

Different algorithms can also be developed to solve the same problem. You might find a maximum by checking each value against the biggest so far, or by sorting and taking the last value.

Similar code, different result

Algorithms that look alike can produce different results. Swapping the order of two lines in a loop is enough:

count ← 0 REPEAT UNTIL (count = 3) { count ← count + 1 DISPLAY(count) }

count ← 0 REPEAT UNTIL (count = 3) { DISPLAY(count) count ← count + 1 }

The first displays 1 2 3; the second displays 0 1 2. Both loops run 3 times, but one displays before adding and the other after. To compare algorithms, trace both with the same input rather than judging by appearance.

Building blocks worth knowing

New algorithms are often made by combining or modifying existing ones. These are the standard ones to know:

  • Maximum or minimum: keep a "best so far" variable, start it at the first value, and replace it whenever you find something bigger (or smaller).
  • Sum: start a total at 0 and add each value. Average: the sum divided by how many values there are.
  • Divisibility: a MOD b = 0 is true exactly when b divides a evenly. Even numbers are the case b = 2.
  • A robot's path through a maze: combine MOVE_FORWARD, ROTATE_LEFT, ROTATE_RIGHT and CAN_MOVE with loops and conditionals.

Robot questions

Some exam questions show a robot (a triangle pointing the way it faces) on a grid of open and blocked squares. The reference sheet gives four robot commands: MOVE_FORWARD() moves one square in the direction the robot faces; ROTATE_LEFT() and ROTATE_RIGHT() turn it 90 degrees in place; CAN_MOVE(direction) is true if the square in that direction (left, right, forward or backward, relative to the way the robot faces) is open. If the robot tries to move into a blocked square or off the grid, it stays put and the program stops.

Trace robot code by tracking two things: the robot's square and the direction it faces. Draw an arrow for the direction after every turn.

Why reuse algorithms

Using existing correct algorithms as building blocks cuts development time and testing, and makes errors easier to find, because the parts you reused are already known to work. Any new error is probably in the new code.

Worked examples

Try each one yourself first, then open the solution.

  1. Example 1

    Maximum of three

    Variables a, b and c hold three numbers. What does this display when a = 2, b = 9 and c = 5?biggest ← a IF (b > biggest) { biggest ← b } IF (c > biggest) { biggest ← c } DISPLAY(biggest)

    Show the solution
    1. Step 1: biggest starts as a, so biggest = 2.
    2. Step 2: Is 9 > 2? Yes, so biggest = 9.
    3. Step 3: Is 5 > 9? No, so biggest stays 9.
    4. Step 4: The two IFs are separate on purpose: each value gets compared with the biggest so far.

    Answer: 9

  2. Example 2

    Tracing a robot

    A robot is in the bottom-left square of a 5-by-5 grid, facing up (toward the top of the grid). The squares directly above it are open for 3 squares, and the top-left corner square is blocked. In the row the robot reaches, the 4 left-most squares are open and the right-most square is blocked. Where does the robot end up, and which way is it facing?REPEAT UNTIL (NOT CAN_MOVE(forward)) { MOVE_FORWARD() } ROTATE_RIGHT() REPEAT UNTIL (NOT CAN_MOVE(forward)) { MOVE_FORWARD() }

    Show the solution
    1. Step 1: First loop: the robot moves up while the square ahead is open. It moves 3 squares to the second row from the top, where the square ahead (the top-left corner) is blocked, so CAN_MOVE(forward) is false and the loop stops.
    2. Step 2: ROTATE_RIGHT turns it from facing up to facing right.
    3. Step 3: Second loop: it moves right while the square ahead is open. From the first column, it moves 3 squares to the fourth column. The fifth square is blocked, so it stops.

    Answer: In the second row from the top, fourth column from the left, facing right.

Common mistakes

  • Judging two algorithms as the same because they look similar. Trace both with the same input.
  • Starting a maximum at 0. If every value is negative, 0 would wrongly win; start with the first value instead.
  • Losing track of the robot's direction after a turn. ROTATE_RIGHT turns clockwise relative to where it faces, not toward the right side of the page.

On the exam

  • Expect questions asking whether two code segments always produce the same result, or which change to an algorithm keeps its behavior. Test edge cases like equal values or an empty list.
  • Robot questions are common. Track position and direction after every command, and remember the program stops if the robot tries to move into a blocked square.

Connected topics

Videos

Check yourself

4 questions on 3.9 Developing Algorithms. Pick an answer to see if you got it, and why.

Code
PROCEDURE findMax(nums)
{
    max ← 0
    FOR EACH n IN nums
    {
        IF (n > max)
        {
            max ← n
        }
    }
    RETURN (max)
}
Question 1 of 4

The procedure findMax is intended to return the greatest value in a non-empty list of numbers. For which list does it NOT return the greatest value?

Question 2 of 4

Which two changes would make findMax return the greatest value for every non-empty list of numbers? Select two answers.

Select two answers. 0 of 2 chosen

Question 3 of 4

The list scores contains [80, 95, 70, 85]. What is displayed when the following code segment is run? total ← 0 FOR EACH s IN scores { total ← total + s } DISPLAY(total / LENGTH(scores))

Question 4 of 4

The two code segments below look alike. For which starting value of the integer x do they display different output? Segment IIF (x > 0) { x ← x - 1 } IF (x = 0) { DISPLAY("zero") } Segment IIIF (x > 0) { x ← x - 1 } ELSE { IF (x = 0) { DISPLAY("zero") } }

0 of 4 answered