otus

otus-algo-club / algo-2019-04

1. 2019-04-30_otus_algo_01 Введение в алгоритмы, RAM-модель. Порядок роста функций.

Домашнее задание

Реализация алгоритма сортировки на RAM

1. Написать на RAM алгоритм деления двух натуральных чисел через вычитание. На входе делимое и делитель. На выходе частное и остаток.

2. Написать на RAM алгоритм простой сортировки. На входе число N и потом N целых чисел. На выходе N чисел отсортированных по возрастанию. для (каждого i от 0 до N-1) для (каждого k от i+1 до N-1) если (элемент[i] > элемент[k]) элемент[k] <=> элемент[i];

3. Написать, сколько времени ушло на выполнение домашнего задания.

2. 2019-05-07_otus_algo_02 Базовые структуры данных: массив, динамический массив, список, стек, очередь, очередь с приоритетами.

Домашнее задание

Неполный массив или очередь с приоритетом.

1. Динамические массивы.

• Написать метод добавления и удаления элементов: void add(T item, int index); T remove(int index); // возвращает удаляемый элемент
• по индексу во все варианты динамических массивов: SingleArray, VectorArray, FactorArray, MatrixArray *. +1 балл.

2. Таблица сравнения производительности.

• Сравнить время выполнения разных операций для разных массивов с разным порядком значений.
• Cделать обёртку над ArrayList() и тоже сравнить.
• Составить таблицу и приложить её скриншот.
• Сделать выводы и сформулировать их в нескольких предложениях. +1 балл.

3. Приоритетная очередь (на выбор).

• Написать реализацию PriorityQueue - очередь с приоритетом.
• Варианты реализации - список списков, массив списков
• Методы к реализации: enqueue(int priority, T item) - поместить элемент в очередь T dequeue() - выбрать элемент из очереди +2 балла

4. на выбор

• Написать Реализацию класса SpaceArray массив массивов с неполным заполнением.
• Делать на основе одного из уже созданных массивов и/или списков. +2 балла дополнительно.

За выполнение задания до начала следующего урока: +1 балл.

Для реализации можно использовать только стандартные массивы [], созданные классы массивов и/или списков. Стандартные библиотеки не используем! Критерии оценки: 1 задание. Динамические массивы. +1 балл. 2 задание. Таблица сравнение производительности. +1 балл. 3 задание (на выбор). Приоритетная очередь. +2 балла 4 задание (на выбор). +2 балла дополнительно. За выполнение задания до начала следующего урока: +1 балл.

3. 2019-05-14_otus_algo_03 Шахматное программирование

Домашнее задание

Битый конь и FEN-ходы

1. Решить задачу "Лошадью ходи" на сайте: https://www.videosharp.info/console/task/level=1745

2. Написать программу выполнения корректного хода для любой шахматной позиции по техническому заданию с тестами.

Критерии оценки: +1 балл за решение задачи "Лошадью ходи". +1 балл за парсинг/сборку и отображения FEN. +1 балл за реализацию счётчика ходов +2 балла за реализацию всех ходов по заданию +5 баллов за реализацию алгоритмов генерации всех ходов (по желанию)

4. 2019-05-16_otus_algo_04 Алгебраические алгоритмы: алгоритм Евклида, быстрое возведение в степень, решето Эратосфена, быстрое вычисление чисел Фибоначчи.

Домашнее задание

1. Вычисление чисел Фибоначчи Написать следующие алгоритмы и сравнить их быстродействие. Приложить скриншоты/ссылки на результаты экспериментов.

1. **Алгоритм Евклида поиска НОД** +1 балл
1a. Через вычитание
1b. Через остаток

2. **Алгоритм возведения в степень** +1 балл
2а. Итеративный (n умножений)
2b. Через степень двойки с домножением
2c. Через двоичное разложение показателя степени.

3. **Алгоритмы поиска кол-ва простых чисел до N** +1 балл
3a. Через перебор делителей.
3b. Оптимизация перебора делителей.
3c. Решето Эратосфена.
3d. Решето Эратосфена с битовой матрицей, по 32 значения в одном int (по желанию) +1 балл

4. **Алгоритм поиска чисел Фибоначчи** +1 балл
4a. Через рекурсию
4b. Через итерацию
4c. По формуле золотого сечения
4d. Через умножение матриц (по желанию) +1 балл

+1 балл за отправку домашнего задания до начала след. вебинара.

**Написать, сколько времени ушло на выполнение домашнего задания.**

Рекомендации по реализации вычисления чисел Фибоначчи через матричный алгоритм: Алгоритм решета Эратосфена, экономичный к памяти, сразу откинуть четные числа Варианты: битовые операции, сегментация

1. Битовые операции - храним как элемент массива целое число, например byte в Java 8 бита. Соответственно, каждый бит представляет собой true/false для определенного числа. Используя этот алгоритм можно уменьшить потребности в памяти в 8 раз. Откинув четные числа, еще в 2 раза.
2. Сегментация - делаем блоками по определенного размера. Выделяем блок фиксированного размера считаем в нем, например блок размером 1000, а посчитать надо до 5000. Соответственно сеем 5 блоков, не забывая, как у нас смещаются индексы. Критерии оценки: 1. Алгоритм Евклида поиска НОД +1 балл

2. Алгоритм возведения в степень +1 балл
3. Алгоритмы поиска кол-ва простых чисел до N +1 балл 3d. Решето Эратосфена с битовой матрицей, по 32 значения в одном int (по желанию) +1 балл
4. Алгоритм поиска чисел Фибоначчи +1 балл 4d. Через умножение матриц (по желанию) +1 балл +1 балл за отправку домашнего задания до начала след. вебинара.

Рекомендуем сдать до: 20.05.2019

5. 2019-05-21_otus_algo_05 Сортировка вставками, сортировка Шелла, сортировка выбором, пузырьковая сортировка.

Домашнее задание

1. Реализовать Insertion Sort и Shell Sort
2. Реализовать алгоритмы insertion sort и Shell sort. Дополнительно: протестировать работу алгоритмов на случайных массивах и на практически упорядоченных массивах, сравнить производительность. Сравнить производительнсоть сортировки Шелла c разной последовательностью шагов.

Как сравнивать производительность:

Для алгоритмов, как минимум, Insertion Sort, Shell Sort с двумя вариантами последовательностей шагов, сделать для каждого следующие измерения:

• Создать массивы размера от 20, 40, 80, 160 ... и до~100.000 элементов для C++/Java или ~10.000 элементов в случае python. Для каждого размера сделать по три массива: случайный (функцией для shuffle из упорядоченного), массив, в котором перемешаны ~10% элементов, и массив, в котором перемешаны 5 элементов.

• Замерять процессорное время для каждого алгоритма и каждого массива, составить табличку в формате .csv либо график, приложить к коду.

• Варианты последовательностей "шагов" (gap sequences) Shell Sort можно брать отсюда, любые, но интереснее будет с O() < O(n^2): https://en.wikipedia.org/wiki/Shellsort#Gap_sequences

• Критерии оценки: Дополнительно:

  • реализован только один алгоритм сортировки / есть серьезные недочеты в реализации, влияющие на производительность - 1 балл
  • алгоритмы реализованы корректно, но есть небольшие недочеты, влияющие на производительность - 2 балла (2 "основных" балла - необходимый минимум для зачета)
  • оба алгоритма реализованы корректно - 3 балла

• Дополнительно:

  • проведено сравнение производительности на разных массивах - 1 балл
  • проведено сравнение производительности Shell sort с разными последовательностями шагов - 1 балл

Рекомендуем сдать до: 22.05.2019

6. 2019-05-23_otus_algo_06 Пирамидальная сортировка (heap sort), tree sort.

Домашнее задание

1. Реализация heapsort

• Реализовать Drown - 1 балл - Реализовать BuildHeap - 1 балл - Реализовать алгоритм Heapsort - 1 балл - Можно все inline и без отдельных процедур, тогда 3 балла, если все иделаьно работает - Heapsort должен работать для получения зачета - Дополнительно 1: реализовать итеративно, а не через рекурсию - 1 балл - Дополнительно 2: реализовать удаление элемента с сохранением свойст пирамиды - 1 балл - Дополнительно 3: реализовать очередь с приоритетами при помощи heap, сравнить с тем, что было ранее сделано - без баллов, по своему желанию (т.к. нам сложно гарантировать быструю проверку)

Рекомендуем сдать до: 27.05.2019

7. 2019-05-28_otus_algo_07 Сортировка слиянием, timsort. Быстрая сортировка.

Домашнее задание

1. Реализовать quicksort или mergesort, дополнительно - усовершенствовать Реализовать:

• MergeSort или QuickSort (рандомизированный и обычный) -
  • алгоритм работает корректно, используется insertion sort: 3 балла
  • алгоритм работает корректно, но выполняет много лишних действий / отклоняется от реализации не в лучшую сторону - 2 балл
• Дополнительно:
  • quicksort - сравнить рандомизированный и обычный варианты - 1 балл
  • mergsesort - добавить обработку run'ов - 1 балл
  • распараллелить алгоритм - 1 балл (если считаете, что этот материал надо разобрать отдельно - напишите в слак) - 1 балл
  • делать оба алгоритма не обязательно, но при желании можно, баллы ставятся за лучший :

8. 2019-05-30_otus_algo_08 Сортировка за линейное время. Поиск порядковых статистик за линейное время.

Домашнее задание

1. Сортировки за линейное время

• Основное задание** - 2 балла
  • Реализовать алгоритмы Counting Sort и Radix Sort
  • Для сортировки разрядов Radix Sort должен использовать Counting Sort
• Дополнительно
  • Сдать работу вовремя - 1 балл
  • Реализовать Trie (с возможностью добавления и удаления элементов) - 1 балл
  • Реализовать Trie-based Radix Sort - 1 балл

Рекомендуем сдать до: 03.06.2019

9. 2019-06-04_otus_algo_09 Сортировка за линейное время. Поиск порядковых статистик за линейное время.

Домашнее задание

1. Реализовать АВЛ или Декартово дерево 1.1 Вариант 1. Написать реализацию АВЛ-дерева

• Методы к реализации:
  • smallLeft/RightRotation - малое левое/правое вращение
  • bigLeft/RightRotation - большое левое/правое вращение, написать через вызов малых вращений
  • insert
  • remove
  • rebalance

1.2 Вариант 2. Написать реализацию Декартово дерева.

• Методы:
  • merge
  • split
  • add
  • remove
  • Критерии оценки: +5 баллов за реализацию АВЛ-дерева
  • +5 баллов за реализацию Декартово дерева

Рекомендуем сдать до: 05.06.2019

10. 2019-06-06_otus_algo_10 Красно-черные деревья, расширяющиеся деревья, рандомизированные деревья.

Домашнее задание

1. Реализация красно-чёрного дерева, вставки и поиска

Домашнее задание выполняется по желанию.

• Вариант A. Реализовать рандомизированное дерево с операциями вставки, поиска и удаления.
• Вариант B. Реализовать расширяющееся дерево с операциями вставки и поиска и удаления.
• Вариант С. Реализовать красно-чёрное дерево с операциями вставки и поиска.

Сравнить производительность операций с AVL деревом.

• Критерии оценки: +2 за вариант А
• +2 за вариант В
• +4 за вариант С
• +1 за сравнение

Рекомендуем сдать до: 10.06.2019

11. 2019-06-11_otus_algo_11 B-деревья, B+-деревья. Деревья отрезков.

Домашнее задание

1. Реализовать любое дерево поиска.

• Реализовать любое дерево поиска на выбор:
  • Красно-чёрное дерево с операциями добавления и поиска элементов.
  • Рандомизированное дерево с операциями добавления, удаления и поиска.
  • Расширяющееся дерево с операциями добавления, удаления и поиска.
  • В-дерево с операциями добавления, удаления и поиска.
  • Дерево отрезков с функцией сложения и операциями добавления, удаления и изменения элементов.
• Критерии оценки: Критерии оценки:
  • 2 балла - алгоритм запрограммирован но не работает или реализованы не все операции.
  • 3 балла - алгоритм работает верно, но не оптимально, или есть несоответствия требованиям (например, сделано способом, отличным от указанного)
  • 4 баллов - алгоритм работает верно и написан эффективно (нет лишних действий замедляющих работу)
  • +1 балл за выполнение задания в срок (до начала след. урока).

Рекомендуем сдать до: 12.06.2019

12. 2019-06-13_otus_algo_12 Таблицы с прямой адресацией. Хэш-таблицы, хэш-функции. Метод цепочек (chaining).

Домашнее задание

1. Хэш-таблицы, часть I

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

1.1 Реализовать хеш-таблицу, использующую метод цепочек

• дополнительно: для хранения внутри цепочек при достижении значительного числа элементов (~32) заменять их на BST

1.2 Реализовать хеш-таблицу с открытой адресацией

• дополнительно: реализовать "ленивое" удаление
• реализовать квадратичный пробинг
• Критерии оценки: 3 балла максимум за основное задание, 2 за дополнительное.

Рекомендуем сдать до: 17.06.2019

13. 2019-06-18_otus_algo_13 Хеш-функции. Стратегии поиска. Универсальное хеширование.

Домашнее задание

• Домашнего задания нет

14. 2019-06-20_otus_algo_14 Универсальное и идеальное хэширование.

Домашнее задание

• Домашнего задания нет
• Домашнего задания нет

Рекомендуем сдать до: 24.06.2019

15. 2019-06-25_otus_algo_15 Поиск в ширину. Поиск в глубину, поиск компонент сильной связности. Алгоритм Косарайю.

Домашнее задание

1. Реализовать алгоритм Косарайю

• Реализовать алгоритм Косарайю

Входные данные: Граф задан вектором смежности int A[N][Smax]. Это п.5 в структурах данных в лекции. Отличие только в том, что вершины нумеруются от 0 а не от 1, и номера самой вершины первым столбцом в матрице не будет, будут только номера смежных вершин

Задание: Реализовать алгоритм Косарайю, рекурсивный вариант, как он был дан в лекции Если понадобится использование стека/очереди обязательно применение собственных структур данных из предыдущих занятий

Выходные данные: Результат должен быть представлен в виде массива int[] component где элемент с номером вершины содержит номер компонента

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

Дополнительное задание 2 Реализовать поиск по критерию стоимости

Дедлайн 10.03.2019 Критерии оценки: Критерии оценки: 1 балл - алгоритм запрограммирован но не работает, 2 балла - алгоритм работает верно, но не оптимально, или есть несоответствия требованиям (например, сделано способом, отличным от указанного) 3 балла - алгоритм работает верно и написан максимально эффективно (нет лишних действий замедляющих работу) 1 балл. Задание сдано в срок. 1 балл. Выполнено дополнительное задание 1 1 балл. Выполнено дополнительное задание 2

Рекомендуем сдать до: 26.06.2019

16. 2019-06-27_otus_algo_16 Топологическая сортировка.

Домашнее задание

1. Алгоритм Демукрона

• Реализовать алгоритм Демукрона

Граф задан вектором смежности int A[N][Smax]. Это п.5 в структурах данных в лекции. Отличие только в том, что вершины нумеруются от 0 а не от 1, и номера самой вершины первым столбцом в матрице не будет, будут только номера смежных вершин

Задание: Реализовать алгоритм Демукрона Если понадобится использование стека/очереди обязательно применение собственных структур данных из предыдущих занятий Можно использовать стандартный массив [] встроенный в язык

Выходные данные: Результат должен быть представлен в виде массива int[][] level где первый индекс - номер уровня, на каждом уровне массив, с номерами вершин, принадлежащих этому уровню

2. Дополнительное задание 1 - Реализовать алгоритм Тарьяна

3. Дополнительное задание 2 - Реализовать алгоритм поиска мостов или точек сочленения

Дедлайн 17.03.2019 включительно Критерии оценки: Критерии оценки: 1 балл - алгоритм запрограммирован но не работает, 2 балла - алгоритм работает верно, но не оптимально, или есть несоответствия требованиям (например, сделано способом, отличным от указанного) 3 балла - алгоритм работает верно и написан максимально эффективно (нет лишних действий замедляющих работу) 1 балл. Задание сдано в срок. 1 балл. Выполнено дополнительное задание 1 1 балл. Выполнено дополнительное задание 2

Рекомендуем сдать до: 01.07.2019

17. 2019-07-02_otus_algo_17 Минимальные остовные деревья. Алгоритмы Крускала и Прима.

Домашнее задание

1. Реализовать алгоритм нахождения минимального остовного дерева
2. Реализовать алгоритм Краскала

Граф задан вектором смежности int A[N][Smax]. Это п.5 в структурах данных в лекции. Отличие только в том, что вершины нумеруются от 0 а не от 1, и номера самой вершины первым столбцом в матрице не будет, будут только номера смежных вершин

Задание: Реализовать алгоритм Краскала Структура Union-Find собственной реализации. Если понадобится использование стека/очереди обязательно применение собственных структур данных из предыдущих занятий Можно использовать стандартный массив [] встроенный в язык

Выходные данные: Результат должен быть представлен в виде массива Edge[] edges где Edge - класс, содержащий пару вершин, которые соединяет это ребро Edge { int v1; int v2; } Для любителей компактного хранения можно упаковать в long два int-а :) Тогда результат будет long[] edges

3. Дополнительное задание 1 - Реализовать алгоритм Прима
4. Дополнительное задание 2 - Реализовать алгоритм Борувки

Дедлайн 17.03.2019 включительно Критерии оценки: Критерии оценки: 1 балл - алгоритм запрограммирован но не работает, 2 балла - алгоритм работает верно, но не оптимально, или есть несоответствия требованиям (например, сделано способом, отличным от указанного) 3 балла - алгоритм работает верно и написан максимально эффективно (нет лишних действий замедляющих работу) 1 балл. Задание сдано в срок. 1 балл. Выполнено дополнительное задание 1 1 балл. Выполнено дополнительное задание

Рекомендуем сдать до: 03.07.2019

18. 2019-07-04_otus_algo_18 Поиск кратчайшего пути в графе. Алгоритмы Дейкстры, Беллмана-Форда, Флойда-Уоршалла.

Домашнее задание

1. Реализовать алгоритм Дейкстры
2. Реализовать классику всех времен и народов, алгоритм Дейкстры Граф задан вектором смежности int A[N][Smax]. Это п.5 в структурах данных в лекции. Отличие только в том, что вершины нумеруются от 0 а не от 1, и номера самой вершины первым столбцом в матрице не будет, будут только номера смежных вершин Задание: Реализовать алгоритм Дейкстры Если понадобится использование дерева/кучи обязательно применение собственных структур данных из предыдущих занятий Можно использовать стандартный массив [] встроенный в язык Выходные данные: Результат должен быть представлен в виде массива Edge[] edges где Edge - класс, содержащий пару вершин, которые соединяет это ребро Edge { int v1; int v2; } Для любителей компактного хранения можно упаковать в long два int-а :) Тогда результат будет long[] edges

3. Дополнительное задание 1 - "Расскажи своей бабушке". Рассказать идею алгоритма Дейкстры совей бабушке так, что бы она это поняла. Поделиться своим опытом в слаке. Не забыть приложить ссылку на пост в задании
4. Дополнительное задание 2 - Реализовать алгоритм Флойда-Уоршалла или Беллама-Форда на выбор

Дедлайн 24.03.2019 включительно Критерии оценки: Критерии оценки: 1 балл - алгоритм запрограммирован но не работает, 2 балла - алгоритм работает верно, но не оптимально, или есть несоответствия требованиям (например, сделано способом, отличным от указанного) 3 балла - алгоритм работает верно и написан максимально эффективно (нет лишних действий замедляющих работу) 1 балл. Задание сдано в срок. 1 балл. Выполнено дополнительное задание 1 1 балл. Выполнено дополнительное задание 2

Рекомендуем сдать до: 08.07.2019