That's All, Folks!

June 13, 2017

We've just finished grading the final exam. We've posted solutions and statistics here on the website, and will be emailing out exam scores shortly. The actual final exams are available for pickup in the normal exam return filing cabinet and should be available somewhere in the Gates building through the start of Fall quarter.

We're working on getting PS9 graded and will try to get final grades computed and entered by Thursday afternoon.

It's been a pleasure teaching CS103 this quarter. The course staff and I are really proud of your performance. So don't be a stranger! Stay in touch, and have an amazing summer!

Problem Set Nine Released

June 2, 2017

Problem Set Nine - the last one of the quarter! - goes out today. It's due on
**Wednesday, June 7** at 3:00PM. Because this is the last problem set of the quarter, we can't accept any late submissions.
Sorry about that!

This problem set serves as a capstone to our tour of undecidable and unrecognizable languages. You'll get practice writing
proofs that certain languages are undecidable, and will get a new perspective on *L*_{D}. You'll also get to
sharpen your intuitions for which problems are easy, which problems are hard, and why.

You might want to read over our handy Guide to the Lava Diagram before attempting some of the problems on this problem set. And, if you didn't do so last week, we definitely recommend reading the Guide to Self-Reference, which you'll need for the first problem.

Good luck!

Problem Set Eight Released

May 26, 2017

Problem Set Eight goes out today. It's due on Friday, June 2nd at the start of class.

In this problem set, you'll hit the absolute limits of computation. What do context-free languages look like? What's the deal with decidability and recognizability? And how does everything fit together?

In the course of completing this assignment, you'll get to use our nifty little CFG Editor and our Turing Machine Editor, which will let you design and test grammars and TMs, respectively. You should also read over our Guide to Self-Reference, which explores proofs of undecidability via self-reference.

Good luck!

Problem Set Seven Released

May 19, 2017

Problem Set Seven goes out today. It's due on Friday, May 26th at the start of class.

This problem set explores regular expressions, their properties, and their limits. We've set up a regex editor you can use to design, test, and submit your solutions to some of the problems. And, just for fun, we've also released a tool you can use to check whether two regular expressions are equivalent.

Good luck!

Second Midterm Logistics

May 18, 2017

The second midterm exam is this upcoming Tuesday, May 23rd from 7PM - 10PM. Locations are divvied up by last (family) name as follows:

`Abb - Pag`: Go to Hewlett 200.`Par - Tak`: Go to Sapp 114.`Tan - Val`: Go to Hewlett 101.`Var - Yim`: Go to Hewlett 102.`You - Zuc`: Go to Hewlett 103.

As with the first midterm exam, the exam is closed-book, closed-computer, and limited-note. You can bring a single, double-sided sheet of 8.5" × 11" notes with you to the exam. The exam covers the topics up through and including mathematical induction, and focuses on the topics from PS3 - PS5.

We've posted a bunch of extra practice problems along with three practice midterms. Feel free to use those as study resources and to contact us with any questions you might have!

Good luck, and let us know what we can do to help out!

Button FSM Demo

May 15, 2017

Here's a link to the buttons as finite-state machines demo from today's lecture. Enjoy!

Problem Set Six Released

May 12, 2017

Problem Set Six goes out today. It's due on Friday, May 19th at the start of class.

This problem set explores finite automata, regular languages, and their properties and applications. On several of the problems, we'd like you to use our DFA and NFA editor to design, test, and submit your solutions. We hope you enjoy using the tool to get a better feeling for how these automata work!

Good luck!

Extra Practice Problems

May 9, 2017

We've posted four sets of extra practice problems you can work through if you'd like more practice and review with the topics from PS3 - PS5. We'll post solutions next week.

Problem Set Five Released

May 5, 2017

Problem Set Five goes out today. It's due on Friday, May 12th at the start of class. There is no checkpoint problem on this problem set.

This problem set touches on all the concepts we've covered so far this quarter: graphs, binary relations, the pigeonhole principle, set cardinality, functions, and mathematical induction. We hope that it's a fitting coda to our section on discrete math!

Before you start this problem set, please read our Guide to Induction, which covers some details of inductive proofwriting that you'll likely need on this problem set.

Good luck!

Problem Set Four Released

April 28, 2017

Problem Set Four goes out today. The checkpoint assignment is due Monday, May 1st at 3:00PM, and the remaining problems are due on Friday, May 5th at 3:00PM.

This problem set explores the infinite through set theory and cardinalities and the finite through graph theory and the pigeonhole principle. We've chosen a blend of problems that we think will help you get a much richer feeling for how these structures work, as well as some of their applications.

Before you start this problem set, please read the Guide to Cantor's Theorem, which includes a number of proofs and concepts that you'll need in order to complete the problem set.

Good luck!

Problem Set Three Released

April 21, 2017

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

This problem set explores the discrete structures we've talked about this week - binary relations and functions - and their properties. It should be a great way to practice your proofwriting and get a better feel for what these different terms and concepts look like.

Before you start this problem set, you might want to read over our handout on first-order logic and proofs, which might be helpful on some of these problems.

Good luck!

Problem Set Two Released

April 14, 2017

Problem Set Two goes out today. The checkpoint assignment is due Monday, April 17th at 3:00PM, and the remaining problems are due on Friday, April 21st at 3:00PM.

This problem set is all about mathematical logic and how to express statements formally and precisely. It begins with an overview of propositional logic, talks a bit about first-order logic, and concludes with some proofwriting exercises to help keep your skills sharp.

Before you start this problem set, you might want to read over our Guide to Negating Formulas and Guide to Logic Translations, both of which will be useful in the course of completing the assignment.

Good luck!

Problem Set One Released

April 7, 2017

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

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 partner 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!

March 30, 2017

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.

See you soon!

48: Timeline of CS103 Results

30: Induction Checklist

24: Guide to Induction

16: Preparing for the Exam

14: Logic and Proofs

13: FOL Checklist

11: Proofwriting Checklist

09: Guide to Indirect Proofs

08: Mathematical Vocabulary

07: Guide to Proofs

06: Honor Code Policies

05: Problem Set Policies

04: Set Theory Definitions

03: How to Succeed

02: Math Prereqs

01: Syllabus

00: Course Information

Problem Set Nine

(solutions)

Problem Set Eight

(solutions)

Problem Set Seven

(solutions)

Problem Set Six

(solutions)

Problem Set Five

(solutions)

Problem Set Four

(checkpoint solutions) | (solutions)

Problem Set Three

(checkpoint solutions) | (solutions)

Problem Set Two

(checkpoint solutions)
| (solutions)

Problem Set One

(checkpoint solutions)
| (solutions)

Practice Final Exam IV

(solutions)

Practice Final Exam III

(solutions)

Practice Final Exam II

(solutions)

Practice Final Exam I

(solutions)

Extra Practice Problems 12

(solutions)

Extra Practice Problems 11

(solutions)

Extra Practice Problems 10

(solutions)

Extra Practice Problems 9

(solutions)

Yet Another Practice Midterm II

(solutions)

Another Practice Midterm II

(solutions)

Practice Midterm II

(solutions)

Extra Practice Problems 8

(solutions)

Extra Practice Problems 7

(solutions)

Extra Practice Problems 6

(solutions)

Extra Practice Problems 5

(solutions)

Extra Practice Problems 4

(solutions)

Another Practice Midterm

(solutions)

Practice Midterm

(solutions)

Extra Practice Problems 3

(solutions)

Extra Practice Problems 2

(solutions)

Extra Practice Problems 1

(solutions)

Final Exam

(solutions)

Midterm II

(solutions)
| (regrade form)

Midterm I

(solutions)
| (regrade form)

Course Reader

CS103A Website

Guide to ∈ and ⊆

Office Hours Calendar

Truth Table Tool

Guide to Negating Formulas

Guide to Logic Translations

Binary Relation Editor

Guide to Cantor's Theorem

DFA/NFA Editor

Regex Editor

Regex Equivalence Tester

CFG Editor

TM Editor

Guide to Self-Reference

Guide to the Lava Diagram

**
27: The Big Picture
Slides
**

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed | Code

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed

Slides | Condensed