DOC PREVIEW
MIT 6 006 - Problem Set 7

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Introduction to Algorithms: 6.006Massachusetts Institute of Technology April 28, 2011Professors Erik Demaine, Piotr Indyk, and Manolis Kellis Problem Set 7Problem Set 7This problem set contains two theory questions. The problem set is due Friday, May 5th at11:59PM.Solutions should be turned in through the course website. Your solution should be in PDF formatusing LATEX. Remember, your goal is to communicate. Full credit will be given only to a correctsolution which is described clearly. Convoluted and obtuse descriptions might receive low marks,even when they are correct. Also, aim for concise solutions, as it will save you time spent onwrite-ups, and also help you conceptualize the key idea of the problem.Problem 7-1. [50 points] Ghostbusters and GhostsA group of n Ghostbusters is battling n ghosts. Each Ghostbuster carries a proton pack, whichshoots a stream at a ghost, eradicating it. A stream goes in a straight line and terminates when ithits the ghost. The Ghostbusters decide upon the following strategy. They will pair off with theghosts, forming n Ghostbuster-ghost pairs, and then simultaneously each Ghostbuster will shoot astream at his chosen ghost. As we all know, it is very dangerous to let streams cross, and so theGhostbusters must choose pairings for which no streams will cross.Assume that the position of each Ghostbuster and each ghost is a fixed point in the plane and thatno three positions are collinear.(a) [25 points] Argue that there exists a line passing through one Ghostbuster and oneghost such that the number of Ghostbusters on one side of the line equals the numberof ghosts on the same side. Describe how to find such a line in O(n lg n) time.(b) [25 points] Give an O(n2lg n)-time algorithm to pair Ghostbusters with ghosts insuch a way that no streams cross.Problem 7-2. [50 points] Three is companyWith MIT set to increase the size of the incoming class, the evil Housing Office has decided to turnsome East Campus doubles into triples. The existing residents of those rooms are understandablyconcerned about getting saddled with somebody lame, and so they put their considerable overengi-neering prowess to work on the problem.On the way back from putting an ironic protest installation on top of the dome, one of the studentsresponsible for making housing arrangements has an epiphany (or, at the least, heavily caffeinatedinspiration) and proposes the following scheme. Say that Alice and Bob are the existing room-mates; to determine their compatibility with a prospective freshman, they each choose a set of ndistinct integers in the range {0, . . . , m} (A and B, respectively) which correspond to their re-sponses to a survey.2 Problem Set 7Each freshman will also be asked the same questions, producing a similar set C. Alice and Bobwill be considered compatible with that freshman if there is some a ∈ A, b ∈ B, and c ∈ C suchthat a + b = c. Describe an O(mlog23)-time algorithm for determining whether the prospectiveroommate is compatible with Alice and Bob. (Hint: represent each set as a sequence of 0-1coefficients of a


View Full Document

MIT 6 006 - Problem Set 7

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download Problem Set 7
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Problem Set 7 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Problem Set 7 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?