CS 62N: Let There Be Computations
The class will discuss the Theory of Computing as an ambitious intellectual endeavor with impact beyond Computer Science. What are computations? How can their study capture important aspects of the evolution of species, the structure of social networks, and the working of your smart phone? What are the laws of efficiency and complexity that govern computations? We will see surprising algorithms for very familiar problems as well as simple problems no one knows how to solve efficiently. We will encounter logic paradoxes that expose the limitations of computations and explore the different worlds we may be living in, depending on the answers to some of the central problems on computations.n nThe class is intended for students with a wide range of interests. The course will not involve programming. While our class will not rely on any deep mathematics (beyond basic highschool math) we will deal with mathematical formalization of concepts and with mathematical problemsolving. Therefore, some mathematical maturity and interest would be useful.
Terms: Spr

Units: 3

Grading: Letter or Credit/No Credit
Instructors:
Reingold, O. (PI)
Filter Results: