## 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
| Units: 3-5
| UG Reqs: GER:DB-Math, WAY-FR

Instructors:
Lee, C. (PI)
;
Schwarz, K. (PI)

## CS 103A: Mathematical Problem-solving Strategies

Problem solving strategies and techniques in discrete mathematics and computer science. Additional problem solving practice for
CS103. In-class participation required. Prerequisite: consent of instructor. Co-requisite:
CS103.

Terms: Aut, Win
| Units: 1

Instructors:
Lee, C. (PI)
;
Liu, A. (PI)

## CS 124: From Languages to Information (LINGUIST 180, LINGUIST 280)

Extracting meaning, information, and structure from human language text, speech, web pages, social networks. Introducing methods (string algorithms, edit distance, language modeling, machine learning classifiers, neural embeddings, inverted indices, collaborative filtering, PageRank), applications (chatbots, sentiment analysis, information retrieval, question answering, text classification, social networks, recommender systems), and ethical issues in both. Prerequisites:
CS103,
CS107,
CS109.

Terms: Win
| Units: 3-4
| UG Reqs: WAY-AQR

Instructors:
Jurafsky, D. (PI)

## LINGUIST 180: From Languages to Information (CS 124, LINGUIST 280)

Extracting meaning, information, and structure from human language text, speech, web pages, social networks. Introducing methods (string algorithms, edit distance, language modeling, machine learning classifiers, neural embeddings, inverted indices, collaborative filtering, PageRank), applications (chatbots, sentiment analysis, information retrieval, question answering, text classification, social networks, recommender systems), and ethical issues in both. Prerequisites:
CS103,
CS107,
CS109.

Terms: Win
| Units: 3-4
| UG Reqs: WAY-AQR

Instructors:
Jurafsky, D. (PI)

## LINGUIST 280: From Languages to Information (CS 124, LINGUIST 180)

Extracting meaning, information, and structure from human language text, speech, web pages, social networks. Introducing methods (string algorithms, edit distance, language modeling, machine learning classifiers, neural embeddings, inverted indices, collaborative filtering, PageRank), applications (chatbots, sentiment analysis, information retrieval, question answering, text classification, social networks, recommender systems), and ethical issues in both. Prerequisites:
CS103,
CS107,
CS109.

Terms: Win
| Units: 3-4

Instructors:
Jurafsky, D. (PI)

Filter Results: