CSC721: Algorithms
Text:
Dasgupta, Papdimitriou and Vazirani, Algorithms, McGraw-Hill
| Linear Programming | Chapter 7 | 8/27-9/5 |
| Dynamic Programming | Chapter 6 | 9/8-9/17 |
| Greedy Algorithms | Chapter 5 | 9/19-9/29 |
| Divide & Conquer | Chapter 2 | 10/1-10/10 |
| Graph Decomposition | Chapter 3 | 10/20-10/29 |
| Paths in Graphs | Chapter 4 | 10/31-11/10 |
| NP Complete/Hard | Chaper 8 | 11/12-11/19 |
| Consequences of NP Complete/Hard | Chaper 9 | 11/19-11/24 |
| Quantum Algorithms | Chapter 10 | 12/1-12/5 |
In the course we will focus on design, implementation and analysis of algorithms, understanding the significance of the complexity classes such as P and NP, introducing other algorithmic paradigms such as parallel and quantum.
Goals:
The goals of this class include effective algorithmic design and implementation using classical design methodology such as dynamic programming, asymptotic and runtime analysis of the resources required by an algorithm, fairly thorough understanding of complexity classes, and introduction to alternative algorithm paradigms.
Supplements:
I strongly encourage you have have good references for C++, discrete mathematics, statistics and calculus. The library is a good source to find these.
Note:
If you have a disability that may require an accommodation in this course, then please contact the Learning Assistance Center at (758-5929) within the first two weeks of the semester.
Grading:
| Midterm | 10/15 | 30% |
| Final | 12/12 | 40% |
| Labs | 9/19, 10/17, 11/14, 12/5 | 30% |
Labs:
Every lab will be approached as a small and directed research project. You will be required to design, implement, test, and analyze each algorithm. A mini paper will be written for each of these. We will talk a great deal about this during the semester.
| Lab #1 | Bingo | 9/19 |
| Lab #2 | String analysis | 10/17 |
| Lab #3 | dfft | 11/14 |
| Lab #4 | Simulated Annealing | 12/5 |
August 7, 2008
