COS IW 10: Practical Solutions to Intractable Problems, Fall 2023

Course information

Semester: Fall 2023
Meetings: Wednesdays 11:00am-12:20pm
Location: COS 302
Instructors: Zak Kincaid, zkincaid@cs.princeton.edu
Office hours: Mondays 10:00-11:00am, COS 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
Sept 5 Attend the "Getting Started" Information Meeting
Sept 6 Introduction
Sept 13 Project pitches, Heuristic search
Sept 20 Games
Sept 27 Submit a Written Project Proposal, Adversarial search
Oct 18 No class (Fall break)
Oct 25 Submit the Checkpoint Form
Nov 7 Attend "How to Give an IW Talk"
Dec 5 Attend "How to Write an IW Paper"
Dec 10 Submit Oral Presentation Slides and Video-Recorded Oral Presentation
Jan 11 Submit a Written Final Report

Links