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!

More Information

Schedule/syllabus
Course Information
Office Hour Calendar
Deadlines Calendar

Handouts

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 Problems

Discussion 1 [Solutions]
Discussion 2 [Solutions]
Discussion 3 [Solutions]
Discussion 4 [Solutions]
Discussion 5 [Solutions]

Assignments

Homework 1 [Solutions]
Homework 2 [Solutions]
Homework 3 [Solutions]
Homework 4 [Solutions]
Homework 5 [Solutions]
Homework 6 [Solutions]
Homework 7
Homework 8

Resources

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

Lectures

Intro
   Slides (4-up)
1: Syntax Trees
   Slides (4-up)
2: Propositional Logic 1
   Slides
3: Propositional Logic 2
   Slides
4: Predicate Logic 1
   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