EECS 212: Mathematical Foundations of Computer Science

Quarter Offered

Fall : 3-3:50 MWF ; Vijayaraghavan
Winter : 11-11:50 MWF ; Kao


EECS 110 or EECS 111, and MATH 230


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


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


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.


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


GRADES: Varies by instructor