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

Lecture 1 (Jan 6)

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.

Exercise mentioned during the lecture:

• Show that (log n)^1000 = o(n^0.001), n^1000=o(1.001^n), and 1000^n = o(n!).
• Show that n ln (n) / ln (n!) -> 1 as n -> infinity.

Exercise to chew on, but not mentioned in class:

• 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.
• Determine in Big Theta notation the bit model time complexities of the recursion method, the array method, and the fast exponentiation method in the Fibonacci example. In class, we only did the RAM model complexities.

Lecture 2 (Jan 8)

Assignment 1 handed out: this handwritten assignment is due on January 20 at 1:05 pm, in class.

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 outlined in class.

Exercises not mentioned during the lecture:

• One student asked if bad chips would have to lie. If they have to lie, then the problem is done with n-1 tests. Do you see that?