ICA-CP: 9/24/08 - More on algorithms

How do we turn a set of instructions into an algorithm?

State: Turning a set of tasks or instructions into an algorithm involves understanding the goal of the task, indentifying the start conditions for completing the task, and then breaking the task down into a series of sequential steps.

Elaborate: First we need to understand the activity for which we need to write a program. If we need to make a pizza, we would not want to create an algorithm for making a milkshake. We also need to identify what we have been given as a starting set of conditions -- and perhaps asking more questions if we do not have enough information. So, if we want to make a milkshake, we should have all the ingedients available to make a milkshake. In other words, we don't use cheese, pizza sauce, and pepperoni to make a milkshake. Once we have a clear picture of the task (step 1) and a clear set of starting conditions (step 2), then we start creating a set of steps to accomplish the task.

eXemplify: Here are the examples for the first four Karel the Robot assignments.
Assignment #1:
Step 1) Goal: Move Karel from Street 0, Avenue 14 to Street 0, Avenue 0.
Step 2) Start condition: Karel faces West
Step 3) Algorithm: Move Karel 14 steps.

Assignment #2:
Step 1) Goal: Move Karel from Street 0, Avenue 14 to Street 0, Avenue 0.
Step 2) Start condition: Karel faces South
Step 3) Algorithm: (Step 3a) Turn Karel left 3 times. Then, (Step 3b) move Karel 14 steps.

Assignment #3:
Step 1) Goal: Move Karel from Street 0, Avenue 14 to Street 0, Avenue 0.
Step 2) Start condition: Karel faces any of North, South,, West, or East.
Step 3) Algorithm: (Step 3a) Figure out which direction Karel is facing. (Step 3b) Turn Karel left enough times to face West. (Step 3c) Move Karel 14 steps.

Assignment #4:
Step 1) Goal: Move Karel from Street 0, Avenue 14 to Street 0, Avenue 0 picking up all the beepers along Street 0. (Please note: This means we do not pick up beepers that are in any other row than Street 0.)
Step 2) Start condition: Karel faces West
Step 3) Algorithm: (Step 3a) Check if Karel is next to a beeper. (Step 3b) If Karel is next to a beeper, then pick it up. (Step 3c) Move 1 step. (Step 4c) Repeat the series of steps 3a, 3b, and 3c fourteen times.

One note: Only do what is needed to accomplish the task or activity. For example, if the activity is to make a chocolate dessert pizza, do not add extras (like anchovies) to the pizza.

Illustrate:
Creating an algorithm is like making S'mores (understanding the task), identifying the start conditions (ingredients available? heat source = campfire, oven, or microwave?), and then identifying the steps needed to actually "cook" something to eat. I don't want to make brownies if I'm supposed to make S'mores (understaning the task). I may have a campfire instead of a microwave (starting conditions). I don't melt the marshmellow and chocoate until I've put them between two graham crackers (creating the steps).