CPSC 629-600: Analysis of Algorithms
Fall 2002
Course Information
Instructor: Andreas Klappenecker
Office: 509B Harvey R. Bright Building
Office hours: TR 10:30-11:30am
Email: klappi @ cs.tamu.edu
Prerequisite
CPSC 311 Analysis of Algorithms.
Required Textbooks:
- T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introduction to Algorithms,
MIT Press, 2nd edition, 2001.
- M.R. Garey, D.S. Johnson: Computers and Intractability: A Guide to the
Theory of NP-Completeness, W.H. Freeman and Company, 1979.
Additional materials will be distributed during the course.
Grades
- Midterm exam: 25%
- Final exam: 25%
- Assignments: 45%
- Culture: 5%
The course grades will be assigned according to the scale
A=90-100%, B=80-89%, C=70-79%, D=60-69%, F 0-59% of the total
points available.
Course Goals
This course covers algorithm design and analysis techniques, advanced data structures, number theoretic algorithms,
graph algorithms, theory of NP-complete problems, and some specialized
topics. At the end of the course you should be familiar with
- the algorithms and techniques covered
- analysis of algorithms
- the design of algorithms
- some NP-complete problems and reduction techniques
Course Contents
A (tentative) list of topics that will be covered in the course:
- Number Theoretic Algorithms
- Graph Algorithms
- Design and Analysis of Algorithms
- Intractability
- Advanced Data Structures
- Further Topics (time permitting)
Assumed Background
- Familiarity with pseudo code
- Knowledge of C, C++, or the like
- Big Oh, Omega notations
- Mathematical reasoning
- Basic understanding of P, NP, etc.
- Analysis of Algorithms CPSC 311 or equivalent
- Discrete Mathematics Math 302 or equivalent
Computer Use
Some materials will be available only on the
web. You need a CS account for the project.