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.
CS 515 or consent of the instructor.
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.
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.
|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|
|10||Approximations, bounds on accuracy|
|11||Greedy Methods, Divide and Conquer|
|12-13||Greedy Methods, Divide and Conquer|
|14||Simulated Annealing, Neural Networks|
|Genetic Algorithms, DNA Computation|
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.
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.
Artificial Intelligence, a Modern Approach
Stuart Russell, Peter Noring,
Introduction to Algorithms,
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
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.