Stanford Lecture - Strong Components and Weak Components, Dr. Donald Knuth I 2024

[@markxavior]

Honorary senior doctor Knuth. Nice to see you. Give my wishes to him and i wish lots of health to him 🎉🎉🎉.

[@yuedaniel2921]

Its great and fantastic Dr Knuth is still around and teaching Thank you very much

[@Ken-t1w]

Literally my favorite Christmas gift. Here's to many more years!!

[@clarecampbell4481]

Thank you for posting this!

[@zartajmajeed]

This talk is on Algorithm T (Strong components) from The Art of Computer Programming, Vol 4, 7.4.1.2 - currently available as Pre-Fascicle 12A. The algorithm is presented at 1:11:04 - Knuth has improved on Tarjan's algorithm, lowering worst-case bounds from 7m for Tarjan to 5m - where m is number of edges. Separately Tarjan - with Zwick - published an improved version of his own algorithm in 2024 that has bounds of 3m. Both new versions involve much collaboration between Knuth and Tarjan. There's an incredible amount of motivation and historical context in this talk. And it's chockful of personal reminiscences by Knuth.

[@jiaai1385]

Greatly Thank you very much！

[@zartajmajeed]

1:14:43 - "Well, I've been quoted saying that premature optimization is the root of all evil in programming. But this was not premature optimization. This was postmature optimization"