| 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.
Divide-and-conquer (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 worst-case algorithm for finding the k-th
smallest element (the selection problem).
|
| Lecture 5 (Jan 20) |
Lower bounds via decision trees.
Proofs of lower bounds for average and worst-case
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 n-1 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 least-common-ancestor (LCA)
and range-min 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 j-th 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 red-black trees.
Main properties of red-black trees.
|
| Lecture 12 (Feb 12) |
Assignment 3 due.
Discussion of the main operations on red-black trees:
insert, delete, join, split.
Definition of AVL tree, 2-3 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. Level-linked red-black 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 red-black trees,
binary addition.
|
| Lecture 15 (Feb 24)
|
Assignment 4 due.
Potential functions continued.
Weight-balanced 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.
k-ary heaps (determining best k).
Pointer-based 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.
Depth-first search.
|
| Lecture 20 (Mar 19)
|
Assignment 6 due.
Depth-first search, continued. Finding cycles.
Euler tours.
Breadth-first 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.
Prim-Dijkstra 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.
All-pairs shortest path problem.
Floyd-Warshall 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 Gale-Shapley algorithm.
1.5-Approximation 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:
Karp-Rabin algorithm,
Knuth-Morris-Pratt algorithm.
|