Skip to content

Latest commit

 

History

History
432 lines (374 loc) · 32.5 KB

README.md

File metadata and controls

432 lines (374 loc) · 32.5 KB
Raw

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 балл.
  1. Таблица сравнения производительности.
  • Сравнить время выполнения разных операций для разных массивов с разным порядком значений.
  • Cделать обёртку над ArrayList() и тоже сравнить.
  • Составить таблицу и приложить её скриншот.
  • Сделать выводы и сформулировать их в нескольких предложениях. +1 балл.
  1. Приоритетная очередь (на выбор).
  • Написать реализацию PriorityQueue - очередь с приоритетом.
  • Варианты реализации - список списков, массив списков
  • Методы к реализации: enqueue(int priority, T item) - поместить элемент в очередь T dequeue() - выбрать элемент из очереди +2 балла
  1. на выбор
  • Написать Реализацию класса 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 балл
  1. Алгоритм возведения в степень +1 балл
  2. Алгоритмы поиска кол-ва простых чисел до N +1 балл 3d. Решето Эратосфена с битовой матрицей, по 32 значения в одном int (по желанию) +1 балл
  3. Алгоритм поиска чисел Фибоначчи +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 где первый индекс - номер уровня, на каждом уровне массив, с номерами вершин, принадлежащих этому уровню

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

  2. Дополнительное задание 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

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

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

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