Using O(n) ProxmapSort and O(1) ProxmapSearch to motivate CS2 students, Part II

ABSTRACT

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, previously discussed in Part I of this paper, and ProxmapSearch, discussed here.

REFERENCES

• 1: Thomas A. Standish, Data Structures, Algorithms, & Software Principles in C, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 2: Thomas A. Standish, Data Structures, Algorithms, & Software Principles in C, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 3: Thomas A. Standish, Data Structures in Java, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 4: Feller, W., An Introduction to Probability Theory and Its Applications, Vol. I, Wiley, New York, 1957.
• 5: Knott, G. D., Hashing Functions, Computer Journal, 18:3, pp. 265--278, Aug. 1975.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Computer science education

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.m Miscellaneous

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Curriculum

General Terms:
Algorithms, Management

Keywords:
CS2, ProxmapSearch, ProxmapSort, searching, sorting