Academics / Courses / DescriptionsCOMP_SCI 212: Mathematical Foundations of CS Part 1: Discrete mathematics for computer science
VIEW ALL COURSE TIMES AND SESSIONS
Prerequisites
COMP_SCI 110 or COMP_SCI 111Description
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:
- Fall & Winter Section: Mathematics for Computer Science by Lehman, Leighton, and Meyer (e-book: https://courses.csail.mit.edu/6.042/spring18/mcs.pdf)
COURSE INSTRUCTORS: Prof. Aravindan Vijayaraghavan or Prof. Miklos Racz or Anjali Agarwal
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: - COMP_SCI 110 or COMP_SCI 111
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