Computer Algorithms - Approximate Syllabus
Computer Science 4020
This course teaches general techniques for designing and analyzing algorithms.
The exact coverage is subject to change. Possible topics include:
- Introduction: Stable matchings, some representative problems, and the basics of algorithm design.
- Greedy Algorithms: General greedy techniques, minimum spanning trees
- Divide and Conquer
- Dynamic Programming: Weighted interval scheduling, knapsack, and many
- Flows and Cuts in Networks: Max-flow Min-cut Theorem, augmenting paths, basic applications.
- Applications of Flows: Extensions of flows to more general models, more advanced
- Computational Hardness, Reductions, and NP-Completeness
- Algorithms for Hard Problems: Approximation Algorithms, Randomized Algorithms, Local Search
We will have approximately 10 homework assignments, a midterm exam, and a
final exam. There will also be an in-class quiz during the second week of
class testing knowledge that is pre-requisite for this class.
Course Learning Objectives: Students who successfully complete this course will be able to analyze and design efficient algorithms for a variety of computational problems. They will also be able to communicate their ideas in the form of precise algorithm descriptions and rigorous proofs.