Skip to content
QC CSCI + Math Notes

Lecture 12 - KARP 21 Problems Continued (Node Cover, Hitting Set, Steiner Tree, 3D Matching) and NP-Hardness - March 9, 2026

Administrative Updates

Section titled “Administrative Updates”

  • Exam reference material: For exams, students are responsible for Karp’s original definitions of the NP-hard problems. Do not rely on alternative formulations found elsewhere, as variations exist but the course uses Karp’s paper for consistency across exams.

  • Recommended reading (informal homework): The professor encouraged students to read Karp’s original paper on their own, particularly the section on the Steiner Tree problem. This will not be formally checked, but is strongly recommended for solidifying definitions.

  • Updated lecture notes: The professor indicated that the lecture notes will be finalized and a updated version will be sent out later today (March 9).

  • Attendance: Students who had not yet done so were asked to type “present” in the chat before the end of class.

  • Next class: The course will continue on Wednesday.

  • Student questions: A student (Ali) had a question regarding uploading project tags. The professor asked Ali to email the class-designated email address; a personal reply will be sent in the early afternoon. If the matter affects the whole class, a class-wide email will follow.