Lectures in CS252--Winter 2018


The schedule may be updated from time to time, as we progress. CLR refers to Cormen, Leiserson and Rivest.

Lecture 1 (Jan 9) General introduction. Definition of an algorithm. Examples of simple computer models: Turing model, RAM model, pointer based machines, oracles, comparison model. Uniformly bounded time, bit model of computation (or: logarithmic model). Definition and examples of an oracle. Chapter 1 in CLR, web pages from 1997. The Fibonacci example: introduce recursion, iteration, and fast exponentiation. Fast exponentiation. Check here for some notes by David Eppstein.
Lecture 2 (Jan 11) Landau symbols: O, Omega, Theta, small o, small omega. Examples of many complexity classes (linear, quadratic, polynomial, exponential). We covered all of chapter 2 and part of chapter 3 of CLR. Introduction to recurrences. The divide-and-conquer solution to Problem 4.7 (chip testing). Exercise: Show that our chip testing algorithm takes only O(n) time even if n is not a power of two. Divide-and-conquer (Karatsuba) multiplication. Mergesort, convex hulls in the plane. Exercise: Describe in algorithmic form the linear time upper hull merge algorithm described in class.
Lecture 3 (Jan 16) Illustrate induction on the chip testing recurrence. Recurrence for binary search with binary and ternary oracles, and solution by induction for the ternary oracle. Exercise: For binary search using a binary oracle, show that T(n) is not more than 2 + ceiling(log_2 n). The master theorem (statement only). Recursion tree to explain the master theorem. Strassen matrix multiplication. Assignment 1 handed out. Due January 25, 2018, 8:30am.
Lecture 4 (Jan 18) Euclid's algorithm. Exercise: Show that the bit complexity of gcd(n,m) is O(log n . log m). Ham-sandwich and pancake theorems and halfspace counting. The induction method illustrated on mergesort. Linear time selection: finding the k-th smallest by the algorithm of Blum, Floyd, Pratt, Rivest and Tarjan. Exercise: Look at the median-of-3 version of this algorithm and show, by using recursion trees, that its complexity is big theta of n log n.