This course aims to develop your skills as an omniheurist. We will study problems that require heuristics and approximation algorithms. The heuristics include branch and bound, simulated annealing, tabu searching, evolutionary algorithms, and adaptive gradient methods. Approximation algorithms to NP-complete problems will help for subproblems. The problems take minutes to explain but the challenge they pose will keep you busy in a creative way for several hours. I don't promise an easy course, but I believe you will enjoy this class and find it useful.

The goal of this course is to train you to face a new problem, integrate techniques you have learned, arrive at a preliminary solution rapidly, refine it as you learn more about it, and be able to demonstrate (experimentally and sometimes competitively) that the solution is both efficient and close to the best possible.

In the fall of 2012, course problems will be drawn from biological computing, geometry, adversarial game playing, and matchmaking. I will present all necessary domain knowledge in each case. We will have in-class friendly competitions in which the winner receives a small piece of chocolate as a prize. The competitions will involve adversarial games or competitive solutions. For example, you might have to achieve a goal in the context of an adversary who can cause failures or otherwise try to thwart you. The biological computing projects will involve combinatorial problems having to do with verifying DNA sequences using Crick-Watson pairing, the planning of dance movements, the use of combinatorial design for experiments, and so on. At the end, you will be able to face a difficult problem in an area where the domain is not familiar to you, but still be able to contribute a computational solution. You will also learn how to explain your solutions to a small group (because I will make you do it here).

This is hands-on computer science. I will lecture only on a few topics -- dynamic programming, a description of a prototyping language K , (or the newer language q through its basic moves ), game-playing in AI, a description of the puzzles, heuristic techniques, and approximation algorithms for NP-complete problems. I will also serve as a moderator for class discussion. You will be graded on how your program works, on your insights in class, and on your verbal explanation of the strategies you use. Attendance is therefore mandatory unless you have a written excuse from a physician or an employer.

Similar courses have been given by Donald Knuth at Stanford and Ken Ross at Columbia.