Technopark algorithms
Реализация различных алгоритмов на С / С++ для первого семестра Технопарка.
- Алгоритм Дейкстры для разреженных графов(задача поиска кратчайшего расстояния между городами).
- Вычисление всех возможных кратчайших путей в неорентированном графе.
- 4 разных реализации хранения графов(условие задания):
- ListGraph, хранящий граф в виде массива списков смежности,
- MatrixGraph, хранящий граф в виде матрицы смежности,
- SetGraph, хранящий граф в виде массива хэш-таблиц/сбалансированных деревьев поиска,
- ArcGraph, хранящий граф в виде одного массива пар {from, to}.
- Самобалансирующееся АВЛ-дерево. Реализация + решение задачи про распределению солдат по росту
- Декартово дерево.
- Обход бинарного дерева поиска в порядке in-order без рекурсии.
- Хеш-таблица с открытой адресацией и разрешением коллизий методом квадратичного пробирования. Вычисление хеша методом Горнера.
- Реализация сортировки слиянием. Решение задачи на кол-во показов рекламы клиенту.
- Алгоритм поиска k-й порядковой статистики (числа которое бы стояло на позиции с индексом k в отсортированном массиве). Поиск медианы и перцентили.
- Слиянеие K отсортированных массивов при помощи кучи.(Heap merge)
- Реализация очереди на двух стеках.
- Реализация дека на зацикленном динамическом буффере.
- Нахождение пересечения двух массивов неповторяющихся целых чисел, упорядоченных по возрастанию.
- Бинарный и экспоненциальный поиск. Найти границу после которой массив строго убывает за log(m).
- Работа с битовым сдвигом. Проверка по маске