🍎 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
Instructors: Rohan Menezes & Charley Cunningham
Location: Towne 319
Time: Tue 5:15-6:45 PM
Course Sites: Please sign up for Ed 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 1890 but have a conflict with the combined lecture.
🎓 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 (on Tuesday, 1/17).
CIS 1210 is a prerequisite for CIS 1890. 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%
📅 Schedule
| Week | Date | Lecture | Additional Code | Homework |
| 1 | 1/17 | Intro to Hard Problems | Setup and HW0: Finger Exercises (due Tuesday, 1/24 by 4pm) | |
| 2 | 1/24 | Solvers & Encoding | Graph coloring | HW1: Sudoku (due Tuesday, 2/7 by 4pm) |
| 3 | 1/31 | Algorithms for SAT | ||
| 4 | 2/7 | Modern SAT Techniques | HW2: PennSAT (due Tuesday, 2/21 by 4pm) | |
| 5 | 2/14 | Linear & Mixed-Integer Programming | Basic LP, max flows, CPU assignment | |
| 6 | 2/21 | More Mixed-Integer Programming | Debugging MIP | HW3: Kidney Exchange (due Tuesday, 3/14 by 4pm) |
| 7 | 2/28 |
Guest Lecturer: Rick Stone (recording,
passcode: HmqV5B@?)
|
Final projects (partners due 3/16, proposal due 3/23) | |
| 8 | 3/14 | Intro to Constraint Programming | Cryptarithms, taxis, job shop | HW4: Grace Hopper (due Tuesday, 3/28 by 4pm) |
| 9 | 3/21 | More Constraint Programming | Magic sequence, ships | Project proposal due this Thursday 3/23! |
| 10 | 3/28 | From CP to SAT | ||
| 11 | 4/4 | TSP Techniques | ||
| 12 | 4/11 | Local Search | Project check-in due next week! | |
| 13 | 4/18 | Genetic Algorithms | Project presentations next class! |