cs 180 Homework 2 solution

Homework 2

Problem 1. Men, women and yupi live on the planet Alphaomega. They have highly developed
technology and in particular, they have stations for teleportation not only in space but also in time. In
the city Aleph on this planet, there are two teleportation stations. One of these stations allows
travelling both in time and in space, while the other one allows travelling only in time.
One day, there are n requests for teleportation and m of then demand travelling only in time. Each
request has the starting time and the ending time for the station utilization. The goal is to satisfy, i.e.,
to schedule, as many requests as possible without overlapping.
a) (10 pts). Prove that there is always a maximal scheduling.
b) (10 pts). Design an algorithm for building a maximal scheduling and prove that it gives a
maximal scheduling.
c) (40 pts). Design an efficient algorithm for building a maximal scheduling and prove that it
gives a maximal scheduling.
Problem 2. Men, women and gupi live on the planet Alphaomega. Imagine you are travelling by car
on this planet and you need to pass the city Beth. The road goes through this city and you cannot
bypass it. There are only two entrances to the city – one from the side you are coming and another
from the opposite side. Besides, you know that an evil gupi is sitting at one of the intersections in
Beth. When a human being comes close to him, he kidnaps this person and makes the human being a
slave. Fortunately, this gupi is lazy and he kidnaps only those who come close to him. The distance in
one block is safe for you and can feel the presence of the gupi one block ahead of you. At the same
time, other inhabitants of Beth cannot help you because you don’t know their language and they don’t
know your language.
a) (10 pts). Is it always possible to go through the city? Prove that your answer is correct.
b) (10 pts). If it is always possible to go through the city, design an algorithm for doing this.
c) (30 pts). If it is not always possible to go through the city, design an algorithm that will allow
you to go through the city when it is possible or to return back when it is impossible.
Problem 3. In a universe W, there are n planets Pi (i = 1, 2, … , n). Between some pairs of
these planets, wormholes exist, which allow travelling from one of these planets to the other in
one day. Each group of planets, in which any two planets are directly or indirectly connected by
wormholes, decided to form one state.
(30 pts). If it is possible to do this, build an algorithm that finds how many states will be
created.
(30 pts). If it is impossible to do this, prove it.