Skip to content
This repository has been archived by the owner on Jan 20, 2020. It is now read-only.

Latest commit

 

History

History
197 lines (153 loc) · 12.8 KB

README.md

File metadata and controls

197 lines (153 loc) · 12.8 KB
Raw

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

Задачи для курса "Алгоритмы и структуры данных" 2019 года курса в Технополис.

Fork

Форкните проект, склонируйте и добавьте upstream:

$ git clone git@github.com:<username>/2019-ads.git
Cloning into '2019-ads'...
...
$ git remote add upstream git@github.com:polis-mail-ru/2019-ads.git
$ git fetch upstream
From github.com:polis-mail-ru/2019-ads
 * [new branch]      master     -> upstream/master

Схема работы

В общем случае часть задач будет с e-olymp, и проверяться будет средствами этой системы. Но также возможны и задачи, тесты на которые будут оформлены в нашем репозитории.

Решения задач с e-olymp.com

Первым делом регистрируемся на e-olymp.

Для каждого нового домашнего задания заводим новую ветку в своем репозитории. Например, домашнему заданию после первой лекции будет соответствовать ветка part1. Создаем ее в локальном репозитории

$ git checkout -b part1

Исходники решений добавляются в java-пакет ru.mail.polis.ads.<partX>.<username>, где username - логин на Github. Решение каждой задачи - отдельный Java-класс в этом пакете. Можно воспользоваться классом ru.mail.polis.ads.SolveTemplate, в котором остается реализовать лишь метод solve.

После того, как решения будут доведены до рабочего состояния (все тесты будут проходить), можно коммитить, пушить и создавать pull request в polis-mail-ru/2019-ads. В самом PR либо в его описании, либо в комментариях к каждому классу-решению нужно добавить ссылку на submission в e-olymp, где видно, что все решение прошло все тесты. Эти ссылки имеют вид "https://www.e-olymp.com/ru/submissions/5707028".

Все обсуждения решения происходят в рамках комментариев к PR (в противном случае мы зафлудим общий чатик и запутаемся окончательно :))

Решения задач с локальными тестами

Прогон тестов будет осуществляться системами continuous integration, например, TravisCI и/или CircleCI. Тесты в этих системах будут исполняться при созданни PR и при добавлении новых коммитов. В итоге у PR должна появиться зеленая галочка, говорящая об успешном прохождении тестов.

ДЗ 1.

Задачи с e-olymp.com

За каждое полностью рабочее решение дается 2 балла (да, даже за первую задачу).

ДЗ 2.

Задачи с e-olymp.com

За каждое полностью рабочее решение дается 2 балла.

ДЗ 3.

Задачи с e-olymp.com

Дэдлайн - 22.10

В задачах нельзя использовать Arrays.sort()/Collections.sort(). На то они и задачи на сортировку, чтобы мы сами пописали эти сортировки.

ДЗ 4.

Задачи с e-olymp.com

Дэдлайн - 29.10

ДЗ 5.

Дэдлайн - 5.11

ДЗ 6.

Дэдлайн - 12.11

Реализация АВЛ-дерева. Дан интерфейс двоичного дерева поиска с поддержкой упорядоченных операций ru.mail.polis.ads.bst.Bst. Решения с использованием библиотечных структур данных (TreeMap, которая на самом деле не на АВЛ работает) не принимаются.

Основные методы:

  • Value get(Key key) - возвращает значение по заданному ключу или null, если такого ключа нет
  • void put(Key key, Value value) - сохраняет заданное значение по указанному ключу
  • Value remove(Key key) - удаляет заданный ключ (и связанное с ним значение, возвращая его)

Методы, основанные на порядке ключей:

  • Key min() - возвращает минимальный ключ или null, если структура пустая
  • Value minValue() - возвращает значение, ассоцирированное с минимальным ключом, или null, если структура пустая
  • Key max() - возвращает максимальный ключ или null, если структура пустая
  • Value maxValue() - возвращает значение, ассоцирированное с максимальным ключом, или null, если структура пустая
  • Key floor(Key key) - возвращает максимальный ключ, меньший либо равный заданному, или null, если такого нет
  • Key ceil(Key key) - вовзращает минимальный ключ, больший либо равный заданному, или null, если такого нет

Служебные методы:

  • int size() - вовзращает количество узлов в дереве
  • int height() - возвращает высоту дерева (максимальная длина пути от корня до листа)

ДЗ 7.

Дэдлайн - 25.11

Часть 1. Без remove()

N.B. Pull-реквесты нужно делать в ветку red-black.

Реализация Left-Leaning Red-Black Tree. Дан интерфейс двоичного дерева поиска с поддержкой упорядоченных операций ru.mail.polis.ads.bst.Bst. Решения с использованием библиотечных структур данных (TreeMap, которая на самом деле работает на красно-черных деревьях из Кормена) не принимаются.

Основные методы:

  • Value get(Key key) - возвращает значение по заданному ключу или null, если такого ключа нет
  • void put(Key key, Value value) - сохраняет заданное значение по указанному ключу
  • Value remove(Key key) - удаляет заданный ключ (и связанное с ним значение, возвращая его) (делается во втором этапе, после лекции)

Методы, основанные на порядке ключей:

  • Key min() - возвращает минимальный ключ или null, если структура пустая
  • Value minValue() - возвращает значение, ассоцирированное с минимальным ключом, или null, если структура пустая
  • Key max() - возвращает максимальный ключ или null, если структура пустая
  • Value maxValue() - возвращает значение, ассоцирированное с максимальным ключом, или null, если структура пустая
  • Key floor(Key key) - возвращает максимальный ключ, меньший либо равный заданному, или null, если такого нет
  • Key ceil(Key key) - вовзращает минимальный ключ, больший либо равный заданному, или null, если такого нет

Служебные методы:

  • int size() - вовзращает количество узлов в дереве

Часть 2. С remove()

Ко всему прочему добавляется

  • Value remove(Key key) - удаляет заданный ключ (и связанное с ним значение, возвращая его)

ДЗ 8.

Дэдлайн - 4.12

N.B. Pull-реквесты нужно делать в ветку hash.

Реализация HashTable с разрешением коллизий методом цепочек.

Дан интерфейс хеш-таблицы ru.mail.polis.ads.hash.HashTable. Решения с использованием библиотечных структур данных (java.util.HashMap/Hashtable) не принимаются.

Основные методы:

  • Value get(Key key) - возвращает значение по заданному ключу или null, если такого ключа нет
  • void put(Key key, Value value) - сохраняет заданное значение по указанному ключу
  • Value remove(Key key) - удаляет заданный ключ (и связанное с ним значение, возвращая его)

Служебные методы:

  • int size() - вовзращает количество ключей

ДЗ 9.

Дэдлайн - 12.12

ДЗ 10.

Дэдлайн - 27.12