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