Enseñanza

Teaching Algorithms
R i c a r d o A. B a e z a - ¥ a t e s D e p t o . de C i e n c i a s de la C o m p u t a c i 6 n U n i v e r s i d a d de C h i l e Casilla 2777, S a n t i a g o , C h i l e E-mail: rbaeza~dcc.uchile.cl

Abstract

In this paper we propose and discuss how to teach algorithms, including contents, methodologies, textbooks, and computer labs. We use the ACM/IEEE curricula asa startin~ point and compare our proposal to theirs. We raise several issues, but we do not provide definite answers. Our main proposal is a paradigm driven methodology for the main algorithmic course, as well as some paradigms and problems not usually covered. An ultimate teaching algorithm is still an open problem.

1

Introduction

Algorithms and d a t a structures (just algorithms inthe rest of the paper) are at the h e a r t of c o m p u t e r science, being the building blocks of any software. At the same time, learning how to p r o g r a m goes side by side with algorithms. In this paper we address the issue of teaching algorithms, covering the different courses involved, their contents, their bibliography, etc. A l t h o u g h no specific t e x t b o o k is r e c o m m e nd e d , some of t h e m are compared and m a n y others are referenced. First c o m p u t e r science years are usually t a u g h t dividing contents by topics or t y p e of problems. In algorithms this is also true, but a shift to contents based on paradigms or techniques seems to be m o r e useful for future algorithmic challenges. This allows better design and also raises the i m p o r t a n ce of the analysis of algorithms. We also address briefly the interaction between p r o g r a m m i n g and algorithms. P r o g r a m m i n g p a r a d i g m s are naturally tied to design techniques, and i n t r o d u c t o r y c o m p u t e r science courses, are also usually i n t r o d u c t o r y to algorithms. At the beginning, algorithms j u s t need basic p r o g r a m m i n g techniques.Later, when problem complexity and analysis become i m p o r t a n t , algorithms require discrete m a t h e m a t i c s and theoretical foundations as a u t o m a t a theory and formal languages. At this stage, new software tools should be considered, such as algorithm animation or ad-hoc library classes. Algorithms and d a t a structures is one of the nine subject areas of the A C M / I E E E1991 Computing Curricula [2]. We have used this proposal and [1] as a starting point and we c o m p a r e our proposal to theirs. T h e ideas and suggestions given in this paper might be biased by our own experience in teaching algorithms, the curricula of our university and the fact t h a t we do research on algorithms. A preliminary version of this work was presented as an invited paper in the IVIberoamerican Congress on C o m p u t e r Science Education [7].

51

2

Courses

There are five main goals, given in cronological order: 1. Knowledge of b~ic data structures and their associated algorithms. 2. Understanding of basic algorithmic design techniques. 3. Ability to apply mathematical tools to analyze algorithms. 4. Understanding of problem complexity classes. 5. Knowledge ofadvanced data structures, design and analysis techniques, and novel algorithmic areas. Although all of these goals are important, the first two are completely necessary. The approximate contents associated to the goals above, giving between parentheses the corresponding knowledge units (this subject is denoted by AL) of the ACM/IEEE curricula, are: 1. Data structures: arrays, queues, linked lists,search trees, graphs (ALl, AL2). 2. Searching and sorting algorithms (AL6). 3. Design techniques: induction, divide and conquer, dynamic programming, recursion, heuristics, randomization, use of finiteness 1 (AL3, AL8).
4. Analysis: recurrences, order notation, basic analysis tools, lower bounds (AL4).

5. Problem complexity: NP-complete problems and basic time and space complexity classes...