On finding a stable roommate, job, or spouse: a case study crossing the boundaries of computer science courses

ABSTRACT

The use of real world problems as the basis for assignments in Computer Science courses is attractive for many reasons. At the same time it is difficult to find such a problem that offers the same richness that is found, for example, in sorting or searching. In this paper a problem is presented that has many real-world instances and which is pedagogically attractive at all levels of Computer Science from the level of a non-major's course to that of an advanced algorithms course.

REFERENCES

• Bie91: Alan W. Biermann, An overview course in academic computer science: a new approach for teaching nonmajors, Proceedings of the twenty-first SIGCSE technical symposium on Computer science education, p.236-239, February 1990, Washington, D.C., United States
• DH91: Richard W. Decker , Stuart H. Hirshfield, A survey course in computer science using HyperCard, Proceedings of the twenty-first SIGCSE technical symposium on Computer science education, p.229-235, February 1990, Washington, D.C., United States
• GI89: Dan Gusfield , Robert W. Irving, The stable marriage problem: structure and algorithms, MIT Press, Cambridge, MA, 1989
• GJ79: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• GS62: D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9-15, 1962.
• Knu73: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• Knu76: D.E. Knuth. Mariages Stables. Les Presses de l'Universit~ Montreal, 1976.
• Kor86: James F. Korsh, Data Structures, Algorithms and Program Style, PWS Publishing Co., Boston, MA, 1986
• Mar: David Margolick. Annual race for clerks becomes a mad dash, with judicial decorum left in the dust. New York Times, March 17, 1989.
• MW71: D. G. McVitie , L. B. Wilson, The stable marriage problem, Communications of the ACM, v.14 n.7, p.486-490, July 1971 [doi>10.1145/362619.362631]
• Nat91: National Resident Matching Program, Evanston, Illinois. Handbook for students Participating Through U.S. Medical Schools, April 1991.
• Pat88: Richard E. Pattis, Textbook errors in binary searching, Proceedings of the nineteenth SIGCSE technical symposium on Computer science education, p.190-194, February 25-26, 1988, Atlanta, Georgia, United States
• Pat91: Richard E. Pattis, A philosophy and example of CS-1 programming projects, Proceedings of the twenty-first SIGCSE technical symposium on Computer science education, p.34-39, February 1990, Washington, D.C., United States
• Qui85: Michael J. Quinn, A note on two parallel algorithms to solve the stable marriage problem, BIT, v.25 n.3, p.473-476, 1985 [doi>10.1007/BF01935367]
• Rot84: Alvin E. Roth. The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory. Journal of Political Economy, 92(6):991-1016, 1984.
• Sed90: Robert Sedgewick, Algorithms in C, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Tuc91: Allen B. Tucker, editor. Computing Curricula 1991 Report of the ACM/IEEE-CS Joint Curriculum Task Force. ACM Press, 1991.
• Wir76: Niklaus Wirth, Algorithms & data structures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human information processing

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

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

General Terms:
Human Factors