Deterministic finite automaton (DFA)

Set (mathematics)

Set theory

Proof by contradiction

Contraposition

Quantification (logic)

Logical connective

Predicate (mathematical logic)

Function (mathematics)

Constant (mathematics)

Quantifier (logic)

Binary relation

Reflexive relation

Symmetric relation

Transitive relation

Equivalence relation

Equivalence class

Domain of a function

Codomain

Injective function

Surjective function

Bijection

Function composition

Cardinality of the continuum

Cantor's diagonal argument

Graph theory

Mathematical induction

Strong induction

Formal language

Direct proof

Propositional calculus (Propositional logic)

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

Mathematical Foundations

Strings and encodings

Turing Machines

Church-Turing Thesis

Universality

Stable Matching

Randomness

Cryptography

Decidability

Boolean Circuits

Randomized Algorithms

Interactive Proofs

Time Complexity

NP (complexity)

Modular arithmetic

Gödel's Incompleteness Theorems

Graphs

NP-completeness

Group Theory

Probability theory

Fields and Polynomials

Graph Algorithms

Matchings and Bipartite Graphs

Approximation Algorithms

Quantum Computation

15-251 Great Ideas in Theoretical Computer Science Carnegie Mellon University Fall 2018 The course provides a rigorous introduction to the foundations of computer science, improving abstract thinking skills and preparing students to be innovators in the field. Topics include computation, computational complexity, and real-world applications of computational concepts. Prerequisites imply this is an intermediate-level course.  Broadly speaking, the course has several goals. First, it provides a rigorous/formal introduction to the foundations of computer science, which is the science that studies computation in all its generality. An important component of this is improving your analytic and abstract thinking skills since nature's language is mathematics. Second, the course intends to prepare you to be innovators in computer science by presenting some of the great ideas that people in the past have contributed to science and humanity. We hope that you will learn from their examples. Third, the course gives you opportunities to improve your social skills by emphasizing cooperation, clarity of thought, and clarity in the expression of thought.

More specifically, some of the main learning objectives are the following.

- Define mathematically the notions of computation, computational problem, and algorithm.
- Express, analyze and compare the computability and computational complexity of problems.
- Use mathematical tools from set theory, combinatorics, graph theory, probability theory, and number theory in the study of computability, computational complexity, and some of the real-world applications of computational concepts.
- State and explain the important and well-known open problems in the theory of computation.
- Write clearly presented proofs that meet rigorous standards of correctness and conventional guidelines on style.
- Identify and critique proofs that are logically flawed and/or do not meet the expected standards of clarity.
- Cooperate with other people in order to solve challenging and rigorous problems related to the study of computer science.

Note that even though all of the topics we discuss in the course have real-world applications, often we will not be explicitly discussing the applications. This is because initially it is better to separate concerns regarding real-world applications from the exploration of fundamental truths and knowledge that shape how we view and understand the world. The quest for truth and understanding, wherever it takes us, eventually do produce applications, some that we hoped to achieve, and some that were beyond our wildest dreams. The focus of the course is on that quest for truth and understanding, which is arguably more important than specific applications. The formal prerequisites for the course are (15-122 or 15-150) and (21-127 or 21-128 or 15-151). In particular, we expect the students to have taken an introductory computer science course that goes beyond basic computer programming and covers algorithmic thinking. On the mathematics side, we expect the students to have experience reasoning abstractly and know how to write formal proofs. 

15-251 Great Ideas in Theoretical Computer Science

Theoretical Computer Science