Further introduction to the study of algorithms. Analysis of computing time, asymptotic notation and generating functions. Strategies for designing algorithms: Divide-and-conquer, Greedy method, Backtracking, etc. Further topics such as techniques for algebraic manipulations, lower bound theory, NP-Complete problems, and parallel algorithms.

Cormen, Leiserson and Rivest, Introduction to Algorithms, MIT Press/McGraw-Hill, 1990.

Topics covered in 20 CS 671.

This course will provide a solid foundation for the classical theory of sequential algorithms, and to cover some of the most important recent algorithmic developments, including the theory of parallel algorithms. It will also provide the mathematical tools nCSsary to analyze the correctness and efficiency of algorithms, and to be able to judge how close an algorithm is to being optimal for a given problem. It will enhance student?s the ability to create new algorithms or to modify existing algorithms in order to solve new problems.

1. Introduction to Probabilistic Algorithms : e.g., Prime Testing
2. Lower Bound Theory: e.g., Lower Bounds for Searching and Sorting
3. The Greedy Method: e.g., Shortest Path & Minimum Spanning Trees.
4. Divide and Conquer: e.g., Fast Fourier Transform, Matrix Multiplication
5. Dynamic Programming: e.g., All Pairs Shortest Paths, Optimal Search Trees
6. Backtracking and Branch-and-Bound : Bounding Functions and Heuristics
7. P, NP, Co-NP, NP-Complete Problems: e.g., Prime Testing, Satisfiability

1. Students use a UNIX and/or Windows platform. Programs can be written in C++ or Java. Other languages may be used with approval.
2. Approximately 4 assignments, at least one of which will have a programming component..

One or two projects. Course emphasis will be on designing and analyzing algorithms, not on programming.

Engineering science: 1.5 credits or 50%
Engineering design: 1.5 credits or 50%