Heuristic Problem Solving

Dennis Shasha

Graduate Division

Computer Science



Interesting problems usually can't be solved in closed form or using polynomial algorithms. Ambulances can't be scheduled based on rough hunches in a castrophe. Shipping companies must exploit non-linear constraints involving profit margins, demand, and volume, and still keep the boats moving. The same goes for optimal substring search for microarray design or optimal DNA design. The people who program the practical solutions to these problems comprise the elite of their technical organization. They are sought after throughout their careers, because of their versatality, imagination, and programming talent. I call them omniheurists -- solvers of all problems.


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

Prerequsities: this is a course for students who can think creatively about algorithms and are willing to prototype them. I will spend an hour teaching the prototyping language I use (for all of my research) but you are free to use any you like (e.g. MatLab, python, perl, even C).

In the fall of 2003, course problems will be drawn from distributed computing, biological computing, chemistry, and operations research. 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 reconstruction of sequences using restriction enzymes, the use of combinatorial design for experiments, and 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 know how to explain your solutions to a small group.


This is hands-on computer science. I will lecture only on a few topics -- game-playing in AI, a prototyping language K , a description of the puzzles, heuristic techniques, and approximation algorithms for NP-complete problems. I will also serve mostly 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.


Class Prerequisites

To take the class, you should love challenging puzzles, enjoy rapid prototyping, and have some sense of concurrent programming. You will like the class if you think algorithmically and enjoy translating algorithms into programs. Formally, the only requirement is Fundamental Algorithms or its equivalent. You should have done well however.

Basic Class Structure




Your programs must run and you must have a cogent explanation for what you have done. There are no exams, no papers, and only rare excuses. I expect you to spend about 10 hours a week programming, but you may take more or less.

Class schedule


Class Materials -- a growing list




Chris Poultney's Voronoi game implementation





Please register for the class mailing list here

Student Web Pages