Songs and the analysis of algorithms

ABSTRACT

In teaching a course that includes the analysis of algorithms, songs can be used as teaching examples. Multiple examples can be done at one time, or in one homework set, without the background explanation required to analyze real algorithms. Many components of algorithm analysis can be introduced using an analysis of songs. This is particularly useful at gaining experience extracting summations from "word problems."

REFERENCES

• 1: D. Best ~: B. Best, Song _Pest, Crown Publishers, New York, 1955.
• 2: K. Eisemann, Letter: "Further Results on The Complexity of Songs", Comm. ACM, 1985, 28(3), 235.
• 3: W. Gasarch, Sample Abstract, Call for papers for the 1993 STOC conference, 1992.
• 4: Donald E. Knuth, The complexity of songs, ACM SIGACT News, v.9 n.2, p.17-24, Summer 1977 [doi>10.1145/1008354.1008355]
• 5: Donald E. Knuth, The complexity of songs, Communications of the ACM, v.27 n.4, p.344-346, April 1984 [doi>10.1145/358027.358042]
• 6: D. Pinsky, Finger Plays and Action Verses for Chzldren, Cooperative Extension Service, Iowa State University, 1977.
• 7: W. W. Newel1, Games and Songs of Amemcan Chzldren, Harper ~ Brothers, 1883. Reprinted by Dover, 1963, and by ClearfieId, 1992.

INDEX TERMS

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

General Terms:
Theory