The Match: A Case Study In Algorithm Analysis Of The National Resident Matching Program

Abstract

There are rare opportunities when solving an easily-understood problem can bring together application of skills taught in diverse courses in a Computer Science (CS) or Management Information Systems (MIS) program. This paper presents such an opportunity in the typical database management systems course taught at the junior or senior level. Specifically, we describe the case study of solving the classical Hospitals/Residents problem in Microsoft Access. The solution, based on classical Gale-Shapely algorithm for the Stable Marriage problem, offers pedagogical opportunities in data modeling, algorithm and data structure considerations for program development, Visual Basic for Applications (VBA) and embedded SQL (Structured Query Language) programming, and empirical analysis of running time complexity of algorithms that work remarkably well in teaching students the value of each tool in the toolset they take away from required courses as a part of their undergraduate education in CS or MIS.