Techniques for efficient algorithm design. Topics: Divide and conquer, randomized algorithms, dynamic programming, greedy method, and approximation algorithms. Examples from graph theory (e.g., depth-first search), computational geometry (e.g., closest point problems), numeric computation (e.g., Fast Fourier Transform), data compression (Huffman's algorithm), cryptography (RSA), optimization (minimum spanning tree, traveling salesman problem), string matching, and others.

Unit 1. Fundamentals sample unit: the technique of depth-first search in graphs asymptotic estimates, RAMs, polynomial time Unit 2. Cryptography Unit 3. The divide-and-conquer technique computational geometry, Fast Fourier Transform, cache oblivious algorithms Unit 4. Randomized algorithms Unit 5. The dynamic-programming technique 1- & 2-dimensional algorithms from text processing, computational biology, etc. Unit 6. The greedy technique data compression (Huffman's algorithm), minimum spanning trees, etc. Unit 7. Halving & Amortization set merging, dynamic graph algorithms credits, potential functions Unit 8. Approximation algorithms vertex cover & set cover, Travelling Salesman Problem

Learn basic principles of algorithm design.

Knowledge of discrete mathematics and data structures.

Web and e-mail access required, also a short programming assignment will require access to the CSEL.