CS 103: Mathematical Foundations of Computing
What are the theoretical limits of computing power? What problems can be solved with computers? Which ones cannot? And how can we reason about the answers to these questions with mathematical certainty? This course explores the answers to these questions and serves as an introduction to discrete mathematics, computability theory, and complexity theory. At the completion of the course, students will feel comfortable writing mathematical proofs, reasoning about discrete structures, reading and writing statements in firstorder logic, and working with mathematical models of computing devices. Throughout the course, students will gain exposure to some of the most exciting mathematical and philosophical ideas of the late nineteenth and twentieth centuries. Specific topics covered include formal mathematical proofwriting, propositional and firstorder logic, set theory, binary relations, functions (injections, surjections, and bijections), cardinality, basic graph theory, the pigeonhole prin
more »
What are the theoretical limits of computing power? What problems can be solved with computers? Which ones cannot? And how can we reason about the answers to these questions with mathematical certainty? This course explores the answers to these questions and serves as an introduction to discrete mathematics, computability theory, and complexity theory. At the completion of the course, students will feel comfortable writing mathematical proofs, reasoning about discrete structures, reading and writing statements in firstorder logic, and working with mathematical models of computing devices. Throughout the course, students will gain exposure to some of the most exciting mathematical and philosophical ideas of the late nineteenth and twentieth centuries. Specific topics covered include formal mathematical proofwriting, propositional and firstorder logic, set theory, binary relations, functions (injections, surjections, and bijections), cardinality, basic graph theory, the pigeonhole principle, mathematical induction, finite automata, regular expressions, the MyhillNerode theorem, contextfree grammars, Turing machines, decidable and recognizable languages, selfreference and undecidability, verifiers, and the P versus NP question. Students with significant proofwriting experience are encouraged to instead take
CS154. Students interested in extra practice and support with the course are encouraged to concurrently enroll in
CS103A. Prerequisite: CS106B or equivalent. CS106B may be taken concurrently with
CS103.
Terms: Aut, Win, Spr

Units: 35

UG Reqs: GER:DBMath, WAYFR

Grading: Letter or Credit/No Credit
Instructors:
Lee, C. (PI)
;
Schwarz, K. (PI)
CS 154: Introduction to Automata and Complexity Theory
This course provides a mathematical introduction to the following questions: What is computation? Given a computational model, what problems can we hope to solve in principle with this model? Besides those solvable in principle, what problems can we hope to efficiently solve? In many cases we can give completely rigorous answers; in other cases, these questions have become major open problems in computer science and mathematics. By the end of this course, students will be able to classify computational problems in terms of their computational complexity (Is the problem regular? Not regular? Decidable? Recognizable? Neither? Solvable in P? NPcomplete? PSPACEcomplete?, etc.). Students will gain a deeper appreciation for some of the fundamental issues in computing that are independent of trends of technology, such as the ChurchTuring Thesis and the P versus NP problem. Prerequisites:
CS 103 or 103B.
Terms: Aut

Units: 34

UG Reqs: GER:DBEngrAppSci

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