|Lecture 1 (Jan 9)
||General introduction. Definition of an algorithm.
Examples of simple computer models:
Turing model, RAM model, pointer based machines, oracles,
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.
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)
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.