A visual proof for an average case of list searching

ABSTRACT

This paper describes how the more mathematical topics in the data structures curriculum can be illustrated with visual proofs. This frees students from difficult algebraic manipulation. Visual proofs are provided for the average case of searching for a unique item in a list and for searching for an item which occurs independently (and not necessarily uniquely) in the list with a known probability.

REFERENCES

• 1: Joint Task Force on Computing Curricula, Computing Curricula 2001, IEEE-CS and ACM, Appendix B, Dec. 15, 2001, pg. 165.
• 2: Roger B. Nelsen, Proofs without Words ---Exercises in Visual Thinking, Mathematical Association of America, Washington D.C., 1993, ISBN: 0-88385-700-6 pg 69.
• 3: Michael T. Goodrich , Roberto Tamassia, Teaching the analysis of algorithms with visual proofs, Proceedings of the twenty-ninth SIGCSE technical symposium on Computer science education, p.207-211, February 26-March 01, 1998, Atlanta, Georgia, United States
• 4: Tall, D, The Cognitive Development of Proof: Is Mathematical Proof For All or For Some?, Z. Usiskin (Ed.), Developments in School Mathematics Education Around the World, vol, 4, 117--136. Reston, Virginia: NCTM.
• 5: Borwein, P. and Jörgenson, L., 2001, Visible Structures in Number Theory, The American Mathematical Monthly, vol 108(10) 897--910, MAA.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
analysis of algorithms, computer science education, data structures