# Courses / DescriptionsEECS 212: Mathematical Foundations of Computer Science

### Quarter Offered

Fall : 3-3:50 MWF ; VijayaraghavanWinter : 11-11:50 MWF ; Kao

### Prerequisites

EECS 110 or EECS 111, and MATH 230### Description

**CATALOG 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.

- (Formerly EECS 310)
*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.

**RECCOMENDED TEXTS:**

Mathematics for Computer Science by Lehman, Leighton, and Meyer (e-book: http://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. Aravindan Vijayaraghavan** (Fall), **Ming-Yang Kao** (Winter)

**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: **EECS 110 or EECS 111, and MATH 230

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

Part I: Logic, Proofs, and Mathematical Preliminaries

1. Transform statements between English and formal logic, and manipulate logical expressions according to logical principles such as modus ponens, modus tollens, disjunctive syllogism, transposition, De Morgan’s Law, and existential and universal instantiation and generalization.

2. Apply sound logic to develop and prove theorems about mathematical phenomena.

3. Reason about the strengths and weaknesses of various proof techniques, including direct proof, proof by contradiction, proof by cases, and both strong and weak induction.

4. Understand the notation and properties of sets, including set builder notation, union, intersection, complement, difference, De Morgan’s Law, power set, and Cartesian product.

5. Understand the definition, notation, and properties of functions, including domain, range, one-to-one, onto, bijections, arithmetic, and composition.

Part II: Number Theory

1. Understand the notation and properties of modular arithmetic, and be able to solve basic congruences.

2. Understand the definition and properties of prime numbers as well as the Sieve of Eratosthenes.

3. Compute the Greatest Common Divisor of two values using the Euclidean algorithm.

4. Solve systems of linear congruences through the use of the Chinese Remainder Theorem.

5. Apply Fermat’s Little Theorem to solve problems involving modular arithmetic.

6. Encode and decode messages using the RSA cryptosystem.

Part III: Graph Theory

1. Reason about relations with certain properties, which may include relations that are reflexive, irreflexive, symmetric, anti-symmetric, or transitive.

2. Compute the closure of a given relation.

3. Solve problems that can be modeled as n-ary relations.

4. Reason about graphs with certain properties, which may include min or max degree, diameter, radius, partiteness, planarity, chromatic number, clique or independence number, or the number of vertices, edges, or connected components.

5. Prove whether or not two given graphs are isomorphic.

6. Solve problems that can be modeled by Euclidean or Hamiltonian walks or cycles.

7. Solve problems that can be modeled as a directed graph or DAG, which may include topological sorting, network flow, or strongly or weakly connected components.

8. Solve problems that can be modeled as rooted or unrooted trees.

9. Use Hall’s Theorem to solve problems that can be modeled by graph matching.

10. Apply the Mating Ritual to solve problems that can be modeled by stable matchings.

11. Prove whether or not a given graph is planar.

12. Prove that all planar graphs can be colored using no more than five colors.

Part IV: Combinatorics and Probability

1. Apply basic counting principles, including the addition, multiplication, division, and Pigeonhole principles, in order to count or reason about objects of a given description.

2. Produce closed-form expressions for linear and geometric sums and linear recurrences.

3. Use generating functions to produce closed-form expressions for nonlinear recurrences.

4. Apply the Inclusion-Exclusion principle to count objects that can be expressed as a union of sets.

5. Compute the probability of a given event that can be counted.

6. Utilize properties of probabilities, which may include combinations or sequences of events, complementary events, conditional probabilities, or Bayes Rule, to compute the probability of a given event.

7. Establish whether or not two events are conditionally independent.

8. Compute the expected value of a given random variable.

**HOMEWORK ASSIGNMENTS: **Varies by instructor

**LABORATORY PROJECTS:** None

**GRADES:** Varies by instructor