CS547 Computer Algorithms (Fall 2004)

PREREQUISITES
MA211 Foundations or MA346 Applied Algebra and Discrete Mathematics
CS344 Algorithms and Data Structures


INFORMATION
Instructor Christino Tamon
Lectures MWF 08:00 Snell 169
Office Hours MW 9-11am and F 9-10am SC 373
Contact SC 373, tino@clarkson.edu

TEXT
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein,
Introduction to Algorithms, 2nd edition (Cambridge, Massachusetts: The MIT Press, 2001).

RECOMMENDED
Michael R. Garey and David S. Johnson,
Computers and Intractability: A Guide to the Theory of NP-Completeness (New York: W.H. Freeman, 1979).


TOPICAL OUTLINE
This course studies advanced algorithmic techniques for solving computational problems efficiently. Some emphasis will be given on graph-theoretic problems and data structures that are relevant to them. The theory of NP-completeness on the limitations of solving problems efficiently will also be discussed.

OBJECTIVE & OUTCOMES
The objective of this course is to learn fundamental algorithmic techniques, to gain the ability to evaluate the efficiency of algorithms, and to understand certain intractability issues concerning hard algorithmic questions.

The specific outcomes are basic knowledge of the following:

REQUIREMENTS & POLICIES
Although attendance is not mandatory, students are responsible for all course materials covered in lectures and any quizzes given during class periods. Students that need to make up missing course work must provide the required Clarkson official exempt form. All students must submit their own work; the exchange of ideas are encouraged but ultimately the submitted work must be the student's own. Please refer to the Clarkson University Regulations for more guidelines on academic integrity and related matters.

GRADING SCHEME (TENTATIVE)
Midterm Test: 20%
Final Exam: 40%
Assignments and Quizzes: 40%

SCHEDULE OF TOPICS
(Chapter 3 & 4) Asymptotics and Recurrences
(Chapter 15, 16, 17) Dynamic programming, Greedy algorithms, Amortized analysis
(Chapters 22-26) Graph algorithms
(Chapter 29) Linear programing
(Chapter 34) NP-Completeness
(Time permitting) Randomized algorithms