CSG713 07F: Syllabus

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

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

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

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

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

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

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

7. Lecture 07, Fri 09-28-07
   • Greedy algorithms
   • Reading: CLRS 16
   • Homework 02 due
   • Homework 03 assigned

8. Lecture 08, Tue 10-02-07
   • Amortized analysis
   • Reading: CLRS 17

9. Lecture 09, Fri 10-05-07
   • Mergeable heaps: binary, binomial, Fibonacci
   • Reading: CLRS 19, 20
   • Homework 03 due
   • Homework 04 assigned

10. Lecture 10, Tue 10-09-07
    • Data structures for disjoint sets: Union-Find
    • Reading: CLRS 21

11. Lecture 11, Fri 10-12-07
    • Graphs and graph algorithms: BFS, DFS, cycle detection
    • Reading: CLRS 22
    • Homework 04 due
    • Homework 05 assigned

12. Lecture 12, Tue 10-16-07
    • Graph algorithms: DAGs, topological sort, strongly connected components
    • Reading: CLRS 22

13. Lecture 13, Fri 10-19-07
    • Minimum spanning trees: Prim, Kruskal
    • Reading: CLRS 23
    • Homework 05 due
    • Midterm exam assigned

14. Lecture 14, Tue 10-23-07
    • Single-source shortest paths
    • Reading: CLRS 24

15. Lecture 15, Fri 10-26-07
    • Finish SSSP; all-pairs shortest paths
    • Reading: CLRS 24, 25
    • Midterm exam due
    • Homework 06 assigned

16. Lecture 16, Tue 10-30-07
    • Network flow
    • Reading: CLRS 26

17. Lecture 17, Fri 11-02-07
    • Network flow
    • Reading: CLRS 26
    • Homework 06 due
    • Homework 07 assigned

18. Lecture 18, Tue 11-06-07
    • Randomized algorithms, data structures, and analyses: BSTs
    • Reading: CLRS 12.4

19. Lecture 19, Fri 11-09-07
    • Randomized algorithms, data structures, and analyses: skip lists
    • Reading: Skip Lists: A Probabilistic Alternative to Balanced Trees
    • Homework 07 due
    • Homework 08 assigned

20. Lecture 20, Tue 11-13-07
    • Linear programming
    • Reading: CLRS 29

21. Lecture 21, Fri 11-16-07
    • Linear programming
    • Reading: CLRS 29
    • Homework 08 due

22. Lecture 22, Tue 11-20-07
    • Approximation algorithms
    • Reading: CLRS 35

23. Lecture 23, Tue 11-27-07
    • Approximation algorithms
    • Reading: CLRS 35

24. Lecture 24, Fri 11-30-07
    • Topic to be announced...

25. Lecture 25, Tue 12-04-07
    • Topic to be announced...
    • Final exam assigned

26. Final Exam, Tue 12-11-07
    • Final exam due

Switch to:

• CSG713 07F Home Page