Labs
Handouts and solutions
- Wed Aug 26
- Lab 1a: String induction — [induction notes; helpful advice on writing proofs]
- Fri Aug 28
- Lab 1b: Regular expressions
- Wed Sep 02
- Lab 2a: DFA design
- Fri Sep 04
- Lab 2b: DFA product construction
- Wed Sep 09
- Lab 3a: Proving nonregularity
- Fri Sep 11
- Lab 3b: NFA design
- Wed Sep 16
- Lab 4a: Language transformations
- Fri Sep 18
- Lab 4b: Context-free grammars
- Wed Sep 23
- Lab 5: Language transformation practice
- Wed Sep 30
- Lab 6a: Try Binary searching
- Thu Oct 01
- Lab 6b: Fun with Karatsuba
- Wed Oct 07
- Lab 7a: Backtracking
- Fri Oct 09
- Lab 7b: Dynamic programming
- Wed Oct 14
- Lab 8a: More dynamic programming
- Fri Oct 16
- Lab 8b: Dynamic Programming: Return of the King
- Wed Oct 21
- Lab 9a: Applying graph traversals
- Fri Oct 23
- Lab 9b: Applying DAGs
- Wed Oct 28
- Lab 10a: Applying shortest paths
- Fri Oct 30
- Lab 10b: More applying shortest paths
- Wed Nov 04
- Lab 11: Solve it both ways
- Wed Nov 11
- Lab 12a: Polynomial time reductions
- Fri Nov 13
- Lab 12b: NP-hardness proofs
- Wed Nov 18
- Lab 13a: More NP-hardness proofs
- Fri Nov 20
- Lab 13b: The NP-hardness Proofs Revolutions
- Wed Dec 02
- Lab 14a: Undecidability via diagonalization
- Fri Dec 04
- Lab 14b: Undecidability via reductions and Rice's theorem
About labs
Each student must register for one of eleven biweekly lab sections which meet every Wednesday and Friday. As with lectures, lab attendance is strongly encouraged, but not mandatory.
At least during the first few weeks of the semester, please attend only the lab sections for which you are officially registered. Students who want to swap labs with another student should contact one of the TAs.
The labs are opportunities for you to develop your problem-solving and presentation skills. In each lab meeting, the course staff and the students will work on a small set of closely related problems, usually similar to problems in the current week’s homework.
In a typical lab meeting, after giving the students a few minutes to read and understand the problems, the TA walks through the process of solving the first problem on the lab handout, with suggestions from the students. Then the students break into groups of 3–5 to work on the remaining problems, with feedback and suggestions from the course staff and from each other.
If necessary, the TAs may also spend a few minutes reviewing material from past lectures or prerequisite courses, but labs are not intended to be a substitute for the lectures. We assume that students at each lab have attended previous lectures (or watched the videos) and read the appropriate portions of the textbook/lecture notes.
Lab handouts a posted to the course web site (both here and on the week-by-week schedule) at the beginning of each week. We strongly encourage you to look at the problems beforehand and to continue working on them after your section ends. In particular, we strongly encourage discussion of lab problems on Ed Discussion or Discord after each lab session. The course staff also will answer questions, provide hints, and give feedback on proposed solutions in office hours.
The point of the labs is to practice hunting (problem solving), not to acquire more meat (solutions). Our main job is to give you guidance in how to solve problems—how to track the wily inductive hypothesis, what bait best attracts fooling sets, how to sound the mating call of the dynamic programming recurrence, how to protect yourself from a swarm of angry vertices, how to safely build a trap for an undecidability proof—not just to show you answers.
That said, we also post solutions to each lab a day or two afterward, so that you can evaluate the results of your hunt. Please don’t make the mistake of thinking that you can learn to solve problems by reading (or worse, memorizing) solutions. The only way to learn to solve problems is to practice solving problems.