COMP 312 - Algorithms and Complexity |
Spring 2009 |
| Instructor-- | Danny Krizanc |
| Office-- | 631 Science Center |
| Office Hours-- | By appointment |
| Phone-- | 860-685-2186 |
| E-mail-- | dkrizanc at wesleyan dot edu |
This course will cover the design and analysis of efficient algorithms. Basic topics will include greedy algorithms, divide-and-conquer algorithms, and dynamic programming. Depending on the time available other more advanced topics will be addressed such as probabilistic and heuristic algorithms as well as computational complexity.
The following textbook is required:
The list of algorithms textbooks (good and bad) grows every year. A short list of some with merit might include:
There will be eight small written assignments, approximately one per week. The best six assignment grades will contribute ten per cent to your final grade for a total of sixty per cent. No late assignments will be accepted. There will be two in-class tests worth twenty per cent each.
The following is the plan for the course and is subject to change.
|
|
Topic | Readings |
| 1 | Analysis of Algorithms | Chapters 1-3 |
|
|
Recurrences | Chapters 4 |
|
|
Divide-and-Conquer Algorithms | Chapters 7 and 9 (also 28.2, 33.4) |
|
|
Dynamic Programming | Chapters 15 and 25 |
|
|
|
Chapters 1-4, 7, 9, 15, 25 (also 28.2, 33.4) |
|
|
Greedy Algorithms | Chapter 16 and 23 |
|
|
Randomized Algorithms | Chapters 5, 7 and 9 (also 31.8) |
|
|
Computational Complexity | Chapter 34 |
|
|
Approximation Algorithms | Chapter 35 |
|
|
|
Chapters 5, 7, 9, 16, 23, 34, 35 |
| Report problems to dkrizanc at wesleyan.edu
|