##
CS 660: Combinatorial Algorithms

Syllabus

[To Course Home Page]

San Diego State University* -- This page last updated August 21, 1995*

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://cs:8080/cs/coursesFall95/cs660/

Other Sources:

Gonnet, G. H., Baeza-Yates. Handbook of Algorithms and Data Structures,
Addison-Wesley1991

Hehlhorn, Kurt, Data Structures and Algorithms 1: Sorting and Algorithms,
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