Heuristic Problem Solving:


Professor B. Mishra
Teaching Assistants:
TBA [ email: tba ]

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

Cancelled Classes (tentative):
September 11 2014 (Distinguished Lecture in Oklahoma)
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:

Mathematical Maturity, Programming and Algorithms

Grading Policy:
Quiz: 55 %; Project: 35 %; Final Exam: 10 %
Notes [ Lecture #1 ]

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

Bud Mishra
September 1 2003