CSOR-W4231 Homework 3 Solution

Homework Instructions.
1. For all algorithms that you are asked to “give” or “design”, you should
• Describe your algorithm clearly in English.
• Give pseudocode.
• Provide, with an explanation, the best (smallest) upper bound that you can for the running time. All bounds should be worst-case bounds, unless explicitly stated otherwise.
2. If you give a Dynamic Programming algorithm, the above requirements are modified as follows:
(a) Clearly define the subproblems in English.
(b) Explain the recurrence in English. (This counts as a proof of correctness; feel free to give an inductive proof of correctness too for practice but points will not be deducted if you don’t.) Then give the recurrence in symbols.
(c) State boundary conditions.
(d) Analyze time.
(e) Analyze space.
(f) If you’re filling in a matrix, explain the order to fill in subproblems in English.
(g) Give pseudocode.
4. You should submit this assignment as a pdf file to Gradescope. Other file formats will not be graded, and will automatically receive a score of 0.
5. I recommend you type your solutions using LaTeX. For every assignment, you will earn 5 extra credit points if you type your solutions using LaTeX or other software that prints equations and algorithms neatly. If you do not type your solutions, make sure that your handwriting is very clear and that your scan is high quality.
Homework Problems
1. (25 points) There is a network of roads G = (V,E,`) connecting a set of cities V . Each road in E has an associated length (weight) `(e). There is a proposal to add one new road on this network, and there is a list E0 of pairs of cities between which the new road can be built. Each such potential road e0 ∈ E0 has an associated length.
As a designer for the public works department you are asked to determine the road e0 ∈ E0 whose addition to the existing network G will result in the maximum decrease in the driving distance between two fixed cities s and t in the network.
Give an efficient algorithm to solve this problem.
Boxes arrive at the New York station one by one. Each box i has an integer weight wi > 0. The trucking station is quite small, so at most one truck can be at the station at any time. Boxes must be shipped in the order they arrive.
Given a set of n boxes ordered by their arrival time and their weights w1,...,wn, design an efficient algorithm that loads boxes in the trucks so that the number of trucks needed is minimized.
3. (40 points) There are n libraries L1,L2,...,Ln. We want to store copies of a book in some of the libraries. Storing a copy at Li incurs an integer purchase cost ci > 0. A copy of the book is always stored at Ln. If a user requests the book from Li and Li does not have it, then Li+1,Li+2,... are searched sequentially until a copy of the book is found at Lj, for some j > i. This results in a user delay of j − i. (Note that, in this case, no library Lk with an index k smaller than i is searched; also, if the user finds the book at Li, then the user delay is 0.)
We define the total cost as the sum of all the purchase costs and all the user delays, assuming that there is one user in each of the n libraries. For example, if there are 4 libraries, and copies of the book are stored at L1 and L4, the total cost is c1 + c4 + 2 + 1.
Give an efficient algorithm that returns
(a) the minimum total cost; and
(b) a set of libraries where copies of the books must be placed to achieve the minimum total cost.
4. (35 points) A time-series is a sequence of integers a1,a2,...,an, where ai represents some signal at time i.
Often we need to be able to compare two time-series and declare whether they are similar or not. E.g., one time-series might represent the heart beats of a patient and the other a “normal” heart beat.
One way to compare two such time series, say a1,a2,...,an and b1,b2,...,bm is as follows. Define a matching to be a non-decreasing map f : [n] → [m], thought of as a map from indices of a to indices of b, such that f(i) ≤ f(j) whenever i < j. For a given matching f, the cost of the matching is .
We define the distance between a1,a2,...,an and b1,b2,...,bm to be the minimum cost(f) over all non-decreasing matchings f.
Design an efficient algorithm that computes the distance between two given sequences a1,a2,...,an and b1,b2,...,bm. For example, if the input sequences are 4,3,8,8,1 and 3,4,8,2, then the distance is 0 + 1 + 0 + 0 + 1 = 2, corresponding to the matching f(1) = 2,f(2) = 2,f(3) = 3,f(4) = 3,f(5) = 4 (other matchings also achieve this distance).
5. (35 points) You want to break a string of length n into m + 1 pieces. To this end, you are using a string-processing language that offers a primitive operation which splits the string into two pieces. This operation involves copying the original string, so it takes n units of time for a string of length n, regardless of the position of the cut.
Note that the order in which you make the cuts matters: for example, if you want to cut a 20-character string at positions 3 and 10, making the first cut at position 3 incurs a total cost of 20 + 17 = 37, while cutting at position 10 first has a better cost of 20 + 10 = 30.
Given n, and the positions of m cuts in a string of length n, design an efficient algorithm that computes the minimum cost of breaking the string into m + 1 pieces.
RECOMMENDED exercises: Do NOT return, they will not be graded.
1. A server has n customers waiting to be served. The service time for customer i is ti minutes. So if the customers are served in order of increasing i, the i-th customer spends minutes waiting to be served.
Given n, {t1,t2,...,tn}, design an efficient algorithm to compute the optimal order in which to process the customers so that the total waiting time below is minimized:
(time spent waiting by customer i)
2. https://leetcode.com/problems/climbing-stairs/.
3. You are managing a team of engineers and need to assign tasks to them for n weeks. Every week i for 1 ≤ i ≤ n, you can assign to the team one of two kinds of tasks: an easy task with revenue `i > 0 or a difficult task with revenue hi > 0. There is one constraint: if you pick a difficult task in week i, then you must assign no task to your team in week i − 1. That is, your team must be idle during week i − 1, thus earn revenue 0 in week i − 1.
Given sets of revenues `1,`2,...,`n and h1,h2,...,hn, you want to assign tasks to your team during the n weeks so that the total revenue V of the tasks is maximized, subject to the constraint above. Give an efficient algorithm that computes the optimal revenue V . (It is ok for your team to start with a difficult task in week 1.)
4. Give an O(n2) algorithm to compute the length of the longest increasing subsequence of a sequence of numbers a1,...,an. A subsequence is any subset of these numbers taken in order, of the form ai1,ai2,...,aik where 1 ≤ i1 < i2 < ... < ik ≤ n and an increasing subsequence is one in which the numbers are getting strictly larger.
For example, the longest increasing subsequence of 5,2,8,6,3,6,7 is 2,3,6,7 and its length is
4.
j
i and j such that P A[k] is maximized.
k=i
Design and analyze an algorithm for this task that runs in O(n) time.
6. Given two strings x = x1x2 ···xm and y = y1y2 ···yn, we wish to find the length of their longest common substring, that is, the largest k for which there are indices i and j such that
xixi+1 ···xi+k−1 = yjyj+1 ···yj+k−1.
Give an efficient algorithm for this problem.