C9 Lectures: Yuri Gurevich  Introduction to Algorithms and Computational Complexity, 2 of n
Description
Yuri Gurevich is back on C9!! Yuri is a logician, computer scientist and inventor of abstract state machines. He currently works at Microsoft Research (he's a member of Wolfram Schulte's RiSE team).
This is the second part in a series of lectures exploring the fundamental logicrecipe powering all that we do as software engineers and computer scientists—the algorithm. What is an algorithm? You may be surprised to learn that this is not a simple question. Nonetheless, in this video, Yuri presents an answer—one that is perhaps somewhat controversial in nature—based on his own research and philosophy.
Thank you, Yuri, for taking the time to share your extensive knowledge and gentle, kind spirit with Niner Nation. We all really appreciate it! Thanks, too, to Wes Dyer and Bart De Smet for being our live audience for this lecture and asking great questions!
See Part 1
See Part 3
Download
Right click or Alt+Enter to download this episode
 High Quality WMV (607.0 MB)
 MP3 (27.4 MB)
 Mid Quality WMV (346.5 MB)
 High Quality MP4 (1.0 GB)
 Low Quality MP4 (146.9 MB)
The Discussion

Moved into a new house, with no broadband, yet and am using the wifi on my phone, so if ever there was a need to get my connection back...this is it!

this is going to be the best 1 hour in recent time.... I can listen to him all day long.. non stop...
teachers like him make the difference...
I just admired the way explain things with simple examples... simply awesome...

Wes and Bart will be present at the filming of part 3 as well (and maybe an Italian friend of mine with really long, wavy black hair...). In this case, questions were asked at the end of Yuri's presentation. Next time, they will be asked after the topical segments complete (like we did in the first part).
C

Was wondering when the second part would come out. Thanks for this...
If he works for MS Research, does this mean maybe less than a year between segments? Maybe if you guys gave him cookies as incentive? Like really, really good cookies. His presentation style is superb and just can't get enough of him. When talking abstract concepts, how it's delivered really matters. Maybe i can find one of those makeawish cancer kids that likes comp.sci.....
So i guess i'm kinda asking if you guys are gonna try to get a loose schedule (1vid:1month, 1vid:3months) I love these Going Deep shows and Lecture series especially. 
Interesting classification of algorithms into linear, parallel, etc.
I suppose in future we will have to contend with quantum algorithms (as in quantum computing).
Here is an interesting talk on a quantum algorithm that is supposedly faster than its classical equivalent.

@HumanBlade: As you can imagine, Yuri is a very busy guy... We will be filming the next episode at the end of March and it will ship shortly thereafter.
C

Please ask Yuri to use 16 point font, rather than 10 point...

It seems that discussion about "sameness" of two or more algorithms has no point unless participating parties agrees on what sameness means. Which it turn requires definition of a meta algorithm to measure various properties of algorithms of interest and compute measure of sameness. So, question "are two algorithm the same" has no aswer in general case.
For similar reasons, in order to pick a better algorithm, one has to disclose all the constaints and assumptions used to compute measure of "goodness".

As far as I understand, although functions and algorithms have the same "interface", the difference is that algorithms have(/include) states and functions does not, am I right?
Both can have multiple subalgorithms/functions.The problem of the sameness is just that we can't define the precise captured begin and end states of the algorithms,
If the universe is the "main state"... The evolution is just an algorithm, state transforming to another through various substates.
We can use monadic bind to combine functions, so that is also true to algorithms, right? (like in the PDC presentation of F# 3.0, which shows the similarity between compilers and search engines.)

Hi Charls,
Can you upload the slides of this lecture?
Thanks 
hi there, it seems this talk went offline. all videos/audio are unavailable (404).
Is there a chance of putting them back online?
Thanks,
pablo.