COS IW 04: Practical Solutions to Intractable Problems, Spring 2023

Course information

Semester: Spring 2023
Meetings: Wednesday, 11:00am-12:20pm
Location: CS 301
Instructors: Zak Kincaid, zkincaid@cs.princeton.edu
Office hours: Monday 1:30-2:30pm, CS 219
Links: Independent work, Guidelines, Steps and deadlines, Canvas, Ed

Description

Suppose that you encounter an algorithmic problem that you need to solve but which is computationally intractable (say, NP-hard, PSPACE-hard, or even undecidable). What can you do? While it's impossible to design an algorithm that works efficiently all of the time, it's certainly possible to develop solutions that work well 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. We'll survey some strategies for solving hard problems, including heuristic search, relaxation, approximation, and randomization. A typical project is to choose a problem of interest (e.g., a solver for some class of puzzle or an agent for playing a strategy game), and to 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.

Schedule

This is a preliminary schedule that will be populated during the course.

Date Topic/Deadline
Jan 31 Attend the "Getting Started" Information Meeting
Feb 1 Introduction
Feb 8 Project pitches
Feb 15 Games and adversarial search
Feb 20 Submit a Written Project Proposal
Feb 22 Randomization
Feb 29 Relaxation, Integer linear programming
March 5 Heuristic search
Mar 11 Submit the Checkpoint Form
Mar 15 No class (Spring break)
Mar 22 Heuristic search II
Mar 28 Attend "How to Give an IW Talk"
Mar 29 Relaxation
Apr 5 Approximation
Apr 12 Practice presentations
Apr 14 Attend "How to Write an IW Paper"
Apr 16 Submit Oral Presentation Slides and Video-Recorded Oral Presentation
May 1 Submit a Written Final Report

Links