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.)

1. Repeat until only one box remains:
1. Split boxes into equally sized piles
2. Place one pile on each side of scale
3. If left side of scale is heavier:
1. Discard boxes on right side of scale
2. Retain boxes on left side of scale
4. Otherwise, right side of scale is heavier:
1. Discard boxes on left side of scale
2. 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?