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

### Quarter Offered

Fall : 3-3:50 MWF ; Rao
Winter : 4-4:50 MWF ; Golub
Spring : 3-3:50 MWF ; Rao
Spring : 2:00-3:20 TuTh ; Wang

### 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

RECOMMENDED TEXTS:

COURSE INSTRUCTORS: Prof. Shravas Rao (Fall & Spring), Prof. Benjamin Golub (Winter), Xiao Wang (Honors CS 212, Spring)

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

1. Introduction to Logic, Proofs.
2. Principle of Mathematical Induction, Strong Induction.

Part II: Counting, Combinatorics, Probability

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

Part III: Graph Theory

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

Part IV: Number Theory & Miscellaneous

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

HOMEWORK ASSIGNMENTS: Varies by instructor

LABORATORY PROJECTS: None