svetasmirnova | Entries tagged with algorithms

Часть 1. Reduction.

Что это такое: понятно из названия. Писать пометки по заданию смысла нет: всё решает опыт и немножко сообразительности.

Часть 2. Linear programming.

Задачи, которые могут быть решены при помощи Linear programming. Википедия опять рулит:

Linear programs are problems that can be expressed in canonical form:

$\begin{align}<br />& \text{maximize} && \mathbf{c}^\mathrm{T} \mathbf{x}\\<br />& \text{subject to} && A \mathbf{x} \leq \mathbf{b} \\<br />& \text{and} && \mathbf{x} \ge \mathbf{0}<br />\end{align}$

Какая переменная может войти в базис следующей? Те, которые вида 1 x xN и единственные в столбце - это уже базис, соответственно нужно выбирать из оставшихся с положительным коэффециэнтом.
Кто кандидат на покидание базиса? Подробно есть здесь Вкратце: делим правый столбец на коэффециэнты того, кто "входит", строка с меньшим получившимся значением - кандидат на выбывание.

Knuth-Morris-Pratt DFA. Первоначально это задание мне показалось самым простым: нужно для каждой буквы пометить состояние, на которое нужно перемещаться на следующем шаге. Но оно же оказалось и самым сложным, потому что я пыталась делать его в уме и таким образом пропускала некоторые состояния. В результате несколько вариантов запорола. Помогло выписывать пройденный путь отдельной строкой: A B B A и т.п. В таком случае очень легко сравнить с искомой строкой и вероятность ошибки меньше.
Boyer-Moore algorithm. Для выполнения этого задания мне пригодился текстовый редактор: первая строка - текст, в котором искать, вторая строка - первый шаг, третья - второй и т.п. Пробелами располагаем где требуется: если знак в исходном тексте, находящийся на той же позиции, что и последний знак строки, которую мы ищем, совпадает с последним знаком - сдвигаем на одну позицию; совпадает с другим знаком в строке - совмещаем с последним нахождением этого знака; ни с чем не совпадает - сдвигаем всю строку на её длину.
Rabin-Karp hash function. Тут тоже всё элементарно: нужно воспользоваться формулой из слайдов. (((previous_reminder - first_sign_of_prev_sequence*( (R*num_symbols) % Q) ) * R + last_sign_of_cur_sequence) % Q + Q) % Q, где R - порядок

Multiway trie Что это такое - интуитивно понятно, повторяться не буду. Задание тоже проблем не вызвало: нужно построить trie и посчитать вообще все ненулевые ноды, то есть с каким-то контентом, неважно, есть ли у них ненулевые линки или нет.
Ternary search trie тоже интуитивно понятно. Единственное, формулировка вопроса вызвала непонимание с первого раза. "What are the depths of the nodes corresponding to the last characters in the 7 strings (in the order the strings were inserted)?" обозначает, что нужно перечислить глубину до последнего знака для каждой из строк, а я почему-то сначала единственную максимальную посчитала. Корень имеет глубину 0, поэтому если первая строка - "АБВ", го глубина "В" будет 2, а не 3.

Для решения обоих заданий пришлось рисовать на бумажке. Эффективного электронного способа сделать тоже самое не обнаружила.

Алгоритм Ford-Fulkerson-а дался мне тяжело. Я его поняла только после того, как нашла вот этот applet

Касательно задания нужно выбирать edges с максимальной (capacity - flow) и не идти по тем, где (capacity - flow) == 0. Если таких в нужном направлении нет, выбирать обратное.

В mincut же попадают все vertex-ы, от которых можно уйти с ненулевым (capacity - flow).

Часть 1. Minimum Spanning Trees.

Всё очень просто.

Kruskal's algorithm - проходить edges в порядке возрастания и добавлять, если не возникает циклов.
Prim's algorithm - всё тоже самое, но плясать от построенного дерева.

Единственная сложность в задании - не ошибиться в записи промежуточных ответов. К счастью, графическое представление графов сделано в ASCII, поэтому я просто копировала в текстовый файл и помечала пройденный edge ~~крестиками~~ буквой Х.

Часть 2. Shortest Paths.

Здесь для записи промежуточных ответов было удобно пользоваться LibreOffice Calc.

Dijkstra's algorithm - всё просто, relax a vertex, выбираем vertex с наименьшей дистанцией, relax его и так до победного.
Topological order - аналогично предыдущему, но vertex-ы выбираем в указанном порядке.
Bellman-Ford algorithm - а вот с ним я помучалась. Почему-то не сразу сообразила в каком порядке relax vertex-ы. А проходятся они на каждом шаге от первого до последнего. Вкратце:
1. Шаг 1. Все vertex-ы - infinity, кроме того, от которого считаем дистанцию. Он - 0. Relax первый vertex. Предположим, это D. Значит, A, B и С мы уже прошли. Их relax на этом шаге больше не нужно. А если D "открыл" последующие, скажем, E и F, их нужно relax по порядку. Причём, если D "открыл" E, а сумма расстояний от D-F-E меньше расстояния от D до E, менять ничего на этом шаге не нужно. А вот если расстояние D-E-F меньше расстояния D-F - значение для F изменить нужно.
2. Шаг 2. Проходим все vertex-ы, открытые на предыдущем шаге, в порядке возрастания. Опять-таки, никаких возвратов обратно.
3. Шаг 3. Аналогично шагу 2.

Тут тоже имеет смысл сделать заметки только по тестам.

1. Breath-first search.

Аналогично предыдущему заданию.

2. Topological order.

Делаем depth-first search, но запоминаем nodes в порядке убывания из очереди. Затем этот список возвращаем в обратном порядке.

Так, для A->B->C D->E, сначала получим список C B A E D и правильным ответом будет D E A B C

3. Strongly-connected components.

Почти аналогично предыдущему, но components выбирать следующим образом: взять букву, пройти depth-first search-ем все слинкованные nodes; если остались неслинкованные - взять следующую букву из списка.

Reference: algs4.cs.princeton.edu/40graphs/

Попишу-ка я технические заметки про этот курс.

По опыту предыдущего курса: к экзамену забываются, во-первых, требуемый формат ответов, а во-вторых, что-то из усвоенного материала.

Тесты:

1. Depth-first search.

Что такое depth-first search - интуитивно понятно: берём текущую node, проходим путь от неё до тупика, возвращаемся к предыдущей node, проходим от неё до тупика и т.д. пока не доберёмся до цели. Пройденные node дважды не проходятся.

Сложность вопроса: выбрать порядок, принимаемый auto-grader, так как алгоритм сам по себе порядка не определяет.

Решение: смотреть только на текстовое представление графа и не обращать внимание на визуальное.

То есть если есть A: E B F, то надо первым выбрать E, пройти весь путь и только вернувшись обратно пройти сначала B, потом F.

2. Breath-first search.

Аналогично: не смотреть на картинку. Естественно, порядок будет: A E B F, потом по горизонтали E, B и F.

3. Connected components.

Совсем просто: как на слайдах пронумеровать по принадлежности к группе. Тут картинка, наоборот, всё упрощает.

Reference: algs4.cs.princeton.edu/41undirected/