Class Notes
(808,126)

Canada
(493,084)

University of Toronto Scarborough
(30,806)

Computer Science
(300)

CSCC73H3
(10)

Vassos Hadzilacos
(10)

Lecture

# Assignment 1

Unlock Document

University of Toronto Scarborough

Computer Science

CSCC73H3

Vassos Hadzilacos

Fall

Description

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 deﬁned as max 0,f (j)−s(j) ,
where f sj) is the ﬁnish 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 ﬁnd 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 ﬁnd 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 eﬃcient greedy algorithm that ﬁnds 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, diﬀerent paddles to diﬀerent 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