About this Course

7,670 recent views
Shareable Certificate
Earn a Certificate upon completion
100% online
Start instantly and learn at your own schedule.
Flexible deadlines
Reset deadlines in accordance to your schedule.
Intermediate Level

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

All coding assignments require Python 3.

Approx. 30 hours to complete
English

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

Matrix MultiplicationGraph AlgorithmsComputational ModelAlgorithm DesignBoolean Algebra
Shareable Certificate
Earn a Certificate upon completion
100% online
Start instantly and learn at your own schedule.
Flexible deadlines
Reset deadlines in accordance to your schedule.
Intermediate Level

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

All coding assignments require Python 3.

Approx. 30 hours to complete
English

Offered by

Placeholder

Moscow Institute of Physics and Technology

Syllabus - What you will learn from this course

Week
1

Week 1

8 hours to complete

Arithmetics in the Realm of Circuits

8 hours to complete
10 videos (Total 122 min), 2 readings, 2 quizzes
10 videos
Welcome to the Course3m
Definition of Boolean circuits17m
Circuit implementation of (Naïve) Integer Addition19m
Parallel “Product” Prefix computation10m
Applying Parallel Prefix to improve Adder depth17m
Circuit for Subtraction of Integers13m
Circuit for Integer Multiplication18m
Circuit for Integer Division13m
Circuit for Integer Division (continued)7m
2 readings
Soft and Hard Prerequisites for the Course10m
Module Prerequisites10m
Week
2

Week 2

4 hours to complete

Boolean Circuits for Arbitrary Functions

4 hours to complete
6 videos (Total 67 min), 1 reading, 1 quiz
6 videos
Lower bound on the circuit size (continued)15m
Circuits for arbitrary functions: Ingredient 1 — Shannon Expansion11m
Circuits for arbitrary functions: Ingredient 2 — Decoder11m
Circuits for arbitrary functions: Ingredient 3 — Universal Multipole9m
Circuits for arbitrary functions: Conclusion6m
1 reading
Module Prerequisites10m
Week
3

Week 3

7 hours to complete

More on Multiplication of Integers and Polynomials

7 hours to complete
7 videos (Total 74 min), 1 reading, 2 quizzes
7 videos
Strassen’s matrix multiplication algorithm9m
Toom’s algorithm11m
Toom’s algorithm (continued)9m
Fast Fourier Transform: efficient polynomial evaluation and interpolation11m
Fast Fourier Transform (continued)11m
Fast Fourier Transform (conclusion)8m
1 reading
Module Prerequisites10m
Week
4

Week 4

1 hour to complete

Graph Reachability and Distances via Matrix Multiplication

1 hour to complete
6 videos (Total 51 min), 1 reading
6 videos
Computing Transitive Closure of a Graph13m
Computing Distances: Seidel’s algorithm9m
Seidel’s algorithm (continued)7m
Boolean Matrix Product: Four Russians Speedup Trick7m
Four Russians Speedup Trick (continued)8m
1 reading
Module Prerequisites10m

Frequently Asked Questions

More questions? Visit the Learner Help Center.