Announcements | | Course information | | Important dates | | Assignments and tests | | Lecture notes |

For typesetting please use LaTeX. A good introduction to LaTeX is "Essential LaTeX" .

**Reference book:**

- J. Kleinberg, E. Tardos. Algorithm Design.
- Thomas H. Cormen , Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms.

** Marking scheme (tentative!): **
3 assignments 10% each, a test 30%, and a project 30% with a 10% presentation.

** Description: **
The goal of this course is to study both classical and advanced algorithm design techniques with emphasis on real-world applications. We will cover greedy algorithms, dynamic programming, backtracking as well as fast Fourier transform, Integer Linear Programming, etc. The applications would come from many fields, including Bioinformatics and Cryptogaphy. Time permitting, we will consider randomized, parallel and distributed algorithms, and/or streaming algorithms.

A brief list of topics for the test (review sheet).

- Lecture 1 (Jan 6): Introduction and Stable Marriage Problem
- Lecture 2 (Jan 10): Stable matching problem analysis and "representative problems" (KT chapter 1)
- Lecture 3 (Jan 13): Greedy algorithms: interval scheduling, scheduling with deadlines and profits, 1/2 approximation for knapsack
- Lecture 4 (Jan 17): Data compression: Huffman code,(KT4.8) LZ77, gzip Additional readings: gzip algorithms
- Lecture 5 (Jan 19): Minimum Spanning Tree: algorithms of Kruskal and Prim
- Lecture 6 (Jan 24): String Matching: Rabin-Karp algorithm (scribed by Md. Asaduzzaman)
- Lecture 7 (Jan 26): String Matching: Knuth-Morris-Pratt algorithm
- Lectures on dynamic programming

- Lecture 11 (Feb 14): Bellman-Ford algorithm (scribed by Abdullah Al Mamun)

- Lectures on network flows (from previous course)

- Lectures 14 and 15 (Feb 28 and Mar 1st): bioinformatics applications, guest instructor Lourdes Peņa-Castillo

- Lecture 17 (Mar 8th) Divide-and-conquer, closest points problem (from KT).

- Lecture 18 (Mar 13th) Fast Fourier Transform and polynomial multiplication

- Lecture 19 (Mar 15th) Limits of tractability, survey