Date

Topic

Readings

Notes

Jan 18
Introduction, Class overview,
RAM model, Worst-case complexity,
Insertion sort, and Asymptotics
Chapter 1, Section 2.1, 2.2 and 3.1
Note 1
Jan 23
Asymptotics, Induction,
Divide and conquer, Merge sort,
Recurrence, Recursion tree
Section 2.3 and 3.2
Sort with dance
Sorting algorithms in six minutes
Note 2
Jan 25
Binary search, Powering, Matrix
multiplication, Strassen's algorithm
Master theorem
Section 4.2, 4.3 and 4.5
Note 3
Jan 30
Randomized algorithms
Quicksort and its analysis
Chapter 5, Section 7.1 and 7.2
Appendix C for basics of probability
Note 4
Feb 1
Randomized Quicksort
Sectioin 7.3 and 7.4
Note 5
Feb 6
Selection in linear time, and
Lower bound on comparison sorts
Section 9.2, 9.3 and 8.1
Note 6
Feb 8
Counting sort and Radix sort
Hash tables and hash functions
Section 8.2 and 8.3
Section 11.1 and 11.2
Note 7.1
Note 7.2
Feb 13
Universal hashing
Section 11.3.3
Note 8
Feb 15
Perfect hashing and
Binary search trees
Section 11.5 and Chapter 12
Note 9.1
Note 9.2
Feb 20
Red-Black trees
Chapter 13
Note 10
Feb 22
Augmenting data structures
Order statistics, Interval trees
Chapter 14
Note 11
Feb 27
Greedy algorithms
Activity selection
Section 16.1 and 16.2
Note 12
Mar 1
Greedy: Huffman trees,
Dynamic programming: Rod cutting
Section 16.3 and 15.1
Note 13
Mar 6
Dynamic programming: Longest
common subsequence
Section 15.3 and 15.4
See Note 13
Mar 8
Midterm in class
FAY 313 and MUDD 1127


Spring Recess, Mar 13 -- Mar 17


Mar 20
Dynamic programming: Optimal
binary search tree; midterm problems
Section 15.5
Note 14
Mar 22
Amortized analysis
Chapter 17
Note 15
Mar 27
Graphs and Breadth-first search
Section 22.1 and 22.2
Note 16
Mar 29
Breadth-first search and its correctness
Section 22.2
See Note 16
Apr 3
Depth-first search and Topological sort
Section 22.3 and 22.4
Note 17
Apr 5
Strongly connected componentsMinimum spanning tree: the generic method
Section 22.5 and Section 23.1
Note 18
Apr 10
Minimum spanning trees:
Kruskal and Prim
Chapter 23 and Section 21.1-2
Note 19
Apr 12
Single-source shortest path:
Bellman-Ford and Dijkstra
Chapter 24
Note 20
Apr 17
All-pairs shortest paths
Chapter 25
Note 21
Apr 19
Maximum Flow: Ford-Fulkerson
Section 26.1 and 26.2
Note 22
Apr 24
Edmonds-Karp, and
Maximum bipartite matching
Section 26.2 and 26.3
Note 23
Apr 26
NP-completeness
Chapter 34
Note 24
May 1
NP-completeness
Chapter 34
Note 25

Final exam
7:10-10pm on Monday May 8