Skip to content
Algebra & Algorithms
- Arithmetics in the Realm of Circuits
- In this module we will study a mathematical model of hardware: the Boolean circuits. They provide the birds eye view of how one builds a complex logical circuit from elementary building blocks by linking them with wires. We will learn efficient ways to construct circuits for all four arithmetic operations on integers represented in binary form. Among other things we will see how to efficiently calculate all carries while adding two numbers (much faster than just computing these carries sequentially) and how Newton’s approximation method for solving equations helps with implementing integer division.
- Boolean Circuits for Arbitrary Functions
- In this second and last module devoted to Boolean circuits we move from arithmetics to the problem of constructing efficient circuits for arbitrary Boolean functions. On the way, among other things, we will see how to estimate the number of trees via DFS traversals and how to construct efficiently a circuit that computes all functions of given small number of variables.
- More on Multiplication of Integers and Polynomials
- Multiplication of integers is among the first things people learn to do with integers at school, later moving on to higher spheres: multiplying matrices, polynomials, permutations etc. Multiplication is one of the central things in algebra. This week we focus on classical algorithms for efficient integer multiplication first, and then move on to matrix and polynomial multiplication. On the way we will see how closely integer and polynomial multiplication are really intertwined and what polynomial interpolation has to do with multiplication.
- Graph Reachability and Distances via Matrix Multiplication
- This module is the first one to feature application pf efficient algorithms for algebraic operations to something outside algebra. Currently we turn to distances in graphs. We also study a non-typical way of multiplying matrices motivated by applications to graph reachibiilty, namely, Boolean matrix multiplication, and consider a corresponding rather general speedup technique.
- More on Matrix Computations
- This week we first learn how to compute determinant and invert a matrix on a parallel computer, and how working with seemingly “computationally inconvenient” infinite series helps deriving quite a efficient formulas for the determinant. The second part of this module is devoted to a more common single-threaded computational model and there we prove that essentially the complexity of inverting a matrix is the same as that of matrix multiplication.
- Matchings in Graphs via Matrix Determinants
- In the last module of the course we learn some tools for efficient use of randomization and algebra in algorithm design and use our knowledge about the existence of fast algorithms for parallel determinant computation to find perfect matchings in bipartite graphs unbelievably quickly on parallel computers.