CLR refers to Cormen, Leiserson, Rivest and Stein: "Introduction to Algorithms (Third Edition)".

Lecture 1 (Jan 7)

General introduction. Definition of an algorithm. Examples of simple computer models: Turing model, RAM model, pointer based machines, comparison model. RAM model (or uniform cost model), bit model (or: logarithmic cost model). Definition and examples of oracles (not done explicitly),. The Fibonacci example: introduce recursion, iteration (the array method), and fast exponentiation. Worst-case time complexity. Landau symbols: O, Omega, Theta, small o, small omega. Examples of many complexity classes (linear, quadratic, polynomial, exponential).

Resources:

• CLR, chapters 1, 2 and 3.
• Notes by David Eppstein on the computation of Fibonacci numbers.
• Scribed notes on Landau symbols.
• Handwritten notes for lecture 1 on myCourses.

Exercise mentioned during the lecture:

• Show that for the fast exponentiation method in the RAM model, T_n = O(log(n)) even if n is not a power of 2.
• Show that (log n)^1000 = o(n^0.001), n^1000=o(1.001^n), and 1000^n = o(n!).

Exercise to chew on, but not mentioned in class:

• Determine in Big Theta notation the bit model time complexities of the recursion method, the array method, and the fast exponentiation method. In class, we only did the RAM model complexities.

Lecture 2 (Jan 9)

Introduction to the divide-and-conquer principle. Fast exponentiation revisited. Introduction to recurrences. The divide-and-conquer solution to the chip testing problem in CLR. Divide-and-conquer (Karatsuba) multiplication. Mergesort, convex hulls in the plane. We covered all of chapter 2 and part of chapter 3 of CLR.

Resources:

• CLR, chapter 4.
• Scribed notes on divide-and-conquer (part I).

Exercises mentioned during the lecture:

• Describe in algorithmic form the linear time upper hull merge algorithm described in class.

Lecture 3 (Jan 14)

Binary search using a ternary oracle (with analysis by the substitution method). Strassen matrix multiplication. The master theorem (statement only). Recursion tree to explain the master theorem. Ham-sandwich and pancake theorems and halfspace counting.

Resources:

• CLR, chapter 4.
• Scribed notes on divide-and-conquer (part II).

Lecture 4 (Jan 16)

Linear time selection: finding the k-th smallest by the algorithm of Blum, Floyd, Pratt, Rivest and Tarjan. O(n) complexity proof based on induction. Linear expected time selection by Hoare's algorithm "FIND". The induction method illustrated on mergesort. Euclid's algorithm for the greatest common divisor.

Resources:

• CLR, chapter 9.
• Scribed notes on divide-and-conquer (part III).

Exercises mentioned during the lecture:

• For the binary search algorithm with ternary oracle, show by induction on n that the worst-case number of comparisions T_n satisfies T_n <= ceiling ( log_2 (n+1) ) for all n.
• For the binary search algorithm with binary oracle, show by induction on n that the worst-case number of comparisions T_n satisfies T_n <= 2 + ceiling ( log_2 (n) ) for all n. Convince yourself that T_1 =2, and that T_n = 1 + T_{floor ( (1+n)/2 )}.
• Show that the bit complexity of Euclid's algorithm for gcd (n,m) is O( log n . log m ).

Lecture 5 (Jan 21)

Assignment 1 due at 4 pm on myCourses. Assignment 2 handed out (on myCourses). Due January 30, 2025, 4 pm. The Fast Fourier Transform. Multiplying polynomials in time O(n log n).

Resources:

• CLR, chapter 30.
• Printed notes posted on myCourses.

Lecture 6 (Jan 23)

Dynamic programming. Computing binomial coefficients and partition numbers. The traveling salesman problem. The longest common subsequence problem. The knapsack problem.

Resources:

• Scribed notes on dynamic programming. These notes have a bit more than we will see in class.