Jason (jcreed) wrote,

Dang, the proposal talk needs some serious work still. Summarizing "The Twelf Worldview" enough to go on and say things that only really make detailed sense within it is damned hard, even though I have tried to do it a zillion times. Also I need to stop totally freezing up when I start getting embarrassed about things not making enough sense.

Before that I saw a talk by Erik Demaine about adaptive analysis of algorithms, which was very neat. The basic idea is analyzing algorithms in terms of measures other than just problem size. So, in terms of list length, sorting is Θ(n lg n) — you can't do any better than that bound, and you can achieve it. If you categorize unsorted lists by a D standing for how "unsorted" they are, you can derive more refined lower bounds, (it's something Θ of an expression involving n and D) and devise algorithms that have not only good worst-time performance, but be guaranteed to perform better on easier examples. The really cool stuff is that there is a "difficulty" measure for sorting that is somehow universal — optimality with respect to the all the other difficulty measures follows from optimality with respect to it.
Tags: talks
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded