A Post tag system simulating the Collatz 3x+1 function.

Description Fall 2017

In a nutshell, the main idea behind this course is that the discovery of the digital computer, together with the theory of computation, is 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 include: iteration, orbits and fixed points; order and equivalence relations; actions and enumeration; finite state machines and transducers; finite fields, shift register sequences and pseudo-random numbers; propositional logic and satisfiability testing; first-order logic; theorem provers.

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. A few pictures can be found here: CDM Gallery (challenge: figure out what these pictures mean, for as many as you can manage). A rather dated paper outlining the course philosophy can be found at Jeric.


  • Instructor: Klaus Sutner

    sutner AT cs DOT cmu DOT edu
    Office hours: Tuesday 4:30-5:30

  • TA: Barry Li

    barryl AT andrew DOT cmu DOT edu
    Office hours: Wednesday 13:00-14:00

  • TA: Runtian

    runtianz AT andrew DOT cmu DOT edu
    Office hours: Monday 3:30-4:30