SDSU 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