[general info][lecture notes] [homeworks] [exams]
- 6/04 practice final solutions and Homework 7 solutions
- 5/31 Practice final
- 5/30 Homework 6 solutions
- 5/23 Homework 7
- 5/23 Homework 5 solutions
- 5/16 Homework 6
- 5/15 Homework 4 solutions
- 5/13 Another correction to Homework 5 (a typo in one of the examples describing the language in 1.b)
- 5/12 Notes for Lecture 15 and a previewof the Notes for Lecture 16
- 5/11 Three corrections to Homework 5: new problem 1.b, requirement to submit regular expressions online, correction to picture in part 4.b
- 5/09 Homework 5
- 5/07 Homework 3 solutions
- 5/05 If you think the homeworks are too easy, here are some more difficult problems that you can solve with the math that you already know
- 5/05 Correction to Homework 4: you can use OR in problem 2
- 5/02 Homework 4
- 4/29 Homework 2 solutions
- 4/28 solutions of the midterm review problems
- 4/26 The problems from the discussion section of 4/22 and the midterm review problems from the next discussion section of 4/29
- 4/25 Homework 1 solutions and Homework 3
- 4/25 some notes on mathematical logic
- 4/21 Note the new office hours of James and Bryan
- 4/19 Homework 2
- 4/04 Homework 1, Notes on Lecture 3
- 3/31 Welcome to the class
general information
Instructor: LucaTrevisan, Gates 474, Tel. 650 723-8879, email trevisan at stanford dot edu
TAs:
- Bryan Hooi bhooi at stanford.edu
- Neha Nayak nayakne at stanford.edu
- Aditya Palnikar aditpal at stanford.edu
- James Shapiro jamess5 at stanford.edu
Classes are MWF, 12:50-2:05, 420-040
Discussion sections are Tuesdays, 5:30-6:30pm in Thornton110
Office hours:
- Luca: Mondays and Wednesdays, 2:30-3:30pm, 474 Gates
- Aditya Tuesdays and Thursdays, 10am-noon, Huang basem*nt
- Bryan Tuesdays and Thursdays, 2:30-4:30, Gates Basem*nt
- James Wednesdays 4-6pm, and Thursdays 5-7pm Meyer Library, 2nd floor
- Neha Mondays 6-8pm, Huang Basem*nt, and Fridays 9-11am, Huang basem*nt
You can ask questions using piazza
You can reach the whole CS103 staff at cs103-spr1314-staff@lists.stanford.edu
References:
- For the first part of the course, on sets, graphs, and proofs:
- Notes by Keith Schwarz
- (Not required) Kenneth Rosen. Discrete Mathematics and its Applications McGraw-Hill, 7th edition.
(You can also buy an used earlier edition)
- For the rest of the course, on automata, computability and complexity:
- Michael Sipser. Introduction to the Theory of Computation Cengage, 3rd edition
(The first edition published by PWS and the second edition published by Thomson also contain all the necessary material)
- Michael Sipser. Introduction to the Theory of Computation Cengage, 3rd edition
- Some additional resources:
- A tool to construct and test automata
- A tool to constructand test regular expressions
- Some challenging mathematical problems to think about
Homeworks:
- Late policy: Homeworks are due on Fridays and solutions will be posted the following Tuesday. Of the seven homeworks, you can turn two of them late, before the following Tuesday at noon. After you hand in two late homework, any other late homework will be graded as zero.
- Collaboration versus cheating: make sure you are familiar with our policy on collaboration
- How to write your solution: if you are handwriting your solution, make sure it is legible. When describing a mathematical proof, do not skip important steps. The description of your proofsshould be as clear as possible (which does not meanlong — in fact, typically, good clear explanations are alsoshort.) The TAs will split the grading by problem, so make sure that your name and student ID is on every page and that the solutions of different problems are on different pages.
- Submitting the homework:Drop your completed homework in the CS103 homework submission box which is on the ground floor of Gates.
You can also submit your homework by email, sending it to cs103-spr1314-hw at lists.stanford.edu
classes and lecture notes
so far:- 03/31. Introduction, summary of the content of the course, sets, Cantor's theorem
Readings: Notes, chapter 1 - 04/02. "Just do it" proofs: sum of two odd integers is even, product of two odd integers is odd, how to argue that two sets are equal or that a set is contained in another,properties of boolean XOR, one-time pad. Preview of proofs of contradiction: square root of 2 is not rational
Readings: Notes, sections 2.1 and 2.2 - 04/04. Proofs by contrapositive and contradiction. How to negate implications. Pigeonhole principle. There are infinitely many primes.
Readings: Notes, sections 2.3 and 2.4, additional notes - 04/14. Proofs by induction. A formula for the sum of squares. Solving the "fake coin" problem with the minimal number of measurements.
Readings: Notes, sections 3.1 and 3.2 - 04/16. More on proofs by induction: strong induction, induction with several base cases, using a starting point different from zero. Proof that integers can always be written as a product of primes and of the "division algorithm" theorem, proofs by "infinite descent" using the well-ordering principle.
Readings: Notes, sections 3.4.1 (can skip 3.4.1.1), 3.5.1, 3.5.3, 3.6.1 - 04/18. Binary relations: partial orders, well-orderings, induction over well-orderings, equivalence relations, equivalence classes.
Readings: Notes, sections 5.1.1, 5.1.2, 5.2.1, 5.3 (skip starred sections), 5.4 - 04/21. Graphs: directed and undirected graphs, paths, connectivity and connected components, strong connectivity
Readings: Notes, sections 4.1, 4.2 (skip 4.2.2 and 4.2.3) - 04/23. Proving properties of graphs: topological sort, a directed graph has a topological sort if and only if it is acyclic, vertex-colorings of undirected graphs,an undirected graph has a two-coloring if and only if it has no odd cycle
Readings: Notes, section 4.3 (skip 4.3.2) - 04/25. Propositional logic
Readings: notes - 04/28. First-order logic
Readings: notes of lecture 9, additional notes to be posted - 05/02. Introduction to DFA
Readings: Sipser Section 1.1 (skip subsection on regular operations) - 05/05. Formal definition of DFA, introduction to NFA, examples of NFA, converting an NFA to DFA
Readings: Sipser Section 1.2 (skip subsection on regular operations; note that we have not talked about epsilon-transitions yet) - 05/07. epsilon-transitions. Regular languages are closed under union, intersection and complement
Readings: Sipser subsections on regular operations in Sections 1.1 and 1.2 - 05/09. Definition of regular expressions. Equivalenceof regular expressions and DFAs and NFAs
Readings: Sipser Section 1.3 - 05/12. Distinguishable and indistinguishable strings. The Myhill-Nerode theorem.
Readings: notes - 05/14. Using the Myhill-Nerode theorem to prove that languagesnot regular. Minimizing the number of states of a DFA.
Readings: notes - 05/16. More on minimizing the number of states of a DFA.
Readings: same notes as previous lecture - 05/19. Definition of Turing machines, variants of Turing machines.
Readings: Sipser Chapter 3, skip part on enumerators - 05/21. The halting problem is not decidable
Readings: Sipser Section 4.2 (skip part on non-recognizable languages)
Optional reading: Turing's original paper is a good read - 05/23. Universal turing machines, equivalence of enumerable and recognizable languages, non-recognizable languages.
Readings: Section on enumerators in Chapter 3 and section on non-recognizable languages in 4.2 - 05/28. More undecidable problems. Mapping reductions.
Readings: Sipser Section 5.3 - 05/30 Review of mapping reductions
Readings: Sipser Section 5.3 - 06/02. P, NP, polynomial time reductions (not part of the syllabus for the final)
- 06/04. NP-completeness of SAT (not part of the syllabus for the final)
the plan:
- 03/31. Introduction, summary of the course, Cantor's theorem
- 04/02. "Just-do-it" proofs
- 04/04. Proofs by contradiction
no class 04/07, 04/09, 04/11 - 04/14. Induction
- 04/16. Induction, part 2
- 04/18. Binary relations
- 04/21. Graphs
- 04/23. The pigeonhole principle
- 04/25. Logic
- 04/28. Logic, part 2
- 04/30. midterm
- 05/02. Finite automata
- 05/05. Finite automata, part 2
- 05/07. Finite automata, part 3
- 05/09. Regular expressions
- 05/12. Pumping lemma
- 05/14. Myhill-Nerode theorem
- 05/16. Turing machines
- 05/19. Turing machines, part 2
- 05/21. Decidable and Undecidable problems
- 05/23. Reductions
- 05/26. Memorial Day
- 05/28. Complexity theory, P and NP
- 05/30. Complexity theory, P and NP, part 2
- 06/02. NP-compleness of 3SAT
- 06/04. more NP-complete problems
discussion sections
- Problems from 4/22
- Problems from 4/29 and solutions (midterm review)
- Problems from 5/6
homeworks
Homeworks are out on Friday and are due the following Friday.- Homework 1 is due 04/18 (solutions)
- Homework 2 is due 04/25 (solutions)
- Homework 3 is due 05/02 (solutions)
- Homework 4 is due 05/09 (solutions)
- Homework 5 is due 05/16 (solutions)
- Homework 6 is due 05/23 (solutions)
- Homework 7 is due 05/30 (solutions)
exams
The midterm will be in class, on April 30. The syllabus for the midterm is up to, and including, the 04/23 lecture, but it does not include logic.The midterm is closed-book and closed-notes, but you can use one sheet of notes (double-sided is ok)The final will be on June 6, 8:30-11:30am, in 420-40. The syllabus for the final is up to the 5/28 lecture. The final exam is closed-book and closed-notes, but you can use two sheets of notes (each can be double-sided)
Practice problems for the final and solutions
