Created: Sun 03 Sep 2006
Last modified:
Note: This is an approximate syllabus; it may change at any time.
- Lecture 01, Wed 09-06-06
- Introduction; admistrivia; overview of CSG713
- Four methods for computing the Fibonacci numbers
- Reading: CLRS 1 (skim)
- Homework 00 assigned
- Lecture 02, Mon 09-11-06
- 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-13-06
- Finish recurrence review: recursion trees, master method
- Start average case analysis: quicksort
- Reading: CLRS 4 (review), 5 (review), 7.4
- Handouts:
- Homework 00 due
- Homework 01 assigned
- Lecture 04, Mon 09-18-06
- Finish average case analysis
- Median and order statistics: expected and worst-case linear time
- Reading: CLRS 7.4, 9
- Lecture 05, Wed 09-20-06
- 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-25-06
- Dynamic programming
- Reading: CLRS 15
- Handouts:
- Lecture 07, Wed 09-27-06
- Lecture 08, Mon 10-02-06
- Amortized analysis
- Reading: CLRS 17
- Lecture 09, Wed 10-04-06
- Mergeable heaps: binary, binomial, Fibonacci
- Reading: CLRS 19, 20
- Homework 03 due
- Lecture 10, Wed 10-11-06
- Data structures for disjoint sets: Union-Find
- Reading: CLRS 21
- Homework 04 assigned
- Lecture 11, Mon 10-16-06
- Graphs and graph algorithms: BFS, DFS, cycle detection
- Reading: CLRS 22
- Lecture 12, Wed 10-18-06
- Graph algorithms: DAGs, topological sort, strongly connected components
- Reading: CLRS 22
- Homework 04 due
- Homework 05 assigned
- Lecture 13, Mon 10-23-06
- Minimum spanning trees: Prim, Kruskal
- Reading: CLRS 23
- Lecture 14, Wed 10-25-06
- Single-source shortest paths
- Reading: CLRS 24
- Homework 05 due
- Midterm exam assigned
- Lecture 15, Mon 10-30-06
- Finish SSSP; all-pairs shortest paths
- Reading: CLRS 24, 25
- Lecture 16, Wed 11-01-06
- Network flow
- Reading: CLRS 26
- Midterm exam due
- Homework 06 assigned
- Lecture 17, Mon 11-06-06
- Network flow
- Reading: CLRS 26
- Lecture 18, Wed 11-08-06
- Randomized algorithms, data structures, and analyses: BSTs
- Reading: CLRS 12.4
- Homework 06 due
- Homework 07 assigned
- Lecture 19, Mon 11-13-06
- Lecture 20, Wed 11-15-06
- Linear programming
- Reading: CLRS 29
- Lecture 21, Mon 11-20-06
- Lecture 22, Mon 11-27-06
- Approximation algorithms
- Reading: CLRS 35
- Lecture 23, Wed 11-29-06
- Approximation algorithms
- Reading: CLRS 35
- Homework 08 due
- Lecture 24, Mon 12-04-06
- Lecture 25, Wed 12-06-06
- Topic to be announced...
- Final exam assigned
- Final Exam, Wed 12-13-06
Switch to:
jaa@ccs.neu.edu