Python examples

This repository contains some material from different computer science topics in a form of jupyter notebooks. The core feature of the presentation from is vast use of automatically generated animated examples.

Text animations

Here's an example of quicksort algorithm using text state representation

Matplotlib animations

Using matplotlib one can visualize some plane algorithm, for example EM algorithm for Old Faithfull eruption data

or domino coloring based on 5-coloring algorithm for planar graphs

or convex hull construction

Graphviz

Using graphviz one can visualize basic graph algorithms, here's an example of Dijkstra algorithm

Requirements and installation

A proper installation on debian-based systems is

cat apt.txt | xargs sudo apt-get install
pip install -r requirements.txt

For other linux-based OS use the appropriate package manager to install packages listed in apt.txt which currently contains graphviz and latex needed for proper visualization in notebooks. Note that there also might be problems with ipywidgets in jupyter lab, check the docs for installation instructions.

Table of content

Eng

Linear programming

Introduction to linear programming, simplex method and interior point method. Some animations are presented in this notebook including ellipsoid method.

Gradient descent with momentum

Compararison between different gradient momentum methods for a basic quadratic function. Currently code and animations only.

Paths on rectangles (junk)

Some exdamples of probability walk on rectangular grid.

Covid-19

Some basic parse and analysis of global Covid-19 data from Johns Hopkins University.

Rus

Замощене доминошками

Рассматривается задача покрытия фигур на плоскости, состоящиех из квадратных клеток одинакового размера и два её программных решения: с помощью динамического программирования по профилю и с помощью нахождения максимального паросочетания. Бонусом идет раскраска планарного графа в 5 цветов (не протестировано).

Обходы на графх

Разобраны обходы в глубину и ширину, а так же их базовые применения.

Кратчайшие пути на графах

Основные алгоритмы для задачи о крайших путях от одной вершины до всех остальных. Все алгоритмы представлены как модификации "сканирующего метода".

Префиксное дерево

Префиксное дерево, префикс-функцию, алгоритм Ахо-Корасик и их применения в марковских моделях для обработки текста.