Final Exam Logistics

June 1, 2012

The final exam for CS103 is next **Friday, June 8** and runs from 12:15-PM
to 3:15PM. It covers material up through and including Monday's lecture.

The final exam location is based on the first letter of your last name:

- A - R: Go to Nvidia Auditorium
- S - Z: Go to Huang 018

We have posted an extra credit practice exam to help you prepare for the final. If you complete this practice exam and make a good-faith attempt to answer all of the questions, it's worth +5 extra credit points. We will release additional practice final exams between now and the final exam, but they will not be worth any extra credit points.

Problem Set Nine Out

June 1, 2012

Problem Set 9, the last problem
set of the quarter, is now available. It covers P, NP, and NP-completeness
along with a review of the entire hierarchy of languages we've covered. It is
due next **Wednesday**, June 6. You may use a late day on this problem
set if you would like, but we will not accept any submissions later than Thursday,
June 7th at 2:15PM so that we can release solutions.

Good luck!

Problem Set Eight Out

May 25, 2012

Problem Set 8 is now available. The problem set is due on Friday, June 1 at 2:15PM and explores what lies beyond the scope of what can be solved.

Good luck!

Problem Set Seven Out

May 18, 2012

Problem Set 7 is now available. The problem set is due on Friday, May 25 at 2:15PM, and explores R and RE languages, their properties, and their limits.

Good luck!

Problem Set Six Out

May 11, 2012

Problem Set 6 is now available. The problem set is due on Friday, May 18 at 2:15PM, and explores context-free languages, their representations, and their limits.

Good luck!

Problem Set Five Out

May 4, 2012

Problem Set 5 is now available. The problem set is due on Friday, May 11 at 2:15PM. This problem set explores regular languages, their properties, and their limitations. This will be the first time that you get to apply your mathematically savvy to computability theory, and I hope you're excited!

Some of the questions on this problem set will ask you to design DFAs and NFAs. This quarter, we're rolling out a new tool that you can use to design, test, and submit automata. If you are interested in trying out the tool, you can access the DFA and NFA editor through the preceding link. Please let us know if you have any questions about the tool or suggestions for improvement!

Good luck!

Midterm Logistics

May 2, 2012

The midterm exam is coming up next **Tuesday, May 8** from 7:00PM - 10:00PM.
It will cover material up through and including Wednesday's lecture on regular
expressions and closure properties.

The midterm location is based on the first letter of your last name:

- A - J: Go to 200-002
- K - Z: Go to Hewlett 201

We have posted a practice midterm exam to help you prepare for the midterm. Its content and form are similar to the sorts of problems that you might see on the real midterm.

Problem Set Four Out

April 27, 2012

Problem Set 4 is now available. There are no checkpoint problems this time, and the problem set is due on Friday, May 5 at 2:15PM. This problem set concerns logic and its applications, and should make you very comfortable with propositional logic, first-order logic, and properties of SAT-solving algorithms.

Good luck!

Problem Session Location Change

April 23, 2012

The time and place for the problem sessions has moved. They will now be held
on Mondays from **4:15 - 5:05PM** in **Huang 018**. Hope to see you there!

Problem Set Three Out

April 20, 2012

Problem Set 3 is now available. The checkpoint problems are due next Monday, April 23rd, at the start of class. The remaining problems are due at the start of class on Friday, April 27th. These problems cover graphs, relations, functions, inverses, cardinality, and the pigeonhole principle, and by the time you're done you'll have a good feel for how these concepts interrelate.

Good luck!

Problem Set Two Out

April 13, 2012

Problem Set 2 is now available. The checkpoint problems are due next Monday, April 16th, at the start of class. The remaining problems are due at the start of class on Friday, April 20th. This problem set should give you a chance to play around with induction and to see just how powerful a technique it is.

Good luck!

Office Hours Schedule Posted

April 6, 2012

We have posted our office hours schedule for the quarter. We're still getting rooms reserved, so check back periodically to see where we'll be. Office hours start this Saturday, April 7.

Problem Set One Out

April 5, 2012

Problem Set 1 is now available. The checkpoint problems are due next Monday, April 9th, at the start of class. The remaining problems are due at the start of class on Friday, April 13th. This problem set should give you a chance to play around with set theory and proof techniques.

Good luck!

Welcome to CS103!

March 30, 2012

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: Problem Set 1

03C: Problem Set 1 Checkpoint Solutions

03S: Problem Set 1 Solutions

04: Section Handout 1

04S: Section Solutions 1

05: Problem Set 2

05C: Problem Set 2 Checkpoint Solutions

05S: Problem Set 2 Solutions

06: Relations

07: Section Handout 2

07S: Section Solutions 2

08: Problem Set 3

08C: Problem Set 3 Checkpoint Solutions

08S: Problem Set 3 Solutions

09: Section Handout 3

09S: Section Solutions 3

10: Problem Set 4

10S: Problem Set 4 Solutions

11: Section Handout 4

11S: Section Solutions 4

12: Practice Midterm

12S: Practice Midterm Solutions

13: Problem Set 5

13S: Problem Set 5 Solutions

14: CS103 Midterm

14S: CS103 Midterm Solutions

15: Problem Set 6

15S: Problem Set 6 Solutions

16: Section Handout 5

16S: Section Solutions 5

17: Problem Set 7

17S: Problem Set 7 Solutions

18: Section Handout 6

18S: Section Solutions 6

19: Problem Set 8

19S: Problem Set 8 Solutions

20: Problem Set 9

20S: Problem Set 9 Solutions

21: EC Practice Final

22: Practice Final #1

22S: Practice Final #1 Solutions

23: Practice Final #2

23S: Practice Final #2 Solutions

24: Practice Final #3

24S: Practice Final #3 Solutions

25: CS103 Final Exam

25S: CS103 Final Exam Solutions

Problem Set 1

(checkpoint solutions)

(solutions)

Problem Set 2

(checkpoint solutions)

(solutions)

Problem Set 3

(checkpoint solutions)

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

Section Handout 1
(solutions)

Section Handout 2
(solutions)

Section Handout 3
(solutions)

Section Handout 4
(solutions)

Section Handout 5
(solutions)

Section Handout 6
(solutions)

Office Hours Schedule

Course Notes

Lecture Videos

00: Introduction, Set Theory

01: Direct Proofs

02: Indirect Proofs

03: Mathematical Induction

04: Mathematical Induction, Part 2

05: Graphs and Relations

06: Functions

07: The Pigeonhole Principle
(code)

08: Mathematical Logic

09: Mathematical Logic, Part 2

10: SAT Solving

11: DFAs

12: NFAs

13: Regular Expressions

14: Limits of Regular Languages

15: Context-Free Languages

16: Pushdown Automata

17: Limits of CFLs

18: Programming Turing Machines

19: The Universal Turing Machine

20: Unsolvable Problems

21: Reductions

22: Reductions, Part 2

23: P

24: NP

25: NP-Completeness

26: Topics in Complexity

27: The Big Picture