Lecture 1 (Jan 6) 
General introduction. Definition of an algorithm.
Examples of simple computer models:
Turing model, RAM model, pointer based machines,
comparison model.
Uniformly bounded time, bit model of computation
(or: logarithmic model).
Landau symbols: O, Omega, Theta, small o, small omega.
Polynomial versus exponential time classes.
Chapter 1 in CLR.
The Fibonacci example: introduce recursion, dynamic programming,
and fast exponentiation. The Russian peasant method.
Check here for some notes by David Eppstein.

Lecture 2 (Jan 8) 
We covered all of chapter 2
and part of chapter 3 of CLR.
Some discussion of complexity classes.
Introduction to recurrences.
Solutions of simple recurrences.
Binary search.
Mergesort.
Recursive solution for convex hulls in the plane.
Divideandconquer (Karatsuba) multiplication.
Master theorem.
Recursion tree to explain the master theorem.

Lecture 3 (Jan 13) 
The chip testing problem.
Ulam's problem (finding an integer with an incorrect oracle).
Strassen matrix multiplication.
Euclid's algorithm.
Hand out assignment 1, due January 22, 2014.

Lecture 4 (Jan 15) 
Solving recurrences by induction: mergesort.
Linear worstcase algorithm for finding the kth
smallest element (the selection problem).

Lecture 5 (Jan 20) 
Lower bounds via decision trees.
Proofs of lower bounds for average and worstcase
time based on decision trees (take notes).
Part of the material is in section 9.1.
Examples include sorting, searching, and Mastermind.
The reduction method: lower bound of n log n for finding the
convex hull in the plane.

Lecture 6 (Jan 22) 
Lower bounds via witnesses and adversaries:
finding the maximum,
finding maximum and minimum.
Finding the median.
Merging sorted sets by using finger lists.
Hand out assignment 2, due February 3, 2014.

Lecture 7 (Jan 27) 
Introductory remarks about ADTs (abstract data types).
Lists.
Chapter 11 of CLR: primitive data structures
such as stacks, queues, deques, and lists.
We deviate only slightly from this chapter.
For the notation for list operations, chapter 1 of
Data Structures and Network Algorithms
(R.E. Tarjan, SIAM, Philadelphia, 1983).
Classification and use of linked lists.
Introduction to trees:
free trees, rooted trees,
ordered trees, position trees, binary trees.
Counting binary trees: Catalan's formula.
Coding of binary trees.

Lecture 8 (Jan 29) 
Preorder, postorder, inorder traversals and representations.
Correspondence between forests of ordered trees and binary trees.
Correspondence between ordered trees on n nodes and binary trees on n1 nodes.
Complete binary trees: implementation, path properties, height.
Heavy and light edge decomposition of a tree.
Finding the least common ancestor in O(log n) time given the heavy/light edge decomposition.

Lecture 9 (Feb 3) 
Handout on various algorithms for the leastcommonancestor (LCA)
and rangemin query (RMQ) problems.
Hand out assignment 3, due February 12, 2014.

Lecture 10 (Feb 5) 
Introduction to the ADT Dictionary.
Cartesian trees with as special cases, binary
search tree, treap, and random binary search tree.
Binary search trees: chapter 13 of CLR.
Standard operations, all taking time O(h).
Searching with an oracle.
Inorder traversal, insertion sort.
Treap operations.
Analysis of expected depth of the jth ranked
node in a treap.

Lecture 11 (Feb 10) 
Course notes on Cartesian trees and treaps handed out.
Analysis of delete, insert, and join in a treap.
Definition of a pagoda.
Analysis of quicksort.
Definition of redblack trees.
Main properties of redblack trees.

Lecture 12 (Feb 12) 
Assignment 3 due.
Discussion of the main operations on redblack trees:
insert, delete, join, split.
Definition of AVL tree, 23 tree.
Hand out assignment 4, due February 24, 2014.

Lecture 13 (Feb 17)

Augmented data structures.
This is nicely described in CLR (chapter 15).
Examples:
 (1) Combining search trees and ordered linked lists.
 (2) Order statistics trees. Operations rank and selection.
 (3) Interval trees. VLSI chip layout application. Sweepline paradigm.
 (4) Browsing operation. Levellinked redblack trees.
 (5) Combining search trees and heaps.

Lecture 14 (Feb 19)

Introduction to amortized analysis.
Potential functions.
Simple examples: stack with multipop,
dynamic tables,
lazy delete in redblack trees,
binary addition.

Lecture 15 (Feb 24)

Assignment 4 due.
Potential functions continued.
Weightbalanced search trees (handout).
Splay trees (handout).
Hand out assignment 5, due March 10, 2014.

Lecture 16 (Feb 26)

Splay trees (continuation).
Priority queues.
Tournament trees (handout pending).
Binary heaps (chapter 7 of CLR).
Heapsort. Additional binary heap operations.
kary heaps (determining best k).
Pointerbased implementation of binary heaps.

Lecture 17 (Mar 10)

Assignment 5 due.
Binomial heaps. Fibonacci heaps.
Hand out assignment 6, due March 19, 2014.

Lecture 18 (Mar 12)

Fibonacci heaps, continued.
Disjoint set data structures: chapter 22 of Cormen.

Lecture 19 (Mar 17)

Introduction to graphs.
Depthfirst search.

Lecture 20 (Mar 19)

Assignment 6 due.
Depthfirst search, continued. Finding cycles.
Euler tours.
Breadthfirst search.
Detecting bipartite graphs.
Hand out assignment 7, due March 26, 2014.

Lecture 21 (Mar 21)

Shortest path properties.
Shortest path problem. Dijkstra's algorithm.
Minimal spanning tree.
PrimDijkstra method.
Brief mention of Kruskal's method.

Lecture 22 (Mar 24)

Directed acyclic graphs. Topological sorting.
NIM games. PERT networks.
Strongly connected components in directed graphs.

Lecture 23 (Mar 26)

Assignment 7 due.
Allpairs shortest path problem.
FloydWarshall algorithm (dynamic programming).
Bushfire algorithm.
Transitive closure via strongly connected component decomposition.
Transitive closure by matrix multiplication.

Lecture 24 (Mar 31)

Hand out assignment 8, due April 2, 2014.
Introduction to matchings.
Stable matchings. The GaleShapley algorithm.
1.5Approximation for the traveling salesman
tour via maximal weighted matchings and
Christofides's algorithm.
Maximum bipartite weighted matching / the
assignment problem: introduction.

Lecture 25 (Apr 2)

Assignment 8 due.
Pattern matching:
KarpRabin algorithm,
KnuthMorrisPratt algorithm.
