2016-2017 2017-2018 2018-2019 2019-2020 2020-2021
 Browseby subject... Scheduleview...

# 1 - 3 of 3 results for: CS154

## 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 first-order 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 first-order 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 first-order 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 first-order logic, set theory, binary relations, functions (injections, surjections, and bijections), cardinality, basic graph theory, the pigeonhole principle, mathematical induction, finite automata, regular expressions, the Myhill-Nerode theorem, context-free grammars, Turing machines, decidable and recognizable languages, self-reference 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, Sum | Units: 3-5 | UG Reqs: GER:DB-Math, WAY-FR

## CS 154:Introduction to the Theory of Computation

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? NP-complete? PSPACE-complete?, 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 Church-Turing Thesis and the P versus NP problem. Prerequisites: CS 103 or 103B.
Terms: Aut | Units: 3-4 | UG Reqs: GER:DB-EngrAppSci

## CS 163:The Practice of Theory Research

(Previously numbered CS 353). Introduction to research in the Theory of Computing, with an emphasis on research methods (the practice of research), rather than on any particular body of knowledge. The students will participate in a highly structured research project: starting from reading research papers from a critical point of view and conducting bibliography searches, through suggesting new research directions, identifying relevant technical areas, and finally producing and communicating new insights. The course will accompany the projects with basic insights on the main ingredients of research. Research experience is not required, but basic theory knowledge and mathematical maturity are expected. The target participants are advanced undergrads as well as MS students with interest in CS theory. Prerequisites: CS161 and CS154. Limited class size.
Terms: Win | Units: 3 | UG Reqs: WAY-SMA
Filter Results:
term offered
 Autumn Winter Spring Summer
updating results...
teaching presence
 in person remote: asynchronous remote: synchronous independent studies
updating results...
number of units
 1 unit 2 units 3 units 4 units 5 units >5 units
updating results...
time offered
 early morning (before 10am) morning (10am-12pm) lunchtime (12pm-2pm) afternoon (2pm-5pm) evening (after 5pm)
updating results...
days
 Monday Tuesday Wednesday Thursday Friday Saturday Sunday
updating results...
UG Requirements (GERs)
 WAY-A-II WAY-AQR WAY-CE WAY-ED WAY-ER WAY-FR WAY-SI WAY-SMA Language Writing 1 Writing 2 Writing SLE DB:Hum DB:Math DB:SocSci DB:EngrAppSci DB:NatSci EC:EthicReas EC:GlobalCom EC:AmerCul EC:Gender IHUM1 IHUM2 IHUM3
updating results...
component
 Lecture (LEC) Seminar (SEM) Discussion Section (DIS) Laboratory (LAB) Lab Section (LBS) Activity (ACT) Case Study (CAS) Colloquium (COL) Workshop (WKS) Independent Study (INS) Intro Dial, Sophomore (IDS) Intro Sem, Freshman (ISF) Intro Sem, Sophomore (ISS) Internship (ITR) Arts Intensive Program (API) Language (LNG) Clerkship (CLK) Practicum (PRA) Practicum (PRC) Research (RES) Sophomore College (SCS) Thesis/Dissertation (T/D)
updating results...
career