CIS 189: Solving Hard Problems in Practice

Fall 2021

🍎 Course Overview

What does Sudoku have in common with debugging, scheduling exams, and routing shipments? All of these problems are provably hard — no one has a fast algorithm to solve them. But in reality, people are quickly solving these problems on a huge scale with clever systems and heuristics!


In this minicourse, we’ll explore how researchers and organizations like Microsoft, Google, and NASA are solving these hard problems, and we’ll get to use some of the tools they’ve built!


Topics covered include: routing, scheduling, and packing problems; constraint programming in Python; SAT solving; optimization; operations research.

🧭 Logistics

Instructor: Jediah Katz

Location: Towne 307

Time: Tues 5:15-6:30 PM

Course Sites: Please sign up for Piazza and Gradescope through Canvas!

19x Combined Lecture: You must also enroll in the combined lecture, which consists of 3 optional lectures. Please reach out if you want to take CIS 189 but have a conflict with the combined lecture.

🎓 Enrollment

Please sign up through the CIS waitlist!

CIS 121 is a prerequisite for CIS 189. You are expected to be fairly comfortable with programming and familiar with graphs. Experience with Python is helpful but not necessary. Knowledge of NP-completeness is not necessary but useful to motivate the course.

📝 Grading

Homeworks will consist of 4 medium-size programming projects, assigned roughly biweekly.


You will work in pairs on a final project of your choosing — you might choose to solve a practical problem using the tools we’ll learn, implement a solver with modern techniques, or even explore new methods of your own!


Homework: 60%

Final Project: 30%

Attendance: 10%

👋 Teaching Staff

Jediah Katz

Instructor

jediahk@seas

Office hours:

After class

Ying Eng

Teaching Assistant

yxeng@seas

Office hours:

Mon 4-5pm, Fri 2:30-3:30pm (Zoom)

Aditya Singh

Teaching Assistant

adiprs@seas

Office hours:

Tue & Thu 12:30-1:30pm (Zoom)

Charley Cunningham

Teaching Assistant

ccunning@seas

Office hours:

Sun 4-5pm, Wed 1:30-2:30pm (Zoom)

All OH except Jediah's will be held on the 5th floor of Levine Hall, at the tables by the elevator. TA office hours are also available on Zoom if you cannot make it in person -- the Zoom links can be found in the OH schedule above.

📅 Schedule

Week Date Lecture Additional Code Homework
1 8/31 Intro to Hard Problems Setup, logistics form, and HW0: Finger Exercises (due Tuesday, 9/7 by 4pm)
2 9/7 Solvers & Encoding Graph coloring HW1: Sudoku (due Tuesday, 9/21 by 4pm)
3 9/14 Algorithms for SAT
4 9/21 Variable Selection & Solver Engineering Debugger tutorial HW2: PennSAT (milestone due 10/5 by 4pm, final submission due 10/19 by 4pm)
5 9/28 Modern Techniques in SAT Solving HW2 milestone due next week, don't forget!
6 10/5 Linear & Mixed-Integer Programming Basic LP, max flow, CPU assignment
7 10/12 Intro to Constraint Programming Taxi assignment, job shop scheduling
8 10/19 More Constraint Programming Magic sequences, shipment allocation HW3: Grace Hopper (due 11/2 by 4pm), Final Project (find partner by 11/2)
9 10/26 Symmetry Breaking Sports scheduling
10 11/2 From CP to SAT Final project proposal (due 11/9 by 4pm)
11 11/9 Guest Lecture with Serdar Kadıoğlu
12 11/16 TSP Techniques Final project check-in (due 11/30 by 4pm)
- 11/23 No Class - Thanksgiving Schedule
13 11/30 Local Search
14 12/7 Final Project Presentations Final project (due 12/10 by midnight)