Name: SID# _

CS 180
Midterm Test
Summer 2021
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.
3—n
log102n
4—n3
—nn
log102n+ 5n
5n + 5n
n7/2
log10(n5+ 5n)


Timed quiz 1BABBAR
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.












































学霸联盟