Alternate Final Exam Locations
December 11, 2011

The alternate final exam tonight (Sunday, 7:00PM - 10:00PM) will be in Gates 100. Tuesday's alternate final exam (Tuesday, 12:15PM - 3:15PM) will be in Herrin T175.

Final Exam Logistics
December 7, 2011

The final exam for CS103 will be on Monday, December 12 from 12:15PM - 3:15PM in Hewlett 200 (the same location as the midterm). It will be worth 20% of your total grade in the course and is heavily weighted toward the latter half of the material.

There will be two alternate final exam times: Sunday, December 11 from 7:00PM - 10:00PM in Gates 100 and Tuesday, December 13 from 12:15PM - 3:15PM in Herrin T175. If you want to take the exam at an alternate time, please contact us no later than this Friday at 2:15PM so that we can make room arrangements.

Over the weekend, we will hold two review sessions, one on Saturday, December 10 from 3:00PM - 5:00PM in Gates 104 and one on Sunday, December 11 from 1:00PM - 3:00PM. Feel free to stop by with any questions; we want these sessions to be as useful as possible.

To help you study, we have released an extra credit practice final. This practice final is worth 20 extra credit points and is graded based on whether or not you made a good-faith effort to do the problems rather than whether you have correct answers, so as long as you make an effort to solve the problems we'll be happy to award you extra credit. This practice final is due right before you take the final exam.

Over the next three days, we will be releasing old final exams with solutions. The structure of the final exam for this quarter will be similar to the structure of the extra credit practice final, but the problems on the old final exams should help you prepare for the upcoming exam.

As always, if you have any questions, please feel free to get in touch with us.

Good luck!

Problem Set Nine Out, Problem Set Eight Due
December 2, 2011

Problem Set 9, the final problem set of the quarter, went out today and is due Friday, December 9 at 2:15PM. This problem set explores nondeterminism and NP-completeness, and I hope it gives you an appreciation for how common and difficult NP-complete problems can be.

Problem Set 8 is due right before class.

Good luck!

Problem Set Eight Out, Problem Set Seven Due
November 18, 2011

Problem Set 8 went out today and is due Friday, December 2 at 2:15PM. That's after the break, so hopefully you'll have some time to recharge before you start probing the limits of what can be solved by a computer. :-)

Problem Set 7 is due right before class.

Good luck!

Problem Set Seven Out, Problem Set Six Due
November 11, 2011

Problem Set 7 went out today and is due Friday, November 18 at 2:15PM. This problem set explores context-free grammars, pushdown automata, and their limits, and by the time you're done you'll have a thorough command of context-free languages.

Problem Set 6 is due right before class.

Good luck!

Problem Set Six Out, Problem Set Five Due
November 4, 2011

Problem Set 6 went out today and is due Friday, November 11 at 2:15PM. This problem set explores the limits of regular languages, and I hope that it gives you a better intuition for what can and cannot be solved with DFAs, NFAs, and regular expressions.

For those of you who are interested in getting more practice with proofs, I've posted a handout of extra practice problems that reviews all of the material before automata theory. Feel free to email us if you have any questions!

Problem Set 5 is due right before class.

Good luck!

Problem Set Five Out, Problem Set Four Due
October 28, 2011

Problem Set 5 went out today and is due Friday, November 4 at 2:15PM. This problem set should help give you a better feel for what the regular languages are, how finite automata work, and how the mathematical techniques we've built up over the course of the quarter can be applied to the theory of computation. I hope you have fun with it!

Problem Set 4 was due right before the midterm last night. If you want to turn it in using a late day, it will be due tonight at 7:00PM.

Good luck!

Midterm Locations
October 26, 2011

The midterm examination will be tomorrow, Thursday, October 27 from 7:00PM - 10:00PM in Hewlett 200. There are two alternate exam times: Wednesday, October 26 from 7:00PM - 10:00PM in Gates 100, and Thursday, October 27 from 9:00AM - Noon in Gates 167. If you have not already indicated that you'd like to take the midterm at an alternate time, please do so immediately by emailing the staff list so we that we can reserve extra space if we need it.

Best of luck!

Practice Midterm Available
October 23, 2011

A practice midterm is available to help you prepare for Thursday's midterm exam. The format of the exam is very similar to the real exam in terms of number, ordering, and content of questions. The midterm will be open-book, open-note, open-computer, but closed-network, meaning that you can bring in your laptop if you'd like, but you must not use a network connection. After all, I do not want you to print out thousands of pages of lecture slides!

This exam contains one question that is on a topic we have not yet covered (finite automata). The actual midterm will contain at least one question on material from Monday and Wednesday's lectures, but it will not require a deep understanding of the material. If you attend lecture, you should have no trouble solving it.

Solutions will be handed out in this week's review sessions and will be posted on Monday night.

Problem Set Four Out, Problem Set Three Due
October 21, 2011

Problem Set 4 went out today and is due Thursday, October 27 at 7:00PM, right before the midterm. This problem set explores functions, the pigeonhole principle, and structural induction, and I think you're really going to enjoy some of the results you'll end up proving.

Problem Set 3 is due right before class today at 2:15PM.

Good luck!

Problem Set Three Out, Problem Set Two Due
October 14, 2011

Problem Set 3 went out today and is due Friday, October 21 at 2:15PM, right before class starts. This problem set explores propositional logic, first-order logic, and applications of induction and proofs to algorithms and data structures. I hope you have a lot of fun with it!

Problem Set 2 is due right before class today at 2:15PM.

Good luck!

Problem Set Two Out, Problem Set One Due
October 7, 2011

Problem Set 2 went out today and is due Friday, October 14 at 2:15PM, right before class starts. This problem set delves into the wonderful and beautiful world of induction, giving you a taste of just how powerful this simple technique can be. As always, feel free to stop by office hours if you have any questions.

Problem Set 1 is due right before class today at 2:15PM.

Good luck!

Review Session Tonight in 370-370
September 30, 2011

We will be holding our first review session tonight in 370-370 from 7-8PM. Note that the room has changed, we are no longer meeting in 380-380W. We hope that this will be a great way to sharpen your skills with proofs, sets, relations, and graphs. We will be covering questions from this section handout, so it might be a good idea to review the questions before showing up.

Hope to see you there!

Problem Set One Out, Due Friday, October 7
September 30, 2011

Problem Set 1 went out today and is due Friday, October 7 at 2:15PM, right before class starts. This will be a great way to play around with sets, relations, graphs, and proof techniques, and I hope that you have fun with it. As always, feel free to email us with questions or drop by office hours.

Good luck!

Office Hours Schedule Posted
September 30, 2011

The office hours schedule for this quarter is now available. We're still filling in all the gaps in room assignments, so be sure to check back periodically for more information about where to meet us.

Hope to see you there!

Welcome to CS103!
September 22, 2011

Welcome to CS103, an exciting and fast-paced introduction to discrete mathematics, computability theory, and complexity theory! We have an great quarter ahead of us filled with interesting and exciting results in the power and limits of computation, and I hope that you're able to join us.

In the meantime, feel free to check out the course information handout to learn more about what this class is all about, the prerequisites, and the course policies. If you have any questions in the meantime, feel free to email me at with questions.

See you soon!

Office Hours Schedule


00: Course Information
01: Syllabus
02: Prior Experience Survey
03: Relations
04: Problem Set 1
04S: Problem Set 1 Solutions
05: Section Handout 1
05S: Section Solutions 1
06: Problem Set 2
06S: Problem Set 2 Solutions
07: Section Handout 2
07S: Section Solutions 2
08: Problem Set 3
08S: Problem Set 3 Solutions
09: Section Handout 3
09S: Section Solutions 3
10: Problem Set 4
10: Problem Set 4 Solutions
11: Practice CS103 Midterm
11S: Practice CS103 Midterm Solutions
12: CS103 Midterm
12S: CS103 Midterm Solutions
13: Problem Set 5
13S: Problem Set 5 Solutions
14: Section Handout 4
15: Problem Set 6
15S: Problem Set 6 Solutions
16: Extra Practice Problems
17: Section Handout 5
18: Problem Set 7
18: Problem Set 7 Solutions
19: Section Handout 6
19S: Section Solutions 6
20: Problem Set 8
20S: Problem Set 8 Solutions
21: Section Handout 7
21S: Section Solutions 7
22: Problem Set 9
22: Problem Set 9 Solutions
23: Section Handout 8
23S: Section Solutions 8
24: Extra Credit Practice Final
25: Additional Practice Final #1
25S: Additional Practice Final #1 Solutions
26: Additional Practice Final #2
25S: Additional Practice Final #2 Solutions
27: Additional Practice Final #3
27S: Additional Practice Final #3 Solutions
28: CS103 Final Exam
28S: CS103 Final Exam Solutions


Problem Set 1 (solutions)
Problem Set 2 (solutions)
Problem Set 3 (solutions)
Problem Set 4 (solutions)
Problem Set 5 (solutions)
Problem Set 6 (solutions)
Problem Set 7 (solutions)
Problem Set 8 (solutions)
Problem Set 9 (solutions)
Extra Credit Practice Final

Section Handouts

Section Handout 1 (solutions)
Section Handout 2 (solutions)
Section Handout 3 (solutions)
Practice CS103 Midterm (solutions)
Section Handout 4 (solutions)
Section Handout 5 (solutions)
Section Handout 6 (solutions)
Section Handout 7 (solutions)
Section Handout 8 (solutions)


00: Set Theory
01: Graphs and Relations
02: Proof Techniques
03: Proof Techniques II
04: Induction
05: Induction II
06: Induction III
07: Propositional Logic
08: First-Order Logic
09: First-Order Logic II
10: Functions and the Pigeonhole Principle
11: Trees and Structural Induction
12: DFAs
13: DFAs II
14: DFAs III, NFAs
15: NFAs II, Regular Expressions
16: Regular Expressions
17: The Pumping Lemma
18: Context-Free Grammars
19: Pushdown Automata
20: The Limits of CFLs, Turing Machines
21: Turing Machines
22: The Limits of Turing Machines
23: More Unsolvable Problems
24: Reductions and Rice's Theorem
25: P
26: NP
27: NP-Completeness
28: More NP-Completeness
29: Approximation Algorithms