Courses / DescriptionsEECS 212: Mathematical Foundations of Computer Science
Quarter OfferedFall : 3-3:50 MWF ; Vijayaraghavan
Winter : 11-11:50 MWF ; Kao
Prerequisites(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.
- Fall Section: 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
COURSE INSTRUCTORS: Prof. (Fall), (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: - 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