COMP 1104 · The Beauty of Algorithms

Led by Knuthian Algorithm Simulacrum

Why is one correct algorithm beautiful and another ugly? Economy, generality, surprise, clarity — applied. Based on Knuth.

1. Module 1

   What Is Algorithmic Beauty?

   Led by Knuthian Algorithm Simulacrum

   The question

   Economy, generality, surprise, clarity — these are the four criteria. What is the difference between a beautiful algorithm and a merely clever one? Knuth says cleverness shows off; beauty is inevitable.

   Outcome

   The student can state and apply Knuth's four beauty criteria.

   Sub-units

   1. ○ 1.1 The Four Criteria Open this unit → ✓ ↻
   2. ○ 1.2 Beauty vs Cleverness Open this unit → ✓ ↻
   Begin the course → Print certificate of completion
2. Module 2

   Euclid's Algorithm: 2300 Years of Beauty

   Led by Knuthian Algorithm Simulacrum

   The question

   Euclid's algorithm for the GCD is 2300 years old. Nothing has improved it. Its proof is its algorithm — they are the same object. Why has no one done better?

   Outcome

   The student can implement and prove Euclid's algorithm and explain its optimality.

   Sub-units

   1. ○ 2.1 Implement and Prove Open this unit → ✓ ↻
   2. ○ 2.2 Essay: Why Has Nothing Improved It? Open this unit → ✓ ↻
   Open this module → Print certificate of completion
3. Module 3

   The Fast Fourier Transform: Beauty at Scale

   Led by Knuthian Algorithm Simulacrum

   The question

   The FFT insight: the DFT of n points equals two DFTs of n/2 points. This single observation reduces O(n²) to O(n log n) and underlies every digital communication system. Why did it take until 1965?

   Outcome

   The student can explain the FFT's divide-and-conquer structure and two applications.

   Sub-units

   1. ○ 3.1 The Central Insight Open this unit → ✓ ↻
   2. ○ 3.2 Applications Open this unit → ✓ ↻
   Open this module → Print certificate of completion
4. Module 4

   Two Solutions, One Problem: Beauty vs Correctness

   Led by Knuthian Algorithm Simulacrum

   The question

   Fibonacci by recursion (beautiful definition, exponential time), iteration (prosaic but linear), or matrix exponentiation (mathematically deep, O(log n)). Which is most beautiful — and is the most beautiful algorithm always the one to use?

   Outcome

   The student can analyse three algorithms by beauty criteria and articulate why beauty does not always mean practicality.

   Sub-units

   1. ○ 4.1 Three Analyses Open this unit → ✓ ↻
   Open this module → Print certificate of completion
5. Module 5

   Can Beauty Be Taught?

   Led by Knuthian Algorithm Simulacrum

   The question

   Can algorithmic taste be taught — or only recognised? And does it matter whether the code is beautiful if it runs correctly?

   Outcome

   The student can take a defended position on whether algorithmic beauty matters practically.

   Sub-units

   1. ○ 5.1 Final Essay: Does Beauty Matter? Open this unit → ✓ ↻
   Open this module → Print certificate of completion