The final exam will be on Wednesday, December 9 from 3:30PM - 6:30PM in Cemex Auditorium. Best of luck with the rest of your studying, get a good night's sleep, and we'll see you tomorrow!
For Problem Set Eight, you're welcome to use your remaining late days. However, all submissions must be received no later than Monday, November 23.
In the Password Checking problem on Problem Set Eight, Problem 6.iv should ask you to prove that L is not in R, not that it's not in RE (we haven't talked about how to prove languages aren't in RE yet). Sorry for the typo!
The second midterm exam is this upcoming Monday, November 16 from 7PM - 10PM. The exam location is divvied up by your last (family) name:
Good luck!
The original automaton given in Problem 5 of Problem Set Six is incorrect. There should be a Σ-transition from the start state back to itself. We've posted an update to the electronic copy. Sorry about that!
The first midterm exam is this upcoming Monday, October 26 from 7PM - 10PM. The exam location is divvied up by your last (family) name:
Good luck!
We accidentally gave out an impossible problem in Problem Set Three. On Problem Three, part (v), the statement to prove should not be a biconditional. Instead, you should just prove that if <A has height two or less, then its covering relation is a strict order. It turns out that the other direction of implication isn't actually true. We've posted a corrected version of the problem set to the course website. Sorry about that!
Problem Set Two goes out today. The checkpoint is due on Monday and the remaining problems are due on Friday. We strongly recommend reviewing this handout on how to negate first-order formulas before starting it, as you'll need this skill at several points in the assignment.
Good luck!
The very first problem set of the quarter, Problem Set One, goes out today and is due in two parts. The checkpoint assignment is due this upcoming Monday at the start of class and will be graded based on effort. The remaining problems are then due on Friday at the start of class. We hope that this problem set gives you a lot of practice with the three main proof techniques we've seen so far and gives you a sense of what you can do in the realm of discrete math. If you have any questions, please feel free to reach out to us!
We're using GradeScope this quarter for assignment submissions. To sign up for GradeScope, please have each group member register using the code given in the Problem Set Policies handout. We strongly recommend leaving at least two hours of buffer time when submitting just in case you run into any technical issues.
Good luck!
If you'd like a fun little diversion, check out Vi Hart's video about Pythagoras and √2.
Also, as mentioned in lecture, if you assume 1 = 0, you can prove anything, including that Winston Churchill is a carrot. Just thought I'd share that gem of wisdom with you.
Many of you have also asked for some clarification about the proof of Cantor's theorem. If you're curious to learn more about the mathematical nature of infinity, check out this Vi Hart video about infinity or this Numberphile video about infinities. Thanks to our awesome TA Sarah for finding these videos!
Welcome to CS103, an 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.
If you have any questions in the meantime, feel free to email me at htiek@cs.stanford.edu with questions.
See you soon!
41D: Final Exam Distribution
35: Timeline of Results
33R: Midterm 2 Regrade
33D: Midterm 2 Distribution
24: Guide to Induction
23R: Midterm 1 Regrade
17: Exam Strategies
13: Logic and Proofs
11: How to Negate Formulas
10: Greek and Hebrew Letters
08: Mathematical Vocabulary
07: Guide to Proofs
06: Honor Code Policies
05: Problem Set Policies
04: How to Succeed
03: Math Prereqs
02: Set Theory Definitions
01: Syllabus
00: Course Information
Problem Set Nine
Problem Set Eight
Problem Set Seven
Problem Set Six
Problem Set Five
Problem Set Four
Problem Set Three
Problem Set Two
Problem Set One
Challenge Problems Three
Practice Final Exam
Practice Problems Nine
Practice Problems Eight
Practice Problems Seven
Challenge Problems Two
Practice Midterm Exam 2
Practice Problems Six
Practice Problems Five
Practice Problems Four
Challenge Problems One
Practice Midterm Exam
Practice Problems Three
Practice Problems Two
Practice Problems One
Course Reader
CS103A Website
Office Hours Schedule
Truth Table Tool
Relation Editor
DFA/NFA Editor
Regex Editor
CFG Editor
Turing Machine Editor
29: The Big Picture
Slides
28: NP-Completeness, Part II
Slides |
Condensed
27: NP-Completeness, Part I
Slides |
Condensed
26: Complexity Theory
Slides |
Condensed
25: Unsolvable Problems, Part II
Slides |
Condensed
24: Unsolvable Problems, Part I
Slides |
Condensed
23: Turing Machines, Part III
Slides |
Condensed |
Quine
22: Turing Machines, Part II
Slides |
Condensed
21: Turing Machines, Part I
Slides |
Condensed
20: Context-Free Grammars
Slides |
Condensed
19: Nonregular Languages
Slides |
Condensed
18: Regular Expressions
Slides |
Condensed
17: Finite Automata III
Slides |
Condensed
16: Finite Automata II
Slides |
Condensed
15: Finite Automata I
Slides |
Condensed
14: Eulerian and Hamiltonian Graphs
Slides |
Condensed
13: Induction II
Slides |
Condensed
12: Induction I
Slides |
Condensed
11: Graphs II
Slides |
Condensed
10: Graphs I
Slides |
Condensed
09: Functions III
Slides |
Condensed
08: Functions II
Slides |
Condensed
07: Relations II, Functions I
Slides |
Condensed
06: Binary Relations I
Slides |
Condensed
05: Mathematical Logic III
Slides |
Condensed
04: Mathematical Logic II
Slides |
Condensed
03: Mathematical Logic I
Slides |
Condensed
02: Indirect Proofs
Slides |
Condensed
01: Direct Proofs
Slides |
Condensed
00: Set Theory
Slides |
Condensed