Technopark algorithms

Реализация различных алгоритмов на С / С++ для первого семестра Технопарка.

Модуль 3

• Алгоритм Дейкстры для разреженных графов(задача поиска кратчайшего расстояния между городами).
• Вычисление всех возможных кратчайших путей в неорентированном графе.
• 4 разных реализации хранения графов(условие задания):
  • ListGraph, хранящий граф в виде массива списков смежности,
  • MatrixGraph, хранящий граф в виде матрицы смежности,
  • SetGraph, хранящий граф в виде массива хэш-таблиц/сбалансированных деревьев поиска,
  • ArcGraph, хранящий граф в виде одного массива пар {from, to}.

Модуль 2

• Самобалансирующееся АВЛ-дерево. Реализация + решение задачи про распределению солдат по росту
• Декартово дерево.
• Обход бинарного дерева поиска в порядке in-order без рекурсии.
• Хеш-таблица с открытой адресацией и разрешением коллизий методом квадратичного пробирования. Вычисление хеша методом Горнера.

Модуль 1

• Реализация сортировки слиянием. Решение задачи на кол-во показов рекламы клиенту.
• Алгоритм поиска k-й порядковой статистики (числа которое бы стояло на позиции с индексом k в отсортированном массиве). Поиск медианы и перцентили.
• Слиянеие K отсортированных массивов при помощи кучи.(Heap merge)
• Реализация очереди на двух стеках.
• Реализация дека на зацикленном динамическом буффере.
• Нахождение пересечения двух массивов неповторяющихся целых чисел, упорядоченных по возрастанию.
• Бинарный и экспоненциальный поиск. Найти границу после которой массив строго убывает за log(m).
• Работа с битовым сдвигом. Проверка по маске