CSCC73H3 Quiz: Assignment One Solution.pdf
6 Oct 2013
School
Department
Course
Professor
Document Summary
We say that a set a of locations for the superboxes covers a set of locations b of houses if every element of b is within distance d of some element of a. We rst sort l in increasing distance from the start of the road. We maintain a set s of locations for the superboxes, and a set c of the set of houses covered by s. initially s and c are both empty. C := while c 6= l do. := the rst (smallest) element in l c. C := c {h l : h + 2d} return s. We prove the correctness of this algorithm using the promising set (also known as. , tm be the elements of t in increasing order. A straightforward induction on the iteration number proves the following invariant: At the end of each iteration of the algorithm, s covers c and does not cover any element in.
