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

Sign in to queue

More episodes in this series

Related episodes

The Discussion

  • User profile image
    ivan_

    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.

    Thanks!!!

     

     

  • User profile image
    Heavens​Revenge

    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
    ivan_

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

    Thanks!

Add Your 2 Cents