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

Mathematical Foundations of Computing (2024)

FAQs

What is the foundation of computing mathematics? ›

Foundations of Computational Mathematics (FoCM) is an international nonprofit organization that supports and promotes research at the interface of mathematics and computation.

Is mathematical computing hard? ›

The complexity of computational mathematics is subjective and largely depends on an individual's passion for the subject. For those who are fascinated by mathematical calculations and computational technologies, this course can be engaging and enjoyable rather than difficult.

Is Foundations of Computational Mathematics a good journal? ›

Foundations of Computational Mathematics (FoCM) publishes research and survey papers of the highest quality, which further the understanding of the connections between mathematics and computation, including the interfaces between pure and applied mathematics, numerical analysis and computer science.

Is computer science math heavy? ›

Computer science operates on the language of math. That means earning your bachelor's degree in computer science will likely require taking several math courses. Of course, the number and kinds of classes will depend on your program. At its core, math is about verifying whether certain logical statements are true.

What is the basic math for computing? ›

Binary mathematics is the heart of the computer and an essential math field for computer programming. For all mathematical concepts, the binary number system uses only two digits, 0 and 1. It simplifies the coding process and is essential for low-level instructions used in hardware programming.

Do you need maths for computing? ›

Do you need math in computer science? Because math is a foundational part of computer systems, every programmer and computer scientist needs to have basic mathematical knowledge. The type and level of math you need depends on what areas of computer science you want to work in.

What is the hardest subject in math? ›

This blog is about the five most difficult topics in mathematics that students fear.
  • Calculus. Calculus is the study of integrals, function limits, and derivative combinations for real numbers and their analysis. ...
  • Differential equations and dynamic systems. ...
  • Algebra. ...
  • Combinatory. ...
  • Logic.
Sep 20, 2021

What is harder math or computer science? ›

The answer is: it depends entirely on where you go, and your personal skills and affinities . It really does, as much of a frustrating non-answer as that is. CS is more challenging than Math in one particular form: Math is more of a classical discipline, where CS is more of a lifestyle.

Is computer coding a lot of math? ›

Web development and software engineering require basic algebra and arithmetic, while more specialized areas such as machine learning, computer graphics, or data analysis require advanced mathematical competency. Also, logical thinking and problem-solving skills are essential for coding.

Is Foundations of College algebra hard? ›

Depending on the school, class, and teacher, College Algebra can be about the same as Algebra II, a little more advanced, or a little easier. If you are prepping to enter a calculus course, it will be harder. If it's simply a required gen-ed, it may be a little easier.

What is the world's most widely read math journal? ›

Notices of the American Mathematical Society is the world's most widely read journal aimed at professional mathematicians.

Is computational math a good degree? ›

Is a Computational Mathematics degree worth it? Absolutely! The skills gained from this degree are highly sought after in our increasingly data-driven world.

What level of math is computer science? ›

How Much Math Does a Computer Science Degree Require? Typical undergraduate computer science curriculum spans calculus, probability, algebra, discrete math and statistics coursework, including classes like: Calculus 1. Linear Algebra.

Does an IT degree require math? ›

Math is a large component of computer and information technology, and courses in it will be required. If you struggle with mathematics but are still interested in studying hard and pursuing information technology, there are ways to overcome these struggles and excel in math.

Is accounting hard if you're bad at math? ›

Expertise in mathematics is not required to succeed as a bookkeeper or an accountant. What is needed, however, is the confidence and ability to be able to add, subtract, multiply, divide as well as use decimals, fractions and percentages.

What is the foundation of computing? ›

The Computing Foundations cluster investigates the theory, tools, and practices that enable all areas of computing. Topics include the theory of computation, logic, algorithms, architecture, programming languages, software engineering, and parallel and high-performance computing.

What is the foundational concept of computing? ›

A computer is basically a programmable machine capable to perform arithmetic and logical operations automatically and sequentially. It is also known as a data processor, as it can store, process, and retrieve data as per the wish of the user.

What is mathematics of computing? ›

Computational mathematics is the study of the interaction between mathematics and calculations done by a computer. A black and white rendition of the Yale Babylonian Collection's Tablet YBC 7289 (c.

What is the basic foundation of mathematics? ›

foundations of mathematics, the study of the logical and philosophical basis of mathematics, including whether the axioms of a given system ensure its completeness and its consistency.

Top Articles
Latest Posts
Recommended Articles
Article information

Author: Msgr. Refugio Daniel

Last Updated:

Views: 6227

Rating: 4.3 / 5 (54 voted)

Reviews: 85% of readers found this page helpful

Author information

Name: Msgr. Refugio Daniel

Birthday: 1999-09-15

Address: 8416 Beatty Center, Derekfort, VA 72092-0500

Phone: +6838967160603

Job: Mining Executive

Hobby: Woodworking, Knitting, Fishing, Coffee roasting, Kayaking, Horseback riding, Kite flying

Introduction: My name is Msgr. Refugio Daniel, I am a fine, precious, encouraging, calm, glamorous, vivacious, friendly person who loves writing and wants to share my knowledge and understanding with you.