CS 5114

Theory of Algorithms

Course Description

Fall, 2001

Instructor:                             Donald Allison, allison@cs.vt.edu or allisond@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 218, 9.05 – 9.55 am

GTA:                                     Ming Luo, lming@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, a 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: C++ or any high-level procedural language

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 for grading must be the student's own individual work.

Note:

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

Course Outline

            Topic                                                                                       Week

Introduction:                                                                                         1

            Mathematical induction, examples

Complexity of Algorithms:                                                                     1-2

            Asymptotic notation

            Worst case/average case bounds

            Recurrence relations

Design of Efficient Algorithms:                                                               3-4

            Polynomial evaluation

            Divide and conquer

            Dynamic programming

 Sorting and Searching: 5-7

            Binary search

            Radix sort, insertion sort, mergesort

            Quicksort, heapsort

            Order statistics

Graph Algorithms:                                                                                 8-9

            Graph traversal

            Minimum spanning trees

            Shortest path problems

            Hamiltonian tours

Geometrical Algorithms:                                                                        10-11

            Convex hulls and related problems

            Optimal placement

            Intersection problems

Algebraic and Numeric Problems:                                                         11-12

            Polynomial multiplication

            Matrix multiplication and related problems

            Fast Fourier Transform

NP-Completeness:                                                                               13-14

            Intractable problems

            Cook's theorem

            NP-Completeness proofs

            Coping with NP-complete problems

Parallel Algorithms                                                                                15

            Algorithms for shared-memory machines

            Algorithms for interconnection networks