Course 21190120:

Algorithm design and analysis

News:

0. Course is finished. The final scores are available already. (July 9, 2007)

Lecture notes:

1. Introduction

2. Math foundation

3. Divide-and-conquer

4. Dynamic programming

5. NP-Complete and Polynomial reduction

6. Greedy method

7. Approximation algorithm

8. Local search

9. Geometry computation

10. Randomized algorithm

11. Linear programming and flows

12. Extension topics: online algorithms

Projects:

1. Project1, due dates: June 6.

2. Project2, due dates: June 27. Please submit it after June 10.

Reading lists: (the following papers just for students in this class)

1. A linear space algorithm for computing maximal common subsequences. D.S. Hirschberg. Communication of ACM, 18(6): 341-343, 1975.

2. A New Efficient Algorithm for Computing the Longest Common Subsequence. Costas S. Iliopoulos and M. Sohel Rahman 2007.

3. Sorting X+Y. L.H. Harper, T.H. Payne, J.E. Savage, and E. Straus. Communication of ACM, 18(6): 347-349, 1975.

4. The Longest Common Subsequence Problem Revisited. A. Apostolico 1 and C. Guerra I, Algorithmica (1987) 2:315-336, 1987.