![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
svetasmirnovaПопишу-ка я технические заметки про этот курс.
По опыту предыдущего курса: к экзамену забываются, во-первых, требуемый формат ответов, а во-вторых, что-то из усвоенного материала.
Тесты:
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/
По опыту предыдущего курса: к экзамену забываются, во-первых, требуемый формат ответов, а во-вторых, что-то из усвоенного материала.
Тесты:
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/
