Theory of Algorithms
Instructor: Donald Allison, email@example.com
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, firstname.lastname@example.org
Office Hours: To be arranged
WWW information: http://courses.cs.vt.edu/~cs5114
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.
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.
Introduction to Algorithms, Manber, Addison-Wesley, 1989
Introduction to Algorithms, Cormen, Leiserson, and Rivest, MIT Press, 1992
The Design and Analysis of Computer Algorithms, Aho, Hopcroft and Ullman,
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
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%
The Honor Code applies to all aspects of this course. All work submitted must be the student's own work.
If any student needs special accommodations because of a disability please contact the instructor during the first week of classes.