Elementary cellular automaton 77 and its reversible Fredkin version.
In a nutshell, the main idea behind this course is that the development 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 (logic, relations, functions, 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 will include a selection from: iteration and fixed points; order and equivalence relations; transition systems; groups and actions; finite fields; randomness; SAT solvers; equational theorem proving; automata based decision algorithms.
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, mostly frivolous, pictures can be found here: CDM Gallery. Here is a 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.
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. Some background in algebra is also useful. Several of the homework assignments will require a bit of computation, so you need to be able to hack in at least one language. Python will do, but I will use the computer algebra system Mathematica as a workhorse throughout the course (Mathematica is freely available for all CMU students).