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

В этом курсе мы изучаем некоторые алгоритмы и структуры данных из разных разделов информатики. Упор делается на алгоритмы которые легко объяснить, понять и реализовать.

Как решать задачи

Вы можете писать код на любом удобном вам языке программирования. Чтобы вы могли проверить, что решили задачу правильно, я буду выдавать к ним тесты. Задачи должны предполагать, что получают данные из стандартного ввода, т.е. клавиатуры, а печатают результат в консоль. Тесты распространяются в виде набора файлов с расширениями, соответственно, in и out. Для проверки решения необходимо запускать программу, перенаправляя стандартный ввод и вывод, чтобы не надо было по-настоящему вводить с клавиатуры. При запуске из командной строки это делается следующим образом:

program.exe <test.in >program.out

При запуске из среды разработки нужно настроить параметры запуска и указать там перенаправление ввода и вывода, это делается по-разному в зависимости от среды разработки.

Для проверки правильности ответа нужно сравнить ваш вывод с правильным. Из командной строки это делается следующим образом:

diff program.out test.out

Добавьте ключ --strip-trailing-cr, чтобы игнорировать различие в символах перевода строки:

diff --strip-trailing-cr program.out test.out

Есть графические программы для сравнения текстовых файлов, например, Meld. Но, думаю, ваша среда разработки тоже умеет сравнивать файлы. В средах от JetBrains (IntelliJ IDEA, PyCharm) вы можете выбрать файлы и нажать Ctrl + D.

Сдача заданий

Для сдачи заданий вы должны сделать fork репозитория на github: Algorithms and data structures Spring 2022

Для каждого задания он содержит папку, внутри которой находятся тесты. Вы должны решать каждую задачу в соотвтствующей ей папке и пользоваться предложенными там тестами. Рекомендуется не изменять исходные файлы с тестами, чтобы в случае обновления тестов не возникало конфликтов.

Лекции

  1. Двоичный поиск и двоичный поиск по ответу. Немного о сложности. (в аудитории)
  2. Двоичные деревья поиска и двоичная куча. лекция 2 конспект
  3. Система непересекающихся множеств, динамическое программирование: набрать сумму монетками. Наибольшая возрастающая подпоследовательность. лекция 3 конспект
  4. Задача о поиске подстроки в строке, алгоритм Кнута Мориса Пратта. Edit distance. Вычислительная геометрия: площадь многоуогольника, проверка точка внутри выпуклого многоугольника, выпуклая оболочка. лекция 4 конспект

Задания

  1. Двоичный поиск и двоичный поиск по ответу
  2. Двоичные деревья
  3. Система непересекающихся множеств
  4. Динамическое программирование
  5. Алгоритмы со строками
  6. Вычислительная геометрия

Бонус

  1. Алгоритмы работы с большими данными (англ.): MMDS