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.
- Wed Jan 21
- Lab 1a: String induction — [solutions, induction notes, helpful advice on writing proofs]
- Fri Jan 23
- Lab 1b: Regular expressions — [solutions]
- Wed Jan 28
- Lab 2a: DFAs — [solutions]
- Fri Jan 30
- Lab 2b: DFA product construction — [solutions]
- Wed Feb 04
- Lab 3a: Proving nonregularity — [solutions]
- Fri Feb 06
- Lab 3b: NFA design — [solutions]
- Wed Feb 11
- Lab 4a: Language transformations — [solutions]
- Fri Feb 13
- Lab 4b: Context-free grammars — [solutions]
- Wed Feb 18
- Lab 5: Turing machines — [solutions]
- Wed Feb 25
- Lab 6a: Hint: Binary search — [solutions]
- Fri Feb 27
- Lab 6b: Fun with Karatsuba — [solutions]
- Wed Mar 04
- Lab 7a: Backtracking — [solutions]
- Fri Mar 06
- Lab 7b: Dynamic programming — [solutions]
- Wed Mar 11
- Lab 8a: More dynamic programming — [solutions]
- Fri Mar 13
- Lab 8b: Dynamic programming: fire and ash — [solutions]
- Wed Mar 25
- Lab 9a: Graph modeling — [solutions, graph layering notes]
- Fri Mar 27
- Lab 9b: More graph modeling — [solutions]
- Wed Apr 01
- Lab 10a: Shortest paths — [solutions]
- Fri Apr 03
- Lab 10b: More shortest paths — [solutions]
- Wed Apr 08
- Lab 11: Greedy algorithms and/or minimum spanning trees — [solutions]
- Wed Apr 15
- Lab 12a: Reductions — [solutions]
- Fri Apr 17
- Lab 12b: NP-hardness proofs — [solutions]
- Wed Apr 22
- Lab 13a: The NP-hardness proofs strike back — [solutions]
- Fri Apr 24
- Lab 13b: The return of the NP-hardness proofs — [solutions]
- Wed Apr 29
- Lab 14a: Undecidability via diagonalization — [solutions]
- Fri May 01
- Lab 14b: Undecidability via reductions and Rice's theorem — [solutions]