Announcements

December 16, 2016

We've finished grading final exams! We've posted a set of final exam solutions that also includes statistics and common mistakes. The physical graded exams are available for pickup in the Gates building in the same place we've traditionally stored midterms - in the side entrance marked "Stanford Engineering Venture Fund Laboratories," in the filing cabinets under all the pictures of the section leaders. They should still be available for pickup all the way through the first few weeks of next quarter, so feel free to stop by and pick them up at your convenience! (SCPD students - the SCPD office says they'll have the exams back by the middle of next week.)

Thanks for being such a great class, and have a great break!

Final Exam Logistics
December 8, 2016

Our final exam is coming up on Monday. It'll be held from 3:30PM - 6:30PM. We're split across five rooms, divvied up by last (family) name as follows:

• Abd - Fis: Go to Gates B01
• Fit - Jar: Go to Gates B03
• Jim - Tor: Go to Nvidia Auditorium
• Tra - Win: Go to Thornton 102
• Wu - Zub: Go to Huang 018

The exam is closed-book, closed-computer, and limited-note. Like the first two midterms, you can bring a double-sided sheet of 8.5" × 11" notes with you. The exam is cumulative and the topics are split at roughly 50% on discrete mathematics (PS1 - PS5) and roughly 50% on computability and complexity theory (PS6 - PS9).

We will be holding a proctored practice final exam on Saturday from 2PM - 5PM in Hewlett 200, using "Practice Final Exam 3." Everyone is welcome!

Problem Set Nine Released
December 2, 2016

Problem Set Nine goes out today. It's due on Friday, December 9th. Per university policies, no late days may be used on this assignment and no late submissions will be accepted.

This problem set explores the outer limits of computing power. What problems are truly undecidable? What lies outside of RE? We hope this is a fitting coda to this quarter's exploration of the limits of computation!

There are two resources we've released that we think might be useful. The first is the Guide to Self-Reference, which goes into depth about how to write self-referential programs to prove undecidability. The second is the Guide to the Lava Diagram, which you may find useful for one of the problems on this problem set.

Good luck!

Problem Set Eight Released
November 18, 2016

Problem Set Eight goes out today. It's due on Friday, December 2nd.

This problem set explores the context-free languages as well as what you can do with Turing machines. It hopefully will give you a richer feel for how all these concepts relate to one another and set us up for the grand finale when we get back and start exploring the limits of Turing machines.

We've also released two tools you'll need for this problem set, our nifty CFG designer
where you can design, test, and submit CFGs for the problem set, and our awesome TM designer
which does the same for Turing machines.

Good luck!

Problem Set Seven Released
November 11, 2016

Problem Set Seven goes out today. It's due on Friday, November 18th.

This problem set explores regular expressions, nonregular languages, and their properties. As with DFAs and NFAs, we have a handy tool you should use to design, test, and submit your regular expressions for this problem set. We also have another tool for checking equivalence of regular expressions that you might find useful in case you're checking answers with your teammates.

Good luck!

Midterm Logistics
November 8, 2016

The second midterm exam is next Monday, November 14, from 3:00PM - 4:20PM (our regularly-scheduled class time). As with last time, locations are divvied up by last (family) name. This is the same room assignment as before:

• Abd - Pan: Go to Hewlett 200.
• Pap - Zub: Go to Nvidia Auditorium.

In terms of topic coverage, the exam focuses on material from Lectures 06 - 13 (binary relations through induction) and material from Problem Sets Three, Four, and Five. The exam will be 80 minutes long. It's closed-book, closed-computer, and limited-note. You can bring a single, double-sided sheet of 8.5" × 11" paper with you when you take the exam with whatever notes you'd like.

As with the previous midterm, we'll be releasing a number of practice problems over the course of the week. We've released four sets of extra practice problems (available online) and we'll get solutions out on Wednesday. We will also be holding a practice midterm on Wednesday, November 9 from 7PM - 9PM in room 320-105. If you can attend, this would be a great way to get a sense of where you stand and what you'll need to practice. Solutions will also be posted online in case you can't make it.

Let us know if there's anything we can do to help you prepare, and good luck on the exam!

Problem Set Six Released
November 4, 2016

Problem Set Six goes out today. It's due on Friday, November 11th.

This problem set explores finite automata (DFAs and NFAs), the regular languages, their properties, and their applications. For this problem set, we have this handy DFA/NFA tool you should use to design, test, and submit your automata. We hope you find this tool useful!

Good luck!

Problem Set Five Released
October 28, 2016

Problem Set Five goes out today. It's due on Friday, November 4th, and there is no checkpoint problem on this problem set.

This set explores the pigeonhole principle and induction and should serve as a cumulative review for the course topics we've covered so far. We strongly recommend reading over the Guide to Induction before starting this problem set, as it has some useful advice about structuring inductive proofs.

Good luck!

Problem Set Four Released
October 21, 2016

Problem Set Four goes out today. The checkpoint assignment is due Monday, October 24 at 3:00PM, and the remaining problems are due on Friday, October 28 at 3:00PM.

This problem set explores cardinality and graph theory. Before you start it, please read through the Guide to Cantor's Theorem, which covers a few necessary topics. As always, please feel free to ask questions on Piazza, over the staff mailing list, or in office hours.

Good luck!

Midterm Logistics
October 17, 2016

The first midterm exam is coming up soon - it's next Monday, October 24, from 3:00PM - 4:20PM. Room assignments are divvied up by last (family) name:

• Abd - Pan: Go to Hewlett 200.
• Pap - Zub: Go to Nvidia Auditorium.

In terms of topic coverage, the exam covers material from Lectures 00 - 05 (the first two weeks of class) and material from Problem Set One and Problem Set Two. The exam will be 80 minutes long. It's closed-book, closed-computer, and limited-note. You can bring a single, double-sided sheet of 8.5" × 11" paper with you when you take the exam with whatever notes you'd like.

We've released a handout about how to prepare for the exam, and we highly recommend reading over it to get a sense of what to do over the upcoming week. Over the course of the week, we'll release a number of practice problem sets. The first, Extra Practice Problems 1, is now available. Solutions will go out on Wednesday.

We will be holding a practice midterm exam tomorrow night, Tuesday, October 18, from 7PM - 9PM. This will be held in room 420-040. It's entirely optional, but highly recommended. If you can't make it, no worries - we'll post the practice exam with solutions up here.

Let us know if there's anything we can do to help you prepare, and good luck on the exam!

Problem Set Three Released
October 14, 2016

Problem Set Three goes out today. The checkpoint assignment is due Monday, October 17 at 3:00PM, and the remaining problems are due on Friday, October 21 at 3:00PM. This problem set explores binary relations, functions, and their properties. It's designed to get you more practice writing proofs and exploring the usefulness of providing definitions in first-order logic.

Before you begin, we recommend that you read our handout about first-order logic and proofs, which details how to read a first-order logic statement and determine how to prove it. We also recommend playing around with our nifty binary relation editor, which lets you play around with binary relations and might give you a better sense of what different types of relations look like.

Good luck!

Problem Set Two Released
October 7, 2016

Problem Set Two goes out today. The checkpoint assignment is due Monday, October 10 at 3:00PM, and the remaining problems are due on Friday, October 14 at 3:00PM.

This problem set explores propositional logic and first-order logic and concludes with some extra practice writing proofs. Before you start this problem set, we recommend reading the Guide to Negating Formulas and the Guide to Logic Translations, which talk about two skills you'll need throughout the problem set. You should also take a look at the Truth Table Tool, which you might find useful on the initial problems.

Good luck!

Problem Set One Released
September 30, 2016

Problem Set One goes out today. The checkpoint assignment is due Monday, October 3 at 3:00PM, and the remaining problems are due on Friday, October 7 at 3:00PM. (All times are Pacific time).

This problem set explores set theory and the proof techniques we explored in lecture (direct, contradiction, contrapositive). The problems start with a set of review questions on set theory, then transition into a number of proof exercises. We recommend that you take a look at the problem set as soon as it goes out and start thinking about the problems - as mentioned in our How to Succeed handout, you're going to want to start early!

We've released a number of handouts alongside this one. Our Problem Set Policies handout covers information about how to submit assignments, our collaboration policy, how we grade, etc. The handout on the Honor Code talks about how the Stanford Honor Code applies to CS103 - you are expected to read this handout and abide by its terms throughout the quarter. The next few handouts are a guide to proofs that discusses elements of good proofwriting, a survey of mathematical vocabulary that you're likely to use in the course of the problem set, and a guide to indirect proof techniques. We recommend that you read over these handouts before you start the problem set.

We've also posted our office hours calendar. You're welcome to stop by any of our OH time slots to ask questions about the material or the problem sets, or more generally just to chat with us. We're looking forward to meeting you!

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!

Welcome to CS103!
September 22, 2016

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!

Lectures

27: The Big Picture
Slides
26: Complexity Theory, Part II
Slides | Condensed
25: Complexity Theory, Part I
Slides | Condensed
24: Unsolvable Problems, Part II
Slides | Condensed
23: Unsolvable Problems, Part I
Slides | Condensed | Code
22: Turing Machines III
Slides | Condensed
21: Turing Machines II
Slides | Condensed
20: Turing Machines I
Slides | Condensed
19: Context-Free Grammars
Slides | Condensed
18: Nonregular Languages
Slides | Condensed
17: Regular Expressions
Slides | Condensed
16: Finite Automata III
Slides | Condensed
15: Finite Automata II
Slides | Condensed
14: Finite Automata I
Slides | Condensed
13: Induction II
Slides | Condensed
12: Induction I
Slides | Condensed
11: Graphs II
Slides | Condensed
10: Graphs I
Slides | Condensed
09: Cardinality
Slides | Condensed
08: Functions
Slides | Condensed
07: Binary Relations II
Slides | Condensed
06: Binary Relations I
Slides | Condensed
05: First-Order Logic II
Slides | Condensed
04: First-Order Logic I
Slides | Condensed
03: Propositional Logic
Slides | Condensed
02: Indirect Proofs
Slides | Condensed
01: Direct Proofs
Slides | Condensed
00: Set Theory
Slides | Condensed