Office hours: By zoom on Thursdays 10:30 to 11:30 AM, no appointment necessary. https://nyu.zoom.us/j/92842629337

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 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.

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.

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 if it's not clear.

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

• The architecture team (for the cases when the problems are adversary games inspired by distributed computing) will be responsible for constructing a web-based interface using PHP (or possibly CGI). The interface should provide two interfaces: a browser interface, so the games can be played on the web by anyone; and a programmatic interface. For the programmatic interface, players register and get back a cookie, identifying them. Each player sends the cookie with every command. The architecture team should support a getstate request from a client and a sendmove command from a client.
  • Getstate should return only when it is the appropriate player's turn.
  • Sendmove should create a new board state visible from the web browser. The interface should check validity of sendmove and should record the time per move.
  • Other support commands as needed.
  The Architecture team will be evaluated based on the look and feel and timeliness (hopefully ready one week before the class of the competition) of the interface. They will present and demonstrate the interface during Discussion night. Often I will be able to give you software from previous years. You can reserve architecture spots as early as next week. Hopefully, this will help with timeliness. Here is some general advice for architecture teams from 2016

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 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. You will present it at the student showcase at the end of the fall.

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

• Class 1:
  • Overview of the course -- discussion of some of the problems/puzzles/games, discussion of the few topics I will lecture about: game-playing, heuristic techniques, approximation algorithms for NP-complete problems, and a prototyping language.
  • Review of heuristic dynamic programming including the Ukkonen trick.
  • Presentation of the Card Nim problem .
  • Begin discussion of k , a language that you might want to use, especially if you later want to do time series analysis. Here are some introductory examples in k.
  • If someone wants to give a talk about another high level language such as Choco or a Prolog-based alternative such as gnu-prolog
  • During class, we will select an architectural team for Card Nim.
  • Optional Reading: Part 2 of Puzzles for Programmers and Pros up to dynamic programming.
  • Here are my lecture notes on dynamic programming
• Class 2:
  • Discussion of the Card Nim problem.
  • Discussion of the A* algorithm.
  • Choose team names and members
  • Discussion of approaches to the travelling salesman problem that guarantee a solution that is within a factor of 2 of optimal. On your own, you might also consider Lin-Kernighan optimizations and the vehicle routing problem.
  • Presentation of the Optimal Touring Problem.
  • Optional Reading: chapters 1 and 2 of Modern Heuristics.
  • Here are my cryptic lecture notes on astar and a guaranteed approximation to traveling salesman
• Class 3:
  • Card Nim Competition.
  • Discussion of the Tour Problem
  • Traveling salesman heuristics
  • Ant colony optimization basics (reinforced paths)
  • Discussion of ant colony optimization as applied traveling salesman problem (start at time 4:35)
  • Discussion of ant colony optimization as applied to vehicle routing (which may be useful for the ambulance problem).
  • Presentation of Seesaw Game.
  • Optional Reading: chapters 3 and 4 of Modern Heuristics.
• Class 4
  • Tour Competition.
  • Seesaw game discussion.
  • Simulated annealing and tabu search. Also, part 2 of the Programmers and Pros book.
  • Game playing in Artificial Intelligence from the paper by Pantel: "Advanced Adversary Search Algorithms"
  • Reading: Understand that paper.
  • Presentation of the Ambulance Pickup problem.
• Class 5
  • Seesaw game competition.
  • SafePredict
  • Clustering Algorithm
  • Ambulance Pickup discussion.
  • Presentation of the Flaky Oracle Game game.
  • Optional Reading: rest of part 2 of Puzzles for Programmers and Pros Optional Reading: chapters 5 and 6 of Modern Heuristics.
• Class 6
  • Ambulance Pickup competition.
  • Discussion of Flaky Oracle.
  • A quick introduction to resampling statistics from the free book (for NYU students) Statistics is Easy . If your institution has a license and you are logged in as if you were at NYU, then you can download the book from the Morgan Claypool site for free. Here are some lecture notes from Statistics is Easy and here are some notes on good approaches to multiple testing. Here is a nice article about why most articles about the secrets of success should be thrown in the trash.
  • Presentation of the Evasion problem. Here is an implementation that may be helpful.
  • Optional Reading: chapter 7 of Modern Heuristics.
• Class 7
  • Flaky Oracle competition
  • Discussion of Evasion
  • Evolutionary algorithms: bit encoding and the knapsack problem.

    Folksy (slightly misleading) explanation of genetic algorithms. A hardware-construction application of the genetic algorithm idea. And a short discussion of swarm algorithms.

  • Presentation of the PegBand game.
• Class 8
  • Presentation of the Stacking the Deck problem.
  • Discussion of PegBand.
  • Gradient method and the characteristics of the search space (pp. 74 ff of book)
  • Optional Reading: chapter 9 of Modern Heuristics. and the very nice paper by Leon Bottou.

    And here is a very nice simple discussion of gradient descent by Alex Rubinsteyn from 2008.

    Finally, machine learning and clustering can be combined

  • Perhaps decision tree learning ( information gain which is used for decision trees from Andrew Moore's notes), if time.
  • Evasion competition.
  • Optional Reading: chapter 11 of Modern Heuristics.
• Class 9
  • PegBand competition
  • Presentation of the Gravitational Voronoi Game
  • Discussion of Stacking the Deck.
  • Here is a classic example of a satisfiability puzzle. Mr. Green, Mr. Red, and Mr. Blue are together. Between them they have one green shirt, one red shirt, and one blue shirt. Similarly for pants. Nobody wears the color of his name. Nobody wears shirts and pants of same color. Mr. Green has blue pants. Find a satisfying assignment of colors to all shirts and pants. e.g. start with G_has_blue_pants & (R_has_green_shirt or R_has_blue_shirt) & (R_has_green_pants or R_has_blue_pants) & ( (not R_has_green_pants) or (not R_has_green_shirt)) & ((not R_has_blue_pants) or (not R_has_blue_shirt)) etc.
  • Satisfiability solvers based on lecture notes from Clark Barrett. (pdf page 52, 63, 99 following) This can help for program verification or for constraint problems like the puzzle and other elimination puzzles like sudoku. Here is a paper with more examples.
  • Optional Reading: chapter 10 of Modern Heuristics.
• Class 10
  • Stacking the Deck competition
  • Discussion of Gravitational Voronoi Game
  • Linear programming (pp. 70 ff of the book) and On the language AMPL, we see the diet example here.
  • The newer GAMS language with examples here (particularly product mix).
  • Convex optimization as shown in Steve Boyd's examples here.
• Class 11
  • Gravitational Voronoi Game competition
  • Presentation of other games for final projects to go on the Dr Ecco game site. Here are some suggestions from players of the games already on the site. Here is most of the existing code from the 2016 site. A final project could be to reflect these improvements and any others you have in mind.
    • The duellists which is similar to but more emotive than Optimal Basketball
    • Word Wrestle game.
    • Prime Squares game.
    • Circuit checking The ability to infer the semantics of a network is a major research area in the interpretation of neural nets.
    • Canoe problem (solitaire game) Note: There is a bug in proposed solution to the warm-up.
    • Strategic Bullying
    • Chair Games (solitaire)
    • Snowwalkers Here are some hints to get you started. To make this a two person game imagine that plowing the street on one side of a block or opening up a block so it's possible to go from any corner of the block to any other one are both moves that a player can make. The player wins who achieves the final connection.
    • Any game you like inspired by Shasha's CACM Upstart Puzzles which you can find on the ACM digital library. Here are some possibilities: roulette, auction, balance, canoe, cardnim, choreography, dust wars, finding october, lava, ruby risks, chair games, find me quickly, randomower, strategic bullying, string along, string wars, take your seats.
    • Competitive solitaire games such as for example Conway's Game of Life. as suggested by former Heuristics student Aaron McKinstry.
• Class 12
  • Presentation of Dr. Ecco site interface for uploading games.
  • Each team presents the team's idea for a game. Dennis may try to simplify.
  • Redemption for Evasion.
• Class 13
  • Presentation of first final projects.
  • Gravitational Voronoi game redemption. Here are some artworks resulting from a "melee" version of Gravitational Voronoi from 2017.
  • Upstart puzzles.
  • Redemption for Evasion or Seesaw.
• Class 14
  • All "production-quality" software on the website.
  • Metaalgorithm for machine learning. Here are slides about safepredict. Here is the code
  • Presentation of more software
  • Redemption day if more redemption is desired.

Books

• Optional: Puzzles for Programmers and Pros D. Shasha John Wiley/Wrox, 2007.
• Optional: How to Solve It: Modern Heuristics Z. Michaelewicz and D. Fogel Springer Verlag, ISBN 3-540-66061-5
• Optional: Games of No Chance Richard J. Nowakowski Cambridge University Press ISBN: 0521646529

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.

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. Here is a decision tree to help guide the choice of linear programming/ non-linear programming solutions.

An article about student-invented games is 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.

Gruelinga and rewarding in equal measure.

One of the best courses that I have taken at NYU! Although it's an insane amount of work, definitely gonna miss the weekly classes and the KitKats!

Ravi, Prasad, and I [Zeno] 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.

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.

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.

Amount of coursework: far too much (but in a good way).

For the difficulty, amount, and pace, I say 4 because notably difficult, but I really enjoyed the challenge. Best course I have taken here yet. Rather than feeling like I learned new information, I feel more intelligent overall!

Great course--very good structure in terms of pairing up and playing the role of competitors and architects. Some of the games had somewhat ambiguous or underspecified rulesets. Also others seemed to be somewhat overly complex needelessly, so possibly just try to simplify in some cases for the next offering. Overall they were quite varied and engaging though!

Love the setup of the course. Solving problems is the best way to learn ComputerScience and that is exactly the aim of the course.... self sustained class where everybody can leave with a smile on their faces at the end of the course.

Really loved this course!!! At the end of the class I realized always always it's more important to come up with a solution. And then, it's cool to OPTIMIZE that!

More chocolates. Harder and bigger chocolates.

I am going to University of Toronto for Ph.D. next January. And I put the KitKat rewards in the reward/honor section of my CV.

Saurabh Singh 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.