Decidability

Register Machines

Iteration 

Closure

Zero Space

Minimization

First-order logic

Logic

Infinite Words

Groups

Polya Counting

Feedback Shift Registers

Coding Theory

Effective Resistance

Hypercomputation

Nondeterminism

Computation & Discrete Math

Primitive Recursion

Orbits

Automata

Determinization

Finite Fields

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

Mathematical Foundations

Strings and encodings

Deterministic finite automaton (DFA)

Turing Machines

Church-Turing Thesis

Universality

Stable Matching

Randomness

Cryptography

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

Decidability (logic)

Decidability

2 courses cover this concept

15-354 Computation & Discrete Math

15-251 Great Ideas in Theoretical Computer Science