© Institute of Mathematics and Informatics,

ISSN 1822-7732

Teaching the Concept of Online Algorithms

Dennis KOMM

Department of Computer Science ETH Zurich, Switzerland E-mail: dennis.komm@inf.ethz.ch


The term algorithm is well-defined: It is the formal description of a strategy, which always has to produce a solution for a specific problem. It is probably the most basic concept of computer science and accordingly both the creation and implementation of algorithms are among the most important things students have to learn when dealing with the subject. The situation is usually as follows. Given an input x for some problem P, we are interested in designing an algorithm A that reads x, performs calculations depending on x and creates some output A(x) of some predefined form. Conversely, in many practical applications, this model is actually not accurate. Here, at one specific point in time, only parts of the input are known to the algorithm whereas parts of the output are already needed. We call an algorithm handling such a situation an online algorithm. Among the numerous examples for such situations are parts of any operating system, or routing and scheduling problems.

To the best of our knowledge, teaching the concept of online scenarios and algorithms to secondary school students only received little attention in the past. However, our experiences show that it catches the students' attention when taught in a comprehensive and motivated way. In this paper, we want to propose a strategy of how to introduce online algorithms by explaining the major ideas to students and we further want to share our experiences.


teaching, secondary school, online algorithms, competitive analysis

PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe

Copyright © Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2011