# Courses  /  DescriptionsCOMP_SCI 212: Mathematical Foundations of Computer Science

### Quarter Offered

Fall : 3-3:50 MWF ; Vijayaraghavan
Spring : 3-3:50 MWF ; Staff
Winter : 4-4:50 MWF ; Staff

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

COURSE INSTRUCTORS: TBA (Winter), Prof. Aravindan Vijayaraghavan (Fall & 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

GRADES: Varies by instructor