День 32 - Начало 4ой недели

Закончил полностью 3 неделю курса, повторил весь прошлый материал. Все-таки конспект очень хорошо помогает в этом 😁

Summary недели:
1. Изучены Quick Sort & Merge Sort - для полнейшего закрепления, рекомендую следующие видео:
https://www.youtube.com/watch?v=7h1s2SojIRw&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=36
https://www.youtube.com/watch?v=mB5HXBb_HY8&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=34
2. Сделал небольшой dive deep в recurrent relations 🤓. Об их важности для понимания алгоритмов Divide & Conquer уже писал не раз.
https://t.iss.one/frontend_engineer_blog/28 👈 вот тут вместе с материалом, который стоит изучить
3. Выполнил курсеровский ассеймент 🤯
4. Повторил материал прошлых недель

Следующие шаги:
1. Изучение 4ой недели курса
2. Поиск хороших дополнительных материалов
3. Немного литкода на тему Priority Queue

Идем дальше 👊

Табличка базовых сортировок со 2ой и 3ей недели курса

День 35 - Priority Queues. Binary Trees, Heap, HeapSort 🤔

Закончил изучение первой части теории 4ой недели курса. В целом, все понравилось и было относительно несложно, но пришлось дополнить обучение парочкой видео. Чтобы быть молодцом и понять первую часть теории, нужно:

1. Разобраться с бинарным деревом . Понять термины - Full Binary Tree, Complete Binary Tree.
2. Написать PriorityQueue просто на основе неупорядоченного массива 👩‍💻
3. Затем перейти к теме хипа. Нарисовать операции вставки / удаления в дерево на листочке / доске / конспекте 🤓 Только так можно понять и запомнить алгоритм.
4. Заимлементить BinaryHeap (thanks cap)
5. Далее стоит разобраться с преобраованием обычного массива в хип. Метод называется heapify. Если получилось сделать все предыдущие пункты, то эти 3 строчки кода напишутся очень быстро
6. Перейти к HeapSort. Сама сортировка элементарная, но нужно понимать все предудыщие пункты.

Вот материалы, которые стоит посмотреть, если будете браться за топик:
1. Abdul Bari’s (каждый раз думаю, огонь мужик ) - https://www.youtube.com/watch?v=HqPJF2L5h9U&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=33&t=0s
2. Google Engineer videos 14-19 https://www.youtube.com/watch?v=wptevk0bshY&list=PLDV1Zeh2NRsB6SWUrDFW2RmDotAfPbeHu&index=14

Следующие шаги:
1. Сделать ассаймент на курсере - 8 Puzzle.
2. Перейти ко второй части теории этой недели.

Приятных выходных ☺️

День 39 - Конец ассаймента 4ой недели.

Бурные праздничные дни прошли 😁 Сегодня закончил задание 4ой недели - 8-puzzle. Задание оказалось на много проще 3ей недели 🤔. Основная задача, воспользоваться Priority Queue и заимлементить алгоритм для поиск оптимального пути A*. Сам алгоритм неплохо расписан в задании, поэтому сложностей с его имлементацией возникнуть не должно.

Главная рекомендация - хорошо изучить первую часть материала, об этом писал в предудыщем посте.

Также почти закончил со второй частью теории недели - Symbol Tables. Завтра осталось повторить несколько моментов и можно двигаться дальше 👊

День 41 - Конец 4ой недели курса

Вот и подошла к концу 4ая неделя. Небольшое саммари по второй части:

Теоритический материал второй половинки недели относитетельно сложный. Но в нем очень важно разобраться 🤓

Symbol Tables - это Абстрактный тип данных ( ADT ), который описывает собой словарь или dictonary. Его имлементации активно используются компиляторами, различными системами, которые работает по типу Key -> Value . И скорее всего, Вы ее точно использовали очень часто)

Важно понимать, что Symbol Table это ADT. То есть, всего лишь интерфейс. Существуют различные имлементации:
1. Хэш таблицы - Hash Tables
2. Бинарные деревья поиска - Binary Search Trees
3. Упорядоченный массив с использованием бинарного поиска
4. Последовательный поиск - Sequantial Search с использованием связанного списка.

На курсе, рассматриваются все, кроме Hash Tables.

Чтобы полность разобраться с темой - нужно:
1. Заимлементить простую реализацию через связанный список. Посмотреть на complexity. Понять что можно лучще.
2. Далее заимлементить с использованием упорядоченного массива и бинарного поиска. Так мы делаем улучшаем операцию поиска значения и вставки и можем итерировать по упорядоченной коллекции
3. Далее стоит разораться с Binary Trees. Мы уже использовали эту структуру для Heap. Но здесь логика работы с ДС немного другая.

Рисуем и имлементим каждую операцию:
- get(key) - поиск значения по ключу
- put(key, value) - вставка нового значения
- min & max - поиск минимум и максимума
- floor - поиск самого большого по значений ключа ключа, который <= входному ключу
- ceil - поиск самого маленького по значению ключа, который >= входному ключу
- size - определение размера
- delete. - удаление элементов

С delete разобраться с ходу тяжело 🤯, мне потребовалось несколько раз нарисовать на доске и выполнить алгоритм, чтобы разобраться с ним. Много corner case. Минус Binary Searh Tree, в том, что операции удаления, делают дерево разбалансированным, что увелиивает его высоту вместо log(n) до sqrt(n)&

Это потихоньку нас подводит к Balanced Trees, теме следующей - 5 недели, где нас ждет последний ассаймент на курсе 🙈

Тем временем, мы двигаемся дальше 👊

Всем замечательных выходных 👍

Слайд из курса со сравнинем комплексити операций различных имлементаций Symbol Tables

День 43 - Сбалансированные деревья. Красно-черное дерево, B-Trees 🤯

Закончил первую часть теории 5ой недели по сбалансированным деревьям. Теория довольно сложная и потребовала глубокого разбора.
Основные вещи, которые проходятся на неделе:

2-3 Trees
Очень важно разобрать данный вид деревьев, так как они является базой для понимания Красно-Черного дерева на основе деревьев бинарного поиска - Red-Black BST
Имлементировать данную DS не надо. Это займет очень много времени и сил и вы все-равно не запомните, так как операции удаления и вставки, имееют очень много операций трансформаций над деревом. Как, мне кажется, важно запомнить Time Complexity и понять базовый принцип работы структуры.

Red-Black Binary Search Trees
А вот тут стоит подготовить свою нервную систему. Готовьтесь к тому, что придется потратить пару дней для того, чтобы вкурить и понять эту DS. Основный принцип, что мы с помощью BST иммитируем структуру 2-3 дерева и все операции направлены на поддержание данной структуры. Как начать и не сдаться?

1. Берем первую и самую простую операцию - search. Здесь не требуется никаких изменений по-сравнению с обычным BST. Это обычный поиск по бинарному дереву. Имлементим данную операцию.

2. Понять, как связь между двумя линками помечается красной или черной. Посмотреть из теории 2-3 Дерева, что такое 3-node и 4-node. Научиться конвертировать 3-Node в бинарное дерево на листочке.

3. Освоить операции поворота узла влево и вправо (rotateLeft и rotateRight), которые используется для поддержания дерева сбалансированным. Это несложная операция, которая требует проработки на листочке или доске. Пару раз достаточно нарисовать все и будете вертеть узлы как шашлык 😁

4. Учимся превращать воображаемый 4-Node в 2 Node путем смены цвета связей между узлами. flipColors

5. Разбираемся с финальным боссом - insert. Там есть несколько кейсов, каждый кейс стоит разорать на листочке
- 2 левых узла красные h.left == RED && h.left.left == RED ( поворот направо )
- Правый красный, левый черный ( поворота налево )
- Левый и Правый красный ( смена цветов )

Посмотрите, как каждая операция поддерживает структуру нашего красно-черное дерево в виде 2-3 дерева. Как только в голове придет понимание как это все соотносится, будет на много легче ☺️ Я реально страдал, пока разбирался 😭

6. Есть операция, хуже финального босса - это удаление. У Сенджвика написано 2 научных работы о том, как удалять узлы из такого дерева. Лично мне кажется, это то, что можно пропустить и не пытаться разбирать. Алгоритм запомнить очень сложно, много условий, кода и трансформаций. Врятли после курса вы вспомните об этом методе и врятли на собеседовании вас попросят его написать 😁
Если очень интересно, в учебнике Сенджвика есть имлементация этого метода. Я ее даже прочел, но закрыл как страшный сон 🙈
Все предыдущие операции ( вставка. поиск, повороты ) дают 90% базы, о том, как работает данная структура данных, а нам важно умение применять и понимать, что применяешь.

Полезно, но опционально: B-Trees
В курсе также рассказыается про данный вид деревьев, которые активно применяются в базах данная и различных индексах. Для себя нашел эту тему полезной, так как неплохо расширяет кругозор. Сможете по-умничать и сказать, как устроен поиск по индексу в SQL базе данных 😁

Вот полезное видео на эту тему, одного просмотра достаточно для понимания:
https://www.youtube.com/watch?v=aZjYr87r1b8&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=77

Следующие шаги:
1. Geometric Applications of BST - звучит как жара 🔥
2. Последний ассаймент курса 🤯

Stay Tuned 👍

#algorithms_part_1, #bst, #red_black_tree, #week_5

Финальная сравнительная табличка имлементаций Symbol Table

День 48 - Конец 5 недели 🎉🎉

Закончил последний ассаймент 5ой недели курса Kd Trees 🎉. Было интересно.

Небольшое саммари, как подходить ко второй части теории недели и ассайменту 🤔 :

1. Нужно хорошо понимать BST из 4й недели. Если сможете с нуля написать его и реализовать базовые операции, задание не будет сложным

2. К сожалению, курсера содержит старое описание задание. На сайте принстона имеется обновлённая версия и чек лист с частыми вопросами.
Я сразу не догадался поискать его, в итоге типичные проблемы и вопросы пришлось додумывать самому :), а в чеклисте они уже были расписаны.

Ссылка на обновлённое задание:👉
https://www.cs.princeton.edu/courses/archive/spring19/cos226/assignments/kdtree/specification.php

Ссылка на чек-лист:👉 https://www.cs.princeton.edu/courses/archive/fall19/cos226/assignments/kdtree/checklist.php

3. К заданию приложены полезные клиенты визуализаторы Range Selection и Neighborhood Selection. Не поленитесь их скачать и дебажить на них ваш код, очень помогает :)

4. Если что-то непонятно, пересмотрите снова теорию по Kd tree. На следующий день обычно становится понятнее.

5. Реализацию стоит начинать с методов 👉 size, search, insert 👈. Так как в целом, эти методы совпадают с BST и вы быстро их напишите.

6. По началу очень сложно представить в голове деление плоскости, когда добавляем новые узлы в дерево. Стоит проработать это на доске 👨‍🏫 прежде, чем писать код.

Следующие шаги :
1. Неделя 6ая, считается опциональной на курсе, думаю быстренько её пройти и перейти ко второй части курса.

2. Обновить цель на smartprogress, добавить пройденный материалы, расписать следующую половину теоретической подготовки.

Идём дальше 👍

Всем хороших выходных и не болеть 🤭

День 50 - Завершение первого части курса по алгоритмам 🎉🎉🎉

Закончил 6ую неделю курса по алгоритмам. Неделя не содержит никаких заданий и теория относительно простая. На данной неделе рассматриваются хэш-таблицы - еще один вариант Symbol Tables

Если хотите погрузиться в тему, рекомендую следующие материалы👇:

1. Структуры данных в картинках: https://habr.com/ru/post/128017/ , автор потрясающе объясняет детали имлементации хэш-таблиц в джаве. Для фронтендеров, наверное стоит просто разобраться с общей концепцией, но если вы генералист, советую максимально изучить данную серию статей 🤔

2. Плейлист от гугл инжинера, автор подробно рассказывают про теорию, коллизии в таблице, варианты ее разрешения и что не мало важно6 приводит код, который можно посмотреть и зареимплементить, если совсем интересно (ps так и сделал 😊 )
Ссылка: https://www.youtube.com/watch?v=2E54GqF0H4s

Ниже оставляю финальную сравнительную таблицу имлементаций Symbol Tables 💻

Следующие шаги:
1. Обновить цель на smartprogress
2. Начать изучение первой недели

Идем Дальше 💪

Обновил цель на smartprogress. Добавил туда следующие степы по подготовке и материал. Если у вас есть какой-либо полезный материал по темам, присылайте мне, добавим в док 👍

https://smartprogress.do/goal/374957/

День 57 - Графы и геморрой 🙈

Закончил работать над 7ой неделей курса по алгоритмам. Могу сказать, что данная неделя одна из самых сложных пока на курсе. Что проходим?

1. Undirected Graphs
2. Directed Graphs

Теория графов довольно обширная и алгоритмов целая гора. Как мне кажется, материала на курсе не хватает, пришлось брать дополнительно 👨‍🏫 . И так, материал, который я рекомендую для просмотра / прочтения:

Видео с канала гугл инжинера:

1. Введение в теорию графов https://www.youtube.com/watch?v=eQA-m22wjTQ&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P

2. Какие проблемы решают графы - https://www.youtube.com/watch?v=87X57ldq1ok&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=2

3. DFS - https://www.youtube.com/watch?v=7fujbpJ0LB4&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=3

4. BFS - https://www.youtube.com/watch?v=oDqjPvD54Ss&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=4

5. BFS on grid - https://www.youtube.com/watch?v=KiCBXu4P-2Y&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=5

Как подходить к теории на курсере?
Здесь лучший совет будет - имлементировать следующие вещи самостоятельно:

1. UndirectedGraph и DirectedGraph. Отличий на самом деле минимум. Разница только в том, что в первом варианте графа, вершины связаны в обе стороны всегда.

2. Обход в глубину DFS

3. Обход в ширину BFS

4. Топологическая сортировка

5. Connected and Strongly Connected Components

Не поленитесь и имлементируйте все.


————————————
Ассаймент 7ой недели
————————————
Тут нам предстоит написать свой WordNet, программа по поиску однородных слов.

Как начать? 🤔

1. Обязательно посмотреть в чек лист - https://www.cs.princeton.edu/courses/archive/spring19/cos226/assignments/wordnet/checklist.php . В нем содержится подсказки и частые вопросы по имплементации данного задания. Странно, что опять пришлось его искать самостоятельно. Курсере стоит добавить его в ссылки на ресурсы.

2. Дополнительные разъяснения по заданию, ссылка из чеклиста. Лично мне очень помогли, так как после прочтения задания на сайте, я не понимал, что мне надо в итоге сделать. https://www.youtube.com/watch?v=EtPfujaKHwc&feature=youtu.be

3. Советую начать с парсинга файлов с hypernyms и synsets. Используйте необходимые структуры для хранения. Имлементировать ничего не нужно, используйте пакет java.lang и algs4 либу

Cпойлер: HashMap и Digraph

4. Для определения, зациклен ли граф - можно использовать класс DirectedGraphCycle

5. Далее переходим к SAP - Shortest Ancestor Path. Тут главное не за оверинженирить. Существует популярная на лит коде проблема Least Common Ancestors. Которая фактически повторяет то, что пытаемся сделать мы. Есть несколько решений - динамика - одно из них. Не надо его применять. Мы ограничены структурой данных пакета и от нас ожидают наиболее простое решение - наивное 😂

6. c Outcast сложностей возникнуть не должно, это самая простая часть задания.

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

Next Steps - Leecode ❤️

Разминка:
1. https://leetcode.com/problems/find-the-town-judge/

Основная часть:

1. Topological Sort - https://leetcode.com/problems/course-schedule-ii/

2. Cycle Detection - https://leetcode.com/problems/course-schedule/

3. Check Graph is Bipartite - https://leetcode.com/problems/is-graph-bipartite/

4. Escape Dungeon Problem - https://leetcode.com/problems/escape-a-large-maze/

5. DFS - https://leetcode.com/problems/find-eventual-safe-states/

Идем дальше 💪

День 60 - Решаем литкод 🤔

В связи со временным переездом в другой город ✈️, смог приступить к задачам только сегодня. Решил 4 задачки на графы.

Разобью задачи по типу проблемы:

Немного размяться:

997. Find the Town Judge

Простенькая задачка, чтобы по-упражняться на графах. Комментарии не требуются 😄

Топологическая сортировка и поиск цикла в графе.

1. 207 - Course Schedule
2. 210 - Course Schedule II

Обе задачи сводятся к тому, чтобы топологически отсортировать граф. В первой, просят определить можно ли это сделать, во второй вывести отсортированный массив. Тут надо просто один раз изучить алгоритм топологический сортировки, я взял Kahn's Algorithm, разобрал его и реализовал обе задачи. Алгоритм очень простой 👍

Рисуете все на листочке или доске, проделываете каждый шаг. Так хорошо запоминается и укладывается все в голове.

Определение двудольного графа ( Bipartite Graph )

785. Is Graph is bipartite

Интересная задачка. Тут просто нужно разобраться что такое Bipartite Graph и как он выглядит.

Поможет: https://www.geeksforgeeks.org/bipartite-graph/

У меня ушло примерно по 30-40 минут на каждую задачу. Но сейчас, скорость решения не преследую, главное закрепить теоритический материал.

Что дальше ? 🙈
1. https://leetcode.com/problems/escape-a-large-maze/
2. https://leetcode.com/problems/find-eventual-safe-states/

Всем stay home и не болеть, сейчас это актуально, как никогда 💪

День 62 - Закончил решать задачки на графы ☄️

Сегодня решил 2 задачки:

1036 - Escape a large maze ( hard 🤔 )
Задача хоть и с пометкой - hard, но не является сложный. Перед нами Dungeon Problem aka Maze. - матрица миллион на миллион. Нам нужно понять, можно ли найти выход. Основная сложность, оптимизировать, чтобы не искать путь полностью и выбрать правильные эвристику для оценки

Если сложно, помогут вот эти ссылки. Там нет решения задачи, скорее полезный материал👇:
1. https://www.youtube.com/watch?v=KiCBXu4P-2Y&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=5 - BFS on grid
2. https://cs.stanford.edu/people/abisee/gs.pdf - Презентация стенфорда рассматривающие основные алгоритмы поиска путей

Ну и на крайний случай, ссылка на мое решение на JS с комментами:
https://leetcode.com/problems/escape-a-large-maze/discuss/561992/Javascript-BFS-solution-with-explanation

802. Find Eventual Safe States

Тут отрабатывается стандартный DFS. Задача показалась не очень сложной. Ссылка на решение:
https://leetcode.com/problems/find-eventual-safe-states/discuss/562069/Easy-to-understand-Javascript-solution

В общем, после решение набора задачек на графы, чувствую себя на много увереннее в теме. Готов приступать к 8 Неделе курса по алгоритмам 💪

Следующие шаги:
1. Начать 8 неделю курса
2. Обновить материалы на smartprogress

Всем хороших выходных 👍

День 67 - Конец теории 8ой недели - Часть 1 🤔

Закончил изучение теории 8ой недели - Shortest Paths, Minimum Spanning Tree. Неделя очень насыщенная и интересная в плане теории.

Разберем каждую тему по порядку👇

Minimum Spanning Tree
Тут Сенджвик дает нам intro в Greedy 👨‍🏫 алгоритмы, которое мне показалось совсем недостаточным чтобы понять основную концепцию.

Отличное пояснение дает Abdul Bari вот здесь👇
https://www.youtube.com/watch?v=ARvQcqJ_-NY&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=40&t=0s

Далее разбираются основные алгоритмы для нахождения Minimum Spanning Tree - далее MST.

Kruskal's Algorithm
На практике, довольно простой алгоритм. Советую имлементить его в ходе прохождения курса.

Чтобы максимально эффективно разобраться с ним, нам понадобится👇

1. Знание структуры Union Find прямиком из 1ой недели - используется, для того того чтобы эффективно понять, что вершина уже в MST
2. Знание приоритетной очереди - Priority Queue из 4ой недели - Сортирует ребра по весу
3. Имлементация взвешенного графа. Единственное отличие от обычного - ребро представляется в виде объект Edge(v,w,weight).
4. Сам алгоритм - Сенджвик довольно понятно его объясняет.

Полезный материал, который поможет👇
https://www.youtube.com/watch?v=4ZlRH0eK-qQ&t=700s

Prims's Algorithm - lazy version
Отличается от Крускала тем, что тут мы начинаем с 0 вершины и идем по графу по соседним вершинам, кладя ребра в приоритетную очередь. Требования к знаниям такие же как в случае с Крускалом. Имеет один drawback, для того, чтоы обновить вес ребра, приходится класть в MinPQ дубликат. Фиксится с использованием eager версии алгоритма.

Полезный материал👇
1. Prim's explanation https://www.youtube.com/watch?v=jsmMtJpPnhU&t=193s
2. Abdul Bari example https://www.youtube.com/watch?v=4ZlRH0eK-qQ&t=700s

Prims's Algorithm - eager version 😳
А вот тут я немного приуныл. Алгоритм несложный, основное отличие, что мы избегаем хранения дублируемых ребер, которые кладем в приоритетную очередь, путем использования IndexPriorityQueue 🤯. Это небольшое расширение над обычной PQ, которая позволяет нам эффективно изменять приоритет элементов, которые мы храним в ней.

Странно, что Сенджвик не разбирает это на 4 неделе. Для того, чтобы полностью понять, как все работает, советую самостоятельно ее заимплементить. Потратьте на это время, очень поможет!

Материал для погружения👇
1. Index PQ https://www.youtube.com/watch?v=DT8xZ0Uf8wo
2. Prims Eager version - https://www.youtube.com/watch?v=xq3ABa-px_g

Конец 1 части 👨‍🏫

День 68 - Конец теории 8ой недели - Часть 2

Краткий обзор второй части теории недели 🤔 Данная часть знакомит нас с основными алгоритмами поиска кратчайших путей в графе:

1. Алгоритм Дейкстра
2. Алгоритм для Edge Weighted Acyclic Graph на основе топологической сортировки
3. Алгоритм Беллмана-Форда

Сами алгоритмы несложные и легко реализуются, и в целом похожи немного друг на друга. Ниже приложил полезные материалы по каждому из них:

Дейкстра:
1. Abdul Bari - https://www.youtube.com/watch?v=XB4MIexjvY0&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=45
2. William Fillset https://www.youtube.com/watch?v=pSqmAO-m7Lk&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=15&t=760s

Здесь нам снова понадобиться IndexMinPQ, поэтому советую, если не изучили, посмотреть материал на эту ДС

DAG:
1. William Fillset - https://www.youtube.com/watch?v=TXkDpqjDMHA&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=13

Беллман-Форд
1. William Fillset - https://www.youtube.com/watch?v=lyw4FaxrwHg&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=16

Советую также уделить особое внимание алгоритму Дейкстра, так как он необходим для выполнения задания 8ой недели 👨‍🏫

Ниже прикладываю небольшое саммари по использованию каждого из алгоритмов. Слайд из презентации Сенджвика:

День 68 - Конец ассаймента 8ой недели ☄️

Завершил задание 8ой недели - Seam Carver 🎉 Задача решает проблему content-aware image resizing - изменение размера картинки с сохранинием наиболее важных частей контента, путем расчета "энергии" пикселя

Мне понравилась задача, особенно зная, что данный алгоритм применяется внутри современных графический редакторов. и самое главное, она решается с помощь графов и алгоритма поиска кратчайшего пути Дейкстра 👨‍🏫 На первый взгляд, задача кажется сложной, но достаточно внимательно вчитаться и начать имлементить простые методы - станет легче 😊

Как начать и не сдаться? 💪

1. Повторяем алгоритм Дейкстра для поиска SP

2. Имлементим первые методы SeamCarver
- getPicture() - возвращаем копию картинки
- width() - возвращаем ширину картинки
- height() - возвращаем высоту картинки
- energy(x, y) - расчитываем по формуле из задания энергию пикселя
- SeamCarver конструктор, в двумерный массив, записываем энергию каждого пикселя

3. Тестим расчет энергии через утилитный класс ShowEnergy, который идет в комплект к заданию вместе с файлами для тестов

4. Далее переходим к самому сложному:
- findVerticalSeam() - seam - это полоса пикселей, которую мы можем "вырезать" из картинки. По-сути это поиск кратчайшего пути, где весом является энергия пикселя. Ищем этот кратчайший путь, записываем номера колонок и возвращаем.

- transponse() - просто переворот картинки, для того, чтобы не имлементить findHorizontalSeam()
- findHorizontalSeam() - Делаем transpose() картинки и вызываем findVerticalSeam()

На этом основные методы закончились, удаление removeHorSeam & removeVerSeam, не представляют сложности, по-сути это просто копирование массивов исключая наши horizontal & vertical seam.

Следующие шаги:
1. Обновить материалы на smart-progress 👨‍🏫
2. Решить: https://leetcode.com/problems/network-delay-time/
3. Решить: https://leetcode.com/problems/cheapest-flights-within-k-stops/
4. Начать 9ую неделю курса ☄️

Идем дальше 💪

День 70 - Начало 9 недели

Закончил решать задачки:
1. https://leetcode.com/problems/network-delay-time/
2. https://leetcode.com/problems/cheapest-flights-within-k-stops/

Обе задачи являются неплохой практикой по практике алгоритмов Shortest Paths в графе. Нужно выбрать алгоритм, который вам нравится 🤔

1. Дейкстра
2. DFS
3. Беллман-Форд

Я выбрал Bellman-Ford, так как он не требует использования Priority Queue для решение задачи. В JS нет стандартной имлементации этой ДС 😔. Поэтому, если вы на джаве или шарпах, то Дейкстра для вас не проблема.

Min cut - Max Flow

Также, начал теорию 9ой недели. Как я понимаю, это заключительная часть по графам на курсе 🎉

Следующие шаги:
1. Закончить 1 тему недели Min cut - Max Flow
2. Выполнить assignment Baseball Elimination

Идем дальше 💪