jejikeh / data_structures

Задачи курса Stepic "Алгоритмы: теория и практика. Структуры данных"

data_structures

Задачи курса Stepic "Алгоритмы: теория и практика. Структуры данных"

1. Базовые структуры данных.
   • Скобки в коде. Проверить, правильно ли расставлены скобки в данном коде.
   • Высота дерева. Вычислить высоту данного дерева.
   • Обработка сетевых пакетов. Реализовать обработчик сетевых пакетов.
   • Стек с поддержкой максимума. Реализовать стек с поддержкой операций push, pop и max
   • Максимум в скользящем окне. Найти максимум в каждом окне размера m данного массива чисел A[1 . . . n].
2. Очереди с приоритетом. Системы непересекающихся множеств.
   • Построение кучи. Переставить элементы заданного массива чисел так, чтобы он удовлетворял свойству мин-кучи.
   • Параллельная обработка. По данным n процессорам и m задач определите, для каждой из задач, каким процессором она будет обработана.
   • Объединение таблиц. Ваша цель в данной задаче — реализовать симуляцию объединения таблиц в базе данных.
   • Автоматический анализ программ. Система равенств и неравенств Проверить, можно ли присвоить переменным целые значения, чтобы выполнить заданные равенства вида xi = xj и неравенства вида xp != xq.
3. Хеш-таблицы.
   • Телефонная книга. Реализовать структуру данных, эффективно обрабатывающую запросы вида add number name, del number и find number.
   • Хеширование цепочками. Ваша цель в данной задаче — реализовать схему хеширования цепочками, используя таблицу с m ячейками и полиномиальной хеш-функцией.
   • Поиск образца в тексте. Найти все вхождения строки Pattern в строку Text.Реализуйте алгоритм Карпа–Рабина.
4. Деревья поиска.
   • Обход двоичного дерева. Построить in-order, pre-order и post-order обходы данного двоичного дерева.
   • Проверка свойства дерева поиска. Проверить, является ли данное двоичное дерево деревом поиска.
   • Проверка более общего свойства дерева поиска.
   • Множество с запросами суммы на отрезке. Реализуйте структуру данных для хранения множества целых чисел, поддерживающую запросы добавления, удаления, поиска, а также суммы на отрезке.