The University Of New Hampshire Written Problems Worksheet
Description
Unformatted Attachment Preview
Solve the following problems. When you are asked to éve!n algorithm, please be sure to prove that it
is correct and exhibits the desired running time!
1. You are an usher in a theater with n balconies for a childrenàmatinee performance with n children
in attendance. You are given a list of m statements of the form `hates j. f i hates j, then you do
not want to seat i above or in the same balcony as j, otherwise i will throw popcorn at j instead of
watching the play. Give an algorithm that assigns balconies to children (or determines that no feasible
assignment exists) in time O(m + n). We can assume that balconies are numbered ascending with
height.
2. Letàassume that UNH IT has a pretty good idea of where people like to use their laptops iFi.
Given a set of n points on campus representing demand for WiFi bandwidth and a set of b points
representing some proposed wireless access points locations, each with a fixed total bandwidth T (in
number of users) and radio range R, give an algorithm (polynomial in n and b) for determining whether
this proposed access point layout will satisfy all the users.
3. You are consulting for a cell phone company in Arizona. They have a long straight road that has some
houses at known locations along it. The company wants to build the minimum number of cell towers
such that every house is within four miles of a tower. Give an efficient algorithm to place the towers
and prove that it finds optimal solutions.
4. Give an O(n) algorithm to determine the laziest way to dial an n-digit number on a telephone keypad
using two fingers. The two fingers start on the * and # keys. You can assume that the effort required
to move a finger from one button to another is proportional to the Euclidean distance between them.
5. It is midnight and pitch black, but you are holding a dim lighted candle. You are facing a high wall
that stretches infinitely in both directions. There is a door in the wall, but you don know where.
The candlelight is only sufficient to enable you to see the door when you are right in front of it. Give
an algorithm that will enable you to find the door in O(n) steps, where n is the number of steps that
you would take if you knew the location of the door and walked directly to it.
1
Purchase answer to see full
attachment
Have a similar assignment? "Place an order for your assignment and have exceptional work written by our team of experts, guaranteeing you A results."