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 |
| 9/2 |
Introduction. | 1, Appendix A, B1-3; T1.1-4 |
slides | |
| 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 |
|
| 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.3-4.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 |
data-structure approach: Priority Queue,
PQ-sort (Heapsort) Another PQ: Leftist heaps; lazy leftist heaps |
6, T3 (esp. 3.3), (8) | hw2
is due |
|
| 9/25 |
Searching: Dictionary link-list, array (binary search) hash tables |
10 11 |
Review: hashing (11) slides |
|
| 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; |
| 11 |
10/7 |
Search trees: dynamics (insertions), keeping balance: 2-3-4 trees, Red-Black trees |
13 | |
| 10/9 |
More Red-Black 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 |
|
Self-review stack, queue, linked-list,
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, 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 |