Mathematics-Discrete (MAD)

Introduction to concepts of discrete mathematics, as used by computer scientists. Topics include symbolic logic and Boolean algebra, propositional and predicate calculus, sets, functions, and relations, enumeration and counting principles, introduction to graphs, trees, spanning trees, shortest path and matching algorithms, finite state automata, Turing machines.

An introduction to concepts of discrete mathematics and combinatorics, as used by computer scientists and mathematicians. Topics include: algorithms and complexity, counting principles, permutations and combinations; discrete probability, advanced enumeration techniques, generating functions, recurrence relations, and inclusion-exclusion, introduction to graphs, trees, spanning trees, shortest path and matching algorithms, finite state automata, Turing machines and Markov chains.

Introduction to the theory and applications of graphs. Topics include definitions and basic properties, Euler and Hamilton circuits and applications, connectivity, spanning trees and enumeration problems, cycle space and application to networks, matching algorithms and applications, shortest path problems, planar graphs and dual graphs, coloring problems and algorithms network flows, max flow-min cut theorem, Ramsey theory.

Introduction to basic concepts and methods of numerical approximation, with emphasis on error estimates and computer algorithms. Topics include numerical differentiation and integration, solution of initial value problems, interpolation and quadrature, numerical solution of algebraic and transcendental equations, systems of equations, finite differences, introduction to finite element methods.

Mathematical principles of the theory of computation and computer science. Topics include finite and infinite state machines, regular expressions and their recognition automata, pushdown automata, Turing machines, grammars and parsing, recursive functions, decidability and unsolvability, halting problem.

Basics of Combinatorial theory. Topics include enumerative methods, inclusion-exclusion principle, lattice theory, block designs, and related topics.

Implementation of numerical methods underlying modern data analysis techniques for solving large scale problems, with an emphasis on the use of scientific computing software. Topics include Jacobi and Gauss-Seidel iterations for solving linear systems of equations, Newton’s method and its variants for solving nonlinear systems, line-search and descent methods for nonlinear optimization, Gauss-Newton and Levenberg-Marquardt methods for solving least squares problems, and Runge-Kutta methods for ordinary differential equations as time permits.