Late Policy Clarification

November 18, 2015

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.

Problem Set Eight Correction

November 16, 2015

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!

Second Midterm Logistics

November 11, 2015

The second midterm exam is this upcoming Monday, November 16 from 7PM - 10PM. The exam location is divvied up by your last (family) name:

- Aga - Ven: Go to Hewlett 200
- Ver - Zhe: Go to 370-370

Good luck!

Problem Set Six Correction

October 31, 2015

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!

Midterm Logistics

October 23, 2015

The first midterm exam is this upcoming Monday, October 26 from 7PM - 10PM. The exam location is divvied up by your last (family) name:

- Aga - Ven: Go to Hewlett 200
- Ver - Zhe: Go to 370-370

Good luck!

Problem Set Three Correction

October 10, 2015

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

October 2, 2015

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!

Problem Set One Out

September 25, 2015

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!

For Fun: Four Mathematical Links

September 25, 2015

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!

September 18, 2015

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!

35: Timeline of Results

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

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

**
26: Complexity Theory, Part I
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
**