EECS 340 Algorithms
2018 Spring Semester
Homework 5Homework 5
Due on April 11th, 12:45pm
This assignment covers dynamic programming and greedy algorithms.
1. Warm-Up: Applying Dynamic Programming Algorithms Use the dynamic pro-
gramming algorithms given in class to solve the following problems. Show your
work.
(a) Coins in a Line
Solve R-12.4 in the text. (?)
(b) 0-1 Knapsack
Solve R-12.5 in the text. (?)
(c) Telescope Scheduling Redux
Solve R-12.6 in the text. (?)
2. Warm-Up: Applying Greedy Algorithms Use the greedy algorithms given in class
to solve the following problems. Show your work.
(a) Fractional Knapsack
Solve R-10.1 in the text. (?)
(b) Task Scheduling
Solve R-10.3 in the text. (?)
3. Warm-Up: Coins in a Line and the Failings of Greed
Solve C-12.3 in the text. (? ?)
4. The Cleveland Pothole Problem
Brick roads evidently not being bumpy enough, Little Italy’s Mayfield Road has
recently developed several potholes. The potholes this year are very bizarre – they
are zero-dimensional points which send cars passing over them to a place nobody
1
knows. 1 Unfortunately, the city does not have enough money to hire construction
workers, but fortunately, the city does have an enormous reserve supply of 24’x24’
2 metal covering plates to prevent cars from entering the underworld. Suppose that
you are given an array of the positions of these potholes 3 {s1, …sn} where each si
represents the distance along the road from the intersection of Euclid and Mayfield
to a pothole. Give an algorithm which returns the minimum number of metal plates
required to cover all potholes, and prove its correctness. (? ?)
5. Zombie Apocalypse: Cooking Edition
The year is 2050, and you’re the manager for Bone Apple Tea, CWRU’s only dining
service left operating after the start of this year’s HvZ. You have been asked by Babs
to distribute rations to maximize the number of students who survive. Luckily, you
have exactly as many packs of rations as there are students, but your entire kitchen
has been zombified and the packs of rations are of wildly varying caloric values.
Suppose that you have a list C = (c1, …, cn) of the calorie counts of the rations, and
a list B = (b1, …, bn) of the benefits 4 per calorie toward survivability of each student
5. A pairing of students with rations is an assignment of one and only one ration 6 to
each student, represented as a list of pairs of the form (i, j) where i represents the
index of a ration in the list of rations, and j represents the index of the student it
was assigned to in the list of the students’ benefits per calorie. Give an algorithm
to pair students and rations so as to maximize the total benefit toward survivability,
and prove its correctness. (? ?)
6. Checker-Sum Redux
Recall from Homework 2 that for a matrix A ∈ Rn×n, we call the checkerboard sum
matrix of A the matrix whose ith column and jth row is given by:
checker-sum(A)i,j = (−1)i+j
i∑
k=1
j∑
l=1
(−1)k+lAk,l
Use dynamic programming to implement checker-sum(A). (? ?)
7. On The Grid
Suppose that we have a recursive function F : {1, …n}×{1, …m} → N implemented
1The length of the potholes being zero in Cleveland is how you know that this question is purely hypo-
thetical.
2Enough to stretch the entire width of the road.
3In no particular order.
4In Utils, a completely fake unit also used for keeping the business students happy.
5That is, student i receives the benefit bi per calorie.
6Company policy only allows one portable rations swipe per person per week.
2
as:
Algorithm 1: F(n, m)
if Test(n, m) then
return Base(n, m)
end
else
I← NextIndices(n, m);
Results← [] ;
for (i, j) ∈ I do
Results.append(F(i, j))
end
return Combiner(Results)
end
For some implementations of the functions ”Base”, ”Combiner”, and ”NextIndices”
which you do not have access to the implementations of.
Suppose that we draw a n×m grid, where every grid point corresponds naturally 7
to a point in {1, …n} × {1, …m}. Consider these grid points as vertices of a directed
graph G = (V,E), where there is an edge from (i, j) to (k, l) iff any call to F (k, l)
directly results in a recursive call to F (i, j) 8 For example, if m = n = 3, and F (i, j)
depends on F (i − 1, j) and F (i, j − 1) when i and j are both not 1, this graph will
look like:
(1, 1) (1, 2) (1, 3)
(2, 1) (2, 2) (2, 3)
(3, 1) (3, 2) (3, 3)
Describe a dynamic programming algorithm whose inputs are m,n and a topo-
logical ordering of the graph G (constructed as above) which returns the value of
F (n,m) (? ?) .
8. A State of Balance
Solve C-12.13 in the text. (? ?)
9. Monotonically Decreasing Subsequences
Describe an O(n2) algorithm to find the length of the longest monotonically (strictly)
decreasing subsequence(s) of n integers. For example, given the sequence (2, 4, 1, 3)
7(Row,Column), where row numbers increase downward and column numbers increase rightward.
8That is, (i, j) is in the list returned by NextIndices(k, l).
3
(n = 4), the decreasing subsequences are (4, 1), (2, 1), (4, 3), (2), (4), (1), and (3), so
your algorithm should return 2 in this case. (? ? ?)
10. Let’s Do the Time Warp Again
Solve A-12.8 in the text. (? ? ?)
11. The following is for EECS 454 students only. Read Section 17.4 in the textbook and
then solve the following problems:
(a) R-17.9
(b) R-17.10
(c) R-17.12
(d) C-17.10
Submission
Hand in your paper in-class by the beginning of class on the due date. Always check
Canvas for updates and corrections.
4