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 divideandconquer 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.
Divideandconquer (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).
Hamsandwich and pancake theorems and halfspace counting.
The induction method illustrated on mergesort.
Linear time selection: finding the kth smallest
by the algorithm of Blum, Floyd, Pratt, Rivest and Tarjan.
Exercise: Look at the medianof3 version of this algorithm
and show, by using recursion trees, that its complexity is
big theta of n log n.
