Created: Wed 04 Sep 2012
Note: This is an approximate syllabus; it may change at any time.
- Lecture 01, Wed 09-05-12
- Introduction; admistrivia; overview of CS7800
- Four methods for computing the Fibonacci numbers
- Reading: CLRS 1 (skim)
- Lecture 02, Mon 09-10-12
- Analysis of algorithms; orders of growth
- Start recurrence review: substitution, iteration
- Reading: CLRS 2.2, 3, 4 (review),
Appendix A (review), Appendix C (review)
- Handouts:
- Lecture 03, Wed 09-12-12
- Finish recurrence review: recursion trees, master method
- Start average case analysis: quicksort
- Reading: CLRS 4 (review), 5 (review), 7.4
- Handouts:
- Homework 01 assigned
- Lecture 04, Mon 09-17-12
- Finish average case analysis
- Median and order statistics: expected and worst-case linear time
- Reading: CLRS 7.4, 9
- Lecture 05, Wed 09-19-12
- Lower bounds for sorting; sorting in linear time
- Introduction to dynamic programming
- Reading: CLRS 8.1-8.3, 15
- Information:
- Homework 01 due
- Homework 02 assigned
- Lecture 06, Mon 09-24-12
- Dynamic programming
- Reading: CLRS 15
- Handouts:
- Lecture 07, Wed 09-26-12
- Lecture 08, Mon 10-01-12
- Amortized analysis
- Reading: CLRS 17
- Lecture 09, Wed 10-03-12
- Lecture 10, Wed 10-10-12
- Data structures for disjoint sets: Union-Find
- Reading: CLRS 21
- Homework 04 due
- Lecture 11, Mon 10-15-12
- Graphs and graph algorithms: BFS, DFS, cycle detection
- Reading: CLRS 22
- Lecture 12, Wed 10-17-12
- Graph algorithms: DAGs, topological sort, strongly connected components
- Reading: CLRS 22
- Midterm exam assigned
- Lecture 13, Mon 10-22-12
- Minimum spanning trees: Prim, Kruskal
- Reading: CLRS 23
- Lecture 14, Wed 10-24-12
- Single-source shortest paths
- Reading: CLRS 24
- Midterm exam due
- Homework 05 assigned
- Lecture 15, Mon 10-29-12
- Finish SSSP; all-pairs shortest paths
- Reading: CLRS 24, 25
- Lecture 16, Wed 10-31-12
- Lecture 17, Mon 11-05-12
- Network flow
- Reading: CLRS 26
- Lecture 18, Wed 11-07-12
- Randomized algorithms, data structures, and analyses: BSTs
- Reading: CLRS 12.4
- Homework 06 due
- Lecture 19, Wed 11-14-12
- Lecture 20, Mon 11-19-12
- Linear programming
- Reading: CLRS 29
- Lecture 21, Mon 11-26-12
- Linear programming
- Reading: CLRS 29
- Lecture 22, Wed 11-28-12
- Approximation algorithms
- Reading: CLRS 35
- Homework 07 assigned
- Lecture 23, Mon 12-03-12
- Approximation algorithms
- Reading: CLRS 35
- Lecture 24, Wed 12-05-12
- Computational geometry
- Homework 07 due
- Final exam assigned
- Final Exam, Wed 12-11-12
Switch to:
jaa@ccs.neu.edu