### Course Schedule (Tentative)

Reading assignments are given according to the main text book (Cormen et al).
Recommended readings will be denoted as e.g. T1.1-4 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 1 9/2 Introduction. 1, Appendix A, B1-3; T1.1-4 slides 2 9/4 algorithms in the real world;  complexity   proving correctness   sorting: selection 2; Appendix C, B4-5 slides Discussion: big-O (and other letters); comparing growth rates 3 9/9 another example of reduction+greedy: insertion   divide & concur: mergesort, binary search 3 pg.49 is esp. useful slides 4 9/11 Recurrences, Master Theorem 4.3-4.4 5 9/16 QuickSort (and QuickSelect), Quicksort analysis  (divide&concur, probabilistic style) 7, 9 hw1 is due, slides 9/15: Last Day to ADD Classes 6 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" 7 9/23 data-structure approach: Priority Queue, PQ-sort   (Heapsort) Another PQ: Leftist heaps; lazy leftist heaps 6, T3 (esp. 3.3), (8) hw2 is due slides, special sorts: radix, bucket, etc.  lower bounds - how are the special sorts special? 8 9/25 Searching: Dictionary     link-list, array (binary search)     hash tables 10 11 Review: hashing (11) slides 9 9/30 Dictionary:  search tree 12 Review: trees (B.5), search-trees (12) 10 10/2 Dictionary: hash tables(cont), hashing analysis; birthday paradox 11 (5.4) hw3 is due; 10/6: Last Day to DROP Classes (without 'W') 11 10/7 Search trees: dynamics (insertions), keeping balance:  2-3-4 trees, Red-Black trees 13 slides 12 10/9 More Red-Black trees slides 10/14 No class (Monday schedule) 13 10/16 Dictionary+: augmented data structures Authenticated dictionaries hw4 is due; slides references: 1, 2 (see also this) 14 10/21 Introduction to Graph Algorithms Appendix B, 22 15 10/23 Midterm Self-review stack, queue, linked-list, pointers and rooted trees.(10) Notes for section; 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, round-robin [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 (Bellman-Ford) read intro to Ch.24 (up to 24.1) 26 12/4 All-Pairs 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: 9-11am