EE360C: Algorithms
University of Texas at Austin Homework 5
Dr. Christine Julien, Dr. Vallath Nandakumar Due: March 1, 2018 (not submitted)
Homework 5
You should try to solve these problems by yourself. I recommend that you start early and get help
in office hours if needed. If you find it helpful to discuss problems with other students, go for it.
Problem 1: Greedy Choice
You are consulting for a trucking company that does a large amount of business shipping packages
between New York and Boston. The volume is high enough that they have to send several trucks
each day between the two locations. Trucks have a fixed limit W on the maximum amount of weight
they are allowed to carry. Boxes arrive at the New York station one by one, and each package i
has a weight wi . The trucking station is quite small, so at most one truck can be in the station
at any time. Company policy requires that boxes are shipped in the order they arrive; otherwise
a customer might get upset. At the moment, the company is using a simple greedy algorithm for
packing: they pack boxes in the order they arrive, and whenever the next box does not fit, they
send the truck on its way.
But they wonder if they might be using too many trucks, and they want your opinion on
whether the situation can be improved. Here is how they are thinking. Maybe one could decrease
the number of trucks needed by sometimes sending off a truck that was less full, and in this way
allow the next few trucks to be better packed.
Prove that, for a given set of boxes with specified weights, the greedy algorithm currently in
use actually minimizes the number of trucks that are needed.
Solution
We prove that the greedy algorithm uses the fewest possible trucks by showing that it “stays
ahead” of any other solution. If the greedy algorithm fits boxes b1 , b2 , . . . bj into the first k
trucks, and the other solution fits b1 , . . . bi into the first k trucks, then i ≤ j. We will prove
this by induction on k. The base case is easy; k = 1 and we only require a single truck to
send all of the packages. Now, assuming the above holds for k − 1: the greedy algorithm
fits j ′ boxes into the first k − 1 trucks and the alternate (possibly optimal) algorithm fits i′
boxes into the first k − 1 trucks; i′ ≤ j ′ . Now for the k th truck, the alternate solution puts
in boxes bi′ +1 , . . . , bi . Thus since j ′ ≥ i′ , the greedy algorithm is able at least to fit all the
boxes bj ′ +1 , . . . , bi , if not more into the k th truck.
, 2. Now consider a weighted version of the class scheduling problem, where different classes offer
different number of credit hours (totally unrelated to the duration of the class lectures). Your goal
is now to choose a set of non-conflicting classes that give you the largest possible number of credit
hours, given an array of start times, end times, and credit hours as input.
(a) Prove
Homework that the
5: March greedy
1, 2018 algorithm
(not described in the notes — Choose the class that ends first and
submitted) 2
recurse — does not always return an optimal schedule.
(b) Describe
Problem an algorithm
2: Another to compute
Interval Problemthe optimal schedule in O(n2 ) time.
Let X be a set of n intervals on the real line. A subset of intervals Y ⊆ X is called a tiling path
if the intervals
3. Let X be a in
set Yof n
cover the intervals
intervals on the realinline.
X, Athat is, of
subset any real value
intervals Y ⊆ Xthat is contained
is called in some
a tiling path if the
interval in X is also contained in some interval in Y . The size of a tiling cover is just the
intervals in Y cover the intervals in X , that is, any real value that is contained in some interval in number
of intervals.
X is also contained in some interval in Y . The size of a tiling cover is just the number of intervals.
Describe an algorithm to compute the smallest tiling path of X. Assume that your input consists
Describe and analyze an algorithm to compute the smallest tiling path of X as quickly as
of two arrays XL [1 . . n] and XR [1 . . n], representing the left and right endpoints of the intervals
possible. Assume that your input consists of two arrays X [1 .. n] and X R [1 .. n], representing the
in X. Argue that your algorithm is correct (hint: rememberL that an argument of correctness for
left and right endpoints of the intervals in X . If you use a greedy algorithm, you must prove that it
any greedy algorithm has two components). The figure below shows an example of a tiling path,
is correct.
though a non-optimal one.
A set of intervals. The seven shaded intervals form a tiling path.
Solution
Let Xboth
4. Sort be aX set
L of
and n intervals on the
XR so that thereal
jobsline.
withWethe
sayearliest
that a set P oftimes
start stabs
pointsare X ifInclude
first. every interval
the
in X interval
first contains(theat least
one one
withpoint in P. Describe
the earliest and analyze
start time). It hasantoefficient algorithm
be in your tiling. to
If compute
there arethe
smallest intervals
multiple set of points
withthat sameXstart
thestabs . Assume
timethat
(andyour inputallconsists
they’re of twostart
the earliest arrays X L [1choose
time), .. n] and
X R [1
the .. n],
one thatrepresenting the left
has the lastest andtime
finish right endpoints
(after all, it of theyou
gets intervals in Xbang
the most . As usual,
for your If you
buck).use a
greedy
Then algorithm,
remove you must
everything prove
that that it is correct.
is overlapped completely by the interval you just selected.
(There’s no use including any of these since they don’t add anything. Now recurse. After
the first subproblem, you want to look at all of the intervals that include the finish time of
5. Let X be a set of n intervals on the real line. A proper coloring of X assigns a color to each interval,
the interval you just included. Of these intervals, you want to pick the one of them that
so that any two overlapping intervals are assigned different colors. Describe and analyze an
has the latest finish time. That is, say the greedy choice in the previous step was to include
efficient algorithm to compute the minimum number of colors needed to properly color X . Assume
interval i. After removing all of the intervals that are completely overlapped by interval i,
the next greedy choice is an interval that starts on or before XR [i] and finishes the latest
of all such intervals. 9
Optimal Substructure. The problem exhibits optimal substructure. After making the
greedy choice and removing all of the intervals that are completely overlapped by the greed-
ily chosen interval, we’re left with a smaller problem (the original set X minus some inter-
vals) and a smaller piece of the line to cover (specifically, we’re left with the portion of the
line that is NOT covered by the greedily chosen interval).
The Greedy Choice is Good. Suppose that the greedy choice was not good. That is,
suppose that you hand me an optimal tiling path that does not contain the earliest starting
interval (and of the earliest starting intervals the one with the latest finish time). I can
take your tiling path and remove the interval that has the earliest starting time in it and
replace it with the greedy choice. Either my interval starts before yours (in which case, your
solution wasn’t correct, since you didn’t cover the entire line) or they start at the same time.
In the latter case, I’ve only covered more of the line since my selected interval has a later
finishing time than yours (since I selected the earliest starting one with the latest finishing
time). Either that or our intervals were exactly the same.
University of Texas at Austin Homework 5
Dr. Christine Julien, Dr. Vallath Nandakumar Due: March 1, 2018 (not submitted)
Homework 5
You should try to solve these problems by yourself. I recommend that you start early and get help
in office hours if needed. If you find it helpful to discuss problems with other students, go for it.
Problem 1: Greedy Choice
You are consulting for a trucking company that does a large amount of business shipping packages
between New York and Boston. The volume is high enough that they have to send several trucks
each day between the two locations. Trucks have a fixed limit W on the maximum amount of weight
they are allowed to carry. Boxes arrive at the New York station one by one, and each package i
has a weight wi . The trucking station is quite small, so at most one truck can be in the station
at any time. Company policy requires that boxes are shipped in the order they arrive; otherwise
a customer might get upset. At the moment, the company is using a simple greedy algorithm for
packing: they pack boxes in the order they arrive, and whenever the next box does not fit, they
send the truck on its way.
But they wonder if they might be using too many trucks, and they want your opinion on
whether the situation can be improved. Here is how they are thinking. Maybe one could decrease
the number of trucks needed by sometimes sending off a truck that was less full, and in this way
allow the next few trucks to be better packed.
Prove that, for a given set of boxes with specified weights, the greedy algorithm currently in
use actually minimizes the number of trucks that are needed.
Solution
We prove that the greedy algorithm uses the fewest possible trucks by showing that it “stays
ahead” of any other solution. If the greedy algorithm fits boxes b1 , b2 , . . . bj into the first k
trucks, and the other solution fits b1 , . . . bi into the first k trucks, then i ≤ j. We will prove
this by induction on k. The base case is easy; k = 1 and we only require a single truck to
send all of the packages. Now, assuming the above holds for k − 1: the greedy algorithm
fits j ′ boxes into the first k − 1 trucks and the alternate (possibly optimal) algorithm fits i′
boxes into the first k − 1 trucks; i′ ≤ j ′ . Now for the k th truck, the alternate solution puts
in boxes bi′ +1 , . . . , bi . Thus since j ′ ≥ i′ , the greedy algorithm is able at least to fit all the
boxes bj ′ +1 , . . . , bi , if not more into the k th truck.
, 2. Now consider a weighted version of the class scheduling problem, where different classes offer
different number of credit hours (totally unrelated to the duration of the class lectures). Your goal
is now to choose a set of non-conflicting classes that give you the largest possible number of credit
hours, given an array of start times, end times, and credit hours as input.
(a) Prove
Homework that the
5: March greedy
1, 2018 algorithm
(not described in the notes — Choose the class that ends first and
submitted) 2
recurse — does not always return an optimal schedule.
(b) Describe
Problem an algorithm
2: Another to compute
Interval Problemthe optimal schedule in O(n2 ) time.
Let X be a set of n intervals on the real line. A subset of intervals Y ⊆ X is called a tiling path
if the intervals
3. Let X be a in
set Yof n
cover the intervals
intervals on the realinline.
X, Athat is, of
subset any real value
intervals Y ⊆ Xthat is contained
is called in some
a tiling path if the
interval in X is also contained in some interval in Y . The size of a tiling cover is just the
intervals in Y cover the intervals in X , that is, any real value that is contained in some interval in number
of intervals.
X is also contained in some interval in Y . The size of a tiling cover is just the number of intervals.
Describe an algorithm to compute the smallest tiling path of X. Assume that your input consists
Describe and analyze an algorithm to compute the smallest tiling path of X as quickly as
of two arrays XL [1 . . n] and XR [1 . . n], representing the left and right endpoints of the intervals
possible. Assume that your input consists of two arrays X [1 .. n] and X R [1 .. n], representing the
in X. Argue that your algorithm is correct (hint: rememberL that an argument of correctness for
left and right endpoints of the intervals in X . If you use a greedy algorithm, you must prove that it
any greedy algorithm has two components). The figure below shows an example of a tiling path,
is correct.
though a non-optimal one.
A set of intervals. The seven shaded intervals form a tiling path.
Solution
Let Xboth
4. Sort be aX set
L of
and n intervals on the
XR so that thereal
jobsline.
withWethe
sayearliest
that a set P oftimes
start stabs
pointsare X ifInclude
first. every interval
the
in X interval
first contains(theat least
one one
withpoint in P. Describe
the earliest and analyze
start time). It hasantoefficient algorithm
be in your tiling. to
If compute
there arethe
smallest intervals
multiple set of points
withthat sameXstart
thestabs . Assume
timethat
(andyour inputallconsists
they’re of twostart
the earliest arrays X L [1choose
time), .. n] and
X R [1
the .. n],
one thatrepresenting the left
has the lastest andtime
finish right endpoints
(after all, it of theyou
gets intervals in Xbang
the most . As usual,
for your If you
buck).use a
greedy
Then algorithm,
remove you must
everything prove
that that it is correct.
is overlapped completely by the interval you just selected.
(There’s no use including any of these since they don’t add anything. Now recurse. After
the first subproblem, you want to look at all of the intervals that include the finish time of
5. Let X be a set of n intervals on the real line. A proper coloring of X assigns a color to each interval,
the interval you just included. Of these intervals, you want to pick the one of them that
so that any two overlapping intervals are assigned different colors. Describe and analyze an
has the latest finish time. That is, say the greedy choice in the previous step was to include
efficient algorithm to compute the minimum number of colors needed to properly color X . Assume
interval i. After removing all of the intervals that are completely overlapped by interval i,
the next greedy choice is an interval that starts on or before XR [i] and finishes the latest
of all such intervals. 9
Optimal Substructure. The problem exhibits optimal substructure. After making the
greedy choice and removing all of the intervals that are completely overlapped by the greed-
ily chosen interval, we’re left with a smaller problem (the original set X minus some inter-
vals) and a smaller piece of the line to cover (specifically, we’re left with the portion of the
line that is NOT covered by the greedily chosen interval).
The Greedy Choice is Good. Suppose that the greedy choice was not good. That is,
suppose that you hand me an optimal tiling path that does not contain the earliest starting
interval (and of the earliest starting intervals the one with the latest finish time). I can
take your tiling path and remove the interval that has the earliest starting time in it and
replace it with the greedy choice. Either my interval starts before yours (in which case, your
solution wasn’t correct, since you didn’t cover the entire line) or they start at the same time.
In the latter case, I’ve only covered more of the line since my selected interval has a later
finishing time than yours (since I selected the earliest starting one with the latest finishing
time). Either that or our intervals were exactly the same.
