🍎 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.
3.4
Course
3.5
Instructor
2.2
Difficulty
2.1
Workload
🧭 Logistics
Instructor: Ishaan Lal
Location: Towne 327
Time: Thurs 7:00-8:30 PM
Course Sites: Please sign up for Ed and Gradescope through Canvas!
🎓 Enrollment
Please request permission through Path! Permits to register will be granted periodically. Even if you aren't officially enrolled yet, feel free to show up to the first class!
CIS 1210 is a prerequisite for CIS 1921. 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.5 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
📅 Schedule
| Week | Date | Lecture | Additional Material | Homework |
| Syllabus | ||||
| 1 | 8/29 | Lecture Slides and Lecture Notes | Setup and HW0: Finger Exercises (due Monday, 9/9 by 11:59pm) | |
| 2 | 9/5 | Solvers & Encoding Slides and Lecture Notes | Graph coloring Code and Lecture Recording | HW1: Sudoku (due Monday, 9/23 by 11:59pm) |
| 3 | 9/12 | Algorithms for SAT: Lecture Slides and Lecture Notes | Lecture Recording | |
| 4 | 9/19 | Modern SAT Techniques | Lecture Recording | HW2: PennSAT (due Monday, 10/7 by 11:59pm) |
| 5 | 9/26 | Linear & Mixed-Integer Programming Slides and Notes | Basic LP, max flows, CPU assignment Lecture Recording | |
| 6 | 10/10 | More Mixed-Integer Programming Lecture Slides and Lecture Notes | Lecture Recording | HW3: Kidney Exchange (due Monday, 10/28 by 11:59pm) |
| 7 | 10/17 | Guest Lecture | Final Project Details | Final Project: Partners due 10/24, Proposal due 10/28 |
| 8 | 10/24 | Intro to Constraint Programming Slides and Notes | Cryptarithms, taxis, job shop. Lecture Recording | HW4: Grace Hopper (due Monday, 11/11 by 11:59pm) |
| 9 | 10/31 | More Constraint Programming Slides and Notes | Magic Sequence, Ships, Queens | Project Checkpoint due 11/21! |
| 10 | 11/7 | From CP to SAT Slides and Notes | Lecture Recording |