Announcements

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!

Handouts

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

Assignments

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)

Section Handouts

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)

Resources

Course Notes
Definitions and Theorems
Office Hours Schedule
Lecture Videos
Grades
DFA/NFA Developer

Lectures

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