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

Play C9 Lectures: Yuri Gurevich - Introduction to Algorithms and Computational Complexity, 3 of 3
Sign in to queue


The great Yuri Gurevich is back!! Smiley Yuri is a logician, computer scientist, and inventor of abstract state machines. He currently works in Microsoft Research (he's a member of Wolfram Schulte's RiSE team).

This is the third and final part in our introductory series of lectures exploring the fundamental logical construct that powers all that we do as software engineers—the algorithm.

In part 3, Dr. Gurevich teaches us about bounded complexity and the axiomatic definition of sequential algorithms.

Find some time to watch this. You'll be learning about algorithms from one of the world's premiere minds in the science of logic and algorithms. In this lecture, Yuri references a few of his academic papers, which you can find here.

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.

Part 1
Part 2



Download this episode

More episodes in this series

Related episodes

The Discussion

  • User profile image

    This is great!

    Thank you, Charles, Yuri, Wes and Bart!

    It was a very interesting discussion Smiley.

    I still didn't get how a "crash" case is implicitly defined.

    I can understand that mathematical sets don't have duplicate and therefore duplicate values are excluded either by UNION or by { }.

    I can also see how "crash" could be formalized in various ways, I just don't know which would be the most appropriate. So basically I don't see the set constraint or a definition of an "inconsistent set". I think both pairs { (a1,v1), (a1,v2) } in this set are valid mathematically and there needs to be another condition!? I am not sure.




  • User profile image

    Personally I consider that the classical algorithm evolved into a higher order algorithm called a design pattern, which utilizes multiple algorithms together which itself doesn't have a bounded time but makes use of algorithms which do execute in bounded time.

    It was sort of funny how Bart & Wes were trying to specialize the general semantics to fit modern practice and machine architecture so they could connect it with classical computer science. But this is basically just explaining how computer science evolved and the algorithm can be formally defined, even though we just have basic common knowledge of this if we program, but as this lecture shows, the math and science and formal explanation shows how computing can indeed be complex and its great that we can abstract away the need for knowing all this to create a massive learning curve.

    @ivan_ I've understood the meaning of "crash" to be interchangeable with "fail". So things fail and don't work which implies a crash to happen and being invalid. But that is just my understanding and not his formal explanation on the subject.

  • User profile image

    It is implicit. Yuri calls it "inconsistent set" where at least two of the pairs have the same location such as in my example { (a1, v1), (a1, v2)}, where a1 is a location and v1 <> v2. In this case crash occurs. So we can define it something like that (sorry no math notations in here just English):

    for every Ai where i = {1..k} and k < (infinity), there exists at least two tuples in the form (A, V)i,  where Aj = Al, while Vj <> Vl and j <> l,  and j,l = {1..k}.

    This to me would be a definition of a "crash" or inconsistent state. I think (which doesn't bear a lot of weight Smiley ).


Add Your 2 Cents