CSCC73H3 Lecture : Assignment 1
19 Oct 2011
School
Department
Course
Professor
Document Summary
Due: september 28, 2010, by 10:30 am (in the drop box for your cscc73 tutorial section, near room sw-626a) Appended to this document is a cover page for your assignment. Fill it out, staple your answers to it, and deposit the resulting document into the course drop box (without putting it in an envelope). Question 1. (10 marks) consider a variation of the problem of minimising lateness, discussed in kt 4. 2: If so, prove that this is the case; if not, provide a counterexample. Question 2. (10 marks) we are given an interval i = [s, f ] and a set of intervals {i1, i2, . , in} that covers i; i. e. , i n i=1ii. We wish to nd a subset of {i1, i2, . , in} that covers i and has as few intervals as possible. (think of i as the period during which a building must be guarded, and i1, i2, .
