COS IW 08: Practical Solutions to Intractable Problems, Spring 2017

Course information

Semester: Spring 2017
Lectures: Monday 3:00 - 4:30pm
Location: CS 301
Instructors: Zak Kincaid, zkincaid@cs.princeton.edu
Links: Independent work, Guidelines, Steps and deadlines, Piazza

Description

In theoretical computer science, a problem is typically considered to be tractable if it can be solved by a polynomial time algorithm. There are many natural problems for which no such algorithm exists: finding a satisfying assignment to a boolean formula, finding a winning strategy for a game of checkers, finding an input that makes a program crash, etc. While theory dictates that all algorithms for such problems must have poor worst case behavior, it is often possible to avoid the worst case in practice. For example, despite the fact that boolean satisfiability is NP-complete, modern SAT solvers can scale to millions of variables and clauses for the kinds of formulas that arise in typical applications, such as verification, synthesis, and planning.

In this seminar, students will engage in research on how intractable problems are solved in practice. A typical project is to choose a problem of interest and design, implement, and experimentally evaluate a technique for solving that problem. The technique could involve exploiting existing tools (such as SAT solvers, theorem provers, or integer programing solvers) or designing a new algorithm (perhaps based on the principles of heuristic search, relaxation, or approximation).

Schedule

This is a tentative schedule that will be changed during the course.

Date Topic/Deadline
Feb 6 Aarti Gupta on Propositional Satisfiability
Feb 7 Attend the Information Meeting 12:30 PM, Convocation Rm., Friend Center
Feb 13 Relaxation
Feb 20 Project Pitches. Randomization and approximation.
Feb 24 Submit a Written Project Proposal
Mar 13 Submit the Checkpoint Form
Apr 3-7 Sign up to give an Oral Presentation
TBA Attend "How to Give an IW Talk"
TBA Attend "How to Write an IW Paper"
Apr 23 Submit Slides for an Oral Presentation
Apr 24-28 Give an Oral Presentation
May 5 Submit a Written Final Report
Mar 20 No class (Spring break)
May 11 Present at the Poster Session in Convocation Room, Friend Center

Reading