Duplicate Deletion – A Didactical Explanation of an Intricate Algorithm by Teuhola and Wegner

Heinz Dobler, Peter Rechenberg

Publikation: ArbeitspapierArbeits- und Diskussionspapier


Duplicate Deletion is the problem of deleting all those elements from an array that occur more than once. Teuhola and Wegner published an algorithm to solve this problem in linear time with constant space. As their presentation was hard to understand, two other authors tried to explain the algorithm by formal derivation. We found both attempts unsatisfactory. In this paper we try to explain the algorithm in a didactic manner by solving the problem it in three major steps. We stress the key ideas, the algorithm is based on and give the results of some measurements to compare our solution to the original one.
HerausgeberJohannes Kepler Universität Linz
PublikationsstatusVeröffentlicht - 1992