Week 
Date 
Lecture topics 
Additional resources/comments 
14 
Dec 1 
33: Main ideas and basic concepts (Chap 34)
 Sample Final 
Dec 3 
Review of Final
Assignment #5 due in class 
Assignment #5 back on Dec 10, from my office (Marker: Amin) 

Dec 12 
2:004:00pm: Final Exam in CAB 269 
Grades preassigned by Dec 18, finalized by Dec 22 
1 
Sep 3 
1: Course introduction, basic concepts (Chap 1.1) 

Sep 5 
2: Getting started with insertion sort (Chap 1.2, 2.1, 2.2) 
Assignment #1 on Chapters 13, ready in moodle 
2 
Sep 8 
3: Insertion sort: analysis (Chap 2.2) 
L.I. swapped to Lecture 2 
Sep 10 
4: Merge sort: analysis (Chap 2.3); big O (Chap 3.1) 

Sep 12 
5: Growth of functions (Chap 3.1, 3.2, Appendix A) 

3 
Sep 15 
6: Recurrence and iterated substitution (Chap 2.3, 4.1) 
Assignment #2 on Chapters 4, 6, 7, ready in moodle 
Sep 17 
7: More iterated substitution, recursion tree method (Chap 4.2) 

Sep 19 
8: Iterated substitution leading to Master Theorem (Chap 4.3, 4.4.1) 
No Chap 4.4.2; Today covered only the first 6 slides 
4 
Sep 22 
9: More dicussion on Master Theorem, and heaps (Chap 4.3, 6.1)
Assignment #1 due in class 

Sep 24 
10: Heap properties & construction, heapsort algorithm (Chap 6.2, 6.3, 6.4) 

Sep 26 
11: More discussion on heapsort, priority queue (Chap 6.4, 6.5) 

5 
Sep 29 
12: Quicksort algorithm, correctness (Chap 7.1) 
Assignment #1 back (Marker: HsiuChin) 
Oct 1 
13: Quicksort: WC & BC running time (Chap 7.2) 

Oct 3 
14: Quicksort: AC running time, and a randomized version (Chap 7.3, 7.4) 
Assignment #3 on Chapters 8.1, 15, ready in moodle 
6 
Oct 6 
15: Two kinds of trees and decision tree lower bound (Chap 8.1)
Assignment #2 due in class 

Oct 8 
16: Dynamic programming concepts w/Fibonacci numbers (Page 56, Chap 15.1) 

Oct 10 
Midterm #1 review 

7 
Oct 13 
Thanksgiving 
Oct 15 
Midterm #1 in class (Coverage: Assignments 1 & 2) 
Assignment #2 back Tuesday (Marker: Babak) 
Oct 17 
17: Matrixchain multiplication, DP characteristics (Chap 15.2, 15.3) 

8 
Oct 20 
18: Longest common subsequence (Chap 15.4) 

Oct 22 
19: An activityselection, or scheduling, problem (Chap 16.1)
Assignment #3 due in class 
Assignment #4 on Chapters 16 & 22, ready in moodle 
Oct 24 
20: Elements of the greedy strategy (Chap 16.2) 

9 
Oct 27 
21: Graph notions and BreadthFirstSearch (Appendix B.4, Chap 22.12) 
Slides 79 skipped 
Oct 29 
22: BreadthFirstSearch (Chap 22.2) 
Assignment #3 back (Marker: HsiuChin) 
Oct 31 
23: DepthFirstSearch (Chap 22.3) 

10 
Nov 3 
24: Biconnected components (undirected version of Chap 22.5) 
Sample Midterm #2 (no solutions will be posted) 
Nov 5 
25: Topological sort (Chap 22.4) 
Assignment #5 on Chapters 2325, ready in moodle 
Nov 7 
26: Greedy algorithms and the MST problem (Chap 23.1)
Assignment #4 due in class 

11 
Nov 10 
Fall term class break 
Nov 12 
27: Prim's & Kruskal's MST algorithms (Chap 23.2) 

Nov 14 
Review of Midterm #2
 Assignment #4 back (Marker: Babak) 
12 
Nov 17 
Midterm #2 in class (Coverage: Assignments 3 & 4) 

Nov 19 
28: Kruskal's MST algorithm (Chap 23.2) 

Nov 21 
29: SSSP problem and BellmanFord's algorithm (Chap 24.1) 

13 
Nov 24 
30: Prim's MST algorithm and Dijkstra's SSSP algorithm (Chap 24.23) 

Nov 26 
31: APSP problem and the first algorithm (Chap 25.1) 

Nov 28 
32: FloydWarshall's APSP algorithm (Chap 25.2) 
