CS660 Combinatorial Algorithms
Fall Semester, 1996
CS 660 Syllabus
[To Course Home Page]
San Diego State University -- This page last updated Monday, 02 September, 1996
Combinatorial Algorithms - CS 660
Instructor: Roger Whitney
Office: P-243
Phone: 594-3535
E-mail: whitney@cs.sdsu.edu
Text: Introduction to Algorithms by Cormen, Leiserson,
Rivest
Course URL: http://www.eli.sdsu.edu/courses/fall96/cs660/
Course mailing list:
- The list server is listproc@roswell.sdsu.edu. To subscribe to the course
mailing list send mail to listproc@roswell.sdsu.edu with the body of the
message begin:
- subscribe cs660 yourName
- To send mail to the list, send mail to cs660@roswell.sdsu.edu. For more
information see the course web site.
Other Sources:
- Gonnet, G. H., Baeza-Yates. Handbook of Algorithms and Data Structures,
Addison-Wesley, 1991
- Mehlhorn, Kurt, Data Structures and Algorithms 1: Sorting and Searching,
Springer-Verlag, 1984
- Hester, James and Hirschberg, Daniel, "Self-Organizing Linear Search",
Computing Surveys, 17(3):295-311, September 1985.
- Pugh, William, "Skip Lists: A Probabilistic Alternative to Balanced
Trees", Communications of ACM, 33(6):668-676, 1990.
- Sleator, D. and Tarjan, R. "Self-adjusting binary search trees", J. of
the ACM, 32(3):652-685, 1985
Grading : Your grade in this course will be determined as follows:
| Homework and Programs: | 33% |
| Exams(1): | 33% |
| Final: | 34% |
Cheating: Any one caught cheating will receive an F in the course.
Course Outline
- Introduction - Review of analysis
- Chapters 1-4.2
-
- Dynamic Structures
- Chapters 14, 15, 18, papers
- Self-organizing linear search, AVL trees, splay trees, red-black trees,
skip lists, dynamic trees, a-b trees, BB[] trees, persistent trees
-
- Network Flows Chapters
- Chapter 27
- Ford-Fulkerson, Goldberg-Tarjan algorithms, matching
-
- Optimization Algorithms
- Chapters 16, 17, 37
- NP-Completeness
- Chapter 36