Курс Algorithms от Coursera (4-6 недели обучения)

Как и обещал, пишу продолжение статьи, посвященной обучению на курсе Algorithms.

Тех кто не знает структуру курса, прошу в первую статью, там я расписал, как проходит работа. Здесь я расскажу о программе заключительных 3 недель обучения и о финальном экзамене.

Неделя 4

• Priority Queues (очередь с приоритетами). Рассматриваются очереди с приоритетом, их базовые операции, оценивается сложность выполнения каждой из них. Рассматривает реализация очереди через двоичную кучу (Binary Heap), а также сортировка на базе этой структуры данных (Heap Sort).
• Elementary Symbol Tables (символьные таблицы). Эта глава посвящена «символьным таблицам» (уж простите за такой прямой перевод), другими словами хранению пар ключ-значение. Рассматриваются базовые операции и их сложность при реализации символьных таблиц через связный список и через бинарное дерево. На мой взгляд данную главу можно рассматривать и как отличное пособие по бинарным деревьям и операциям выполняемым на них. По большому счету не так важно, что мы в них храним, глава вполне могла называться Elementary Symbol Tables and BST.
• В качестве практического задания будет предложено реализовать программу для поиска решения игры «пятнашки».

Неделя 5

• Balanced Search Trees (сбалансированные поисковые деревья, снова извиняюсь за прямой перевод, возможно правильно не поисковые, а бинарные деревья). Наверное одна из самых полезных глав за весь курс. Рассматривается красно-черное дерево, одна из фундаментальных структур данных. Рассматривается очень подробно и доходчиво, начинается анализ с 2-3 деревьев, а затем, как их развитие рассматривается красно-черное дерево. К своему удивлению узнал, что автор курса Роберт Седжевик, непосредственно приложил к руку к созданию красно-черного черного дерева в том виде, в котором мы его знаем.
• Geometric Applications of BSTs (применение бинарных деревьев для решения геометрических задач). Этот раздел стал для меня откровением, если все что рассматривалось ранее, я в той или иной степени знал, то здесь почти все было в новинку, особенно kd-деревья — очень интересная структура данных. В целом рассматривается возможность применения бинарных деревьев для поиска принадлежности множества точек (или точки) на плоскости другому множеству точек (отрезок или прямоугольник). Рассматривает такие разновидности бинарных деревьев, как KD-дерево и дерево «интервалов»(Interval Search Tree).
• Для практического задания предложено реализовать поиск ближайшей точки на плоскости и принадлежность точки на плоскости заданному прямоугольнику с помощью kd-дерева.

Неделя 6

• Hash Tables (хеш-таблицы). Как следует из названия, глава посвящена хеш-таблицам. Первая лекция посвящена хеш-функциям, а также способам реализации хеш-функций в java. Дальше разговор идет про сами хеш-таблицы: рассматривается их реализация, проводится оценка сложности выполняем операций. Большое внимание уделяется способам разрешения хеш коллизий в хеш-таблице. Один из методов всем известен и основан на списках для каждого значения хеш-функции, второй метод, например для меня, стал так же открытием, раньше такого не встречал (используется один связный список для хранения всех значений).
• На последней неделе курса практического задания нет, вместо него есть финальный экзамен.

Финальный экзамен
Надо сказать, финальный экзамен довольно непростая штука. 20 вопросов, многие из которых являются открытыми, т.е. без вариантов ответов (например, написать массив чисел после выполнения над ним n-шага указанной сортировки). Большинство вопросов уже были в предыдущих упражнениях курса, но есть и несколько новых типов заданий. Например, даны несколько утверждений или вопросов, так же даны несколько вариантов ответов, необходимо сопоставить ответы с соответствующими утверждениями. Задача усложняется тем, что каждый из вариантов может быть использован для 1 и более утверждений или не использован вообще. Или другой пример: даны 10 массивов слов и указан исходный массив, необходимо определить промежуточным состоянием какой сортировки является тот или иной массив (задание это меня прилично напрягло, а так как взялся делать его последним, то надолго меня не хватило и плюнув, поставил некоторые варианты наугад).

На финальный экзамен дается три попытки, зачтена будет лучшая (у меня к сожалению, свободное время на экзамен было только перед финальным дедлайном, поэтому попытка у меня была всего одна). По времени надо ориентироваться на 2-3 часа работы в спокойной обстановке, очень важна внимательность и аккуратность. У меня два задания были завалены просто потому, что не корректно перенес финальный ответ с бумаги в поле ввода: в одном задании не дописал последний элемент массива, в другом из-за нескольких исправлений на бумаге вместо числа 90 написал 92. На финальном экзамене можно набрать максимум 20 баллов, мне удалось набрать 14.77 из 20, хотя, как писал выше, просто будучи чуть внимательней, смог бы набрать 16-17 баллов. К сожалению, после финального теста не было произведено расчета общей оценки за курс (а может я просто не нашел ее?), хотя выставление баллов за упражнения и практически задачи, наводило на мысль о наличии итоговой оценки. Если ответственно проходить весь курс от начала и до конца, то финальный тест не вызовет затруднений.

В целом, курс очень понравился, почерпнул много нового и свел в единую систему свои разрозненные до того знания. Уже записался на анонсированную на ноябрь вторую часть данного курса. Тем, кто еще не слушал первую часть — настоятельно рекомендую. К сожалению, пока на сайте нет точной даты начала курса, но можно подписаться и получить уведомление о его начале.

Ссылки:
Сайт Сoursera — www.coursera.org
Курс «Алгоримы. Часть 1» — www.coursera.org/course/algs4partI
Курс «Алгоримы. Часть 2» — www.coursera.org/course/algs4partII