Heuristic Problem Solving:

CSCI-GA.2965-001


Lecturer:
Professor B. Mishra
with
Teaching Assistants:
Julien Rabinow [ email: jnr305@nyu.edu ]
office hours: Monday 4 to 5PM and Tuesday from 6 to 7 PM

Calendar
First Day of Class: September 04 2014
Last Day of Class: December 11 2014

Cancelled Classes (tentative):
September 11 2014 (Distinguished Lecture in Oklahoma)
October 2 2014 (Summer School in Como, Italy)
November 6 2014 (Plenary Talk at GAMESEC14 in LA)
Note that some of these classes may be covered by Guest Lectures.


Office Hours: By appt.
Office Phone: 212.998.3464
Email Address: mishra@nyu.edu

Day, Time and Place:
Thursdays, 5:10-7:00pm EST, CIWW 512 (251 Mercer St, NYC).

Credits for Course:
3

Prerequisites:
Mathematical Maturity, Programming and Algorithms

Grading Policy:
Quiz: 55 %; Project: 35 %; Final Exam: 10 %
Notes:
[ Lecture #1 || Lecture #2 || Lecture #3 || Lecture #4 || Lecture #5 || Lecture #6 || Lecture #7 ]

Syllabus:
Project 1: Kumar and Chris have published a specification and sample datasets for the TSP challenge. The details are contained in a Google Doc which is accessible here ...

You can leave comments in the Google doc or email them directly: ck1456@nyu.edu kumar.prabhu@nyu.edu There is a companion website where you can get all of the sample data (inputs and outputs)...


Syllabus:
Computational thinking is not new; it is grounded in more fundamental disciplines such as mathematics, philosophy and linguistics. Algorithmic approaches to understand the world has proven excitingly successful, with many important examples: Chmosky's formulations of linguistics, Feynman's formulations of quantum computing, systems biology formulations of developmental biology, game theoretic models of social networks, markets, and institutions, etc.

Yet, many of the computational problems we face are incomprehensibly intractable: satisfiability of logical formulas, geometry of optimal tours, whole genome (genotypic/haplotypic) assembly, machine learning for probabilistic graphical models, Compressive sensing, etc., to name a few. Despite theoretical pessimism, there have been some spectacular successes (NP-Easy problems).

Even more frustratingly, our ability to understand and formulate new problems that the society faces (with increasing access to computing and ability to generate data) has been dismal. Ideas based on hypotheses generation, prototyping minimal experiments (MVPs), and scaling continue to expose us to enormous risks (and rewards).

This course will focus on computational thinking, problem formulating, characterizing complexity, and problem solving using various heuristic approaches.

A detailed syllabus for the class will be designed in collaboration with the students attending the class.


Some Topics:
1. Problem Classes
2. Complexity: Itractability
3. Examples: SAT, TSP, WGSA, CS, PGM, etc.
4. Heuristics
5. Easy Instances of Hard Problems
6. Hypotheses Testing and Experiment (MVP) Design
7. Pivoting

Required Text(s):


Recommended Text(s):


Midterm Date:
No Midterm.
Final Date:
Class Project.
Homework(s):
Class Presentation.

Bud Mishra
September 1 2003