Problem Set 7 Released

February 23, 2018

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

February 16, 2018

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'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

February 9, 2018

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?

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 4 Released

February 2, 2018

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

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

*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

February 1, 2017

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

`A - H`: Go to Cubberley Auditorium.`I - Z`: Go to 320-105.

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 four 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

January 26, 2018

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. A few of the problems from this problem set reference concepts that we will be covering this upcoming Monday. They're clearly marked as such.

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.

*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

January 19, 2018

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.

A few of the problems from this problem set reference concepts that we will be covering this upcoming Monday. They're clearly marked as such.

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!

*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

January 12, 2018

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.

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

January 3, 2018

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 cbl@cs.stanford.edu or htiek@cs.stanford.edu.

See you soon!

31: How to Improve

29: Induction Checklist

28: Guide to Induction

21: Preparing for the Exam

18: Discrete Structures Checklist

17: Guide to Discrete Structures

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

Practice Second Midterm 5

(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 4

(solutions)

Practice Midterm 3

(solutions)

Practice Midterm 2

(solutions)

Practice Midterm 1

(solutions)

Extra Practice Problems 1

(solutions)

Course Reader

CS103A Website

Guide to ∈ and ⊆

Qt Creator

Office Hours Calendar

Truth Table Tool

Guide to Negations

Guide to Logic Translations

Guide to Cantor's Theorem

DFA/NFA Editor

Regex Editor

**
18: Nonregular Languages
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