Homework 8 Posted

February 27, 2015

We've released Homework 8. You can find the assignment here, or under Assignments to the right.

These are all to be submitted on Scoryst. **Please note that the first problem is due Monday**; the rest are due on Friday.

Here are the deadlines.

Hard Deadline | |

Problem 1 | 3/2/2015 12:30PM |

Problems 2-5 2 | 3/6/2015 12:30PM |

Pumping Lemma Reading Material

February 24, 2015

An excerpt from the textbook containing some proofs using the Pumping Lemma is available here.

Homework 7 Posted

February 20, 2015

We've released Homework 7. You can find the assignment here, or under Assignments to the right.

Problems 1 and 2 are to be completed and submitted using the DFA tool and Regular Expression tool respectively, and may be submitted early by lecture Monday for the usual bonus. The rest you should submit on Scoryst.

Here are the deadlines.

Early Deadline | Regular Deadline | |

Problem 1: DFA tool |
2/23/2015 12:30PM | 3/2/2015 12:30PM |

Problem 2: RegEx tool |
2/23/2015 12:30PM | 3/2/2015 12:30PM |

Problems 3-5: Scoryst |
- | 3/2/2015 12:30PM |

Homework 6 (All)

February 13, 2015

We've released all of Homework 6. You can find the assignment here, or under Assignments to the right. Note that this link also includes Problem 1 (also released below).

These are primarily to be completed **and submitted** using the DFA tool and Regular Expression tool. Be sure to read the instructions carefully.

Here are the deadlines.

Early Deadline | Regular Deadline | |

Problem 1: DFA tool |
2/16/2015 12:30PM | 2/20/2015 12:30PM |

Problems 2-4: DFA tool |
- | 2/20/2015 12:30PM |

Problem 5: RegEx tool |
- | 2/20/2015 12:30PM |

Problem 6 (Challenge): Scoryst |
- | 2/20/2015 12:30PM |

Homework 6 Part 1

February 11, 2015

We've released the first problem of the forthcoming set, to give you a chance to get started early. This problem involves constructing finite automata using our online DFA tool, through which you will also be submitting this problem. ~~You can find the assignment here, or under Assignments to the right~~ (link removed now that the full assignment has been released, which includes this part).

Here are the deadlines for this part.

Early Deadline | Regular Deadline | |

Problem 1 | 2/16/2015 12:30PM | 2/20/2015 12:30PM |

Homework 5 Posted

February 6, 2015

Homework 5 is now up! You can find it here, or under Assignments to the right.

**Please note**: The first exercise is due by 12:30 *Wednesday*; the rest as usual by 12:30 Friday. There is no edX component this week, and no early bonus. Still, get started ASAP.

Here are the deadlines.

Deadline | |

Problem 1 on Scoryst (early) | 2/11/2015 12:30PM |

Problems 2-6 (+challenge) on Scoryst | 2/13/2015 12:30PM |

Homework 4 Posted

January 30, 2015

Homework 4 is now up! You can find it here, or under Assignments to the right.

This homework includes problems on edX, which can be submitted early for a bonus as per usual. The remaining problems are to be submitted on Scoryst, with no bonus for early submission (except the glow of a job well done).

We've released a tool where you can define binary relations and see which properties they satisfy. You may find it useful for some of the problems on the homework. The tool itself is just for your benefit; there's no opportunity or necessity to submit anything from it.

Here are the deadlines. **Note** that these are due Monday, because of the **midterm Thursday night**. The next week's will be due on Friday as usual (that is, five days after this one).

Early Deadline | Regular Deadline | |

Problem 1: edX | 2/3/2015 11:59PM | 2/9/2015 12:30PM |

Problem 2-9 (+challenge) on Scoryst | - | 2/9/2015 12:30PM |

Program Puzzlers Solutions

January 25, 2015

There were a couple of programming-related puzzles mentioned offhand in the early lectures: is floating-point arithmetic associative?, and, can you make a tree causing the tree-evaluation program from the Syntax Trees lecture to go into infinite recursion? Now that you've had some time to think about them yourself, here's Prof. Dill's writeup.

Homework 3 Posted

January 23, 2015

Homework 3 has been posted. Here are the relevant deadlines.

Early Deadline | Regular Deadline | |

Problems 1 and 2 on EdX | 1/26/2015 | 1/30/2015 |

Problem 3 on Scoryst | 1/26/2015 | 1/30/2015 |

Problems 4-7 on Scoryst | - | 1/30/2015 |

All deadlines are at 12:30pm, 20 minutes before lecture starts.

You can also find this information on the deadlines calendar linked under More Information.

Course Feedback

January 18, 2015

Please fill out this survey about how class has been going! Submitting is considered part of HW2, but we'd love for you to fill it out ASAP! Link is here http://goo.gl/forms/jEkTevMtBb

Homework 2 Posted

January 16, 2015

Homework 2 is now up! You can find it here, or under Homeworks to the right.

Two of the problems are auto-graded; you can find more details in the PDF. Note that there are new rules in the proof checker - make sure to check out the new docs. Also note that the auto-graded components cannot be submitted on Scoryst, unlike last week.

Here are the deadlines:

Early Deadline | Regular Deadline | |

Problem 1: Blocks World | 1/19/2015 11:59PM | 1/23/2015 12:30PM |

Problem 2: Quantifier Identities | 1/21/2015 11:59PM | 1/23/2015 12:30PM |

Problem 3: Written Problems | - | 1/23/2015 12:30PM |

Problem 4: Feedback | - | 1/23/2015 5PM |

Deadlines

January 12, 2015

For clarity, here's the deadlines for this week's homework:

Early Deadline | Regular Deadline | |

Homework 1 Autograded Questions | 1/12/2015 | 1/16/2015 |

Week 1 Autograded Questions | 1/9/2015 (5 pm) | 1/16/2015 |

Equational proofs (Question 1 on the handout) | 1/13/2015 (11:59 pm) | 1/16/2015 |

Written questions (Questions 2 and 3 on the handout) | - | 1/16/2015 |

You can also find this information on the deadlines calendar linked under More Information.

Problem Session Locations

January 11, 2015

The optional problem sessions will be held during 7-8:30PM on Mondays in Building 160, Room 329, except for the weeks in which Monday is a holiday, in which case they will be held on Tuesday in Gates 100. You can find more information under course information.

Dead bugs!

January 11, 2015

We've fixed the known bugs in the proof checker. Check the link below for more details.

Calendars!

January 10, 2015

We've put up calendars of office hour times & locations and of deadlines; you can find them under "More Information".

edX: Week 1

January 10, 2015

Homwork 1 was assigned Friday. It is due next Friday,
Jan 16.

There are several new sets of early submission bonus problems with deadlines that are very soon. Check the homework!

Especially, try the propositional logic proof checker.

January 7, 2015

We have just released the edX questions for the week! The early deadline is this Friday at 5PM. You may, of course, wait until the hard deadline, next Friday, but you will not receive extra credit.

FYI, edX is only allows times to be listed in UTC, so go by the times posted on the website / in announcements (or make sure you convert to PST).

Let us know if you have any issues!

Getting Started

January 7, 2015

**Sign Up!**

There are a few different tools we'll be using this quarter to manage the class. Please sign up for:

Piazza

Scoryst

edX

**Homework**

There will be two components to the class assignments.

- First, there will be a series of questions posted on edX each week. These questions will have an early deadline and a hard deadline. If you submit before the early deadline, we will give you 10% extra credit on the questions. You must submit before the hard deadline to receive credit. You only need to submit once.
- There will be longer written assignments, which will be submitted electronically on Scoryst. These questions will only have one deadline, which will be the same as the hard deadline for the edX questions (generally, Friday at 12:49 PM, immediately before class).
- There may be additional components for each individual assignment, but we will announce these week by week.

**Office Hours/Discussion Section**

There will be many office hours throughout the week. As Prof. Dill indicated, lots of the learning in CS 103 occurs during OH, so please stop by! A calendar of the hours and locations will be posted to the website shortly. There will also be a weekly discussion section, where we will go over additional problems on Mondays from 7 - 8:30 PM. We will post the location shortly. You don't need to signup for this; just show up!

**Piazza Policy**

Piazza is a discussion forum for the class. You are encouraged to ask questions publicly, as many students may share your questions. That said, if you are asking about *your solution* to a problem, you should post privately. You should consider Piazza as an extension of in person collaboration. See the section on the Honor Code and Collaboration if you have any questions.

The staff will NOT answer questions about the homework on Piazza starting at 8 PM on Thursday night until the homework is due at class on Friday. Please start the homeworks early, so that you can get your questions answered!

**Reference**

There is lots of information about the class at web.stanford.edu/class/cs103/courseinfo.html. If you have a question about logistics, check here first, and if you can't find an answer, then post to Piazza.

If you have any questions throughout the quarter, feel free to stop by OH, post on Piazza, or for more pressing/personal issues, contact the staff directly on the staff list (cs103-win1415-staff@lists.stanford.edu).

If you have any questions, don't hesitate to reach out to any of the staff members. Looking forward to a great quarter!

Welcome to CS103!

January 5, 2015

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 dill@cs.stanford.edu with questions.

See you soon!

Schedule/syllabus

Course Information

Office Hour Calendar

Deadlines Calendar

Class Definitions

A Guide to Good (and Bad) Proofs

Proof References

Sample Midterm 1 [Solutions]

Midterm 1 Review Slides

(Video to Appear on EdX)

Midterm Solutions

Sample Midterm 2 [Solutions]

Midterm 2 Review Slides

(Video to Appear on EdX)

Discussion 1 [Solutions]

Discussion 2 [Solutions]

Discussion 3 [Solutions]

Discussion 4 [Solutions]

Discussion 5 [Solutions]

Homework 1 [Solutions]

Homework 2 [Solutions]

Homework 3 [Solutions]

Homework 4 [Solutions]

Homework 5 [Solutions]

Homework 6 [Solutions]

Homework 7

Homework 8

Piazza (discussion forum)

Scoryst

edX

Keith Schwarz's CS103 notes

Truth table tool

Propositional logic proof checker

Binary relation editor

DFA Tool

Regular Expression Tool

**
Intro
Slides
(4-up)
**

Slides (4-up)

Slides

Slides

Slides

5: Predicate Logic 2

Slides

6: Proofs 1

Slides

7: Proofs 2

Slides

O1: Proofs - OLD

Slides

8: Set Theory 1

Slides

9: Set Theory 2

Slides

10: Set Theory 3

Slides

11: Set Theory 4

Slides

12: Set Theory 5

Slides

O2: Set Theory - OLD

Slides

O3: Relations - OLD

Slides

O4: Functions - OLD

Slides

13: Induction 1

Slides

M: Some missing slides from lecture 10

Slides

14: Induction II

Slides

O5: Induction- OLD

Slides

15: Formal Languages

Slides

16: Deterministic Finite Automata

Slides

17: Nondeterministic Finite Automata

Slides

18: Regular Expressions

Slides

O6: Regular Expressions - OLD

Slides

19: Proofs of Non-regularity

Slides

20: Decidability I

Slides

21: Decidability II

Slides

22: Decidability III

Slides