Algorithms Homework Assignment

Beasties, LLC is a highly original company that sends out monsters every night to
scare kids. (Actually, just guys in monster suits. And people keep telling them to stop.)
Anyway, the input is an undirected graph G = (V, E) with n nodes; a designated
subset M ⊂ V where there are initially monsters (M = m1, . . . , mt
, where mi
is the
starting location of monster i, all distinct); and a designated subset of vertices K ⊂ V
that are kids’ houses. Both of these sets could be large, e.g. size .1n or whatever; they
are not bounded in size by a constant.
You also are given a time budget T, with 1 ≤ T ≤ n. Each of your monsters can take
one step in the graph per unit of time, and immediately scare any kids on whose houses
they land. Monsters can share a vertex.
Give an algorithm running in time at most C
n
, for some constant C > 1, that decides
whether or not our team of monsters can scare all the kids in the allotted time.
Note: this is slow—it is exponential, not polynomial, in the input size—but it is at
least much more efficient than a runtime bound such as n! or n
n
, both of which are
2
Θ(n log n)
.
2
XC1.2 [15 points]
This problem is about the Pac-Man game on graphs. The input is an undirected,
unweighted graph G = (V, E) with a designated start position s ∈ V for Pac-Man, and
4 starting Ghost locations g1, g2, g3, g4 ∈ V . (The thematic link here is that ghosts are
scary.)
It’s a turn-based game with alternating turns. On the Pac-Player’s turn, Pac-Man
(or Ms. Pac-Man, Pac-Man Jr., etc.) can move from their current vertex to any adjacent
vertex, or stay put. The Ghosts are a team trying to catch Pac-Man, and have the same
mobility as Pac-Man (they can each take up to one step per turn). Ghosts are allowed to
share a vertex, and if one of them is ever in the same vertex as Pac-Man it’s game over.
There are no dots, power-ups, etc. so Pac-Man just has to keep running.
Pac-Man and the Ghosts both have complete knowledge of the game state at all times.
Your goal is to decide (yes/no) whether, for the given graph and starting positions, there
is a strategy for Pac-Man to avoid the Ghosts indefinitely, regardless of their chosen
strategy.
Oh, and you should achieve this in time bounded by a polynomial in the input graph
size n + m = |V | + |E|.
3
XC1.3 [15 points]
A Weighted Companion Cube is an emotional-support object that can also be used
to escape puzzle chambers. In what follows you’ll have an opportunity to interact with
several Cubes and, perhaps, form a lasting bond with one of them.
In the Tunnel-Escape Problem, you’re (kidnapped and) placed at the leftmost end of
a tunnel—considered as the origin, x = 0, on a number line. There are n locked Doors to
your right standing between you and, supposedly, freedom. Also found in this tunnel at
various points are some number m of Cubes of different weights, as well as n “Platforms.”
• Each Platform has a distinct index, i ∈ [n], associating it to some Door i. Door i
is opened if you place a Cube of sufficient weight on Platform i; each Platform has
its own weight requirement ri (a positive integer). Any Cube of weight ≥ ri placed
on Platform i will cause Door i to open.
• You can only place at most one Cube on a given Platform at any one time. You
are strong enough to hold/carry any number of Cubes.
• If a Cube is lifted from Platform i where it was previously opening Door i, then this
Door shuts immediately (destroying any obstructing objects, so don’t try to jam
it!). You could, however, reopen that door, perhaps by placing a different Cube on
the platform.
You start out with perfect knowledge in this situation: You are given a list of 3n
positive integers
(Di
, Pi
, ri) , i ∈ [n] ,
where Di
is the location of Door i and Pi the location of Platform i, whose weight
requirement is ri
. You may assume D1 < D2 < . . . < Dn and, for each i, we have
Pi < Di
.
You are also given the locations and weights (`j
, wj ) , j = 1, 2, . . . , m, of all Cubes
(all positive integers). Assume that no initial placements of any objects coincide.
Give an algorithm of running time bounded by some polynomial in (n+ m) to decide,
given this information, whether it is possible to escape the tunnel. (Just decide. You
are not asked to output an action-sequence.) Prove your algorithm’s correctness and
efficiency.