Due not later than 10 a.m. PT Thursday, July 22, 2021

Problem 1 (40 pts).

Men, women and yupi live on the planet Alphaomega. Imagine you find yourself in the city Aleph on this planet. You know that a generous yupi lives there who gives a flying car to a person when he first meets this person. You also know that there is a big letter Y on the house of the generous yupi and there are no other houses with this sign. You want to get a flying car but you don’t know where the generous yupi lives and other inhabitants of Aleph cannot help you because you don’t know their language and they don’t know your language. Design an algorithm that will allow you to find the generous yupi if you know that his castle is at one of the intersections in Aleph. 

a) 20 pts for any correct algorithm.

 b) Up to 40 pts for an efficient algorithm with estimation of its time complexity.

Problem 2 (30 pts). 

Take the following functions and arrange them in descending order of growth rate indicating when functions have the same order of growth rate.

Problem 3 (30 pts). 

On the planet Alphaomega, there are n spaceships and n persons having the rank of a spaceship captain. Each captain has the preference list of spaceships and the crew of each spaceship has the preference list of captains. The goal is to find a Stable Spaceship Matching of pairs (c, s). Decide whether the following statement is true or false.

In every instance of the Stable Spaceship Matching, there is a stable matching containing a pair (c, s)

 such that, at least, one of them is ranked third on the preference list of the other. 

If it is true, give a short explanation and design an algorithm. 

If it is false, give a counterexample and explain that it is correct.