The solution to the dirty sock problem can be specified by the following algorithm:
(Pre-condition: The number of boxes is a power of 2; only one box has a dirty sock.)
- Repeat until only one box remains:
- Split boxes into equally sized piles
- Place one pile on each side of scale
- If left side of scale is heavier:
- Discard boxes on right side of scale
- Retain boxes on left side of scale
- Otherwise, right side of scale is heavier:
- Discard boxes on left side of scale
- Retain boxes on right side of scale
There are three control structures in algorithms:
- Sequence: Start with the first statement, proceed to next, and so on
(i.e. Do this, then that, then the next thing).
- Selection: One path of execution is selected from multiple potential
paths (i.e. Do this or that, depending on a condition).
- Repetition: A set of instructions is executed multiple times until
some condition terminates the repetition (i.e. Do this over and over until a condition is met)
Can you find an instance of each control structure in the dirty sock algorithm?