AP Computer Science Principles · Unit 3 lecture · Part 7 of 14 · 10 min

3.9 Developing algorithmsMany ways to solve it, and the robot

Mr. Thompkins
You now have all three ingredients: sequencing, selection and iteration. Every algorithm ever written is some mix of them. Let's use them to build things, and meet the exam's favorite character, the robot.

Algorithms can be written in different ways and still accomplish the same task. Algorithms that look almost the same can produce different results or side effects. Some conditional statements can be rewritten as equivalent Boolean expressions, and some Boolean expressions can be rewritten as other, equivalent Boolean expressions. The exam often shows two versions of code and asks whether they always do the same thing.

1IF (a > b)2{3  big ← a4}5ELSE6{7  big ← b8}
Version A: the larger of a and b.
1big ← a2IF (b > big)3{4  big ← b5}
Version B: assume a, then replace it if b is bigger.

Are A and B equivalent? Test the cases: a bigger, b bigger, and the tie. If a = b, A goes to the ELSE and sets big to b, while B keeps big as a. Since a and b are equal, both give the same value. So yes, they always produce the same result. Checking the tie is the step people skip, and it's where non-equivalent versions usually differ.

?Wait, how do I decide whether two code segments are equivalent?
Try inputs from every case: each branch of each IF, the boundaries, and ties. If any one input gives different results, they aren't equivalent. If all the cases agree, explain why they must always agree.

You don't have to invent every algorithm from scratch. Algorithms can be created from an idea, by combining existing algorithms, or by modifying existing ones. The course expects you to know a few building blocks: finding the maximum or minimum of two or more numbers, computing a sum or an average, deciding whether one integer is evenly divisible by another (n MOD d = 0), and finding a robot's path through a maze. Using existing correct algorithms as building blocks saves development time, reduces testing, and makes errors easier to find.

The robot

Robot questions show a grid of squares. The robot sits in one square, facing a direction. Dark squares are blocked. The reference sheet gives four commands.

CommandWhat the robot does
MOVE_FORWARD()One square in the direction it faces
ROTATE_LEFT()Turns 90° left, staying in its square
ROTATE_RIGHT()Turns 90° right, staying in its square
CAN_MOVE(direction)true if the square to its left, right, forward or backward is open
Blocked or off the gridThe robot stays put and the program ends
The robot commands. Directions are always from the robot's point of view.
?Wait, which way is "left" for the robot?
The robot's own left, not yours. If the robot faces down the page, its left is your right. The safest habit: turn your paper (or your head) so you face the way the robot faces, and write its square and direction after every line.
Pause and think
A robot faces right. It runs ROTATE_LEFT() three times. Which way does it face now? What single command would do the same?
I thought about it. Show me
Left turns from right: up, then left, then down. It faces down. Three left turns equal one right turn, so ROTATE_RIGHT() does the same.
Trace the robot
The robot starts in the bottom-left square facing up. Where does it end, and which way does it face?
The start: bottom-left square, facing up. Dark squares are blocked; green is the goal.
  1. Line 1 checks CAN_MOVE(forward) before each pass. Facing up from the bottom row, the square above is open, so it moves up one.
    Why?
    REPEAT UNTIL (NOT CAN_MOVE(forward)) means "keep moving while the square ahead is open".
  2. It moves up again: now it's in the middle row. The square above that is blocked, so CAN_MOVE(forward) is false, NOT false is true, and the loop stops.
  3. ROTATE_RIGHT(): from facing up, the robot now faces right.
  4. REPEAT 2 TIMES MOVE_FORWARD(): two squares right. It ends in the middle row, third column: the goal square, facing right.
    Why?
    Write the square and direction after every line. Robot questions are lost by one wrong turn.

Answer: It ends on the goal square, middle row and third column from the left, facing right.

1REPEAT UNTIL (NOT CAN_MOVE(forward))12{3  MOVE_FORWARD()4}5ROTATE_RIGHT()26REPEAT 2 TIMES7{8  MOVE_FORWARD()9}
  1. line 1 Keep going until the square ahead is blocked
  2. line 5 A right turn from the robot's point of view
The robot's program.
The path the robot takes: up two squares until blocked, turn right, two squares right.
Stuck? Get a hint
  1. Start by moving up. When is the square ahead blocked?
  2. After the loop, turn right from the robot's view: up becomes right.
  3. Then count two squares to the right.
Check yourself
Which code segment sets isDiv to true exactly when the whole number n is evenly divisible by 4?
  1. AisDiv ← (n / 4 = 1)
  2. BisDiv ← (n MOD 4 = 0)
  3. CisDiv ← (4 MOD n = 0)
  4. DisDiv ← (n MOD 4 = 4)
Show the answer

B. n is divisible by 4 when n ÷ 4 leaves no remainder: n MOD 4 = 0. Notice that a Boolean expression can be assigned directly to a variable; no IF is needed.

  • Different algorithms can solve the same problem; similar-looking ones can give different results.
  • Check equivalence on every case, especially boundaries and ties.
  • Know the building blocks: max/min, sum/average, divisibility (MOD), robot paths.
  • Robot: directions are from the robot's view. Blocked or off-grid moves end the program.