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 2024, course problems will be drawn from biological computing, geometry, adversarial game playing, and concept drift in machine learning. 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. 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). I'm told that students who survive this course become friends for life.
You have the option of working alone or in a team of two (but no more). In some cases the problem will be an as yet unanalyzed game and your team's task will be to compete with other teams.
Use of large language models is permitted These will be tools available to you throughout your career, so I encourage you to use them. When you describe your solution, share the prompt you used, the result of the prompt, and how you used the result.
The games are often games of strategy and full information. A side effect of each effort will be an evolving Omniheurist website that attracts many visitors over the years.
Two members of the class of 2017 worked out a communication infrastructure that architects can use: The git repo for the package is this address It includes a sample auction game as a demo. The code can be installed with 'pip install --user hps-nyu' Only Python specific aspects (i.e. the servers and the Python clients) of the package are installed. The C++ and Java clients need to be copied from the git repo.
Sometimes, you will have a design problem, but in all cases you will work as a member of your team. 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 superfast vector language k, 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 (including the prompts you used if you use a large language model). If your program does not run, you do not present. This is a rubber-meets-the-road kind of course. Attendance (even if only by zoom) 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.