Introduction to probabilistic algorithms. Lower bound theory. Major design strategies: the greedy method, divide-andconquer, dynamic programming, backtracking and branch-and-bound, introduction to NPcomplete problems.

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

20-CS-471, Design & Analysis of Algorithms I

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. 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. To enhance 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<br>Java. Other languages may be used with approval.<br>2. Approximately 4 assignments, at least one of which will have a programming<br>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%