*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- Greedy algorithms
*Reading:*CLRS 16- Homework 02 due
- Homework 03 assigned

**Lecture 08**, Mon 10-01-12- Amortized analysis
*Reading:*CLRS 17

**Lecture 09**, Wed 10-03-12- Mergeable heaps: binary, binomial, Fibonacci
*Reading:*CLRS 19- Homework 03 due
- Homework 04 assigned

**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- Network flow
*Reading:*CLRS 26- Homework 05 due
- Homework 06 assigned

**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- Randomized algorithms, data structures, and analyses: skip lists
*Reading:*Skip Lists: A Probabilistic Alternative to Balanced Trees

**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*Final exam due*

jaa@ccs.neu.edu