CS 374 A


Handouts and Solutions

Wed Aug 23
Lab 1a: String induction [solutions] [induction notes] [helpful advice on writing proofs]
Fri Aug 25
Lab 1b: Regular expressions [solutions]
Wed Aug 30
Lab 2a: DFAs [solutions]
Fri Sep 1
Lab 2b: DFA product construction [solutions]
Wed Sep 6
Lab 3a: Proving nonregularity [solutions]
Fri Sep 8
Lab 3b: Regular expression to NFA to DFA (to regular expression) [solutions]
Wed Sep 13
Lab 4a: Language transformations [solutions]
Fri Sep 15
Lab 4b: Context-free grammars [solutions]
Wed Sep 20
Lab 5: More language transformations [solutions]
Fri Sep 22
Review for Midterm 1

Wed Sep 27
Lab 6a: Hint: Binary search [solutions]
Fri Sep 29
Lab 6b: Fun with Karatsuba [solutions]
Wed Oct 4
Lab 7a: Backtracking [solutions]
Fri Oct 6
Lab 7b: Dynamic programming [solutions]
Wed Oct 11
Lab 8: More dynamic programming [solutions]
Fri Oct 13
Lab 8b: Return of the son of revenge of dynamic programming [solutions]
Wed Oct 18
Lab 9a: Graph modeling [solutions]
Fri Oct 20
Lab 9b: Topological sort [solutions]
Wed Oct 25
Lab 10a: Shortest paths [solutions]
Fri Oct 27
Lab 10b: All-pairs shortest paths [solutions]
Wed Nov 1
Lab 11: Solve it both ways [solutions]
Fri Nov 3
Review for Midterm 2

Wed Nov 8
Lab 12a: Reductions [solutions]
Fri Nov 10
Lab 12b: NP-hardness proofs [solutions]
Wed Nov 15
Lab 13a: More NP-hardness proofs [solutions]
Fri Nov 17
Lab 13b: Even more NP-hardness proofs [solutions]
Wed Nov 29
Lab 14a: Yet even still more NP-hardness examples [solutions]
Fri Dec 1
Lab 14b: Using Rice's Theorem [solutions]
Wed Dec 6
Review for the final exam

About Labs

Each student must register for one of ten 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. 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. At the end of the meeting, the TA quickly walks through the solutions to the remaining problems, with help from the students. If necessary, the TAs may also briefly review material from past lectures or prerequisite courses, but they will not present new course material.

We will post lab handouts 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 on Ed Discussion and/or Discord after each lab session; students who post correct solutions or insightful hints for lab problems will get some extra credit. 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. But don't make the mistake of thinking that you can learn to solve problems by reading solutions. The only way to learn to solve problems is to practice solving problems.