COMP 312 - Algorithms and Complexity |
Fall 2009 |
| Instructor-- | Danny Krizanc |
| Office-- | 631 Science Center |
| Office Hours-- | Mondays 5:30-7:00 or 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 seven small written assignments, every one to two weeks. The best five assignment grades will contribute ten per cent to your final grade for a total of fifty per cent. No late assignments will be accepted. There will be two in-class tests worth twenty-five 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 | Chapter 4 |
|
|
Divide-and-Conquer Algorithms | Chapters 7 and 9 (also 2.3, 28.2, 33.4) |
|
|
Dynamic Programming | Chapters 15 and 25 |
|
|
|
Chapters 1-4, 7, 9, 15, 25 (also 2.3, 28.2, 33.4) |
|
|
Greedy Algorithms | Chapter 16 and 23 |
|
|
Computational Complexity | Chapter 34 |
|
|
Approximation Algorithms | Chapter 35 |
|
|
|
Chapters 16, 23, 34, 35 |
| Report problems to dkrizanc at wesleyan.edu
|