CS 674 - Heuristic Algorithms

Bulletin 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.

Prerequisites

CS 515 or consent of the instructor.

Expected Preparation

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.

Student 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.

Syllabus Information

 

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.