Problem Set Nine Out

March 11, 2013

Problem Set Nine goes out today and is due
on *Friday, March 15* at 12:50PM. This problem explores **P** and **NP**
and concludes with a wrap-up of all the complexity and computability classes we've
covered in this course.

You may use a late day on this assignment if you would like. If so, it is due immediately after you take the final exam. Due to university policy, we cannot accept any submissions received after 11:30AM.

Good luck!

Problem Set Eight Out

March 4, 2013

Problem Set Eight goes out today and is due
on *Monday, March 11* at 12:50PM. This problem explores unsolvable problems and
the limits of what computers can do. It concludes with an exploration of why languages
like A_{TM} and L_{D} matter in the real world, and I hope that this
forms a satisfying coda to our treatment of computability.

Good luck!

Problem Set Seven Out

February 25, 2013

Problem Set Seven goes out today and is due
on *Monday, March 4* at 12:50PM. This problem set explores the **RE** and **R**
languages and the limits of Turing machines. This will be your first experience probing
the limits of what problems can be solved by computers, and I hope you find it exciting!

Good luck!

Turing Machines and Self-Assembling Molecules

February 25, 2013

Anna Saplitski found an awesome video describing how self-assembling molecules can simulate Turing machines. This incredible video details the amazing connection between computational processes, emergent behavior, and how complex objects can be built from smaller pieces. I highly recommend it!

Problem Set Six Out

February 15, 2013

Problem Set Six goes out today and is due
on *Monday, February 25* at 12:50PM. It explores context-free languages, their
representations, their properties, and their limits.

Good luck!

Midterm Review Sessions

February 9, 2013

Julius will be holding an online review session on Saturday from 7PM-10PM. We will send out the Google hangout link when the time approaches.

Maurizio will be holding an in-person review session on Sunday, Feb. 10 from 5PM-7PM in Hewlett 200.

Problem Set Five Out

February 8, 2013

Problem Set Five went out today and is due next
*Friday, February 15* at the start of class. This problem set explores regular
languages, their representations, and their limits. This will be your first foray into
computability theory, and I hope that you find it fun and exciting!

We have two online tools you can use in this course of this problem set, both of which are linked under the "Resources" section of this page. Our DFA/NFA developer is a full development environment in which you can design, build, test, and debug finite automata. The regular expression developer will let you build regular expressions and test them on a variety of different inputs.

Good luck!

Second Practice Midterm Available

February 7, 2013

We have posted a second practice midterm exam you can use to help prepare for the upcoming midterm. Solutions to the first practice midterm are also available.

Practice Midterm Available

February 4, 2013

The CS103 midterm is next *Tuesday, February 12* from 7PM - 10PM, location to be
announced soon. It is open-book, open-note, open-computer, but closed-network, so it's
totally fine to bring your laptop with you to the exam.

We have posted a practice midterm exam. This was the exam given in fall quarter, so its content, form, and structure should be similar to that of the real exam. We will release solutions on Wednesday.

Problem Set Four Out

February 1, 2013

Problem Set Four went out today. The checkpoint assignment is due next *Monday, February 4* at 12:50PM and the remaining problems are due next *Friday, February 8* at the start of class. This problem set explores properties of propositional and first-order logic, as well as the power of SAT solving algorithms.

Good luck!

Problem Set Three Out

January 25, 2013

Problem Set Three went out today. The checkpoint assignment is due next *Monday, January 28* at 12:50PM and the remaining problems are due next *Friday, February 1* at the start of class. This problem set explores relations, functions, cardinality, and the pigeonhole principle. After completing it, you'll have a much stronger understanding of discrete structures.

Good luck!

Problem Set Two Out

January 18, 2013

Problem Set Two went out today. The checkpoint assignment is due next *Tuesday, January 22* at 5:00PM and the remaining problems are due next *Friday, January 25* at the start of class. This problem set is all about induction and its applications in computer science. By the time you're done, you'll have a much deeper understanding of just how versatile induction can be.

Good luck!

Notes on the Division Algorithm

January 16, 2013

There is a positively fascinating essay on the division algorithm, its proof, and why it's mathematically so important. I highly recommend giving it a read. It's available online if you are interested in reading through it.

Winston Churchill is a Carrot

January 14, 2013

An interesting consequence of proof by contradiction is that starting with a false statement, it's possible to prove *anything*.

Here is a fun proof online that uses the incorrect 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.

Problem Set One Out

January 11, 2013

Problem Set One went out today. The checkpoint assignment is due next *Monday, January 14* at the start of class and the remaining problems are due next *Friday, January 18* at the start of class. This problem set is designed to get you used to writing mathematical proofs and to get you thinking about set theory, the integers, and even a bit of cryptography!

Good luck!

Vi Hart on Pythagoras and √2

January 11, 2013

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

Welcome to CS103!

January 7, 2013

Welcome to CS103, an exciting and fast-paced 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: Prior Experience Survey

08: Diagonalization

12: Practice Midterm

12S: Practice Midterm Solns

13: Practice Midterm 2

13S: Practice Midterm 2 Solns

15: CS103 Midterm

15S: CS103 Midterm Solns

24: EC Practice Final

25: Practice Final I

25S: Practice Final I Solns

26: Practice Final II

26S: Practice Final II Solns

27: Final Exam

27S: Final Exam Solutions

Problem Set 1

(checkpoint solutions)

(solutions)

Problem Set 2

(checkpoint solutions)

(solutions)

Problem Set 3

(checkpoint solutions)

(solutions)

Problem Set 4

(checkpoint solutions)

(solutions)

Problem Set 5

(solutions)

Problem Set 6

(solutions)

Problem Set 7

(solutions)

Problem Set 8

(solutions)

Problem Set 9

(solutions)

Discussion Problems 1

(solutions)

Discussion Problems 2

(solutions)

Discussion Problems 3

(solutions)

Discussion Problems 4

(solutions)

**Discussion Problems 5**

(midterm week; no recitation)

Discussion Problems 6

(solutions)

Discussion Problems 7

(solutions)

Discussion Problems 8

(solutions)

Discussion Problems 9

(solutions)

Course Notes

Lecture Videos

Definitions and Theorems

Office Hours Schedule

Grades

DFA/NFA Developer

Regex Developer

**00: Set Theory**

Slides (Condensed)

**01: Direct Proofs**

Slides (Condensed)

**02: Indirect Proofs**

Slides (Condensed)

**03: Induction, Part I**

Slides (Condensed)

**04: Induction, Part II**

Slides (Condensed)

**05: Graphs and Relations**

Slides (Condensed)

**06: Functions and Cardinality**

Slides (Condensed)

**07: Unequal Cardinalities**

Slides (Condensed)

**08: Mathematical Logic I**

Slides (Condensed)

**09: Mathematical Logic II**

Slides (Condensed)

**10: Mathematical Logic III**

Slides (Condensed)

**11: Finite Automata I**

Slides (Condensed)

**12: Finite Automata II**

Slides (Condensed)

**13: Finite Automata III**

Slides (Condensed)

**14: The Pumping Lemma**

Slides (Condensed)

**15: Pushdown Automata**

Slides (Condensed)

**16: CFGs**

Slides (Condensed)

**17: Turing Machines**

Slides (Condensed)

**18: Turing Machines II**

Slides (Condensed)

**19: Turing Machines III**

Slides (Condensed)

**20: Decidability and Undecidability**

Slides (Condensed)

**21: co-RE and Reducibility**

Slides (Condensed)

**22: Mapping Reducibility**

Slides (Condensed)

**23: Mapping Reducibility II, Complexity**

Slides (Condensed)

**24: P and NP**

Slides (Condensed)

**25: NP-Completeness**

Slides (Condensed)

**26: NP-Completeness II**

Slides (Condensed)

**27: The Big Picture**

Slides