EdusalsaDiscover Your Stanford

- Ryan Smith
- Amanda Spyropoulos
- Nathan Fotedar
- Samuel Reamer
- Bryce Cai
- Amy Liu
- Anastasiya Vitko
- David Varodayan
- Wenzheng Li
- Dahlia Radif
- John Melloni
- Anthony Galczak
- Cynthia Lee
- Karthik Srivatsan
- Fei Fang
- Qiwen Wang
- Jonathan Li
- Andrew Sharp
- Qile Zhi
- Jacqueline Yau
- Eric Chan
- Joshua Spayd
- Jessica Guo
- Anton de Leon
- Keith Schwarz
- Jonathan Li
- Reyna Hulett

- autumn
- winter
- spring
- summer
- 2019-2020

3 - 5 units

Letter or Credit/No Credit

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.

GER:DB-Math

WAY-FR

## LEC

Monday Wednesday Friday 3:00:00 PM - 4:20:00 PM @ NVIDIA Auditorium with Amanda Spyropoulos Jacqueline Yau Nathan Fotedar Eric Chan Fei Fang Ryan Smith John Melloni Joshua Spayd Jessica Guo Anthony Galczak Anton de Leon Keith Schwarz

May be taken for 3 units by graduate students. Meets in Gates B01 only on Fri, Oct 25.

## LEC

Monday Wednesday Friday 3:00:00 PM - 4:20:00 PM @ Hewlett Teaching Center 200 with Fei Fang Amanda Spyropoulos Anton de Leon Jonathan Li Reyna Hulett Anthony Galczak Andrew Sharp John Melloni Ryan Smith Cynthia Lee

May be taken for 3 units by graduate students.

## LEC

Monday Wednesday Friday 3:00:00 PM - 4:20:00 PM @ NVIDIA Auditorium with Amanda Spyropoulos Nathan Fotedar Samuel Reamer Bryce Cai Amy Liu Anastasiya Vitko David Varodayan Wenzheng Li Dahlia Radif John Melloni Anthony Galczak Cynthia Lee Karthik Srivatsan Fei Fang Qiwen Wang Jonathan Li Andrew Sharp Qile Zhi

May be taken for 3 units by graduate students.

## LEC

Monday Wednesday Friday 9:30:00 AM - 11:20:00 AM with Ryan Smith

This is a 5 unit course. Matriculated Stanford graduate students are allowed to enroll in it for 3, 4 or 5 units but must still do the standard 5 units of coursework.

Already Have An Account? Log In

**Pranav Rajpurkar** is a PhD student in Computer Science at Stanford, working on Artificial Intelligence for Healthcare. He was previously a Stanford undergrad ('16).

**Brad Girardeau** got his B.S, M.S. degrees in computer science at Stanford ('16, '17). When not thinking about computer security, he can be found playing violin or running across the Golden Gate Bridge.

## Discussion

## To ask a question about a course and to share your perspective, signup or login