Final Exam Graded

December 13, 2013

After four long days of exam grading, the TAs and I have finished grading the final exam. We've released a handout containing solutions and statistics. The exams should be available soon for pickup in the filing cabinet where the midterm was returned. We'll push grades to the grade reporter by the end of the evening.

The TAs are currently finishing up grading Problem Sets 8 and 9. We'll try to get back to you with feedback on those problem sets by Sunday.

Thanks for a great quarter, everyone, and have a wonderful break!

Final Exam Logistics

December 3, 2013

The final exam will be in several rooms in Hewlett, divvied up by last name:

- Last name
**Aba - Ber**: Go to Hewlett 101 - Last name
**Bil - Ell**: Go to Hewlett 102 - Last name
**Emb - Gra**: Go to Hewlett 103 - Last name
**Gre - Zuo**: Go to Hewlett 200

We have pretty much exactly enough room to hold everyone, so please try to show up to the room corresponding to your last time.

As with the midterm, you can bring any notes to the exam for which you are the original author. You can also use a computer to access the course website or to view any notes for which you are the original author. If you own a copy of Sipser, you can bring that as well. No other materials will be permitted.

Problem Set 9 Released Early

November 29, 2013

In case you want to get a jump on the final problem set, we've posted
Problem Set 9 a bit early.
This problem set explores **P**, **NP**, and **NP**-completeness
and hopefully will be a great way to round out the quarter.

The last few topics that will be necessary to complete this problem set
will be covered in Monday's lecture (namely, **NP**-completeness, SAT,
and 3SAT), so don't worry if you don't fully understand all the problems
yet. If you have a copy of Sipser, you can read ahead a bit to see these
topics early.

This problem set is due on Friday, December 6 at 2:15PM. No late periods can be used on this problem set and no late submissions will be accepted. Our goal is to release solutions as soon as the problem set comes due so that you have the maximum possible time to prepare for the final exam.

Good luck!

Extra Credit Practice Final

November 28, 2013

We have just released an extra credit practice final exam. It's worth five points extra credit and is due right after you take the final exam. If you make a good-faith effort to complete all the problems and submit this practice final exam, we'll give you an automatic 5 points extra credit. Our hope is that this rewards you for taking the time to study for the final exam.

We will not release solutions to this practice final. If you have any questions about it, feel free to stop by office hours, email the staff list, or stop by a final exam review session (to be announced later).

We will release two additional practice exams (not for extra credit) between now and the final exam.

Hope this helps!

Thanksgiving Office Hours

November 21, 2013

During the Thanksgiving Break, starting this Saturday (11/23) through next Sunday (12/1), there will be no regularly scheduled Office Hours. We will resume the posted schedule on the Monday after break (12/2).

In the event that a TA decides to hold impromptu/remote OH, we will email the students list to let you all know about it. Additionally, remember that you are always encouraged to send questions about the PSets to the Staff List. We will do our best to be prompt about responding over break, but understand that there may be a longer delay than usual.

Wishing everyone a relaxing break!

Problem Set 8 Out

November 18, 2013

Problem Set 8 goes out today and is due on Monday, December 2. This problem set is all about impossible problems and what makes them so hard, and we hope that this serves as a fitting coda to our treatment of computability theory. Note that this deadline is after Thanksgiving break, so you should have a fair amount of time to finish.

For planning purposes: this is the last problem set on which you can use a late period, and Problem Set 9 will go out as soon as it's due. Since no late submissions will be accepted for Problem Set 9, we advise against taking a late day on this problem set, since if you start Problem Set 9 on Wednesday of the last week of class you will only have two days to complete the assignment.

Good luck!

On Being "Bad at Math"

November 13, 2013

There is an excellent article by a journalism professor dispeling the idea that someone can be "bad at math." It's an excellent read, especially in Week 8 of a rigorous math course.

Enjoy!

Problem Set 7 Out

November 11, 2013

Problem Set 7 goes out today and is due on Monday, November 18. This problem set explores R and RE languages and will be your first foray into the limits of computation. We hope that you have a lot of fun with it!

Good luck!

Office Hours Updated

November 4, 2013

The Office Hours schedule was just updated to include more hours later in the week and over the weekend. Some of the locations are TBD, but we will update at some point during the week.

Midterm Solutions Released

November 4, 2013

Midterm solutions and statistics are now available. Midterms and printed solutions are available for pickup in a specially-marked filing cabinet across from the homework submissions filing cabinet.

Problem Set 6 Out

November 4, 2013

Problem Set 6 goes out today and is due on Monday, November 11. This problem set explores the limits of regular languages and the expressive power of context-free grammars. We hope that this will help you solidify your understanding of regular languages and how to show that languages are context-free.

Good luck!

On Not Fearing Math

November 3, 2013

YouTube star Mathematigal has an excellent video about her experiences as a math major and how not to be afraid of math:

Midterm Rooms

October 28, 2013

The midterm will be spread across five rooms on campus by last name:

**A - G:**Gates B01**H - K:**Gates B03**L - P:**200-002**Q - V:**420-041**W - Z:**Herrin T175

Applications of Regular Languages

October 27, 2013

Although finite automata might seem very theoretical, they have all sorts of uses in software.

Many UI controls (buttons, dropdown menus, etc.) use finite-state machines to decide when to respond to the user. As an example, here is an interactive demo of the finite-state machine for a pushbutton. You can see what state the button is in as you move the mouse around and iteract with it.

Enjoy!

Midterm Review Sessions

October 25, 2013

We will be holding a midterm review session on *Saturday,
October 26* from 2:15PM - 4:15PM in *370-370*. Everyone is
welcome to attend! If you have any questions you'd like answered, please
try to ask them on the Moderator page so that we can put materials
together for then.

Dilli will be converting his normal Sunday SCPD office hours into an remote review session for SCPD students.

Problem Set Five Out

October 25, 2013

Problem Set Five goes out today. This problem set explores finite automata, regular languages, and their properties, and will be your first foray into computability theory. We hope that you enjoy it!

To make it easier to design and test the automata and regular expressions on the problem set, we have released two online tools. First, we have a DFA/NFA Developer where you can design, test, and submit finite automata for Problem One and Problem Two. Second, we have a Regular Expression Developer where you can design, test, and submit regular expressions for Problem Three. Let us know if you have any questions about them!

Finally, as in the past two problem sets, you can submit your answers to the feedback questions online through this form.

Good luck!

Practice Exams Released

October 21, 2013

We have just release two practice midterm exams you can use to help prepare for the midterm. These exams were given in Winter 2012-2013 and Fall 2012 and are similar in structure to this quarter's midterm. The exams are available under the "handouts" link.

We have also released a handout on exam strategies and policies that we hope will help you get a better sense for how to approach the exam and what we're looking for.

Problem Set Four Out

October 18, 2013

Problem Set Four goes out today. This problem set explores functions, cardinality, diagonalization, and mathematical logic. The checkpoint problem is due Monday, October 21 and the rest fo the assignment is due on Friday, October 25.

To make it easier for us to aggregate feedback, we've put the feedback question online for this problem set. Once you've finished the problem set, please fill out the feedback question online.

Good luck!

Diagonalization Video

October 17, 2013

Numberfile has a video about countable and uncountable infinities and the diagonalization of the real numbers:

Thanks to Jessica Pfund for finding this!

"Proof" Techniques

October 16, 2013

Dan Spaeth found this amazing collection of questionable proof techniques. Highly recommended!

Naturals and Reals

October 14, 2013

Minute Physics has a great video on differing cardinalities. You can see it here:

Thanks to Nick Freybler for finding this!

Problem Set Three Out

October 11, 2013

Problem Set Three goes out today. This problem set explores graphs, relations, and the pigeonhole principle and will give you a chance to play around with discrete structures. The checkpoint problem is due Monday, October 14 and the rest fo the assignment is due on Friday, October 18.

To make it easier for us to aggregate feedback, we've put the feedback question online for this problem set. Once you've finished the problem set, please fill out the feedback question online.

Good luck!

Problem Set Two Out

October 4, 2013

Problem Set Two goes out today. It's all about induction, and by the time you've completed it you'll have a much deeper understanding for just how powerful a proof technique induction can be. There's a checkpoint problem due on Monday, October 7, and the rest of the problems are due on Friday, October 11.

Good luck!

Winston Churchill is a Carrot

September 30, 2013

As mentioned in lecture, if you assume 1 = 0, you can prove *anything*.

Here is a fun proof online that uses the assumption that 1 = 0 to prove that Winston Churchill is a carrot. If you have the time to read over it, it's quite entertaining.

Vi Hart on Pythagoras and √2

September 27, 2013

Here is Vi Hart's video about Pythagoras and √2. Enjoy!

Problem Set One Out

September 27, 2013

Problem Set One goes out today. This problem set explores basic proof techniques - direct proofs, proofs by contradiction, and proofs by contrapositive - through a variety of examples. We hope that this problem set will help you get used to writing mathematical proofs!

This problem set is split into two parts - a set of *checkpoint
problems* that are due on Monday, September 30 and a set of normal
problems due on Friday, October 4. The checkpoint problems are graded
based primarily on effort - did you make a good, honest effort to solve
the problems? - and will be graded and returned by Wednesday, October 2.
Our hope with the checkpoint problems is that you will put in the effort
to write the best proofs that you can so that we can provide useful
feedback on your proofs' correctness and clarity in advance on the normal
problem set due date. You can then use this feedback to tune your answers
for the rest of the problem set.

We recommend that you look over the handout on problem set policies and handout on the Honor Code in CS103 prior to starting this problem set. These handouts contain useful information about how to approach the problem sets, as well as our policies for submitting assignments, asking for regrades, and collaborating with other students. For this problem set in particular, we suggest also reading over the handout on set theory definitions, which contains formal definitions of the set operations we saw on the first day of class.

Good luck!

Welcome to CS103!

September 18, 2013

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

See you soon!

00: Course Information

01: Syllabus

02: Problem Set Policies

03: Honor Code

04: Set Theory Definitions

07: Guide to Proofs

14: Practice Midterm 1

14S: Practice Midterm 1 Solns

15: Practice Midterm 2

15S: Practice Midterm 2 Solns

16: Exam Strategies

18: Extra Review Problems

18S: Extra Review Solns

19S: Midterm Solns

24: Alternate TM Proofs

25: Extra Practice Problems

25S: Solns to Extra Problems

28: Extra Practice Problems 2

28S: Solns to Extra Problems 2

29: EC Practice Final

31: Additional Practice Final 1

31S: Solns to Practice Final 1

32: Additional Practice Final 2

32S: Solns to Practice Final 2

34: Final Exam

34S: Final Exam Solns

**
Discussion Problems 1
(solutions)
Discussion Problems 2
(solutions)
Discussion Problems 3
(solutions)
Discussion Problems 4
(solutions)
Discussion Problems 5
(solutions)
Discussion Problems 6
(solutions)
**
Discussion Problems 7

(solutions)

Discussion Problems 8

(solutions)

Problem Set 1

(checkpoint solutions)

(solutions)

Problem Set 2

(checkpoint solutions)

(solutions)

Problem Set 3

(feedback link)

(checkpoint solutions)

(solutions)

Problem Set 4

(feedback link)

(checkpoint solutions)

(solutions)

Problem Set 5

(feedback link)

(solutions)

Problem Set 6

(feedback link)

(solutions)

Problem Set 7

(feedback link)

(solutions)

Problem Set 8

(feedback link)

(solutions)

Problem Set 9

(feedback link)

(solutions)

Course Reader

Lecture Videos

Theorem and Definition Reference

Office Hours Schedule

Grades

DFA/NFA Designer

Regex Designer

**
00: Set Theory
Slides
(Condensed)
01: Direct Proofs
Slides
(Condensed)
02: Indirect Proofs
Slides
(Condensed)
03: Induction I
Slides
(Condensed)
04: Induction II
Slides
(Condensed)
05: Graphs I
Slides
(Condensed)
06: Graphs II
Slides
(Condensed)
07: Binary Relations
Slides
(Condensed)
08: The Pigeonhole Principle
Slides
(Condensed)
Code
09: Cardinality
Slides
(Condensed)
10: Mathematical Logic I
Slides
(Condensed)
11: Mathematical Logic II
Slides
(Condensed)
12: Finite Automata I
Slides
(Condensed)
13: Finite Automata II
Slides
(Condensed)
14: Finite Automata III
Slides
(Condensed)
15: Regular Expressions
Slides
(Condensed)
16: Nonregular Languages
Slides
(Condensed)
17: Context-Free Grammars
Slides
(Condensed)
18: Turing Machines I
Slides
(Condensed)
19: Turing Machines II
Slides
(Condensed)
20: Turing Machines III
Slides
(Condensed)
21: Unsolvable Problems
Slides
(Condensed)
22: Decidability
Slides
(Condensed)
23: Reducibility I
Slides
(Condensed)
24: Reducibility II
Slides
(Condensed)
25: Complexity Theory I
Slides
(Condensed)
26: Complexity Theory II
Slides
(Condensed)
27: NP-Completeness I
Slides
(Condensed)
28: NP-Completeness II
Slides
(Condensed)
29: The Big Picture
Slides
**