Reading assignments are given according to the main text book (Cormen et
al).
Recommended readings will be denoted as e.g. T1.14 for sections 1 through
4 in the 1st chapter in Tarjan's book.
The more tentative part of the schedule will be marked in gray; in particular the hw
assignments that are not yet finalized.
Lec#  Date 
Topic and/or Event  Reading  Notes 
9/2 
Introduction.  1, Appendix A, B13; T1.14 
slides  
9/4 
algorithms in the real world; complexity proving correctness sorting: selection 
2; Appendix C, B45  slides Discussion: bigO (and other letters); comparing growth rates 

9/9 
another example of reduction+greedy:
insertion divide & concur: mergesort, binary search 
3 pg.49 is esp. useful 
slides 

9/11 
Recurrences, Master Theorem  4.34.4  
9/16 
QuickSort
(and QuickSelect), Quicksort
analysis (divide&concur, probabilistic style) 
7, 9  
9/18 
Probabilistic (randomized) algorithms Randomized Quick Select analysis + hiring prob 
5 (sec.5.4 is optional), 9  slides "3 cups" game origin (play the game on the page! ;). Also here, or here, or google for "Monty Hall, Savant" 

9/23 
datastructure approach: Priority Queue,
PQsort (Heapsort) Another PQ: Leftist heaps; lazy leftist heaps 
6, T3 (esp. 3.3), (8)  hw2
is due 

9/25 
Searching: Dictionary linklist, array (binary search) hash tables 
10 11 
Review: hashing (11) slides 

9/30 
Dictionary: search tree  12  Review: trees (B.5), searchtrees (12)  
10 
10/2 
Dictionary: hash tables(cont), hashing analysis; birthday paradox 
11 (5.4) 
hw3
is due; 
11 
10/7 
Search trees: dynamics (insertions), keeping balance: 234 trees, RedBlack trees 
13  
10/9 
More RedBlack trees  slides  

10/14 
No class (Monday schedule) 


10/16 
Dictionary+: augmented data structures Authenticated dictionaries 
hw4
is due; slides references: 1, 2 (see also this) 

10/21 
Introduction to Graph Algorithms  Appendix B, 22  
10/23 
Midterm 

Selfreview stack, queue, linkedlist,
pointers and rooted trees.(10) 

16 
10/28 
Graph algorithms (MST preview)  22  
17 
10/30 
Disjoint sets  21, 17  hw5 is due 
18 
11/4 
Amortized analysis;  
19 
11/6 
MST (Kruscal)  23  hw6 is due 
20 
11/11 
no class  11/10: Last day to DROP classes (with 'W')  
21 
11/13 
Disjoint sets (take 2  now with amortized performance)  hw7 is due 11/13  
22 
11/18 

23 
11/20 
MST (Prim, roundrobin [Tarjan])  23  hw8 is due 
24 
11/25 
MST (Prim) & Shortest Path (Dijkstra)  24.3  
11/27 
No class (Thanksgiving)  
25 
12/2 
Shortest Path (BellmanFord)  read intro to Ch.24 (up to 24.1)  
26 
12/4 
AllPairs Shortest Path; Hard problems: from Shortest Path to Longest Path 
24, 25  hw9 is due 
27 
12/9 
dynamic programming  15  
12/11 


12/19 Friday 
Final Exam: 911am 