Announcements

Problem Set 9 Released
November 22, 2019

Problem Set Nine, the final problem set of the quarter, goes out today. It's due the Friday after break at 2:30PM, and since that's the last day of class, this is a hard deadline. In this capstone problem set, you'll explore the true limits of computing power by looking at problems that are truly beyond our capacity to solve. It's been a long journey getting here, but wow! Look at the view from the top. We started off this class with the idea that some problems are too hard to be solved by computers, and at this point you're finally working with them!

Before you take on this problem set, we recommend reading over the Guide to Self-Reference and Guide to the Lava Diagram, which contain a bunch of useful pieces of advice on how to approach some of the problems.

You're encouraged to work on this assignment in pairs. It's a great way to bounce ideas off of someone and get extra pairs of eyes on your work.

Good luck!

Problem Set 8 Released
November 15, 2019

Problem Set Eight goes out today. It's due Friday at 2:30. In the course of working through it, you'll get some experience designing context-free grammars, playing around with connections between different classes of languages, building Turing machines, and setting a firm foundation for exploring the limits of computing.

Some of the problems on this problem set will require you to use our online CFG editor and TM editor tools.

You're encouraged to work on this assignment in pairs. It's a great way to bounce ideas off of someone and get extra pairs of eyes on your work.

Good luck!

Problem Set 7 Released
November 8, 2019

Problem Set Seven goes out today. It's due next Friday at 2:30. This problem is all about regular expressions, properties of the regular languages, and the limits of the regular languages. This will be your first time formally proving that certain problems can't be solved with a certain type of computer!

Some of the problems on this problem set are designed to be completed online using our handy Regular Expression Editor. There is no coding component to this assignment.

You're encouraged to work on this assignment in pairs. It's a great way to bounce ideas off of someone and get extra pairs of eyes on your work.

Good luck!

Problem Set 6 Released
November 1, 2019

Problem Set Six goes out today. It's due next Friday at 2:30. This problem is all about finite automata, regular languages, and their properties. We hope that you have fun with this one as you start exploring mathematical models of computers!

Some of the problems on this problem set are designed to be completed online using our handy DFA/NFA Editor. There is no coding component to this assignment.

You may find it helpful to read over the Guide to the Subset Construction before starting this problem set.

You're encouraged to work on this assignment in pairs. It's a great way to bounce ideas off of someone and get extra pairs of eyes on your work.

Good luck!

Problem Set 5 Released
October 25, 2019

Problem Set Five goes out today. It's due next Friday at 2:30. This problem set explores induction in all its many forms and serves as a capstone to the first half of CS103. Once you've finished it, take a minute to look back over what you just did. Did you imagine you'd be here a little over a month after we started with set theory?

Before starting this assignment, we recommend reading over our Guide to Induction and our Induction Proofwriting Checklist, which contain some useful tips and techniques that we think will help you out.

You're encouraged to work on this assignment in pairs. It's a great way to bounce ideas off of someone and get extra pairs of eyes on your work.

Good luck!

Problem Set 4 Released
October 18, 2019

Problem Set Four goes out today. This one doesn't have a checkpoint - all the problems are due on Friday of next week at 2:30PM. This problem set continues our exploration of discrete structures and ventures from the finite (through graphs) to the infinite (through functions and cardinality).

We strongly recommend reading over our Guide to Cantor's Theorem before starting this problem set, since it contains a number of important definitions you'll need along the way.

You're encouraged to work on this assignment in pairs. It's a great way to bounce ideas off of someone and get extra pairs of eyes on your work.

Good luck!

Midterm Logistics
October 14, 2018

Our first midterm exam is this upcoming Monday from 7PM - 10PM. Locations are divvied up by last (family) name as follows:

  • A - G: Go to Hewlett 201.
  • H - Z: Go to Hewlett 200.

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 from Lectures 00 - 05 (set theory up through and including first-order logic), and focuses on the topics from PS0 - PS2.

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

We strongly recommend checking out our handout on how to prepare for the midterm exam, which contains our general policies along with some advice from students of quarters past.

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

Problem Set 3 Released
October 11, 2019

Problem Set Three goes out today. It consists of two parts - a checkpoint assignment due on Monday at 2:30PM, and some remaining problems due next Friday at 2:30PM. This problem set explores discrete structures (binary relations and functions), what they look like, how they act, and how to prove things about them.

Before you start this problem set, please read over our Guide to Proofs on Discrete Structures, which provides advice about how to prove results when definitions are specified in first-order logic, and our discrete structures proofwriting checklist, which contains a number of specific things to look for in the course of writing your proofs.

This assignment has a programming component. You can download the starter files either using the previous link or in the "Assignments" section below.

You're encouraged to work on this assignment in pairs. It's a great way to bounce ideas off of someone and get extra pairs of eyes on your work.

Good luck!

Problem Set 2 Released
October 4, 2019

Problem Set Two goes out today. It consists of two parts - a checkpoint assignment due on Monday at 2:30PM, and some remaining problems due next Friday at 2:30PM. In it, you'll dive into propositional and first-order logic and get some more practice with your proofwriting.

Before you start this problem set, you may want to play around with our Truth Table Tool, which you might want to use on some of the earlier problems. Additionally, you should read over our Guide to Negations and Guide to Logic Translations, which go into some depth about skills you'll need on the problem set.

We've also released a logic translation checklist. This handout details five specific points to watch out for when translating statements from English into first-order logic. Think of it as a style guide for first-order logic - it's a mix of advice about how to keep your formulas clean and readable and how to avoid common pitfalls.

This assignment has a programming component. You can download the starter files either using the previous link or in the "Assignments" section below.

You're encouraged to work on this assignment in pairs. It's a great way to bounce ideas off of someone and get extra pairs of eyes on your work.

Good luck!

Problem Set 1 Released
September 27, 2019

Problem Set One goes out today. It consists of two parts - a checkpoint assignment due on Monday at 2:30PM, and some remaining problems due next Friday at 2:30PM. This problem set explores set theory and mathematical proof techniques, and we hope that you have a lot of fun with it!

We've also released a number of handouts alongside this problem set. Our Guide to Indirect Proofs talks about writing proofs by contradiction and contrapositive. We've also released a handout with ten techniques to get unstuck if you find yourself unsure how to proceed. Please look over this handout - there's a lot of good problem- solving techniques in there!

Finally, we've released our proofwriting checklist. This handout details specific points to watch out for when writing proofs. Please read over this checklist and apply it to all the proofs you write before you submit them - we'll be doing the same when we're grading things!

This assignment has a small programming component. You can download the starter files either using the previous link or in the "Assignments" section below.

You're encouraged to work on this assignment in pairs. It's a great way to bounce ideas off of someone and get extra pairs of eyes on your work.

Good luck!

Welcome to CS103!
September 19, 2019

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 us at htiek@cs.stanford.edu.

See you soon!

Handouts

50: Timeline of Results
29: How to Improve
27: Induction Proofwriting Checklist
26: Guide to Induction
19: Preparing for the Exam
16: Discrete Structures Checklist
15: Guide to Discrete Structure Proofs
14: Regrade Policies
12: Logic Translation Checklist
10: Proofwriting Checklist
09: Ten Techniques to Get Unstuck
08: Guide to Indirect Proofs
07: Guide to Set Theory Proofs
06: How to Succeed
05: Problem Set Policies
04: Honor Code
02: Math Prereqs
01: Course Calendar
00: Course Information

Assignments

Problem Set 9 Problem Set 8 Problem Set 7 Problem Set 6 Problem Set 5 Problem Set 4 Problem Set 3 Problem Set 2 Problem Set 1 Problem Set 0

Practice Problems

Practice Final Exam 8
  (solutions)
Practice Final Exam 7
  (solutions)
Practice Final Exam 6
  (solutions)
Practice Final Exam 5
  (solutions)
Practice Final Exam 4
  (solutions)
Practice Final Exam 3
  (solutions)
Practice Final Exam 2
  (solutions)
Practice Final Exam 1
  (solutions)
Extra Practice Problems 3
  (solutions)
Practice Second Midterm Exam 5
  (solutions)
Practice Second Midterm Exam 4
  (solutions)
Practice Second Midterm Exam 3
  (solutions)
Practice Second Midterm Exam 2
  (solutions)
Practice Second Midterm Exam 1
  (solutions)
Extra Practice Problems 2
  (solutions)
Practice Midterm Exam 4
  (solutions)
Practice Midterm Exam 3
  (solutions)
Practice Midterm Exam 2
  (solutions)
Practice Midterm Exam 1
  (solutions)
Extra Practice Problems 1
  (solutions)

Exams

Midterm Exam 2
  (solutions)
  (regrade request)

Midterm Exam 1
  (solutions)

Resources

Office Hours Calendar
Course Reader
CS103A Website
Guide to ∈ and ⊆
Qt Creator
Truth Table Tool
Guide to Negations
Guide to Logic Translations
Guide to Cantor's Theorem
Guide to the Subset Construction
DFA/NFA Editor
Regex Editor
Regex Equivalence Tester
CFG Editor
TM Editor
Guide to Self-Reference
Guide to the Lava Diagram
Review Session Slides

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, 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: Mathematical Proofs
   Slides | Condensed
00: Set Theory
   Slides | Condensed