Allan Borodin talk - Fields CRM-PIMS prize

Today, I'm in the Fields CRM-PIMS prize talk by Allan Borodin, a professor in Computer Science at the University of Toronto. The talk is on Understanding Simple Algorithms: Toward a More Systematic Study of Algorithms. He is looking into an attempt of a more systematic study of algorithms. Typical algorithms courses deal with big three (simple, greedy, dynamic programming), search algorithm, combinatorial algorithms, but they don't deal with the actual topic of algorithms. So the question is then who cares about algorithms because you can't really give a formal definition. A second thing is that it has been done before. Algorithms have been used in social networks as that done by Jon Kleinberg. Many greedy algorithms deal with maximizing a submodular function. Sometimes there is no maximum cost function in the study of greedy algorithms. In algorithm, you can't capture everything but you want to capture the majority of all cases.

The algorithm should be easy to explain to others and be able to be formalized. Allan explained about his framework for priority algorithms that help to explain greedy algorithms. An example that he gave is to schedule athletes to do biathlon where they do swimming first in one lane and then biking. One example that he is describing is interval scheduling.