1. Что такое хорошая программа (хороший проект)?
2. Основные принципы отладки программ.
3. Хорошие и плохие интерфейсы (модулей и программ).
4. Тестирование и документирование.
5. Краткое содержание курса.
6. Формальности про экзамен.

1. Зачем сжимать информацию?
2. Сжатие с потерями и без потерь.
3. Алгоритм RLE.
4. Алгоритм Хаффмана: построение кодового дерева, упаковка и распаковка.
5. Алгоритм LZ77 (скользящее окно).
6. Алгоритм LZW.
7. Исключительный случай при распаковке LZW.
8. Сжатие с потерями и функциональный анализ.

1. Графические библиотеки для проектов.
2. Спектр задач, в которых появляется трансляция.
3. Виды анализа: лексический, синтаксический, семантический.
4. Лексические анализаторы (сканеры).
5. Интерфейс сканера.
6. Ручная реализация сканера для вычисления арифметических выражений.
7. Недетерминированные конечные автоматы (НКА).
8. Регулярные выражения.
9. Трансформация регулярных выражений в НКА.
10. Понятие порождающей грамматики.
11. Пример грамматики для скобочных выражений.
12. Контекстно-свободные грамматики и деревья разбора.
13. Построение грамматики для разбора арифметических выражений.
14. Отражение приоритетов операций в грамматике выражений.
15. Метод рекурсивного спуска.
16. Реализация разбора арифметических выражений с помощью рекурсивного спуска, обработка ошибок.

1. Общий принцип работы хеш-таблицы.
2. Требования к хеш-функции.
3. Интерфейс хеш-таблицы.
4. Размещение в массиве: метод деления, метод умножения.
5. Тривиальные хеш-функции.
6. Хеш-функция Дженкинса.
7. Хеш-функция для набора элементов.
8. Конфликты и способы их разрешения.
9. Списки коллизий.
10. Открытая адресация: линейное, квадратичное исследование, двойное хеширование.
11. Кукушиное хеширование (cuckoo hash).
12. Хеш vs. дерево.
13. Криптографические хеш-функции.
14. Контрольные суммы.
15. Принцип адресации по содержимому.
16. Фильтр Блума.
17. Генерация хеш-функций для фильтра Блума.

1. 2-3-4 деревья.
2. Красно-черные деревья (red-black trees).
3. Префиксные деревья (trie).
4. Слоеные списки (skip list).

1. Структура данных дерево.
2. Представление деревьев в C.
3. Двоичные деревья.
4. Обходы двоичных деревьев, связь обходов с древовидным представлением арифметических выражений.
5. Преобразование произвольного дерева в двоичное.
6. Интерфейс и применение деревьев поиска.
7. Высота дерева поиска.
8. Удаление элемента.
9. Оптимальные деревья поиска.
10. Выворачивание (splay trees).
11. АВЛ-деревья.

1. Записи
2. Массивы.
3. Адресация в многомерных массивах: C-style, FORTRAN-style, Java-style.
4. Стеки, очереди и их применение в различных задачах.
5. Реализация стека с помощью динамического массива.
6. Связные списки: структура и свойства.
7. Операции над списками.
8. Двусвязные списки, кольцевые списки, двусвязные кольцевые списки.
9. Данные как «белый ящик» и как «черный ящик».
10. Отличия абстрактных типов данных от структур данных.
11. Очередь с приоритетом.

1. Поиск подстроки в строке — метод грубой силы и идеи его ускорения.
2. Алгоритм Боуэра-Мура.
3. Алгоритм Рабина-Карпа.
4. Программирование как борьба со сложностью.
5. Программа как один большой черный ящик.
6. Декомпозиция на модули.
7. Пример модульной структуры: скачивалка изображений.
8. На что указывает граф связей между модулями?
9. Модуль = Интерфейс + Реализация.
10. Устройство модулей в C: заголовочный файл, исходный файл, использование модуля.
11. Стандартная библиотека C как набор модулей.
12. Почему интерфейс важнее реализации?
13. Операционная система как интерфейс.
14. Признаки хорошего интерфейса.

1. Cортировка Шелла.
2. Быстрая сортировка. Процедура разделения массива.
3. Алгоритм выбора k-го элемента.
4. Стабильность сортировок.
5. Сортировка слиянием.
6. Пирамидальная сортировка.
7. Нижняя оценка скорости сортировок, основанных на сравнениях.
8. Линейные сортировки: подсчетом, поразрядная, карманная.

1. Сложность алгоритмов. Нотация O, Ω, Θ.
2. Задача сортировки.
3. Интерфейс функции сортировки в C.
4. Bogosort и bozosort.
5. Сортировка выбором.
6. «Пузырьковая» сортировка.
7. Сортировка вставками.
8. Принцип «Разделяй и властвуй». Примеры: задача о ханойских башнях, получение перестановок, алгоритм Карацубы (умножение длинных чисел).
9. Основная теорема о рекуррентных соотношениях.
10. Поиск в массиве, двоичный поиск.
11. Рекурсия. Удачные и неудачные примеры использования рекурсии.
12. Хвостовая рекурсия.

Сайт с визуализацией сортировок