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
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

hw1 is due, slides
9/15: Last Day to ADD Classes

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
slides, special sorts: radix, bucket, etc.
 lower bounds - how are the special sorts special?

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;
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

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)

14

10/21
Introduction to Graph Algorithms Appendix B, 22  
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