# Academics / Courses / DescriptionsCOMP_SCI 212: Mathematical Foundations of Computer Science

### Quarter Offered

Fall : 3-3:50 MWF ; VijayaraghavanSpring : 3-3:50 MWF ; Rao

Winter : 4-4:50 MWF ; Rao

### Prerequisites

(COMP_SCI 110 or COMP_SCI 111) and Math 228-1 or 230-1 (formerly Math 230)### Description

This course will discuss fundamental concepts and tools in discrete mathematics with emphasis on their applications to computer science. Example topics include logic and Boolean circuits; sets, functions, relations, databases, and finite automata; deterministic algorithms and randomized algorithms; analysis techniques based on counting methods and recurrence equations; trees and more general graphs.

*This course is a required Core course in the CS curriculum in McCormick and Weinberg*

**REQUIRED TEXTS:**

**Fall Section:**No text**Winter Section:**Discrete Mathematics and Its Applications, Kenneth Rosen, 7th ed.

**RECOMMENDED TEXTS:**

Mathematics for Computer Science by Lehman, Leighton, and Meyer (e-book: https://www.seas.harvard.edu/courses/cs20/MIT6_042Notes.pdf)**Fall Section:**Discrete Mathematics and Its Applications by Kenneth Rosen, 7th edition**Fall Section:**

**COURSE INSTRUCTORS:** **Prof. Shravas Rao** **(Winter & Spring)**, **Prof. Aravindan Vijayaraghavan** **(Fall)**

**COURSE COORDINATOR:** Prof. Aravindan Vijayaraghavan

**COURSE OBJECTIVES: **In this course, students should develop mathematical thinking and problem-solving skills associated with writing proofs. Students should also be exposed to a wide variety of mathematical concepts that are used in the Computer Science discipline, which may include concepts drawn from the areas of Number Theory, Graph Theory, Combinatorics, and Probability.

**PREREQUISITES: - Must combine one of the following -**

**DETAILED COURSE TOPICS:** All sections will deal with topics from Part I (Proofs and Mathematical Preliminaries), as well as a selection of topics from Parts II-IV.

Part I: Proofs, and Mathematical Preliminaries

- Introduction to Logic, Proofs.
- Principle of Mathematical Induction, Strong Induction.

Part II: Counting, Combinatorics, Probability

- Counting, Mapping, Functions, Bijection, Inclusion-Exclusion formula.
- Pigeonhole principle, Generalized Pigeonhole.
- Permutations and Combinations. Picking with repetition, without repetition.
- Binomial formula, Pascal Triangle, Generating functions.
- Introduction to Probability: Random Events, Conditional Probabilities, Independence, Bayes Rule.
- Expectation, Linearity of Expectation, Variance of random variables.
- Markov's inequality. Chebychev inequality, Union bound.
- Sums of random variables, Concentration of measure, Statistical significance.

Part III: Graph Theory

- Introduction to graphs, Properties of graphs.
- Connectivity, Connected components, Distances.
- Trees, Cycles, Spanning Trees.
- Planarity, Graph Coloring, Bipartite graphs.
- Matchings, Hall's theorem, Stable marriage.
- Linear Algebra: Adjacency matrix, Edge-vertex matrix. Relating graph properties. Eigenvalues, Eigenvectors.
- Independent set, Vertex cover, Network Flows, Cuts.
- Linear Programming, Duality.

Part IV: Number Theory & Miscellaneous

- Prime numbers, Divisibility, GCD algorithm.
- Modular arithmetic. Prime numbers. Fundamental theorem of arithmetic.
- Cryptography, Computational Complexity.
- Turing Machines, Reductions, NP-hardness.

**HOMEWORK ASSIGNMENTS: **Varies by instructor

**LABORATORY PROJECTS:** None

**GRADES:** Varies by instructor