Episode 1 - Trees and Diameters
Автор: Algorithms Live!
Загружено: 2016-12-30
Просмотров: 27315
Описание:
This week I will present some properties of trees and how to find useful information about a given tree quickly. I'll also prove the correctness of these techniques.
01:48 - Equivalent definitions of tree
05:00 - Diameter of graph
09:04 - Technique of rooting tree
13:32 - Diameter in O(n) by subtree aggregates
18:37 - Greedy algorithm to find diameter
22:45 - Proof of greedy algorithm
32:28 - Bonus questions for viewers about diameters
33:50 - Remoteness and center of a tree
36:50 - How to find center
38:03 - Proof that center lies on diameter
46:35 - Centroid definition
50:00 - Finding centroid
55:21 - Properties of centroids
57:38 - Counting diameters problem
1:06:05 - Announcements for next week
Thank you to Mikhail Goncharov for the time links!
Повторяем попытку...
Доступные форматы для скачивания:
Скачать видео
-
Информация по загрузке:
