OLYMPIADS IN INFORMATICS, 2011, Vol. 5, 58-71
© 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
Abstract
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.
Keywords:
teaching, secondary school, online algorithms, competitive analysis
To preview full
article text in PDF format click here
You
could obtain free Acrobat Reader from Adobe
Copyright © Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2011
