Алгоритмы и структуры данных

Здесь собраны решения всех лабораторных работ на направлении "Информационные системы и технологии" ФИТИП ИТМО

Советы по сдаче в PCMS2

C++ codestyle

Вердикты принимающей системы

Первый семестр

Лабораторная работа №1

Знакомство с проверяющей системой PCMS2.

1. a + b
2. a + b^2
3. Черепашка
4. Простая сортировка
5. Знакомство с жителями Сортленда

Лабораторная работа №2

Сортировка слиянием и быстрая сортировка.

1. Сортировка
2. Соревнования по бегу
3. Число инверсий
4. Анти-QuickSort
5. К-ая порядковая статистика

Лабораторная работа №3

Пирамидальная сортировка, цифровая сортировка.

1. Пирамида ли?
2. Пирамидальная сортировка
3. Цифровая сортировка
4. Приоритетная очередь

Лабораторная работа №4

Стек и очередь, двоичный поиск.

1. Стек
2. Очередь
3. Правильная скобочная последовательность
4. Постфиксная запись
5. Двоичный поиск
6. Гирлянда

Лабораторная работа №5

Двоичное дерево поиска. Интерпретатор языка Quack.

1. Высота дерева
2. Проверка корректности
3. Простое двоичное дерево поиска
4. Интерпретатор языка Quack

Лабораторная работа №6

Хеш-таблицы.

1. Set
2. Map
3. LinkedMap
4. MultiMap

Лабораторная работа №7

АВЛ-дерево

1. Проверка сбалансированности
2. Делаю я левый поворот...
3. Вставка в АВЛ-дерево
4. Удаление из АВЛ-дерева
5. Упорядочное множество на АВЛ-дереве

Второй семестр

Лабораторная работа №8

Графы: основные определения и поиск в ширину.

1. От списка ребер к матрице смежности
2. Проверка на неориентированность
3. Проверка на наличие параллельных ребер
4. Компоненты связнности
5. Кратчайшие пути в невзвешенном графе
6. Лабиринт

Лабораторная работа №9

Поиск в глубину.

1. Топологическая сортировка
2. Поиск цикла
3. Двудольный граф
4. Конденсация графа
5. Гамильтонов путь
6. Игра

Лабораторная работа №10

Минимальные остовные деревья.

1. Степени вершин
2. Остовное дерево
3. Остовное дерево 3
4. Алгоритм двух китайцев

Лабораторная работа №11

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

1. Кратчайший путь
2. Кратчайший путь от каждой вершины до каждой
3. Кратчайший путь
4. Кратчайшие пути и прочее
5. Цикл отричательного веса

Лабораторная работа №12

Динамическое программирование.

1. Наибольшая возрастающая последовательность
2. Наибольшая возрастающая последовательность 2
3. Общая подпоследовательность
4. Ход конём - 2
5. Выбор вершин дереве
6. Дерево (сумма)
7. Рюкзак
8. Футболки

Лабораторная работа №13

Поиск подстрок.

1. Наивный поиск подстроки в строке
2. Быстрый поиск подстроки в строке
3. Префикс-функция
4. Автомат КМП
5. Множественный поиск