ADVANCED ALGORITHMS

MATH 718

Random solvers have been playing increasingly crucial roles in the modern computational tasks. The recent breakthroughs in applied and computational linear algebra that incorporate techniques of randomization have proven to be of great importance in modern applied math, computational sciences and data science, such as inverse problems, machine learning and scientific computing. The guiding principle is that one may greatly reduce computational and storage expenses at the cost of a small probability of failure. Systematic study of these modern methods of randomized linear algebra solvers will be provided, presenting mathematical backgrounds, algorithms, and concrete applications. Core theoretical topics include randomized Kaczmarz and its generalization to stochastic gradient descent, randomized singular value decomposition, random sketching, matrix completion, and compressive sensing, and corresponding applications.

COMPSCI 809

Techniques for quantitative analysis of algorithms. Charging arguments, amortization, probabilistic methods. Adversary and information lower bounds. Use of methods from combinatorics, complex analysis, and asymptotics in obtaining precise analyses of quicksort, chained hashing, and other algorithms. Students are strongly encouraged to have knowledge of algorithms (e.g.,COMP SCI 577) or applied math analysis (e.g.,MATH 321) and theory of probability (e.g.,MATH/​STAT  431).

COMPSCI/ISYE/MATH 728

Introduces optimization problems over integers, and surveys the theory behind the algorithms used in state-of-the-art methods for solving such problems. Special attention is given to the polyhedral formulations of these problems, and to their algebraic and geometric properties. Applicability of Integer Optimization is highlighted with applications in combinatorial optimization. Key topics include: formulations, relaxations, polyhedral theory, cutting planes, decomposition, enumeration. Students are strongly encouraged to have knowledge of Linear Programming (e.g.,MATH/​COMP SCI/​I SY E/​STAT  525), including algorithms, duality and polyhedral theory.

COMPSCI 577

Basic paradigms for the design and analysis of efficient algorithms: greed, divide-and-conquer, dynamic programming, reductions, and the use of randomness. Computational intractability including typical NP-complete problems and ways to deal with them.

COMPSCI 880

Advanced topics in algorithms, complexity, and cryptography. The exact topic varies.