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!

Announcements

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!

Handouts

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

Assignments

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 Handouts

Section Handout 1 (solutions)
Section Handout 2 (solutions)
Section Handout 3 (solutions)
Section Handout 4 (solutions)
Section Handout 5 (solutions)
Section Handout 6 (solutions)

Resources

Office Hours Schedule
Course Notes
Lecture Videos

Lectures

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