Buffer pools and file processing projects for an undergraduate data structures course

ABSTRACT

This paper presents a family of programming projects appropriate to a sophomore-level data structures course, centered around the concept of a buffer pool serving as the access intermediary to a disk file. These projects provide a meaningful vehicle for practicing object-oriented design techniques and teach fundamental material on file processing and manipulating binary data. I begin with a concrete example, a heap stored on disk and mediated by a buffer pool. Several important intellectual concepts introduced by such a project are enumerated. Significant extensions and alternatives to the basic project are then described. I conclude with some observations on the role of file processing in modern CS curricula, and the significance of recent trends away from coverage of these topics.

REFERENCES

• 1: Dan Aharoni, Cogito, Ergo sum! cognitive processes of students dealing with data structures, Proceedings of the thirty-first SIGCSE technical symposium on Computer science education, p.26-30, March 07-12, 2000, Austin, Texas, United States
• 2: Frederick P. Brooks, Jr., The Mythical Man-Month: Essays on Softw, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 3: Department of Computer Science, Virginia Tech. CS2604 data structures and file processing website. Available at courses.cs.vt.edu/~cs2604, 2003.
• 4: Michael T. Goodrich , Roberto Tamassia, Data Structures and Algorithms in Java with Cdrom, John Wiley & Sons, Inc., New York, NY, 1998
• 5: J. T. on Computing Curricula. Computing curricula 2001 computer science final report, Dec. 2001.
• 6: Bruno R. Preiss, Data structures and algorithms with object-oriented design patterns in C++, John Wiley & Sons, Inc., New York, NY, 1998
• 7: Clifford A. Shaffer, A Practical Introduction to Data Structures and Algorithm Analysis, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 8: Thomas A. Standish, Data Structures in Java, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 9: A. Tucker, B. Barnes, R. Aiken, K. Barker, K. Bruce, J. Cain, S. Conry, G. Engel, R. Epstein, D. Lidtke, M. Mulder, J. Rogers, E. Spafford, and A. Turner. Computing Curricula '91. Association for Computing Machinery and The Computer Society of the Institute of Electrical and Electronics Engineers, 1991.
• 10: Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Object-oriented design methods

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Buffering

  E. Data
  E.5 FILES
      Subjects: Organization/structure

General Terms:
Algorithms, Design

Keywords:
buffer pools, data structures, file processing, heaps, object-oriented design