Introduction to Algorithms, Computability, and Complexity

Looking at the world around us, we see computers solving problems on incredibly large scales: finding webpages relevant to our internet searches and returning them in sorted order, computing the quickest way to reach a destination given current traffic conditions, and matching people on dating sites. How is this possible? More computing power? Intensive application-specific engineering? While these certainly have had a role to play, in this course, students are exposed to and learn how to use general algorithm design principles that cut across application domains and remain relevant even as computing technology changes. First among these principles is mathematical abstraction, whereby we capture the essence of a computational problem (as well as the notion of what a computer is) so that we can develop and analyze solutions independent of an implementation. Given these mathematical abstractions, we can apply a toolkit of basic algorithmic techniques in the search for solutions and then gain certainty in their correctness and efficiency through rigorous mathematical proofs. Furthermore, the powerful concept of reductions allows us to identify relationships between computational problems that seem very different on the surface and thus automatically transfer solutions from one to another. At the same time, some important computational problems have defied the search for algorithmic solutions. Computer scientists would love to have debugging tools that determine whether their programs can crash, natural scientists would love to have simulators that quickly determine the energy-minimizing states of physical or biological systems, and university registrars would love to be able to automatically schedule classes in a way that optimally maximizes the use of the best classrooms. Why have no scalable algorithms been found for these problems? In the last part of the course, students learn that many important computational problems are inherently unsolvable—they have no general algorithmic solution whatsoever. Others are solvable, but have no efficient algorithm—the minimum computation time inherently grows exponentially with the size of the problem instance. Uncovering these phenomena (known as uncomputability and intractability, respectively) are unique benefits of a mathematically rigorous approach to algorithms. While we may sometimes be satisfied with empirical demonstrations of the performance of an algorithm we have found, a proof seems to be the only way to convince ourselves that there is no algorithm whatsoever. This course aims to give students the power of using mathematical abstraction and rigorous proof to understand computation. Thus equipped, students are able to design and use algorithms that apply to a wide variety of computational problems with confidence about their correctness and efficiency, as well as recognize when a problem may have no algorithmic solution. At the same time, students may gain an appreciation for the beautiful mathematical theory of computation that is independent of (indeed, predates) the technology on which it is implemented.