Using O(n) ProxmapSort and O(1) ProxmapSearch to Motivate CS2 Students (Part Ⅰ)

摘要

Presenting "cool" algorithms to CS2 students helps convince them that the study of data structures and algorithms is worthwhile. An algorithm is perceived as cool if it is easy to understand, very fast on large data sets, uses memory judiciously and has a straightforward, short proof— or at least a convincing proof sketch — using accessible mathematics. To illustrate, we discuss two related and relatively unknown algorithms: ProxmapSort, discussed here, and ProxmapSearch, to be discussed in Part Ⅱ.