27 апреля 2012 г.



Design and Analysis of Algorithms I: результаты

На этой неделе закончилась первая часть онлайн курса Design and Analysis of Algorithms университета Стэнфорда, доступная через платформу Coursera. В среду я нашел время для финального экзамена (потратил два из трех возможных часов, все же попытка только одна), сдал на 29,5 из 30 (ботан!), оставил фидбэк организаторам и теперь готов рассказать как это было :)

А было на удивление хорошо. Это был мой первый опыт онлайн обучения на какие-то серьезные темы, требующие большего включения и работы головой, чем ставшие уже привычкой просмотры разнообразных докладов конференций и небольших онлайн тренингов. Поэтому были некоторые опасения насчет финального результата - вдруг все это будет просто тратой времени? Скажу сразу - не оправдались.

Итак, весь курс занял 5 недель плюс еще одна, в течении которой можно было сдать финальный экзамен. Ведущий курса - преподаватель Стэнфорда Tim Roughgarden. Учебный процесс достаточно простой:

  • каждую неделю появляется порция видеолекций общей продолжительностью в среднем два часа (их можно скачать либо смотреть онлайн), некоторые видео - опциональные, т.е. в заданиях не будет по ним вопросов
  • лекции могут содержать в себе простые вопросы для студентов, для поддержания интерактивности - ответы на них ни на что не влияют, но помогают погрузиться в тему
  • домашнее задание делится на две части: теоретическую и практическую
  • теоретическая часть - набор из 5 вопросов по материалам лекций, оценивался в максимум 8 баллов, представлен в виде теста с вариантами ответов (возможно несколько правильных), вопросы были как чисто теоретические так и требующие некоторых вычислений на бумажке, две попытки
  • практическая часть - оцениваемый в 6 баллов programming assignment, который можно выполнить с помощью любой технологии; скачиваем файл с входными данными и обратно представляем ответ в требуемом формате, пять попыток
  • по домашнему заданию были дедлайны - две недели со времени публикации задания или к концу курса, но лишь за половину возможных баллов
  • результирующая оценка курса = 40% теоретических задач + 30% практических + 30% финальный экзамен = максимум 100 баллов; если набрал больше 70 - получаешь сертификат об успешном окончании курса (я набрал 92,5 :-Р)
Далее, о содержании курса и несколько примеров из теоретических домашних заданий - прекрасная возможность проверить не заржавели ли знания у вас в голове :). Оставляйте ответы в комментах, правильные появятся через несколько дней. Практические задания можно посмотреть на гитхабе: https://github.com/ddudnik/algo-class-assignments. В начале каждого файла решения есть полное описание задачи, а в папке resources можно найти все входные данные. Код приведен на Ruby, для первых двух недель есть и на Javа для самопроверки. Я решил не терять замечательной возможности не только изучить материал курса, но и заодно немного изучить Ruby :-)

Итак, чему удалось научиться?

Первая неделя

Само собой - введение. Зачем нам нужно изучать алгоритмы, что собой представляет этот курс и т.п. Далее плавно переходим к общим принципам анализа алгоритмов на примере Merge-Sort, говорим несколько слов об используемой нотации Big O (напомню, что я не математик, поэтому даже это было мне в некоторой степени неизвестно) и изучаем один из основных приемов проектирования алгоритмов - принцип разделяй и властвуй - на примерах подсчета инверсий в массиве (на основе Merge-Sort) и алгоритма Штрассена для умножения матриц.

Примеры вопросов из домашки:

1.1) Assume again two (positive) functions f and g such that f(n)=O(g(n)). Is 2f(n)=O(2g(n)) ? (Multiple answers may be correct.)
  • Never
  • Sometimes
  • Always
  • Yes if f(n)≤g(n) for all sufficiently large n
1.2) k-way-mergesort. Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single array of kn elements. Consider the following approach. Using the merge subroutine taught in lecture, you merge the first 2 arrays, then merge the 3rd given array with this merged version of the first two arrays, and so on until you merge in the final (kth) input array. What is the time taken for this strategy, as a function of k and n ? (Optional: can you think of a faster way to do the k-way merge procedure ?)
  • θ(n*log(k))
  • θ(n*k^2)
  • θ(n*k log(n))
  • θ(n*k*log(k))

Вторая неделя

Master Method для оценки рекурсивных алгоритмов, примеры его испольвания, доказательство теоремы и интерпретация результатов. Классика жанра - алгоритм Quicksort. Его описание и время исполнения, доказательство корректности, детали реализации, полный математический анализ. Пришлось вспоминать теорию вероятности, благо специально для таких как я было предложено два опциональных видео в помощь.

Примеры вопросов:

2.1) This question will give you further practice with the Master Method. Suppose the running time of an algorithm is governed by the recurrence T(n)=9∗T(n/3)+n^2,. What's the overall asymptotic running time (i.e., the value of T(n))?
  • θ(n^2)
  • θ(n^2*log(n))
  • θ(n^log(9))
  • θ(n*log(n))
2.2) Define the recursion depth of QuickSort to be the maximum number of successive recursive calls before it hits the base case --- equivalently, the number of the last level of the corresponding recursion tree. Note that the recursion depth is a random variable, which depends on which pivots get chosen. What is the recursion depth of QuickSort (both for a best-case choice of pivots, and for a worst-case choice of pivots)?
  • Best: n, worst: n^2
  • Best: n, worst: n*log(n)
  • Best: log(n), worst: n
  • Best: n^2, worst: n^3

Третья неделя

Выбор (selection) из массива: рандомизированный и детерменированный алгоритмы, их анализ и время исполнения. Графы: их представления (матрица или списки), minimum cut (не знаю как по-русски), алгоритм для определения min cut - Random Contraction algorithm, его анализ и детали реализации.

Примеры вопросов:

3.1) How many min cuts are there in a tree with n nodes (ie. n−1 edges) ?
  • n
  • log (n)
  • n - 2
  • n - 1
3.2) Let 0.5<α<1 be some constant. Suppose you are looking for the median element in an array using RANDOMIZED SELECT (работает по аналогии с Quicksort, по сути является его частным случаем). What is the probability that after the first iteration the size of the subarray in which the element you are looking for lies is ≤α times the size of the original array?
  • α
  • 1 - α
  • 2*α - 1
  • 1 - 2*α

Четвертая неделя

Углубляемся в графы и изучаем поиск элементов направленного графа. Алгоритмы поиска: breadth-first search (BFS) и depth-first search (DFS), то бишь поиск в ширину или глубину. Их особенности и возможности применения для практических задач. Алгоритмы топологичской сортировки узлов направленного графа и поиска сильно связанных компонентов (strongly connected components). 

Кстати, практическое задание на этой неделе было, пожалуй, наиболее интересным с точки зрения реализации. Нужно было найти сильно связанные компоненты в большом графе. Если сам алогоритм закодировать было легко, то преобразовать программу для работы с большим объемом данных было достаточно интересно. Входной граф содержит более 800 000 узлов и более 5 миллионов(!) связей, задавался файлом размером 70 Мб (по одной строке на связь). После первой (рекурсивной) реализации Ruby просто напросто падал с ошибкой "Stack level too deep!", пришлось менять рекурсию на цикл и хранить стэк самостоятельно.

Примеры вопросов:

4.1) Consider the following problem: given an undirected graph G with n vertices and m edges, and two vertices s and t, does there exist at least one s-t path? If G is given in its adjacency list representation, then the above problem can be solved in O(m+n) time, using BFS or DFS. Suppose instead that G is given in its adjacency *matrix* representation. What running time is required, in the worst case, to solve the computational problem stated above? (Assume that G has no parallel edges.)
  • θ(n*log(n))
  • θ(n^2)
  • θ(n*m)
  • θ(m^2)
4.2) On adding one extra edge to a directed graph G, the number of strongly connected components...?
  • ... definitely will remain the same
  • ... will decrease by 1
  • ... will never remain the same
  • ... might remain the same

Пятая неделя

Классика: алгоритм Дейкстры для поиска кратчайшего пути между узлами графа. Его анализ, доказательство корректности, детали реализации. Плавный переход к структурам данных, т.к. оптимальная реализация алгоритма Дейкстры использует структуру Heap (не путать с понятием кучи при динамическом распределении памяти). Довольно подробно рассмотрели Hashtables: детали хорошей и плохой(!) реализации, хэш-функции. Типичное применение Heap и Hashtable в программах, типичные операции и время их исполнения.

Примеры вопросов:

5.1) Consider a directed graph with distinct and nonnegative edge lengths and a source vertex s. Fix a destination vertex t, and assume that the graph contains at least one s-t path. Which of the following statements are true?
  • The shortest s-t path must exclude the maximum-length edge of G.
  • There is a shortest s-t path with no repeated vertices (i.e., a "simple" or "loopless" such path).
  • The shortest (i.e., minimum-length) s-t path might have as many as n−1 edges, where n is the number of vertices.
  • The shortest s-t path must include the minimum-length edge of G.
5.2) Suppose you implement the functionality of a priority queue using a sorted array (e.g., from biggest to smallest). What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)
  • Θ(n) and Θ(1)
  • Θ(1) and Θ(n)
  • Θ(log(n)) and Θ(n)
  • Θ(n) and Θ(log(n))

Вот таким получился курс, честно говоря я уже жду второй части. К сожалению, на данный момент неизвестно, будет ли она. К счастью, Coursera, уже объявила, что в августе и нобяре соответственно планируется старт курсов Algorithms, Part One и Algorithms, Part Two - однако от университета Принстона. Так что - записывайтесь!, не упускайте возможности, все же курсы предоставляют одни из лучших университетов США. Я уже записался на курс Compilers, который стартовал на этой неделе.

Вот ссылка на все курсы платформы Coursera: https://www.coursera.org/courses. Среди них не  только Computer Science, есть много других интересных курсов (учебные процеесы и длительность у всех отличается). Кстати, есть и конкурирующая организация http://www.udacity.com/courses - курсов тут меньше, но зато они более интерактивные и ведут их достаточно известные в мире IT люди. На этой платформе я записался на курс CS212 Design of Computer Programs - в первую очередь, чтобы познакомится с языком и инфраструктурой Python. Ждите отчета через несколько недель :-)






Понравилось сообщение - подпишитесь на блог Подписка на блогFollow grodnosoft on Twitter




Читайте также:


Комментов: 0

Отправить комментарий