CSG713 04F: Syllabus

Note: This is an approximate syllabus; it may change at any time.

1. Lecture 01, Wed 09-08-04
   • Introduction; admistrivia; overview of CSG713
   • Four methods for computing the Fibonacci numbers
   • Analysis of algorithms; orders of growth
   • Reading: CLRS 1 (skim), 2.2, 3 (review), Appendix A (review), Appendix C (review)
   • Handouts:
     • Ten Orders of Growth
   • Homework 00 assigned

2. Lecture 02, Wed 09-15-04
   • Recurrence review: substitution, iteration, recursion trees, master method
   • Reading: CLRS 4 (review), 5 (review)
   • Handouts:
     • Solving Recurrences via Iteration
     • The Simplified Master Method
   • Homework 01 assigned

3. Lecture 03, Mon 09-20-04
   • Average case analysis of quicksort
   • Median and order statistics: expected and worst-case linear time
   • Reading: CLRS 7.4, 9

4. Lecture 04, Wed 09-22-04
   • Lower bounds for sorting; sorting in linear time
   • Introduction to dynamic programming
   • Reading: CLRS 8.1-8.3, 15
   • Information:
     • Punched cards
     • IBM radix sorters
   • Homework 01 due
   • Homework 02 assigned

5. Lecture 05, Mon 09-27-04
   • Dynamic programming
   • Reading: CLRS 15
   • Handouts:
     • Coin changing via dynamic programming

6. Lecture 06, Wed 09-29-04
   • Greedy algorithms
   • Reading: CLRS 16
   • Homework 02 due
   • Homework 03 assigned

7. Lecture 07, Mon 10-04-04
   • Amortized analysis
   • Reading: CLRS 17

8. Lecture 08, Wed 10-06-04
   • Mergeable heaps: binary, binomial, Fibonacci
   • Reading: CLRS 19, 20
   • Homework 03 due

9. Lecture 09, Wed 10-13-04
   • Data structures for disjoint sets: Union-Find
   • Reading: CLRS 21
   • Homework 04 assigned

10. Lecture 10, Mon 10-18-04
    • Graphs and graph algorithms: BFS, DFS, cycle detection
    • Reading: CLRS 22

11. Lecture 11, Wed 10-20-04
    • Graph algorithms: DAGs, topological sort, strongly connected components
    • Reading: CLRS 22
    • Homework 04 due
    • Homework 05 assigned

12. Lecture 12, Mon 10-25-04
    • Minimum spanning trees: Prim, Kruskal
    • Reading: CLRS 23

13. Lecture 13, Wed 10-27-04
    • Single-source shortest paths
    • Reading: CLRS 24
    • Homework 05 due
    • Midterm exam assigned

14. Lecture 14, Mon 11-01-04
    • Finish SSSP; all-pairs shortest paths
    • Reading: CLRS 24, 25

15. Lecture 15, Wed 11-03-04
    • Network flow
    • Reading: CLRS 26
    • Midterm exam due
    • Homework 06 assigned

16. Lecture 16, Mon 11-08-04
    • Network flow
    • Reading: CLRS 26

17. Lecture 17, Wed 11-10-04
    • Finish network flow; linear programming
    • Reading: CLRS 26, 29
    • Homework 06 due
    • Homework 07 assigned

18. Lecture 18, Mon 11-15-04
    • Linear programming
    • Reading: CLRS 29

19. Lecture 19, Wed 11-17-04
    • Linear programming
    • Reading: CLRS 29
    • Homework 07 due

20. Lecture 20, Mon 11-22-04
    • Randomized algorithms, data structures, and analyses: BSTs
    • Reading: CLRS 12.4

21. Lecture 21, Mon 11-29-04
    • Randomized algorithms, data structures, and analyses: skip lists
    • Reading: Skip Lists: A Probabilistic Alternative to Balanced Trees

22. Lecture 22, Wed 12-01-04
    • Approximation algorithms
    • Reading: CLRS 35
    • Homework 08 assigned

23. Lecture 23, Mon 12-06-04
    • Approximation algorithms
    • Reading: CLRS 35

24. Lecture 24, Wed 12-08-04
    • Topic to be announced...
    • Homework 08 due
    • Final exam assigned

25. Final exam, Wed 12-15-04
    • Final exam due

Switch to:

• CSG713 04F Home Page