CS 674 - Heuristic Algorithms
Credits: 3
Course Description
Solving problems that are intractable. Exact techniques such as search integer programming and dynamic programming. Approximation techniques including local search, divide and conquer, and greedy algorithms. Methods based upon natural models such as force-directed iteration, simulated annealing, genetic algorithms, and neural networks. Examples will be selected from active research areas.
Prereqs: CS 515 or consent of the instructor.
Needed Skills
Before taking this course, a student is expected to be familiar with techniques for the analysis of algorithms as well as standard algorithms involving lists, strings, and graphs. Programming skills are assumed.
Learning Outcomes
The student will develop knowledge of and facility in using a variety of tools for finding both approximate and exact solutions to problems that seem unfeasible due to excessive complexity or a nonconvex nature.
Week by Week Course Outline
This is a sample outline. Exact outline will be determined by the instructor offering this course.
| Weeks | Topics |
|---|---|
| 1 | Classes of problems including P and NP |
| 2 | Examples of intractable problems |
| 3-5 | Linear Programming and Integer Programming |
| 6 | Cutting Planes, Upper Bounds |
| 7-8 | Enumeration of Integer Programs & Branch and Bound Methods |
| 9 | Dynamic Programming |
| 10 | Approximations, bounds on accuracy |
| 11 | Greedy Methods, Divide and Conquer |
| 12-13 | Greedy Methods, Divide and Conquer |
| 14 | Simulated Annealing, Neural Networks |
15 |
Genetic Algorithms, DNA Computation |
Required Work
Students shall apply integer programming, branch and bound, divide and conquer, and local search techniques to a problem of their choice and make oral presentations about their methods. The also shall implement some of these and present the results in a term paper.
Grading
Exact details about graded work in this course will be determined by the instructor offering the course and will be made available in the syllabus during the first class meeting. Typically, grades shall be determined by weighting the evaluations of the presentations and term paper. This shall be negotiated at the beginning of the semester.
Possible Textbooks
Artificial Intelligence, a Modern Approach
Stuart Russell, Peter Noring,
Prentice Hall
Introduction to Algorithms,
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
MIT Press
Papers from the literature
Exact details about graded work in this course will be determined by the instructor offering the course and will be made available in the syllabus.