Announcements

That's All, Folks!
December 14, 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 a filing cabinet in the first floor 1B Wing of the Gates building that's marked "CS103 Final Exams" and should be available somewhere in the Gates building through the start of Winter quarter.

We're working on getting PS9 graded and will try to get final grades computed and entered as soon as possible.

It's been a pleasure teaching CS103 this quarter. Feel free to stay in touch with us throughout your further adventures, and enjoy the break!

Final Exam Logistics
December 8, 2017

The CS103 final exam is this Monday, December 11th from 3:30PM - 6:30PM. Locations are divvied up by last (family) name as follows:

  • Abb - Ngu: Go to Cubberley Auditorium.
  • Ogr - Zwa: Go to Cemex Auditorium.

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 final exam is cumulative and covers material from PS1 - PS9 and all of the lectures.

We've posted a ton of practice materials here on the website. There are five practice final exams along with Extra Practice Problems 3, which has 45 problems spanning all of the topics from this course.

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

Problem Set 9 Released
December 1, 2017

The very last problem set of the quarter, Problem Set Nine, goes out today. It's due on the very last day of class at 2:30PM. We're prohibited by university policy from allowing any late submissions on this assignment, so late days can't be used here.

This final problem set explores the absolute limits of computation. We started off in our very first lecture by talking about Cantor's theorem and why it means that unsolvable problems must exist. We think it's fitting that in this final problem set, you'll actually be exploring what sorts of problems we can't actually solve.

We've released two final graphical guides for this problem set. The Guide to Self-Reference explores proofs by self-reference and should help give you a better sense for how to structure and approach them. Our Guide to the Lava Diagram talks about how to look back at all the classes of languages we've seen so far and determine which languages fall where into the hierarchy.

Good luck!

Problem Set 8 Released
November 17, 2017

Problem Set Eight goes out today. It's due the Friday after break 2:30PM. This problem set explores CFGs, Turing machines, and their properties. You'll likely want to play around with our CFG editor and our TM editor as you work through these problems.

Good luck!

Problem Set 7 Released
November 10, 2017

Problem Set Seven goes out today. It's due next Friday at 2:30PM. This problem set explores regular expressions, some additional properties of regular languages, and the limits of regular languages.

At a few points in this problem set, you'll need to design DFAs and regular expressions. Please use our DFA/NFA editor and regular expression editor design, test, and submit your automata and regexes.

Good luck!

Second Midterm Logistics
November 9, 2017

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

  • Abb - Hal: Go to Hewlett 201.
  • Han - Zwa: 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 06 - 13 (binary relations up through and including induction), and focuses on the topics from PS3 - PS5.

There are a number of resources posted here you can use to practice for the exam - there are four practice midterms, with solutions, along with the 21-question Extra Practice Problems 2.

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

Problem Set 6 Released
November 3, 2017

Problem Set Six goes out today. It's due next Friday at 2:30PM. This problem set explores DFAs, NFAs, regular languages, their properties, and their applications.

In lieu of a coding component, in this problem set we're going to ask you design a number of DFAs or NFAs for various languages. To do so, please use our nifty DFA/NFA editor, which will let you design, test, and submit your automata.

Good luck!

Midterm Grades Released
October 29, 2017

Over the next twenty minutes or so we'll be emailing out grades for the first midterm exam. We've posted the exam itself and a set of solutions here on the course website, which we'll release in hardcopy tomorrow. The solutions set contains a ton of useful information - the score distribution for the exam, information on how to interpret your score, common mistakes, and advice on how to improve if you had trouble with any of the questions on the exam. Please take a few minutes to read over it when you get the chance.

We will be returning hardcopies of exams after class tomorrow. If you can't make it to class tomorrow, we'll keep the exams in a publicly accessible location in the Gates building and will send out an email tomorrow with instructions about where to pick it up from. (If you're an SCPD student, we'll be sending your exam to the SCPD office so that they can then send it back to you.)

We'll send out information about exam regrades on Wednesday, once everyone has had a chance to review their exam.

Problem Set 5 Released
October 27, 2017

Problem Set Five goes out today. This problem set serves as cumulative review of all the topics we've covered so far (binary relations, functions, graphs, and set theory) in the broader context of induction. We hope that this problem set gives you a richer sense of how everything fits together and for the power of induction to tackle complex problems!

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

Unlike the previous assignments, there is no checkpoint for PS5.

Before starting this problem set, we strongly recommend reading over our Guide to Induction, which gives advice on how to set up and execute inductive proofs, and our Induction Checklist, which gives a concrete set of things to check for in your inductive proofs before submitting them.

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 20, 2017

Problem Set Four 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 the finite through graph theory, the infinite through set cardinality, and why all of this matters in the first place. It has a combination of surprising mathematical results and practically useful concepts, and we hope you find it interesting!

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!

Midterm Logistics
October 16, 2017

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

  • Abb - Lop: Go to Cubberly Auditorium.
  • Mac - Zwa: 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 PS1 - PS2.

We've posted a set of extra practice problems along with two practice midterm exams. Feel free to use those as study resources and to contact us with any questions you might have! Additionally, we'll be holding an in-person practice midterm exam this Wednesday from 7PM - 10PM in Hewlett 200. If you can't make it, don't worry - we'll post the practice exam we'll use then on the course website.

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 13, 2017

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. It's all about binary relations, functions, and their applications.

We've released a handout about how proofs relate to first-order logic. This handout might be helpful as you work through this week's problems.

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 6, 2017

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. Please read over this checklist and apply it to all the translations you write before you submit them - we'll be doing the same when we're grading things!

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 29, 2017

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 Proofs handout gives some general advice about proofwriting. The handout on mathematical vocabulary talks about the precise meanings of certain mathematical terms. 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 five 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!

Some Fun Reads
September 27, 2017

In lecture, we showed an example of a seven-set Venn diagram. Here's one for eleven sets, if you're curious to see what it looks like!

Also, here's a link to a very short paper with a proof of an existential statement.

Thanks to your wonderful TA Robbie for these links!

Problem Set 0 Released
September 25, 2017

The very first assignment of the quarter, Problem Set 0, goes out today. It's due this Friday at 2:30PM. The handout and a link to the starter files are available under the "Assignments" section to the right.

This assignment is designed to make sure that you can get Qt Creator set up and running and that you're able to submit your work. If you have any questions or concerns about getting Qt Creator up and running, feel free to email the staff list!

Welcome to CS103!
September 21, 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

46: Timeline of Results
31: How to Improve
27: Induction Checklist
26: Guide to Induction
20: Preparing for the Exam
17: FOL and Proofs
16: Regrade Policies
14: Logic Translation Checklist
12: Proofwriting Checklist
11: Ten Techniques to Get Unstuck
10: Guide to Indirect Proofs
09: Mathematical Vocabulary
08: Guide to Proofs
07: Set Theory Definitions
06: How to Succeed
05: Problem Set Policies
04: Honor Code
02: Math Prereqs
01: Syllabus
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 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 4
  (solutions)
Practice Second Midterm 3
  (solutions)
Practice Second Midterm 2
  (solutions)
Practice Second Midterm 1
  (solutions)
Extra Practice Problems 2
  (solutions)
Practice Midterm 3
  (solutions)
Practice Midterm 2
  (solutions)
Practice Midterm 1
  (solutions)
Extra Practice Problems 1
  (solutions)

Exams

Final Exam
  (solutions)
Midterm Exam 2
  (solutions)
  (regrade request form)
Midterm Exam 1
  (solutions)
  (regrade request form)

Resources

Lecture Videos
Course Reader
CS103A Website
Guide to ∈ and ⊆
Qt Creator
Office Hours
Truth Table Tool
Guide to Negations
Guide to Logic Translations
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 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