Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Homework 4

Math 182, Fall 2021

This homework assignment has 6 regular problems (consisting of 5 written problems and 1 programming problem), plus one redemption problem for homework 2 and one redemption problem for homework 3. You should submit 4 of the 6 regular problems. You may also optionally submit at most one redemption problem.

Due date: Friday, October 29 at 5 pm PDT. Turn in the written problems on gradescope. See below for instructions on submitting the programming problem.

Question 1: Greedy partition

Suppose you have a list, X, of positive integers. You would like to form two lists, A and B, such that every entry in X is in either A or B and the maximum of the sum of A and the sum of B is as small as possible.

Example. If X = [5, 3, 4, 7, 5] then the best choice of A and B is A = [5, 7] and B = [3, 4, 5] and the maximum of their two sums is 12.

You decide to solve this problem using a greedy algorithm: at each step, put the next element of X into whichever of A and B currently has the smaller sum.

(a) Show that this algorithm does not always find the correct answer—i.e. give an example of a list X for which the algorithm will not find lists A and B with smallest possible maximum sum.

(b) Show that if the smallest possible value of the maximum of the sum of A and the sum of B is k then the greedy algorithm described above will always find a partition for which the maximum of the sum of A and the sum of B is at most 3k/2.

Question 2: Dynamic coins

Design an efficient algorithm to solve the problem from question 1 on homework 3. Recall that in that problem you are given a list of coin values v1, . . . , vn and a price p and you want to find the smallest number of coins whose values add up to p. Assume that you have an unlimited supply of each type of coin and that there is always some choice of coins whose values add up to p.

Example. Suppose the coins have values 1, 2, 7, and 20. If the price is 31 then minimum number of coins required is 4—one coin of value 20, one coin of value 7 and two coins of value 2.

Question 3: Restaurant placement

You operate a chain of restaurants along a highway. There is a rest stop located every mile along the highway and you can put a restaurant at any rest stop. However, some rest stops are more popular than others so restaurants placed at those rest stops will make more money. Also, to prevent your restaurants from competing with each other, you are not allowed to place any restaurants within k miles of each other (exactly k miles apart is fine though). Design an efficient algorithm to find the amount of money the restaurants will earn when they are placed in the best possible way.

Assume that you are given a length n array A containing the expected income from placing a restaurant at each mile along the highway and a positive integer k, indicating the closest that two restaurants can be to each other. You need to find the maximum possible value of A[i1] + A[i2] + . . . + A[im] for all choices of indices i1 < i2 < . . . < im, subject to the constraint that ii ≤ i2 − k, i2 ≤ i3 − k and so on. For full credit, your algorithm should run in O(nk) time. For partial credit, find any algorithm whose running time is a polynomial in n and k.

Example. Suppose A = [2, 1, 5, 6, 5, 1, 1, 3] and k = 2. Then the maximum amount of money possible is 15, which is given by choosing the restaurants at positions 1, 3, 5, and 8 in the array.

Question 4: Longest common subsequence

Design an efficient algorithm to solve the following problem: given two sequences of integers, a1, . . . , an and b1, . . . , bm, find the length of the longest sequence which is a subsequence of both of them.

Example. If the sequences are 1, 2, 3, 4, 5, 6, 7 and 5, 7, 2, 4, 8, 1, 6, 7, 7 then the longest common subse-quence is 2, 4, 6, 7, which has length 4.

Question 5: Cut the cloth

Suppose you have a large rectangular piece of cloth of dimensions n × m, where n and m are positive integers. Also, for each pair of positive integers, (w, l), there is a fixed price at which you can sell rectangular pieces of cloth with dimensions w × l. You also have a machine that can cut any rectangular piece of cloth into two pieces along any horizontal or vertical line. You want to find the maximum amount of money you can get for your cloth if you cut it up in the optimal way. Design an efficient algorithm to solve this problem.

You should assume that you are given the integers n and m and an array P such that for each pair of positive integers w and l, P[w, l] is the price for which you can sell a rectangular piece of cloth of dimensions w × l. Also assume that P[w, l] = P[l, w] for all w, l (i.e. you cannot get a higher price for a piece of cloth by rotating it 90◦ ).

Question 6: Programming problem: Chain matrix multiplication

Note: The test cases and starter code for this problem are not ready yet and will be posted on canvas sometime on Saturday morning.

In this problem, you will write a program to solve the chain matrix multiplication problem discussed in lecture. However, instead of just returning the minimum number of multiplications, you will also return the optimal placement of parentheses. For example, if the matrices are A1, A2, A3, A4 with dimensions 2 × 3, 3 × 1, 1 × 5 and 5 × 1, respectively, then the minimum number of multiplications required is 13 and the optimal placement of parentheses is

(A1 × A2) × (A3 × A4).

Input. The input is contained in a file called input.txt. The first line of this file consists of a single integer t—the number of test cases. The first line of each test case contains a number n—the number of matrices to multiply. You may assume n ≥ 1. The second line contains a list of n positive integers, separated by spaces, indicating the number of rows in each matrix. The third line also contains a list of n positive integers, separated by spaces, indicating the number of columns in each matrix. In all there are 3t + 1 lines in the file.

Output. Your output should consist of a file called output.txt. For each test case, you should print two lines. On the first, print the minimum number of multiplications needed to find the product of all the matrices in the test case (where, as in lecture, we will assume that to find the product of an n × m matrix and an m × p matrix takes nmp multiplications). On the second, print the optimal way to put parentheses around the matrices. However, instead of each matrix you should simply print an uppercase A and for each multiplication you should print a lowercase x. For example, if the optimal parenthesization is (A1 × A2) × (A3 × A4) then you should print (AxA)x(AxA).

Example. Below is an example of sample input and output. You may use this sample input to test your program but you should only submit the answers to the input in the file on canvas.

Note that any unambiguous parenthesization is acceptable—for example instead of (AxA)x(AxA) in the last example above you could print (((A)x(A))x((A)x(A))).

Starter code. You are free to use any programming language to solve the problem. However, if you would like a little help getting started, the folder “Homework 4 Problem 6” on canvas contains a file called chain_matrix.py containing python code to parse input in the required format, along with instructions in the comments about how to run the program. You are free to use this starter code if you want, but you can also ignore it.

Submission instructions. You can find all the files necessary to complete the problem on canvas in the folder “Homework 4 Problem 6” in the “Homework” folder. You will submit your code, along with your output file, on Gradescope to the assignment called “Homework 4 Problem 6.” You should submit the following files.

● output.txt: Described above. Make sure that the name of this file is exactly “output.txt” and that it is not contained in any directory.

● readme.txt: This file should include complete instructions about how to run your code. Make sure to specify what programming language you used, along with the language version and the compiler/interpreter that you used (if you’re not sure what compiler you used, just leave this part out).

● Your code, along with whatever auxiliary files, directories, etc are needed to make your code work.

Upload all of these files to Gradescope. Note that you should not place these files in a directory or a zipped folder or anything like that. Just upload them directly. Assuming things are working correctly, you should be able to see your score within a few minutes of submission. You may resubmit as many times as you like before the deadline.

Question 7: Redemption problem for homework 2

Design an efficient algorithm to solve the following problem: given two sorted lists of integers, A and B, find the median element of the union of the two lists. For full credit, your algorithm should run in time O(log(n) + log(m)) where n and m are the lengths of A and B, respectively.

Example. If A = [1, 2, 3, 5, 10] and B = [2, 4, 5, 5] then the median of the union of the two lists is 4.

Question 8: Redemption problem for homework 3

Design an efficient algorithm to solve the following problem. Given an array A of integers, find the minimum number of subarrays of A such that each subarray has positive sum and each positive integer in the array is contained in one of the subarrays. If the array does not contain any positive numbers then your algorithm should output 0.

Example. If A = [3, -5, 7, -4, 1, -8, 3, -7, 5, -9, 5, -2, 4] then the smallest number of subarrays required is 3—the subarrays [3, -5, 7, -4, 1], [3, -7, 5], and [5, -2, 4] all have positive sum and cover every positive entry in the array.