🍎 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!
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.
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.
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!
Final Project: 30%
👋 Teaching Staff
|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|
|14||12/7||Final Project Presentations||Final project (due 12/10 by midnight)|