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

Месяц назад несколько раз на Хабре проскакивали статьи о замечательном ресурсе Coursera, где можно пройти курсы обучения по различным направлениям. Среди прочего меня очень заинтересовал курс «Алгоритмы» (часть 1), на который я подписался и начал его изучать. Сейчас курс приближается к завершению, а я решил написать небольшой отчет по первой части курса (надеюсь меня хватить и на описание второй части курса по его завершению), чтобы уважаемый %username% мог определить стоит ли записываться на следующую итерацию курса или нет.

Надо сказать, что незадолго до начала изучения курса я не очень хорошо себя проявил на собеседовании в Одноклассники по традиционному пункту всех девелоперских вакансий — «Уверенное/Хорошее/Отличное знание алгоритмов», это стало дополнительным стимулом к тому, чтобы начать изучение данного курса. Так же отмечу, что алгоритмы я до того изучал в рамках предмета «Структуры данных» в институте, а так позже эпизодически в рамках последующей 4 летней трудовой деятельности. В общем обрывки знаний: где-то хорошо, даже с углубленной подготовкой для собеседований, а где-то пробелы.

Итак, для начала немного о том как построен курс. Длительность курса 6 недель. Каждую неделю открываются лекции посвященные двум темам (по каждой теме 4-6 лекций по 10-20 минут). Прослушав лекции для закрепления выполняются тесты по каждой из тем, а так же одно практическое упражнение — программа на Java, на реализацию прикладной задачи. По каждому из указанных проверочных работ, выставляются баллы (пока не знаю куда они пойдут, подозреваю в конце курса будут как то обработаны в итоговую оценку). Дополнительно есть вопросы по изученной темы, которые могут быть заданы на собеседованиях (там оценок нет, просто для общего развития).

Теперь немного о том, какие темы будут рассмотрены в первые 3 недели курса (весь курс на английском и для некоторых тем я не уверен, что знаю адекватное русское название).

Неделя 1

• Union-Find (поиск объединений): рассматривается проблема определения принадлежности элемента к определенному множеству элементов, а так же операция объединения элементов. Фактически разговор идет о деревьях и поиске принадлежности элемента указанному поддереву, а так же добавлении элемента в указанное поддерево. Рассматриваются плюсы и минусы решения этой задачи на практике через массив и через связный список.
• Analysis of Algorithms (анализ алгоритмов): рассматривают понятия сложности алгоритмов, лучший, худший и средний случай работы алгоритма, способы оценки времени работы алгоритма, а так же способ подсчета затрачиваемой памяти структурами данных в Java.
• В качестве практического задания предлагается реализовать решение Percolation task. К сожалению не знаю как правильно перевести данную задачу на русский, поэтому на пальцах изложу суть: дан двумерный массив ячеек, каждая из которых может быть включена/выключена, после активации очередной ячейки необходимо определить есть ли путь соединяющий верхнюю и нижнюю строки матрицы.

Неделя 2

• Stacks and Queues (стеки и очереди): как понятно из названия рассматриваются указанные структуры данных и их практическая реализация на базе массивов и списков, а так же оценка временной сложности выполнения основных операций при реализации на данных структурах данных. Отдельно время уделено таким вещам как итераторы и дженерики в Java.
• Elementary Sorts (простейшие сортировки): рассматриваются сортировка выбором, сортировка Шелла и сортировка вставками, оценка их временной сложности. Так же рассматривается проблема «перемешивания» элементов. Рассматривается задача построения выпуклого замкнутого многоугольника, охватывающего набор точек на плоскости (Convex Hull).
• Для практики предложено реализовать структуры данных дек и «сумку» (bag).

Неделя 3

• Mergesort (сортировка слиянием): много времени уделено сортировке слиянием, а точнее двум способам ее реализации и оценке их временной сложности. Бонусом рассматривается понятие «устойчивости сортировки», а так же отдельно рассматриваются компараторы в Java.
• Quicksort (быстрая сортировка): здесь все отталкивается от быстрой сортировки. Практическая реализация, оценка ее временной сложности. Дополнительно рассматривается проблема «выборки» элементов (например наибольшего элемента) из множества элементов, а так же внимание уделено тому, как реализована встроенная сортировка в Java.
• На практике попросят решить задачу нахождения коллинеарных точек на плоскости.

Вот так выглядят первые 3 недели обучения. Понравилось, что все темы рассматриваются не в сферическом вакууме, а с реализацией на Java, это делает курс «Алгоритмы» даже как то веселее, отвлекает от формул (кстати ими не очень грузят). Так же понравилось «вкрапление» небольших фрагментов о некоторых особенностях Java (несмотря на опыт разработки на Java, все равно узнаю некоторые новые нюансы). И еще довольным большим плюсом, является необходимость регулярно садится за лекции: деадлайны и по практическим заданиям, и по курсу в целом заставляют не откладывать изучение материала на «потом».

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

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

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

Автор: sphinks