🍎 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.7 / 4
Course
4 / 4
Instructor
1.9 / 4
Difficulty
2.1 / 4
Workload
🧭 Logistics
Instructors: Anushka Daga & Thomas Ngulube
Location: AGH 216B
Time: Tue 5:15-6:44 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 be 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: 45%
Final Project: 30%
PureMEMs: 15%
Participation: 10%
👋 Teaching Staff
📅 Schedule
| Week | Date | Lecture | Additional Material | Homework |
| Syllabus | ||||
| 2 | 1/20 | Intro to Hard Problems: Lecture Slides and Lecture Notes | Setup and HW0: Finger Exercises (due Tuesday 1/27 by 11:59pm) | |
| 3 | 1/27 | snow day | HW1: Sudoku (due Tuesday, 2/10 by 11:59pm) | |
| 4 | 2/03 | Solvers & Encoding: Lecture Slides and Lecture Notes | Graph coloring Code | |
| 5 | 9/11 | Algorithms for SAT: Lecture Slides and Lecture Notes | HW2: PennSAT (due Tuesday, 2/24 by 11:59pm), HW2 Primer Video | |
| 6 | 9/18 | Modern SAT Techniques: Lecture Slides | ||
| 7 | 9/25 | Linear & Mixed-Integer Programming: Lecture Slides and Lecture Notes | Basic LP, Max Flows, CPU Assignment | HW3: Kidney Exchange Program (due Tuesday, 3/17 by 11:59pm) |