On Application Of Stable Matching Algorithm :

Ahmed Hassan Ahmed Abu El-atta

In this thesis, we study some types of matching problems. Matchingproblems involve a set of participants, where each participant has a capacityand ranking a subset of the others in order of preference (strictly or withties). Matching problems are presented in practice by large-scaleapplications, such as automated matching schemes, which assignparticipants together based on their preferences over one another. In ourwork we focus on the two-sided matching problems. Two-sided matchingproblems consist of a two disjoint sets of participants, where each participanthas a capacity and also ranks a subset of the other set of participants in orderof preference (strictly or with ties). In the thesis we present a new model forone problem of two-sided matching problems which is the student projectallocation problem.To help in understanding our work we use visualization. Visualization is the process of transforming information into a visual form, enabling users to observe the information or we can say visualization is any technique for creating images, diagrams, or animations to communicate a message. We understand a message much faster when seeing a picture instead of reading, or hearing, an equivalent textual description, in our daily life. So by using visualization to explain a new algorithm will help to understanding it.In chapter 1, we give a brief review on visualization. In that chapter we describe some different methods to visualize an algorithm and also we give some example on the visualization.iiIn chapter 2, we discuss the famous matching problems. We first give some important definitions for matching problems then we give a simple review on some of the famous matching problems, like stable marriage problem, resident hospitals problem, and stable roommate problem.In chapter 3, we give a brief review on the previous models for the student project allocation problem. We start with the trivial models like Simplified Model for Student-Project Allocation Problem and One Side Student Project Allocation Problem. After that we discuss two previous models, first one is the Student-Project Allocation Problem with preference lists over students in that model lecturer supply preference lists over students and the second was Student-Project Allocation Problem with preference lists over Projects in that model lecturer supply preference lists over projects.In chapter 4, we present our new model for the student project allocation problem. In our model lecturers supply preference lists over (student, project) pairs. We also present an algorithm to solve the new model and also present a new data structure to change the way of storing the preference lists in the memory to reserve the space that was needed for the preference lists.In chapter 5, we present our visualization for the new model the student project allocation problem with preference lists over (student, project) pairs. In this visualization we use applet in the java programming language