Discrete Mathematics and Algorithms

Catalog description

Introduction to theoretical foundations of discrete mathematics and algorithms. Emphasis on providing mathematical tools for combinatorial optimization, i.e. how to efficiently optimize over large finite sets and reason about the complexity of such problems. Topics include: graph theory, minimum cut, minimum spanning trees, matroids, maximum flow, non-bipartite matching, NP-hardness, approximation algorithms, spectral graph theory, and Laplacian systems. Prerequisites: CS 161 is highly recommended, although not required.