## CSci 3501 Algorithms and Computability - Lab 5.

#### September 22nd. Due Wednesday, September 28th at 11:59pm

What to submit and when:

• All submissions are electronic: by e-mail to and CC to all lab partners. Please do not delete your e-mail from "Sent mail" or your mailbox until the end of the semester.
• When working on the lab, please comment your work so that it is clear what contributions of each person are.
• At the end of the lab each group should send me the results of their in-class work. Please indicate if this is your final submission.
• If your submission at the end of the lab time was not final, please send me(CC to the lab partner(s)) a final copy before the due time. Please use the subject "3501 Lab N", where N is the lab number.

### Lab assignment

Work in pairs

Matching problem (30 points). Your task is to design and implement an algorithm that finds a solution to the following problem:

N programmers are looking for a job; N companies are looking to hire a programmer. Each programmer has a ranking of the companies based on his/her preferences for a workplace. Likewise, each company has a ranking of the N programmers based on whom they would like to hire.

Given a set of rankings, it may be impossible to find a pairing of programmers with companies when everyone gets their first choice (what would be an example of such ranking, among, say, 3 programmers and companies?). However, it is always possible to find a satisfactory pairing. A pairing of programmers with companies is called satisfactory if there is no pair of assignments (P1, C1), (P2, C2) (denoting programmers as P and companies as C) such that P1 ranks C2 higher than C1 and C2 ranks P1 higher than P2 (in other words, P1 can switch to C1 to increase both their own and C1's level of satisfaction).

Below is an example of preferences of five companies A, B, C, D, E and five programmers 1, 2, 3, 4, 5:

A B C D E 1 2 3 4 5
2 1 5 1 2 E D D C A
5 2 3 3 3 A E B B D
1 3 2 2 5 D B C D B
3 4 1 4 4 B A E A C
4 5 4 5 1 C C A E E
The pairing A1 B3 C2 D4 E5 is unsatisfactory since A prefers programmer 2 to programmer 1 and programmer 2 prefers company A to company C. Find a satisfactory pairing; you may use it as your test example.

1. Develop an algorithm that, given preferences for N programmers and N companies, finds a satisfactory pairing. If there is more than one satisfactory pairing, you need to find just one.
2. Implement your algorithm and test it on several cases of preferences. It does not matter how your algorithm takes data, but you should clearly explain this in the documentation so that we know how to test it. Also make sure to document all your test cases and results. Check that the pairings found by your program are satisfactory (write a method to do this to save yourself some time).
3. Explain why your algorithm is correct (i.e. it always stops and outputs a satisfactory pairing). You don't need to go into low-level details of your program, but your argument must be precise enough to convince someone who has not seen your program before that it is indeed correct.

1. Correct non-cyclic algorithm: 15 points
2. Programming aspects: data structures used, input/output, code style, clarity, documentation, etc.: 5 points
3. Testing: 3 points
4. Efficiency evaluation and correctness discussion: 7 points