Introduction to Algorithms 6 006 Massachusetts Institute of Technology Professors Erik Demaine Piotr Indyk and Manolis Kellis April 28 2011 Problem Set 7 Problem Set 7 This problem set contains two theory questions The problem set is due Friday May 5th at 11 59PM Solutions should be turned in through the course website Your solution should be in PDF format using LATEX Remember your goal is to communicate Full credit will be given only to a correct solution 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 on write ups and also help you conceptualize the key idea of the problem Problem 7 1 50 points Ghostbusters and Ghosts A group of n Ghostbusters is battling n ghosts Each Ghostbuster carries a proton pack which shoots a stream at a ghost eradicating it A stream goes in a straight line and terminates when it hits the ghost The Ghostbusters decide upon the following strategy They will pair off with the ghosts forming n Ghostbuster ghost pairs and then simultaneously each Ghostbuster will shoot a stream at his chosen ghost As we all know it is very dangerous to let streams cross and so the Ghostbusters 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 that no three positions are collinear a 25 points Argue that there exists a line passing through one Ghostbuster and one ghost such that the number of Ghostbusters on one side of the line equals the number of ghosts on the same side Describe how to find such a line in O n lg n time b 25 points Give an O n2 lg n time algorithm to pair Ghostbusters with ghosts in such a way that no streams cross Problem 7 2 50 points Three is company With MIT set to increase the size of the incoming class the evil Housing Office has decided to turn some East Campus doubles into triples The existing residents of those rooms are understandably concerned about getting saddled with somebody lame and so they put their considerable overengineering prowess to work on the problem On the way back from putting an ironic protest installation on top of the dome one of the students responsible for making housing arrangements has an epiphany or at the least heavily caffeinated inspiration and proposes the following scheme Say that Alice and Bob are the existing roommates to determine their compatibility with a prospective freshman they each choose a set of n distinct integers in the range 0 m A and B respectively which correspond to their responses to a survey 2 Problem Set 7 Each freshman will also be asked the same questions producing a similar set C Alice and Bob will be considered compatible with that freshman if there is some a A b B and c C such that a b c Describe an O mlog2 3 time algorithm for determining whether the prospective roommate is compatible with Alice and Bob Hint represent each set as a sequence of 0 1 coefficients of a polynomial
View Full Document
Unlocking...