Teaching algorithm efficiency at CS1 level: A different approach

Realizing the importance of teaching efficiency at early stages of the program of study in computer science (CS) on one hand, and the difficulties encountered when introducing this concept on the other, we advocate a different didactic approach in the introductory CS course (CS1). This paper describes the approach as it is used at the Open University of Israel (OUI). The OUI, a distance teaching institution with no prior educational requirements, runs a full-fledged CS program. Because of its open door policy, the dropout rate, especially in introductory courses, as well as the percentage of failures, is very high. Using the new approach has raised the percentage of students who pass the course. The new approach advocates integrating three-part questions which ask not only to identify the algorithmic problem that a given algorithm solves and to analyze its complexity, but also to design a new algorithm that performs the same task, while increasing efficiency by an order of magnitude, not only by a constant factor. The research we conducted to examine the implications of using this approach is described here.