Boolean Algebra

Canonical Forms

Circuits

Context-Free Grammar (CFG)

Directed Graphs

English Proofs

Equivalences

Euclidian Algorithm

FSM Minimization

Finite State Machine (FSM)

Greatest Common Divisor (GCD)

Induction

Limitations of DFAs, NFAs, and REs

Modular Equations

Modular Exponentiation

Modular arithmetic

More Structural Induction

Nondeterministic Finite Automata (NFA)

Predicate Logic

Primes

Proofs for Predicate Logic

Proofs for Propositional Logic

Propositional calculus (Propositional logic)

Recursively Defined Functions

Recursively Defined Sets

Regular expression

Relating DFAs, NFAs, and REs

Relation (mathematics)

Set (mathematics)

Set theory

Strong Induction

Structural Induction

Translation

CSE 311 Foundations of Computing I University of Washington Autumn 2021 CSE 311 introduces theoretical computer science, the theory background necessary for other CSE courses, and how to construct rigorous, formal arguments. Topics include logic, set theory, modular arithmetic, induction, regular expression, and relations.  1. Teach you the theory background needed for other CSE courses
    – only topics used in many areas of CSE
1. Teach you how to make and communicate rigorous and formal arguments
    – want to know for certain that systems work
1. Introduce you to theoretical CS
    – may be the only theory course you take  There is no required text for the course. For the first 6-7 weeks of the course, the following textbook can be useful: Rosen, Discrete Mathematics and Its Applications, McGraw-Hill. (Course materials will reference problem numbers from the 6th edition, but more recent versions include the same material.) It should be available through the bookstore and on short-term loan from the Engineering Library.

On occasion, there may be required readings during the course when there is insufficient time to fully cover the material during lecture. If this occurs, the readings will be posted on the web site and students will be notified of the reading via email or the message board.

CSE 311 Foundations of Computing I

The math foundations of Computer Science are the fundamental skills to understand advanced fields in Computer Science, and also the key to more advanced topics such as [*Theoretical Computer Science*](/topic/theoretical-computer-science). It includes a range of topics such as Discrete Mathematics, Probability Theory, Combinatorics etc. 

Mathematical Foundations

Computer Science

Theoretical Computer Science (TCS) is a subset of computer science that focuses on the more abstract, mathematical aspects of computing. Its main purpose is to understand the nature of computation, to provide rigorous frameworks for designing and analyzing algorithms, and to determine the inherent limitations of efficient computation. Common sub-topics include algorithms and data structures, complexity theory, automata theory, cryptography, and other mathematical models of computation.

Theoretical Computer Science

CS 103A Math Problem-Solving Strategies Stanford University Winter 2020 CS 103A serves as an additional review course for CS103 students, focusing on strengthening proof-based mathematics skills and general problem-solving strategies in a context closely tied to CS103. Math, like programming, is a skill that takes practice to develop. In CS103A, we'll
provide extra review of the topics from CS103 and discuss general problem-solving
strategies that often come up in proof-based mathematics. We hope that the course
helps solidify the concepts from CS103 and provides you with a set of tools you can
use to confront challenging math problems with confidence.

If you're interested in taking CS103 but feel like you could use a little bit more practice
and review, this is the course for you!  CS103A has CS103 as a corequisite. This class is specifically designed as an add-on
course for CS103 and the material and presentation will be tailored to current CS103
students. As a result, you must be enrolled in CS103 to take CS103A. 

CS 103A Math Problem-Solving Strategies

15-354 Computation & Discrete Math Carnegie Mellon University Spring 2021 This advanced course reexamines traditional concepts of discrete mathematics (relations, functions, logic, graphs, algebra, automata) in the context of computation and algorithms, necessitating a strong background in discrete math. In a nutshell, the main idea behind this course is that the development of the digital computer, together with the theory of computation, is also one of the most important developments in mathematics in the 20th century. Consequently, this course takes a fresh look at some of the standard concepts of discrete mathematics (relations, functions, logic, graphs, algebra, automata), with strong and consistent emphasis on computation and algorithms. Another key concern is knowledge transfer: we need to realign traditional mathematical concepts with our new computational universe and find ways to apply ideas from one realm to the other. We begin with a brief introduction to computability and computational complexity. Other topics may include: iteration, orbits and fixed points; order and equivalence relations; transition systems; groups and actions; finite fields, randomness; propositional logic and satisfiability testing.

To get a better impression, take a look at some of the homework problems that were used in previous versions of this course: [CDM Assignments](https://www.cs.cmu.edu/~sutner/CDM/notes/hw-master-nosol.pdf). A few pictures can be found here: [CDM Gallery](https://www.cs.cmu.edu/~sutner/CDM/bilder.html) (challenge: figure out what these pictures mean, for as many as you can manage). A slightly dated paper outlining the course philosophy can be found at [Jeric](http://www.cs.cmu.edu/~sutner/papers/JERIC05.pdf).

Needless to say, a solid background in discrete math is necessary for this course. You should feel very much at home with all the 15-251 material.   

15-354 Computation & Discrete Math

CSE 312 Foundations of Computing II University of Washington Winter 2022 This course dives deep into the role of probability in the realm of computer science, exploring applications such as algorithms, systems, data analysis, machine learning, and more. Prerequisites include CSE 311, MATH 126, and a grasp of calculus, linear algebra, set theory, and basic proof techniques. Concepts covered range from discrete probability to hypothesis testing and bootstrapping. ## Why is CSE 312 Important?

While the initial foundations of computer science began in the world of discrete mathematics (after all, modern computers are digital in nature), recent years have seen a surge in the use of probability as a tool for the analysis and development of new algorithms and systems. As a result, it is becoming increasingly important for budding computer scientists to understand probability theory, both to provide new perspectives on existing ideas and to help further advance the field in new ways.

Probability is used in a number of contexts, including analyzing the likelihood that various events will happen, better understanding the performance of algorithms (which are increasingly making use of randomness), or modeling the behavior of systems that exist in asynchronous environments ruled by uncertainty (such as requests being made to a web server). Probability provides a rich set of tools for modeling such phenomena
and allowing for precise mathematical statements to be made about the performance of an algorithm or a system in such situations.

Furthermore, computers are increasingly often being used as data analysis tools to glean insights from the enormous amounts of data being gathered in a variety of fields; you’ve no doubt heard the phrase “big data” referring to this phenomenon. Probability theory and statistics are the foundational methods used for designing new algorithms to model such data, allowing, for example, a computer to make predictions about new or uncertain events. In fact, many of you have already been the users of such techniques. For example, most email systems now employ automated spam detection and filtering. Methods for being able to automatically infer whether or not an email message is spam are frequently rooted in probabilistic methods. Similarly, if you have ever seen online product recommendation (e.g., “customers who bought X are also likely to buy Y”), you’ve seen yet another application of probability in computer science. Even more subtly, answering detailed questions like how many buckets you should have in your a hash table or how many machines you should deploy in a data center (server farm) for an online application make use of probabilistic techniques to give precise formulations based on testable assumptions.
 Our goal in this course is to build foundational skills and give you experience in the following areas:

1. **Understanding the combinatorial nature of problems**: Many real problems are based on understanding the multitude of possible outcomes that may occur, and determining which of those outcomes satisfy some criteria we care about. Such an understanding is important both for determining how ikely an outcome is, but also for understanding what factors may affect the outcome (and which of those may be in our control).
2. **Working knowledge of probability theory and some of the key results in statistics**: Having a solid knowledge of probability theory and statistics is essential for computer scientists today. Such knowledge includes theoretical fundamentals as well as an appreciation for how that theory can be successfully applied in practice. We hope to impart both these concepts in this class.
3. **Appreciation for probabilistic statements**: In the world around us, probabilistic statements are often made, but are easily misunderstood. For example, when a candidate in an election is said to have a 53% likelihood of winning does this mean that the candidate is likely to get 53% of the vote, or that that if 100 elections were held today, the candidate would win 53% of them? Understanding the difference between these statements requires an understanding of the model in the underlying probabilistic analysis.
4. **Applications in machine learning and theoretical computer science**: We are not studying probability theory simply for the joy of drawing summation symbols (okay, maybe some people are, but that’s not what we’re really targeting in this class), but rather because there are a wide variety of applications where probability and statistics allow us to solve problems that might otherwise be out of reach (or would be solved more poorly without the tools that probability and statistics can bring to bear). We’ll look at examples of such applications throughout the class. For example, machine learning is a quickly growing subfield of artificial intelligence which has grown to impact many applications in computing. It focuses on analyzing large quantities of data to build models that can then be harnessed in real problems, such as filtering email, improving web search, understanding computer system performance, predicting financial markets, or analyzing DNA. Probability and statistics form the foundation of these systems. Another example application area is the use of randomized algorithms and probabilistic data structures. These usually have simpler and more elegant implementations than their deterministic counterparts, and have more efficient time and/or space complexity. We will be learning about some of these applications and you will have the opportunity to implement some of these algorithms.
 CSE 311 and MATH 126. Here is a quick rundown of some of the mathematical tools we’ll
be using in this class: calculus (integration and differentiation), linear algebra (basic operations on vectors and matrices), an understanding of the basics of set theory (subsets, complements, unions, intersections, cardinality, etc.), and familiarity with basic proof techniques (including induction). - (Recommended) Alex Tsun, Probability & Statistics with Applications to Computing, 2020. Available free online [here](http://www.alextsun.com/files/Prob_Stat_for_CS_Book.pdf).
- (Optional) Sheldon Ross, A First Course in Probability (10th Ed.), Pearson Prentice Hall, 2018.
- (Optional) Larsen and Marx, An Introduction to Mathematical Statistics (5th edition). Prentice-Hall.
- (Optional) Dimitri P. Bertsekas and John N. Tsitsiklis, Introduction to Probability, First Edition, Athena Scientific, 2000. Available free online [here](https://www.vfu.bg/en/e-Learning/Math--Bertsekas_Tsitsiklis_Introduction_to_probability.pdf).

CSE 312 Foundations of Computing II

CS 70: Discrete Mathematics and Probability Theory UC Berkeley Fall 2022 CS 70 presents key ideas from discrete mathematics and probability theory with emphasis on their application in Electrical Engineering and Computer Sciences. It addresses a variety of topics such as logic, induction, modular arithmetic, and probability. Sophomore mathematical maturity and programming experience equivalent to an Advanced Placement Computer Science A exam are prerequisites. Logic, infinity, and induction; applications include undecidability and stable marriage problem. Modular arithmetic and GCDs; applications include primality testing and cryptography. Polynomials; examples include error correcting codes and interpolation. Probability including sample spaces, independence, random variables, law of large numbers; examples include load balancing, existence arguments, Bayesian inference. The goal of this course is to introduce students to ideas and techniques from discrete mathematics that are widely used in Electrical Engineering and Computer Sciences. The course aims to present these ideas "in action"; each one will be geared towards a specific significant application. Thus, students will see the purpose of the techniques at the same time as learning about them. Sophomore mathematical maturity, and programming experience equivalent to that gained with a score of 3 or above on the Advanced Placement Computer Science A exam. There is no textbook for this class. Instead, there is a set of comprehensive lecture notes posted on [the front page](https://www.eecs70.org/) for each lecture. Make sure you revisit the notes after every lecture. Each note may be covered in one or more lectures.

Distinguished Alum Megan says, “When I took the course, I studied the notes until I was able to comfortably reproduce all of the proofs.

CS 70: Discrete Mathematics and Probability Theory

CSE 311 Foundations of Computing I

Overview

Prerequisites

Learning objectives

Textbooks and other notes

Other courses in Mathematical Foundations

CS 103A Math Problem-Solving Strategies

15-354 Computation & Discrete Math

CSE 312 Foundations of Computing II

CS 70: Discrete Mathematics and Probability Theory

Courseware availability

Covered concepts