Final Exam Logistics

December 11, 2012

The final exam for CS103 will be held in **Cubberly Auditorium** from **12:15PM - 3:15PM** on **Wednesday, December 12**. The exam is open-book, open-note, open-computer, but closed-network, meaning that you can use any notes you'd like and look at lecture slides you've downloaded in advance.

As a reminder, there is an extra credit practice final exam worth +5 extra credit points. It will be due at the exam.

Best of luck on exams!

Problem Set Nine Out

November 30, 2012

Problem Set 9 went out today... it's the last problem set of the quarter!

This problem set explores **P**, **NP**, and **NP**-completeness. It concludes with a "big picture" question exploring the entire hierarchy of languages we built up over the course of the quarter.

Good luck!

Problem Set Eight Out

November 16, 2012

Problem Set 8 went out today. Although there is a checkpoint for this problem set listed in the syllabus, this problem set does not have any checkpoint problems. It is due on Friday, November 30th at 2:15PM.

This problem set explores problems too hard to solve with any feasible computing machine. By the time you've finished it, you will have a much better intuition for **R**, **RE**, and co-**RE** languages.

Good luck!

Problem Set Seven Out

November 9, 2012

Problem Set 7 went out today. Although there is a checkpoint for this problem set listed in the syllabus, this problem set does not have any checkpoint problems. It is due on Friday, November 16th at 2:15PM.

This problem set plays around with **R** and **RE** languages, their
properties, and their limits. This will be your first time playing around with
unsolvable problems, and I hope that you find it exciting!

Good luck!

Problem Set Six Out

November 2, 2012

Problem Set 6 went out today. There is no checkpoint for this problem set, and the assignment is due on Friday, November 9.

This problem set plays around with context-free languages, context-free grammars, pushdown automata, and their limits (both in power and in size). By the time you're done with this problem set, you'll have a much stronger understanding of CFLs.

Good luck!

Problem Set Five Out

October 26, 2012

Problem Set 5 went out today. There is no checkpoint for this problem set, and the assignment is due on Friday, November 2.

This problem set plays around with regular languages, their representations, and their limits. I hope you have fun playing around with our DFA and NFA Designer and learning about the power and limitations of finite automata and regular expressions.

Good luck!

Midterm Logistics

October 22, 2012

The midterm for CS103 will be on **Monday, October 29** from 7PM - 10PM in Cubberly Auditorium. The exam is open-book, open-note, open-computer, but closed-network. It covers material up through and including the lecture on DFAs.

A practice midterm exam is available online, and we will distribute solutions on Wednesday.

Problem Set Four Out

October 19, 2012

Problem Set 4 went out today. The checkpoint problem is due this Monday, October 22 at the start of class and is graded on a received / not received basis. The remaining problems are due on Friday, October 26 at the start of class.

This problem set plays around with logic. You'll get to prove some useful results that make logic more practical in the real world, and will get a good sense of how propositional and first-order logic are connected to proofs.

Good luck!

The Proof is Trivial!

October 14, 2012

Having trouble on the problem set? Perhaps this website can help out!

Thanks to Jenny Hong for the link.

Problem Set Three Out

October 12, 2012

Problem Set 3 went out today. The checkpoint problem is due this Monday, October 15 at the start of class and is graded on a received / not received basis. The remaining problems are due on Friday, October 19 at the start of class.

This problem set explores discrete mathematics - graphs, relations, functions, cardinality, and the pigeonhole principle. By the time you're done, you'll have a thorough command of the material from the past few weeks and will be ready to jump headfirst into formal logic.

Good luck!

Room Change this Friday

October 10, 2012

This Friday's lecture will be in held in **Building 320, room 105** at the normal class time. Braun will be in use for a chemistry symposium then, so we won't be able to use the room.

Hope to see you there!

Problem Set Two Out

October 5, 2012

Problem Set 2 went out today. The checkpoint problem is due this Monday, October 8 at the start of class and is graded on a received / not received basis. The remaining problems are due on Friday, October 12 at the start of class.

This problem set explores mathematical induction and its applications to a diverse range of topics. By the time you're done, you'll have a solid grasp of this powerful and versatile proof technique.

Good luck!

Notes on the Division Algorithm

October 3, 2012

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

October 1, 2012

In lecture I referred to a proof that, starting from the assumption that 1 = 0, proves that Winston Churchill is a carrot. If you're curious about this proof, you can read the proof online. It's quite entertaining.

Problem Set One Out

September 28, 2012

Problem Set 1 goes out today. It consists of two portions. The checkpoint problem is due this Monday, October 1 at the start of class and is graded on a received / not received basis. The remaining problems are due on Friday, October 5 at the start of class.

This problem set explores direct and indirect proof techniques. It's designed to get you up to speed with mathematical proofs so that we can start to rigorously reason about the fundamental nature of computation.

Good luck!

Office Hours Schedule Posted

September 26, 2012

We have just posted our initial office hours schedule. Office hours start today (Friday) and will continue throughout the quarter. There might be some modifications to this schedule over the first week of the course, particularly as we change all the "Location TBDs" to actual locations.

Welcome to CS103!

September 21, 2012

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

07: Diagonalization

10: Practice Midterm

10S: Practice Midterm Solns

12: Practice Midterm 2

12S: Practice Midterm 2 Solns

14: Midterm Exam

14S: Midterm Solutions

18: WB Reference

24: EC Practice Final

25: Practice Final I

25S: Practice Final I Solns

26: Final Exam

26S: Final 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)

Problem Session 1

(solutions)

Problem Session 2

(solutions)

Problem Session 3

(solutions)

Problem Session 4

(solutions)

Problem Session 5

(solutions)

Problem Session 6

(solutions)

Problem Session 7

(solutions)

Problem Session 8

(solutions)

Course Notes

Definitions and Theorems

Office Hours Schedule

Lecture Videos

Grades

DFA/NFA Developer

**00: Set Theory**

Slides (Condensed)

**01: Direct Proofs**

Slides (Condensed)

**02: Indirect Proofs**

Slides (Condensed)

**03: Mathematical Induction I**

Slides (Condensed)

**04: Mathematical Induction II**

Slides (Condensed)

**05: Graphs and Relations**

Slides (Condensed)

**06: Order Relations and Functions**

Slides (Condensed)

**07: Cardinality and Infinity**

Slides (Condensed)

**08: The Pigeonhole Principle**

Slides (Condensed)
(Demos)

**09: Mathematical Logic I**

Slides (Condensed)

**10: Mathematical Logic II**

Slides (Condensed)

**11: Mathematical Logic III**

Slides (Condensed)

**12: Finite Automata I**

Slides (Condensed)

**13: Finite Automata II**

Slides (Condensed)

**14: Finite Automata III**

Slides (Condensed)

**15: Regular Languages**

Slides (Condensed)

**16: Context-Free Grammars**

Slides (Condensed)

**17: Pushdown Automata**

Slides (Condensed)

**18: Beyond CFLs**

Slides (Condensed)

**19: Programming Turing Machines**

Slides (Condensed)

**20: R and RE Languages**

Slides (Condensed)

**21: Unsolvable Problems**

Slides (Condensed)

**22: Mapping Reductions**

Slides (Condensed)

**23: co-RE and Beyond**

Slides (Condensed)

**24: P**

Slides (Condensed)

**25: NP**

Slides (Condensed)

**26: NP-Completeness I**

Slides (Condensed)

**27: NP-Completeness II**

Slides (Condensed)

**28: Topics in Complexity**

Slides (Condensed)

**29: The Big Picture**

Slides