This website contains some of the course material for CS251 (15-251) “Great Ideas in Theoretical Computer Science” at Carnegie Mellon University.

There are two main parts to the content: the lectures and the textbook. The purpose of the textbook is to complement the lectures, so the textbook does not contain full explanations of all the material covered in lectures. In particular, the intuition and motivation behind many concepts and proofs are explained in lectures and not necessarily in the textbook. We view lectures as content consumed once or twice, and the textbook as content that you refer back to many times. So the design of the textbook is motivated by trying to make it a more efficient tool for referencing.

The textbook has an Overview page, which gives an outline for the whole book. Using the provided filters, one can see, say, all the definitions in the book, or all the statements (theorems, lemmas, corollaries, …), or all the exercises.

At CMU, there are two main prerequisites for this course.

• An introductory computer science course that goes beyond basic programming. In particular, we expect students to know the big-O notation and its formal definition, basic graph algorithms like breadth-first search and depth-first search, basic data structures like binary trees, and so on.

• An introductory discrete mathematics course that teaches how to write proofs.

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 students’ logical, analytic and abstract thinking skills as these are crucial for forming deep conceptual understandings, creating new knowledge, and pushing the boundaries of science and technology.

Second, the course intends to help prepare students 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 students will learn from their examples and find inspiration from them.

Third, the course gives students opportunities to improve their social skills by emphasizing cooperation, clarity of thought, and clarity in the expression of thought.

More specifically, some of the 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 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 others in order to solve problems related to the study of computer science.

Even though all 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 course was created by Steven Rudich in 1999. Here is the webpage of an early version. Not surprisingly, the course has evolved and changed quite a bit since then. The current version, as well as this website, is designed and maintained by me, Anıl Ada.

Over the years, many instructors have made invaluable contributions to the course: Victor Adamchik, Luis von Ahn, Anupam Gupta, Venkatesan Guruswami, Vipul Goyal, Bernhard Haeupler, John Lafferty, Ryan O’Donnell, Ariel Procaccia, Daniel Sleator and Klaus Sutner. I would like to single out Ryan because his fingerprints can be found in many parts of the course. Over the years, we’ve had countless hours of discussions about 251. Some of my lectures are based on his lectures, and he has contributed some of my favorite problems.

Special thanks go to the amazing teaching assistants of the course (many are listed in the course staff page). They have been, and continue to be, an integral part of the course. They have helped improve the course and the material presented here in many ways.

Finally, many thanks to the students (too many to name) for sending valuable comments and corrections on earlier drafts. All of this is for them.