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 htiek@cs.stanford.edu with questions.

See you soon!

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 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