If you are visiting from outside Carnegie Mellon, please read the Visitor Letter.
If you are looking for last year's site, try here.
If you are enrolled in this course, go here.
You can find Lectures and Assignments on the Calendar.
This course will take a philosophical and historical perspective on the development of theoretical computer science. The technical material will be self contained, assuming no specific knowledge beyond high school algebra and high school programming.
From a pile of stones to represent and manipulate numbers, humans have progressively developed an abstract vocabulary with which to mathematically represent their world. The ancients, especially the Greeks, realized that they could consistently reason about their representations in a step by step manner. In other words, by computing in abstract models, they could describe and predict patterns in the world around them.
Starting with ancient algorithms for arithmetic, we will revisit the development of mathematics from a computational point of view. Conversely, we will mathematically study the nature of computation itself. What is computation? What is computable, in principle? What is especially easy, or especially hard to compute? To what extent does the inherent nature of computation shape how we learn and think about the world?
Topics will include: representations of number, induction, ancient and modern arithmetic, basic counting principles, probability, number theory, the idea of proof, formal proof, logic, problem solving methods, polynomial representations, automata theory, cryptography, infinity, diagonalization, computability, time complexity, incompleteness and undecidability, random walks, and Kolmogorov/Chaitin randomness.
Computer Science Dept.
Carnegie Mellon University
Baker Hall 136A
(Adamson Wing)
TR 3:00-4:20P