Algebra is one of the definitive and oldest branches of mathematics, and design of computer algorithms is one of the youngest. Despite this generation gap, the two disciplines beautifully interweave. Firstly, modern computers would be somewhat useless if they were not able to carry out arithmetic and algebraic computations efficiently, so we need to think on dedicated, sometimes rather sophisticated algorithms for these operations. Secondly, algebraic structures and theorems can help develop algorithms for things having [at first glance] nothing to do with algebra, e.g. graph algorithms. One of the main goals of the offered course is thus providing the learners with the examples of the above mentioned situations. We believe the course to contain much material of interest to both CS and Math oriented students. The course is supported by programming assignments.

Offered By

## Algebra & Algorithms

Moscow Institute of Physics and Technology## About this Course

Basic algorithms, Linear and common algebra, elementary discrete mathematics and probability.

All coding assignments require Python 3.

### What you will learn

Efficiently doing arithmetics on binary numbers as well as algebraic operations like polynomial multiplication, matrix multiplication and inversion.

Design efficient algorithms problems in graph theory related to distances and matchings based on fast matrix computations and randomization.

### Skills you will gain

Basic algorithms, Linear and common algebra, elementary discrete mathematics and probability.

All coding assignments require Python 3.

### Offered by

#### Moscow Institute of Physics and Technology

Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира. Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой.

## Syllabus - What you will learn from this course

**8 hours to complete**

## 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.

**8 hours to complete**

**10 videos**

**2 readings**

**4 hours to complete**

## 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.

**4 hours to complete**

**6 videos**

**1 reading**

**7 hours to complete**

## 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.

**7 hours to complete**

**7 videos**

**1 reading**

**1 hour to complete**

## 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.

**1 hour to complete**

**6 videos**

**1 reading**

## Frequently Asked Questions

When will I have access to the lectures and assignments?

What will I get if I purchase the Certificate?

Is financial aid available?

Will I earn university credit for completing the Course?

More questions? Visit the Learner Help Center.