C9 Lectures: Yuri Gurevich - Introduction to Algorithms and Computational Complexity, 2 of n

Sign in to queue

Description

Yuri Gurevich is back on C9!! Smiley 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 logic-recipe 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

Embed

Download

Download this episode

More episodes in this series

Related episodes

The Discussion

  • User profile image
    vesuvius

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

  • User profile image
    freefly

    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...

  • User profile image
    Charles

    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

  • User profile image
    HumanBlade

    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 make-a-wish 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.

  • User profile image
    fwaris

    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.

    http://www.youtube.com/watch?v=gKA1k3VJDq8

  • User profile image
    Charles

    @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

  • User profile image
    dglienna

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

     

  • User profile image
    sokhaty

    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".

  • User profile image
    Thorium

    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 sub-algorithms/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 sub-states.

    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.)

  • User profile image
    Manish

    Hi Charls,

    Can you upload the slides of this lecture?

    Thanks

  • User profile image
    pablo

    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.

Add Your 2 Cents