An introduction to the study of algorithms. Analysis of computing time, asymptotic notation, introduction to lower bound theory. Introduction to the theory of parallel algorithms and architectures. Induction, correctness proofs, and recurrence relations. Graphs, digraphs, and sets. Probability and average complexity of algorithms.

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

1. 20-CS-323, Programming Languages & Methodologies
2. 15-MATH-356 or 410, Discrete Math
3. 15-MATH-361, Probabilities & Statistics I
4. 15-MATH-276, Differential Equations or 15-MATH-352, Linear Algebra II
5. Knowledge and experience in a high-level programming language.
6. Familiarity with elementary abstract data types
7. Familiarity with mathematical concepts from calculus, linear algebra, discrete
mathematics, and elementary probability theory.

The goal of this course is to 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 and background
2. Review of ADT's
3. Complexity of algorithms and asymptotic notation
4. Sequential sorting algorithms and their analysis
5. Introduction to parallel algorithms and architectures
6. Parallel sorting
7. Induction, correctness proofs, and recurrence relations
8. Graphs and digraphs
9. Disjoint sets
10. Intro to probability and average complexity

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 four 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%