COMP 312 - Algorithms and Complexity |
Fall 2007 |
| Instructor-- | Danny Krizanc |
| Office-- | 631 Science Center |
| Office Hours-- | Wednesdays 2:30-4:30 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 (in my opinion pretty good) 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 Handout |
|
|
Divide-and-Conquer Algorithms | Chapter 7 |
|
|
Dynamic Programming | Chapter 8 |
|
|
|
Chapters 1-4, 7, 8 |
|
|
Greedy Algorithms | Chapter 6 |
|
|
Probablistic Algorithms | Chapter 10 |
|
|
Computational Complexity | Chapter 12 |
|
|
Heuristic Algorithms | Chapter 13 |
|
|
|
Chapters 6,10,12,13 |
| Report problems to dkrizanc at wesleyan.edu
|