CSG713 06F: Syllabus

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

1. 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

2. 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:
     • Ten Orders of Growth
     • Solving Recurrences via Iteration

3. 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:
     • The Simplified Master Method
   • Homework 00 due
   • Homework 01 assigned

4. 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

5. 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:
     • Punched cards
     • IBM radix sorters
   • Homework 01 due
   • Homework 02 assigned

6. Lecture 06, Mon 09-25-06
   • Dynamic programming
   • Reading: CLRS 15
   • Handouts:
     • Coin changing via dynamic programming

7. Lecture 07, Wed 09-27-06
   • Greedy algorithms
   • Reading: CLRS 16
   • Homework 02 due
   • Homework 03 assigned

8. Lecture 08, Mon 10-02-06
   • Amortized analysis
   • Reading: CLRS 17

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

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

11. Lecture 11, Mon 10-16-06
    • Graphs and graph algorithms: BFS, DFS, cycle detection
    • Reading: CLRS 22

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

13. Lecture 13, Mon 10-23-06
    • Minimum spanning trees: Prim, Kruskal
    • Reading: CLRS 23

14. Lecture 14, Wed 10-25-06
    • Single-source shortest paths
    • Reading: CLRS 24
    • Homework 05 due
    • Midterm exam assigned

15. Lecture 15, Mon 10-30-06
    • Finish SSSP; all-pairs shortest paths
    • Reading: CLRS 24, 25

16. Lecture 16, Wed 11-01-06
    • Network flow
    • Reading: CLRS 26
    • Midterm exam due
    • Homework 06 assigned

17. Lecture 17, Mon 11-06-06
    • Network flow
    • Reading: CLRS 26

18. Lecture 18, Wed 11-08-06
    • Randomized algorithms, data structures, and analyses: BSTs
    • Reading: CLRS 12.4
    • Homework 06 due
    • Homework 07 assigned

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

20. Lecture 20, Wed 11-15-06
    • Linear programming
    • Reading: CLRS 29

21. Lecture 21, Mon 11-20-06
    • Linear programming
    • Reading: CLRS 29
    • Homework 07 due
    • Homework 08 assigned

22. Lecture 22, Mon 11-27-06
    • Approximation algorithms
    • Reading: CLRS 35

23. Lecture 23, Wed 11-29-06
    • Approximation algorithms
    • Reading: CLRS 35
    • Homework 08 due

24. Lecture 24, Mon 12-04-06
    • Topic to be announced...

25. Lecture 25, Wed 12-06-06
    • Topic to be announced...
    • Final exam assigned

26. Final Exam, Wed 12-13-06
    • Final exam due

Switch to:

• CSG713 06F Home Page