Announcements

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 LD. 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!

Handouts

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

Assignments

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 Problems

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)

Exams

Final Exam
  (solutions)
Midterm II
  (solutions) | (regrade form)
Midterm I
  (solutions) | (regrade form)

Resources

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

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, Part III
   Slides | Condensed
21: Turing Machines, Part II
   Slides | Condensed
20: Turing Machines, Part I
   Slides | Condensed
19: Context-Free Grammars
   Slides | Condensed
18: Nonregular Languages
   Slides | Condensed
17: Regular Expressions
   Slides | Condensed
16: Finite Automata, Part III
   Slides | Condensed
15: Finite Automata, Part II
   Slides | Condensed
14: Finite Automata, Part I
   Slides | Condensed
13: Induction, Part II
   Slides | Condensed
12: Induction, Part I
   Slides | Condensed
11: Graphs, Part II
   Slides | Condensed
10: Graphs, Part I
   Slides | Condensed
09: Cardinality
   Slides | Condensed
08: Functions
   Slides | Condensed
07: Binary Relations, Part II
   Slides | Condensed
06: Binary Relations, Part I
   Slides | Condensed
05: First-Order Logic, Part II
   Slides | Condensed
04: First-Order Logic, Part I
   Slides | Condensed
03: Propositional Logic
   Slides | Condensed
02: Indirect Proofs
   Slides | Condensed
01: Direct Proofs
   Slides | Condensed
00: Set Theory
   Slides | Condensed