Teaching algorithms

ABSTRACT

In this paper we propose and discuss how to teach algorithms, including contents, methodologies, textbooks, and computer labs. We use the ACM/IEEE curricula as a starting point and compare our proposal to theirs. We raise several issues, but we do not provide definite answers. Our main proposal is a paradigm driven methodology for the main algorithmic course, as well as some paradigms and problems not usually covered. An ultimate teaching algorithm is still an open problem.

REFERENCES

• 1: Peter J. Denning , D. E. Comer , David Gries , Michael C. Mulder , Allen Tucker , A. Joe Turner , Paul R. Young, Computing as a discipline, Communications of the ACM, v.32 n.1, p.9-23, Jan. 1989 [doi>10.1145/63238.63239]
• 2: Allen B. Tucker, Computing Curricula 1991, Communications of the ACM, v.34 n.6, p.68-84, June 1991 [doi>10.1145/103701.103710]
• 3: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 4: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 5: Sara Baase, Computer algorithms: introduction to design and analysis (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 6: [6] R. Baeza-Yates, "Searching: An Algorithmic Tour", Technical Report, Dept. of Computer Science, Univ. of Chile, 1995.
• 7: [7] R. Baeza-Yates, "Teaching Algorithms", IV Iberoamerican Congress on Computer Science Education, Canela, Brazil, July 1995.
• 8: Lesek Banachowski , Antoni Kreczmar , Wojciech Rytter, Analysis of Algorithms and Data and Structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 9: Gilles Brassard , Paul Bratley, Algorithmics: theory & practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 10: Marc H. Brown , Robert Sedgewick, Progress report: Brown university instructional computing laboratory, ACM SIGCSE Bulletin, v.16 n.1, p.91-101, February 1984
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: Maxime Crochemore , Wojciech Rytter, Text algorithms, Oxford University Press, Inc., New York, NY, 1994
• 13: Jeffrey Scott Vitter , Philippe Flajolet, Average-case analysis of algorithms and data structures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 14: T. J. Fountain, Parallel computing: principles and practice, Cambridge University Press, New York, NY, 1994
• 15: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 16: Alan Gibbons , Wojciech Rytter, Efficient parallel algorithms, Cambridge University Press, New York, NY, 1988
• 17: [17] D. Goldberg, "Genetic Algorithms", Addison-Wesley, 1989.
• 18: G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 19: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 20: David Gries , Fred B. Schneider, A logical approach to discrete math, Springer-Verlag New York, Inc., New York, NY, 1993
• 21: David Gries, Teaching calculation and discrimination: a more effective curriculum, Communications of the ACM, v.34 n.3, p.44-55, March 1991 [doi>10.1145/102868.102870]
• 22: David Harel, Algorithmics: the spirit of computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 23: Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
• 24: T. C. Hu , M. T. Shing , Y. S. Kuo, Combinatorial Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 25: [25] D.E. Knuth, "The Art of Computer Programming", vol. 1, "Fundamental Algorithms", Addison-Wesley, 2nd ed., 1973.
• 26: [26] D.E. Knuth, "The Art of Computer Programming", Vol. 3, "Sorting and Searching", Addison-Wesley, 1973.
• 27: Dexter C. Kozen, The design and analysis of algorithms, Springer-Verlag New York, Inc., New York, NY, 1992
• 28: Lydia Kronsjo, Algorithms: Their Complexity and Efficiency, John Wiley & Sons, Inc., New York, NY, 1979
• 29: Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• 30: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 31: Harry R. Lewis , Larry Denenberg, Data Structures and Their Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 32: Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 33: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 34: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 35: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 36: Jurg Nievergelt , Klaus H. Hinrichs, Algorithms and data structures: with applications to graphics and geometry, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 37: Ian Parberry, Problems on algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 38: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 39: [39] Blaine A. Price, Ronald M. Beacker and Ian S. Small, A Principled Taxonomy of Software Visualization, Journal of Visual Languages and Computing 4, 211-266, 1993.
• 40: Paul Walton Purdom, Jr. , Cynthia A. Brown, The analysis of algorithms, Holt, Rinehart & Winston, Austin, TX, 1985
• 41: Michael J. Quinn, Parallel computing (2nd ed.): theory and practice, McGraw-Hill, Inc., New York, NY, 1994
• 42: Gregory J. E. Rawlins, Compared to what?: an introduction to the analysis of algorithms, Computer Science Press, Inc., New York, NY, 1992
• 43: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• 44: Joseph O'Rourke, Computational geometry in C, Cambridge University Press, New York, NY, 1994
• 45: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 46: Betty Salzberg, File structures: an analytic approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 47: Bruce Schneier, Applied cryptography (2nd ed.): protocols, algorithms, and source code in C, John Wiley & Sons, Inc., New York, NY, 1995
• 48: David Skillicorn, Foundations of parallel programming, Cambridge University Press, New York, NY, 1995
• 49: [49] S. Smith, "Design and Analysis of Algorithms", PWS-Kent, 1989.
• 50: Douglas R. Stinson, Cryptography: Theory and Practice, CRC Press, Inc., Boca Raton, FL, 1995
• 51: Gerard Tel, Introduction to Distributed Algorithms, Cambridge University Press, New York, NY, 1995
• 52: Mark Allen Weiss, Data structures and algorithm analysis, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1992
• 53: Herbert S. Wilf, Algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 54: Niklaus Wirth, Algorithms & data structures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

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

General Terms:
Design, Human Factors, Management, Performance, Theory