Mathematical Foundations of Computing (2024)

[general info][lecture notes] [homeworks] [exams]

what's new

• 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

Welcome to CS103! This course is about mathematical techniques that are useful in computer science, toanalyze algorithms and prove impossibility results. The course has four parts: (1) introduction to the kind of discrete mathematics that is useful in computer science, including sets, graphs and proofs by induction; (2) finite automata, which model simple linear-time algorithms and capture the power of regular expressions — we will be able to understand the power and limitation of this class of algorithms inside out; (3) turing machines and undecidability, in which we study the power of arbitrary algorithms that are allowed arbitrarily large running times — we will show that there are several important problems that are unsolvable even under such conditions; (4) complexity theory and NP-completeness, which is concerned with the study of what we can do with efficient algorithms.

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 basement
• Bryan Tuesdays and Thursdays, 2:30-4:30, Gates Basement
• James Wednesdays 4-6pm, and Thursdays 5-7pm Meyer Library, 2nd floor
• Neha Mondays 6-8pm, Huang Basement, and Fridays 9-11am, Huang basement

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)
• Some additional resources:
  • A tool to construct and test automata
  • A tool to constructand test regular expressions
  • Some challenging mathematical problems to think about

Grading: the homeworks are worth 60% of the grade, the final 25% and the midterm 15%

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.

1. Homework 1 is due 04/18 (solutions)
2. Homework 2 is due 04/25 (solutions)
3. Homework 3 is due 05/02 (solutions)
4. Homework 4 is due 05/09 (solutions)
5. Homework 5 is due 05/16 (solutions)
6. Homework 6 is due 05/23 (solutions)
7. 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