Assignment 1

3 Pages
Unlock Document

University of Toronto Scarborough
Computer Science
Vassos Hadzilacos

Computer Science C73 September 14, 2010 Scarborough Campus University of Toronto Homework Assignment #1 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: Instead of miminising the maximum lateness over all jobs, we wish to minimise the sum of the latenesses of all jobs. (Recall that the lateness of job j in a schedule s is defined as max 0,f (j)−s(j) , where f sj) is the finish time of j in s, and d(j) is the deadline of j.) Does the algorithm described in KT §4.2 solve this variation of the problem? 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 {I ,I ,...,I1} t2at n covers I; i.e., I ⊆ ∪ I . We wish to find a subset of {I ,I ,...,I } that covers I and has as few intervals i=1 i 1 2 n as possible. (Think of I as the period during which a building must be guarded, and I ,I ,...1I 2s the intervals in which each of n guards can be on duty. We want to find the smallest number of guards so that at all times during I at least one guard is on duty.) a. (3 marks) Consider the following greedy strategy. Assume that I ,I 1...2I are norted in decreasing order of the length of their intersection with I. (Rename them, if needed.) Start with the empty subset, and consider each interval in turn, keeping the interval under consideration in the subset if and only if it covers a part of I that isn’t already covered by intervals kept so far. Give a counterexample showing that this strategy does not necessarily yield a desired subset of I 1I ,2..,I .n b. (7 marks) Describe an efficient greedy algorithm that finds a desired subset of I ,I ,.1.,2 . Provn that your algorithm is correct, and analyse its running time. Question 3. (10 marks) The optimal length of a paddle for a canoeist is his/her shoulder height. We have n canoeists with shoulder heights h ,h ,1..2h , andnn paddles of length ℓ ,ℓ ,...1ℓ 2 We munt assign exactly one paddle to each canoeist (and, of course, different paddles to different canoeists). Such an assignment can be conveniently represented by a permutation π of 1,2...,n: canoeist i is assi
More Less

Related notes for CSCC73H3

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.