Written solutions to the following problems will be due at the start of class on Thursday, 13th September. You should design and write the solutions independently. You may discuss general course material or clarifications of the problems with classmates. We showed in class that the G-S Algorithm for stable matching terminates after at most n^2 iterations of the while loop. For a two sets A and B of size n, can a particular list of rankings actually result in a quadratic number of iterations? If so, describe what the rankings would look like. If not, argue why no set of rankings would ever result in a quadratic number of iterations. Note, the algorithm does not need to take exactly n^2 iterations, but rather Omega(n^2) iterations, meaning 0.1 n^2 would be sufficient to show your claim.

Next, can a particular set of rankings result in strictly less than a quadratic number of iterations? Can you design an input that requires O(n) iterations? If so, describe the structure of this input. If not, argue why this is not possible. Finally, can you design an input that takes fewer than n iterations? Why or why not?

Aim for clarity and conciseness in your write up of this problem. You should have all the necessary tools to express your solutions. You do not need formal proofs or psuedocode, but you should be able to clearly articulate your ideas in plain English.

A group of n Portland Hipsters H={h1, h2, ..., hn} are touring a set of local coffee shops C={c1, c2, ..., cn}, over the course of m>=n days. Each hipster hj chooses an itenerary where he/she decides to visit one coffee shop each day (or perhaps take a day off if m>n). However, hipsters are fiercely independent (like WSRN), and prefer not to share coffee shops with other hipsters. Furthermore, each hipster is looking for a coffee shop to call his or her own. Each hipster, h, would like to choose a particular day k_h, and stay at his/her current coffee shop, c_h for the remaining m-k_h days of the tour. Naturally this means that no other hipster could visit c_h after day k_h, since hipsters won't share coffee shops.

Show that it is possible to assign each hipster h a unique coffee shop c_h, such that when h arrives at c_h according to the itinery for h, all other hipsters h' have either stopped touring coffee shops themselves, or h' will not visit c_h after h arrives at c_h. Describe an algorithm to find this matching. Hint: The input is somewhat like the input to stable matching, but at least one piece is missing. Find a clever way to construct the missing piece(s), run stable matching, and show that the final result solves the hipster problem.

It may be necessary to break ties, i.e., two hipsters might choose to visit the same coffee shop on the same day. You may assume that the tie can be broken by having hipsters arrive at different times of the day such that if h and h' both want to visit c on the same day that there is some timestamp on their visits such that it is easy to determine who arrived at c first. Thus, for any given day, at any given coffee shop, there is a well defined ordering to the planned arrival time of the hipsters.

Home Page

Last updated: Tuesday, September 22, 2020 at 09:07:43 AM