Videos / DSA

Episode 19 of 22 · DSA, end to end

Greedy: when the locally best choice is provably the globally best

Chapters

1. The walker on the hill0:00
2. Sort, scan, commit0:15
3. One pass against a search0:32
4. Nine beats eight0:50
5. A conjecture that compiles1:04
6. The two properties1:21
7. Two hands of cards1:39
8. Find where they disagree1:55
9. Do the surgery2:12
10. Swap until it is G2:26
11. Greedy stays ahead2:43
12. A stuck swap is a bug report2:58
13. One room, one day3:15
14. Earliest start fails3:31
15. Shortest duration fails3:49
16. Earliest finish wins4:07
17. Six lines4:25
18. The exchange, in one line4:42
19. E is everywhere, q is not5:02
20. The code is a tree5:19
21. Merge the two rarest5:34
22. Five merges, in order5:51
23. Two hundred and twenty four6:10
24. The two rarest are siblings6:26
25. The till drawer6:43
26. Sixty three cents7:00
27. One, three, four7:19
28. One, seven, ten7:34
29. Pay a table instead7:52
30. Canonical coin systems8:09
31. Cabling the office8:26
32. The two rules8:43
33. It has a name8:57
34. The theorem, both ways9:16
35. Kruskal, with the proof free9:36
36. Sufficient, not the border9:54
37. The swap or the input10:13

Greedy: when the locally best choice is provably the globally best. A greedy algorithm makes one promise. At every step, take the option that looks best right now, and never reconsider it. Picture a walker who only ever steps uphill. They always re

Mark as watchedSaved in this browser only.