Foundations of Algorithms Homework 3

Foundations of Algorithms Homework 3

Problem 1 (8 points)
Consider the following algorithm for generating a binary tree representing a prefix code.
Given a collection of symbols and their corresponding frequencies:
i) Sort the symbols by frequency in ascending order.
ii) Call the following recursive function, passing in the sorted list of symbols and frequencies. The function returns the root of the tree.
(a) If the list contains only a single symbol, return that symbol as the root of the
tree.
(b) Else determine an index at which to cut the list into first and second sub-lists.
This cut index should have the property that among all possible cut points, this
one yields the minimum difference between the cumulative frequency of the two
individual sub-lists.
(c) Make a copy of the first sub-list.
(d) Make a copy of the second sub-list.
(e) Make recursive calls to generate the roots of the left and right sub-trees, in each
case passing in the corresponding sub-list. Attach the root nodes of the left and
right sub-trees to a parent node and return that parent node.
For example, given sorted frequencies: {10, 11, 15, 18, 22, 24}, the algorithm first splits
the list into {10, 11, 15, 18} and {22, 24}, having cumulative frequencies 54 and 46, respectively. The difference |54 − 46| = 8 is the minimum difference achievable by any partition.
Continuing from there, the algorithm splits {10, 11, 15, 18} into {10, 11} and {15, 18}, as
|21 − 33| = 12 is the minimum difference achievable when partitioning that list into two
sub-lists. All lists of size two get split into two lists of size one.
Answer the following questions related to the algorithm. Assume there are n input
symbols.
1. What is a recurrence that describes step ii) of the algorithm?
2. What is the asymptotic complexity of the algorithm? Provide an answer for both the
best case (sub-lists equal size) and worst case (one sub-list has all but one symbol).
No proof is required.
3. Does this algorithm always generate an optimal prefix code? Either provide a proof
that the algorithm always generates an optimal prefix code, or else provide a counterexample for which the algorithm does not generate an optimal prefix code, clearly
arguing why the code is sub-optimal.
1
Problem 2 (12 points: 8 for implementation / 4 for writeup)
In a little town the roads are all laid out in a perfect grid. There is a North-South road
every block. There is an East-West road every block. At every intersection, there is a
traffic light. In order to make sure people obey the traffic lights, there are police cars
stationed at some of the intersections. You have decided to open a corner donut store at
one of the intersections, and need to identify the most profitable location for your store.
The most profitable location will be the one that minimizes the sum of the distances that
the traffic police have to travel to reach your store. The police must travel by using the
existing roads (they can not travel diagonally).
You are given a collection of integer coordinates (x1, y1),(x2, y2), ...,(xn, yn) that represent the locations of traffic police. Give an O(n) algorithm that determines the best corner
location (given by (xbest, ybest)) for your donut store. That is, (xbest, ybest) should be chosen
such that Pn
i=1 |xbest − xi
| + |ybest − yi
| is as small as possible, and (xbest, ybest) should also
be integer coordinates.
Problem 3 (12 points: 8 for implementation / 4 for writeup)
Consider the following variant of the interval scheduling problem. You are a contractor
and want to complete as many jobs (intervals) as you can. You do work for two different
employers. In order to keep both employers happy, you must alternate doing jobs for the
employers. You can choose either employer for the first job, but must make sure never to
do two consecutive jobs for the same employer.
Given are n intervals (jobs). The i
th interval is specified by (si
, fi
, ei), where the interval
runs from starting time si to finishing time fi
, and the employer is ei
. Design an O(n log n)
algorithm that determines the maximum number of compatible jobs that you can complete
while keeping both employers satisfied (i.e. while alternating employers). Note that if job
j has a finish time that is equal to the start time of job k, jobs j and k are considered
compatible.
Problem 4 (15 points: 10 for implementation / 5 for writeup)
Consider a 2-backpack version of Knapsack. Given are two backpacks of capacities W1 and
W2. Given are also n items (w1, c1),(w2, c2), . . . ,(wn, cn), where wi
is the weight and ci
the cost of the i-th item. We want to find a set of items that can be split into two parts:
one that fits in the first backpack and the other in the second backpack, and the sum of
their costs is the largest possible. All the numbers are positive and W1, W2, and all the
wi
’s are integers. Give an O(nW1W2) algorithm that finds the largest possible cost.
Problem 5 (15 points: 9 for implementation / 6 for writeup)
Given is a sequence of numbers a1, a2, a3, . . . , an. We say that aj1
, aj2
, . . . , ajk
is a subsequence of this sequence if and only if 1 ≤ j1 < j2 < . . . < jk ≤ n. The subsequence
is increasing if and only if aj1 < aj2 < . . . < ajk
. In the longest increasing subsequence
problem we search for an increasing subsequence of a1, a2, a3, . . . , an that is the longest
possible (i.e., k is as large as possible).
2
For example, for sequence 8,2,5,7,3,4,9,10, the longest increasing subsequences are
2,3,4,9,10 and 2,5,7,9,10 - either of them is a valid longest increasing subsequence.
This problem is about the longest increasing subsequence. You will implement a recursive approach and a dynamic-programming-based approach and compare their running
times. In both cases we are interested only in finding the length of the sequence, not the
sequence itself.
• Implement the following recursive approach. Implement the function
incrSubseqRecursive(j, A), that computes the maximum length of an increasing
subsequence of the sequence a1, a2, . . . , an (stored in the array A) that ends with the
element aj . This function tries to find a previous element ai such that i < j and
ai < aj , and then it recursively searches for the maximum length of an increasing
subsequence of a1, a2, . . . , ai
. It tries up to j − 1 different i’s and it chooses the one
that gives rise to the maximum length. By concatenating aj to the subsequence of
a1, a2, . . . , ai ending with ai
, we get a longest increasing subsequence of a1, a2, . . . , aj .
• Implement the dynamic programming approach to the longest increasing subsequence
problem.
• Generate about 10 inputs for different values of n (how large can n be?) and report
your observations on the running times of the two respective algorithms.
Note: Heart of the Algorithm
For any problem in which you develop a dynamic program (in this or any future homework!), to explain how your algorithm works (the correctness argument), describe the
“heart of the algorithm” (you do not need to include any other explanation). Recall that
the heart of the algorithm consists of three parts:
• Precise verbal description of the meaning of your dynamic programming array; see
the slides for examples.
• A mathematical formula that describes how to compute the value of each cell of the
array (using previously computed array values).
• Return value of the algorithm.
Note that the discussion of the complexity of your algorithm is separate and must be
included as well.
3