CS 5114

Theory of Algorithms

Course Description

Spring, 2001

Instructor: Donald Allison, allison@cs.vt.edu

Office: 626 McBryde, tel. no. 231-4212

Office Hours: MW 2.30 - 4.00, F 10.00 – 11.00 and by appointment

Class Meets: MWF McBryde 302, 11.15 – 12.05

GTA: Jacob Somervell, jsomerve@vt.edu

Office Hours: To be arranged

WWW information: http://courses.cs.vt.edu/~cs5114

Description:

This is a course in the analysis of algorithms and their complexity. Work concentrates on measuring the time complexity of algorithms taken from a number of important areas. General techniques of analysis are presented. In addition, techniques for constructing efficient algorithms are discussed. The question of what it means for an algorithm to be efficient is addressed. The related question of what it means for a problem to be intractable is pursued via the theory of NP-completeness.

Prerequisites:

Proficiency in a high level language, knowledge of data structures (equivalent to CS 2604), and sufficient mathematical maturity. Consult the instructor if in any doubt.

Textbook:

Introduction to Algorithms, Manber, Addison-Wesley, 1989

On Reserve:

Introduction to Algorithms, Cormen, Leiserson, and Rivest, MIT Press, 1992

The Design and Analysis of Computer Algorithms, Aho, Hopcroft and Ullman,

Addison-Wesley, 1974

Computers and Intractability, A Guide to the Theory of NP-Completeness, Garey

and Johnson, W.H.Freeman, 1979

Algorithms in C, Sedgewick, Addison-Wesley, 1990

Programming Language: Pascal or C

Grading Policy:

Graded work consists of about seven homework assignments, two midterm exams and a final exam. Some of the homework assignments will be programming assignments.

Homework Assignments 45% Midterm Exams 25% Final Exam 30%

Ethics:

The Honor Code applies to all aspects of this course. All work submitted must be the student's own work.

Note:

If any student needs special accommodations because of a disability please contact the instructor during the first week of classes.