CSCI-GA.2965-001

Heuristic Problem Solving
Tuesdays, 7-9, room 101.
Office hours: after class

Dennis Shasha

Graduate Division

Computer Science


 

GOAL

Interesting problems usually can't be solved in closed form or using polynomial algorithms. 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 combine versatality, imagination, and programming talent. I call them omniheurists -- solvers of all problems.

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.

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. python, perl, Java, Ruby even C). R and Matlab may not be fast enough, but you can try.

In the fall of 2013, 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).

Depending on the size of the class, you will work alone or in a team of two. In some cases the problem will be an as yet unanalyzed game and your team's task will be to compete with other teams. The games are games of strategy and full information. A side effect of each effort will be an evolving "Dr Ecco" website that we expect will get many visitors over the years. Sometimes, you will have a design problem, but in all cases you will work as a member of your team. Lots of excellent software is available from previous clases. In addition, an alumnus from 2007, Arefin Huq wrote up his thoughts about how to solve problems. Definitely worth a read.

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.

Class Prerequisites

To take the class, you should love challenging puzzles, enjoy rapid prototyping, and have some sense of concurrent programming (to make use of multi-core chips). 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

For each problem, there will be three relevant classes: Presentation, Discussion, and Competition. So, on class i, I will present problem k, we will discuss k in class i+1 (when problem k+1 will be presented), and there will be a competition for k in class i+2 (when problem k+1 will be discussed and problem k+2 presented). You may have to read the above twice to get it.

For each problem, there will be an Architecture team and Competing Teams. These will be assigned on Presentation night.

Grading

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-15 hours a week programming, but you may require more or less.

You will be expected to produce one lasting software artifact as an architect that will eventually go on either on our game website . This should be a functional web-facing piece of software requiring no downloads on the client side (i.e. no security certificates). It should permit clients to play as humans or allow them to play as bots (i.e. through programs). Your source code should be a pleasure to read and come with documentation that makes it easy to modify. That artifact will constitute roughly 1/3 of your grade.

The documentation accompanying the website should also be a pleasure to read. It should consist of a breakdown of the functions, a description of each function's purpose, its inputs, outputs, and side effects. You should write it as you would like documentation should be written.

Class schedule

Books

Class Materials -- a growing list

Game playing in Artificial Intelligence from the paper by Pantel: "Advanced Adversary Search Algorithms"

Heuristic search algorithm from AI A* description by Justin Heyes-Jones

Genetic Algorithms Tutorial and an example of a genetic algorithm for the knapsack problem implemented in K. Here you can find a genetic algorithm used for compiler optimization.

Chris Poultney's Voronoi game implementation

Here is how to call C from K: Don Orth's description of how to call C from K.

Here is a powerpoint overview of the game framework in php by Alberto Lerner . Here is a text description of php and here are the php pages themselves for tic-tac-toe.

Here is Tyler Neylon's code for the knapsack that performs evolutionary algorithms on general chromosome structures.

Web page of linear and non-linear programming optimization case studies. Try diet and cutting stock optimization. Portfolio optimization is also interesting if you believe the assumptions. You can find implementation considerations in Karla Hoffman article on combinatorial optimization using linear, integer and non-linear programming. A general reference can be found here. A very nice discussion of the relationship among machine learning, evolutionary computation, and data mining can be found here. An excellent site describing research in optimization/operations research can be found here.

Memorable Quotes

The best course I've ever taken but an insane amount of work.

If Courant had a basketball league, our class would be the Harlem Globetrotters.

Ravi, Prasad, and I [Zeno Lee] are working together still at the same software company. The founding partners of our company are always raving about how great it was to have recruited from the heuristics class.

Boris: It was more challenge and fun than any other class that I took. My interview at a company well known for its hard and puzzling questions was a joke after this class :)

Fast. Intense. Harcore. Huge amount of work. Totally awesome.

This is the hardest, best class I have ever taken. It made me weep it was so hard, but I never have learned more or had so much fun as in this class.

The class is probably the most interesting I've ever taken. I learned more than in virtually any other course in order to do the projects, though mostly on my own rather than from the text or lectures. This also changed my idea of how a course SHOULD be taught -- namely using competitions and open-ended projects as motivating devices.

Prof. Shasha prepares you for anything!

I feel I gained more knowledge coding through trial and error than I have in other courses being told how to do specific algorithms. This course also showed me not to disregard ideas as many things performed unexpectedly well.

I really liked the chocolate because it provided me energy when I was hungry.

Saurabh on interviews: Anything which makes people play on an unfamiliar playing field is a more realistic test - trading is a very fluid and battlefield type of arena. Asking "what is your goal in life or big strength" elicits canned response. No one will say "I am lazy and careless." But one look at his attempt at questions from mathematics and computer science will tell us something about his capability... the true test is puzzles and programming tests, so in reality anyone who passes YOUR interviews is the smart one

Dennis on why this course is relevant to research: I have always found it useful to attack a problem from different sides as if I were a burglar trying to find my way into a house. If I have to bust through the front door, ok, but there might be a side window that hasn't been closed completely.