CS 124 Homework 4: Spring 2023
Your name: Collaborators:
No. of late days used on previous psets:
No. of late days used after including this pset:
Homework is due Wednesday March 8 at 11:59pm ET. You are allowed up to twelve (college)/forty (extension school), but the number of late days you take on each assignment must be a nonnegative integer at most two (college)/four (extension school).
Try to make your answers as clear and concise as possible; style may count in your grades. Assign- ments must be submitted in pdf format on Gradescope. If you do assignments by hand, you will need to scan your papers to turn them in.
You may not write anything that you will submit within one hour of collaborating with other students, language models, the internet, etc., or using notes from such sources. That is, whatever you submit must first have been in your head alone, or notes produced by you alone, for an hour. Subject to that, you can collaborate with other students, e.g. in brainstorming and thinking through approaches to problem-solving.
For all homework problems where you are asked to give an algorithm, you must prove the correctness of your algorithm and establish the best upper bound that you can give for the running time. Generally better running times will get better credit; generally exponential-time algorithms (unless specifically asked for) will receive no or little credit. You should always write a clear informal description of your algorithm in English. You may also write pseudocode if you feel your informal explanation requires more precision and detail, but keep in mind pseudocode does NOT substitute for an explanation. Answers that consist solely of pseudocode will receive little or no credit. Again, try to make your answers clear and concise.
1. Polar Transformation: Given integers i, j ∈ {0, . . . , 2l − 1} we say i ⪯ j if every digit in
the binary representation of i is at most the corresponding digit in the binary representation
of j. Formally if i = Pl−1 ik2k and j = Pl−1 jk2k where i0,…,il−1,j0,…,jl−1 ∈ {0,1}, k=0 k=0
theni⪯jifandonlyifik ≤jk foreveryk∈{0,…,l−1}. Forbitsa,b∈{0,1}leta⊕b denotetheirXORortheirsummodulo2. (Soa⊕b=1iffa̸=b.)
For n = 2l the Polar Transformation Pn transforms n bits to n bits as follows: Pn(x0, . . . , xn−1) = (w0,…,wn−1) where
wj =Mxi. i⪯j
(For instance, w20 = x20 ⊕ x16 ⊕ x4 ⊕ x0.) In 2008, Erdal Arikan proved that the Polar Transformation can be used to extract an asymptotically optimal number of “nearly” unbiased coin tosses from a collection of biased coins. Specifically if the xi’s are outputs of n coins of known bias p, then there is a subset S ⊆ {0,…,2l − 1} with |S| ≈ A(p) · n, where A(p) is
the quantity defined in Lecture 1, such that {wi}i∈S are nearly unbiased coins. (The actual definition of “nearly unbiased” is omitted in this description and not needed to solve the problem.)
(a) Design an O(n log n) time algorithm to compute the Polar Transform, i.e., to compute Pn(x0,…,xn−1) given x0,…,xn−1.
(b) Design an O(nlogn) time algorithm to invert the Polar Transform, i.e., to compute (x0,…,xn−1) given (w0,…,wn−1) = Pn(x0,…,xn−1).
(a) First, let us claim the following recursive relation for Pn(x0, . . . , xn−1) as follows: Pn(x0, . . . , xn−1) = Pn/2(x0, . . . , xn/2−1), Pn/2(x0, . . . , xn/2−1) ⊕ Pn/2(xn/2, . . . , xn−1)
until the base case of P1(x0) = x0 (we have no need for floors or ceilings as n is a power of two). Here, ⊕ designates XORing corresponding elements together in Pn/2(x0, . . . , xn/2−1) and Pn/2(xn/2, . . . , xn−1).
With this, we can devise a divide and combine algorithm:
• Divide: Split the input (x0, . . . , xn−1) into two halves, (x0, . . . , xn/2−1) and (xn/2, . . . , xn−1). • Solve: Recursively call Pn/2 on these two halves to get A = Pn/2(x0, . . . , xn/2−1)
and B = Pn/2(xn/2, . . . , xn−1).
• Combine: Return(w0,…,wn−1)=(A,A⊕B).
Correctness: As our algorithm uses recursion, we can naturally prove its correctness via induction. Our base case is simply when n = 1. Here, our algorithm defines P1(x0) = x0. This is clearly correct as 0 ⪯ 0, so our algorithm satisfies the base case.
Now, let us assume that our algorithm is correct when calculating Pn/2 (again, we only have to worry about this case as n is a power of two). We can first look at the left half of the output, (w0, . . . , wn/2−1). All of the wj s in this half are defined as
wj =Mxi i⪯j
and since j ≤ n/2 − 1, i ≤ n/2 − 1 as well. However, this relationship is exactly what Pn/2(x0, . . . , xn/2 − 1) calculates for its jth output, and since wj is set to the jth output of A, our algorithm correctly finds the left half of the output.
For the right half of the output, as n is a power of two, all the indices n/2,…,n−1 have their highest bit set. This means that for any j in this range, we can split the indices i ⪯ j into two sets: S1 for those with their highest bit set to 0, and S2 for those with it set to 1. We also have a one-to-one mapping between these two sets, as swapping the highest bit will still make an index valid. For example, for j = 10012 the possible values of i are i = 00002, 00012, 10002, 10012, and so S1 = {00002, 00012}, S2 = {10002, 10012}. Now, let us consider any output wj in this right half. By our algorithm, it will be set to the j′th output of A ⊕ B, where j′ = j − n/2. In other words, j′ is simply j with its highestbitsetto0. Thisalsomeansthati⪯j′ iffi∈S1 ofj,andsoitfollowsthat
the j′th output of A correctly includes all the indices in S1. Additionally, as B is simply the same as A but with the highest bit on all the indices set to 1, by our one-to-one mapping described above it then follows that the j′th output of B correctly includes all the indices in S2. Combining them, then, will cover all the indices in S1 and S2, which is exactly all the i s.t. i ⪯ j. This proves that A ⊕ B correctly gives the right half of our output, and so we have proven that our algorithm correctly calculates Pn(x0, . . . , xn−1). Runtime: Note that the combine step of our algorithm takes O(n) time, as we have to XOR n/2 elements when calculating A ⊕ B. Since we divide into two equal halves every recursive step, we get the recurrence
T (n) = 2T (n/2) + O(n) for our runtime, which comes out to T (n) = O(n log n).
(b) We claim that Pn(Pn(x0, . . . , xn−1)) = (x0, . . . , xn−1). Thus, if this is true, then we can simply run our algorithm from part (a) on (w0, . . . , wn−1) to recover (x0, . . . , xn−1). Since we know that this algorithm takes O(nlogn) time, we immediately get an O(nlogn) time algorithm to invert the Polar Transform.
Now we just need to prove that Pn(Pn(x0,…,xn−1)) = (x0,…,xn−1). By definition, this is the same as proving that
xj = M wi = M M xk i⪯j i⪯j k⪯i
Wecanseefromthisthatxj canbewrittenastheXORofallxk s.t. k⪯j,butwith each term potentially XOR’d multiple times. We want to show that every xk that is not xj appears some even number of times, so that they all cancel out when XORing. To help us count the number of times each term is included, let us define l as the number of bits set to 1 in j, and k(m) ⪯ j as an index that shares exactly m of these set bits with j. Then xk(m) will be included in wi iff i has the same m bits set as well. This means that the other l − m bits are free to take on whatever value, so xk(m) will be included in 2l−m of the wis.
Let us look at an example of this notation when j = 1102 = 6 and l = 2. If we consider the index k(1) = 0102 = 2, our claim says that x2 will appear 22−1 = 2 times in the expansion of x6, and this is exactly what we see:
x6 =w6 ⊕w4 ⊕w2 ⊕w0
= (x6 ⊕x4 ⊕x2 ⊕x0)⊕(x4 ⊕x0)⊕(x2 ⊕x0)⊕(x0)
Thesamecanbedonefork(2) =1102 =6,k(1) =1002 =4,andk(0) =0002 =0.
Now that we have this notation, the rest of the proof quickly follows. As 2l−m is even for all m < l, this means that every xk(m) will appear an even number of times in the XOR formula and thus cancel out. The only case when this is not true is when m = l. However, since j has exactly l bits, this only applies when k = j. Altogether, we get that
xj =MMxk =xj i⪯j k⪯i
proving that Pn(Pn(x0, . . . , xn−1)) = (x0, . . . , xn−1). 3
2. Consider an algorithm for integer multiplication of two n-digit numbers where each number is split into three parts, each with n/3 digits. (You may assume that n is a power of 3.)
(a) (15 points) Design and explain such an algorithm, similar to the integer multiplication algorithm presented in class. Your algorithm should describe how to multiply the two integers using only six multiplications on the smaller parts (instead of the straightforward nine).
(b) (7 points) Determine the asymptotic running time of your algorithm. Would you rather split it into two parts or three parts?
(c) (7 points) Suppose you could use only five multiplications instead of six. Then deter- mine the asymptotic running time of such an algorithm. In this case, would you rather split it into two parts or three parts?
(d) (0 points, optional)1 Find a way to use only five multiplications on the smaller parts.
(e) (0 points, optional)2 (Harder; Adam will be impressed if you solve it.) Generalize the previous subproblem to when the two initial n-digit numbers are split into k parts, each with n/k digits. (You may assume that n is a power of k.) Hint: also consider multiplication by a constant, such as 2; note that multiplying by 2 does not count as one of the five multiplications. You may need to use some linear algebra.
(a) Suppose we want to multiply two numbers x = a102n/3 + b10n/3 + c and y = d102n/3 + e10n/3 + f where a,b,c,d,e,f each have at most n/3 digits. We want to find x · y = (ad)104n/3 + (ae + bd)10n + (af + be + cd)102n/3 + (bf + ce)10n/3 + (cf) using only 6 multiplications of n/3-digit numbers. Notice that
ae + bd = (a + b)(d + e) − ad − be
af + be + cd = (a + b + c)(d + e + f) − (a + b)(d + e) − (a + b)(d + e) + be bf + ce = (b + c)(e + f) − cf − be
We can generate all of the coefficients for our product xy using only the following 6
multiplications: i. ad
iv. (a+b)(d+e)
v. (a+b+c)(d+e+f) vi. (b+c)(e+f)
1We won’t use this question for grades. Try it if you’re interested. It may be used for recommendations/TF hiring. 2We won’t use this question for grades. Try it if you’re interested. It may be used for recommendations/TF hiring.
Computer Science Tutoring
In our algorithm, we compute 6 products of n/3 digit numbers, along with a constant number of additions and subtractions on O(n) digit numbers which all take linear time, so our recurrence is
T (n) = 6T (n/3) + O(n).
By Master’s Theorem, we get that T(n) = Θ(nlog3 6) ≈ Θ(n1.63). Since this is slower than Karatsuba’s algorithm, which is Θ(nlog2 3) ≈ Θ(n1.585), you would rather split it into two parts.
Similar to part b, if we compute 5 products of n/3 digit numbers, along with a constant number of additions and subtractions on O(n) digit numbers which all take linear time, our recurrence is
T (n) = 5T (n/3) + O(n).
By Master’s Theorem, we get that T(n) = Θ(nlog3 5) ≈ Θ(n1.465), which is better than
Karatsuba’s algorithm, so you would rather split it into three parts.
This problem is somewhat difficult! You can learn about some of the techniques used here and here.
See part d
(25 points)
Suppose we want to print a paragraph neatly on a page. The paragraph consists of words of length l1,l2,…,ln. The recommended line length is M. We define a measure of neatness as follows. The extra space on a line (using one space between words) containing words li through lj is A = M − j + i − Pjk=i lk. (Note that the extra space may be negative, if the length of the line exceeds the recommended length.) The penalty associatedwiththislineisA3 ifA≥0and2−A−A3−1ifA≤0. Thepenaltyforthe entire paragraph is the sum of the penalty over all the lines, except that the last line has no penalty if A ≥ 0. Variants of such penalty function have been proven to be effective heuristics for neatness in practice. Find a dynamic programming algorithm to determine the neatest way to print a paragraph. Of course you should provide a recursive definition of the value of the optimal solution that motivates your algorithm.
(20 points) Determine the minimal penalty, and corresponding optimal division of words into lines, for the text of this question, from the first ‘Determine’ through the last ‘correctly.)’, for the cases where M is 40 and M is 72. Words are divided only by spaces (and, in the pdf version, linebreaks) and each character that isn’t a space (or a linebreak) counts as part of the length of a word, so the last word of the question has length eleven, which counts the period and the right parenthesis. (You can find the answer by whatever method you like, but we recommend coding your algorithm from the previous part. You don’t need to submit code.) (The text of the problem may be easier to copy-paste from the tex source than from the pdf. If you copy-paste from the pdf, check that all the characters show up correctly.)
Solution. Let dp[j] represent the minimum penalty for fitting words 1 through j on the page (summing the penalty over all lines, so we aren’t accounting for the fact that the last line is not penalized yet). Our base case is
dp[0] = 0, 5
Code Help
since printing no words means no penalty.
DefineAij =M−j+i−Pjk=ilk tobetheextraspaceattheendofalinewithwordsi
through j (note that space(i,j) is negative iff words i through j do not fit on a line).
(A3ij Aij ≥ 0 cost(i,j)= 2−Aij−A3ij−1 Aij<0
Then, a recursive relation for j ∈ {1, . . . , n − 1} is
dp[j] = min(dp[k] + cost(k + 1, j)),
where the minimum is taken over all k < j. This is correct because in the optimal solution for fitting l1,...,lj on a page, we clearly must have some last line with lk+1,...,lj for some k. Thus, the optimal overall penalty, given that the last line is lk+1,...,lj, is dp[k]+cost(k+1,j) (since dp[k] is our minimum penalty for words 1 through k and we add the penalty for our last line). Then, we just need to take the minimum penalty over all possible last lines, which is exactly what our DP step is doing.
After we’ve filled in the values of dp[j] for j = 1, . . . , n, we then can find the optimal penalty for fitting all of the words and account for the cases where the last line has no penalty. Since the last line doesn’t get added to the penalty when it has non-negative space, our overall minimum penalty for the whole paragraph is
dp[n] = min(dp[n], min(dp[k])) k
where the minimum is taken over all k < n such that Akn ≥ 0.
Runtime: First we show that when we are calculating dp[j] by taking the minimum over k < j we only have to consider k from j −1 down to j −(5M +1). This is because any given word takes up a non-negative amount of space and consecutive words have spaces between them, so no more than 5M + 1 words will result in 5M spaces which means the remaining space is less than −4M. We can clearly see that the cost associated with −M remaining space is strictly larger than if we just split the line into a word per line since the maximum cost will be less than M4 (assuming no words over M length). Informally, this is because negative space cost scales exponentially while the positive space cost is polynomial. (Should also talk about how this is the same even if there are words with length greater than M, this is true because of the concavity of 2x, so k2x < 2kx, so splitting the words up will always be better).
Thus, our algorithm’s is O(nM) since there are O(n) values in our dp array and calculating each value is O(M) time.
Note that the initial pre-processing to calculate all the word lengths li is also O(nM) since each li ≤ M and there are n words. Thus, this does not affect the asymptotic runtime.
Backtracking: dp[n] only gives us the optimal penalty, but doesn’t actually tell us how to split the paragraph lines. To actually track which words to split the lines at, for each dp[j], store the k that minimizes the dp[j] calculation in prev[j]. Then, we can backtrack starting from n to find the indices of the last word in each line.
Specifically, we backtrack by considering prev[n] = k1, then prev[k1] = k2, then prev[k2] = k3, until we reach prev[km] = 0. The list km, km−1, . . . , k2, k1, n gives us the index of the word at the end of each line (km is for the first line, km−1 is the second line, and so on) in our optimal split.
4. (25 points) Consider the following string compression problem. We are given a dictionary of m strings, each of length at most k. We want to encode a data string of length n using as few dictionary strings as possible. For example, if the data string is bababbaababa and the dictionary is (a,ba,abab,b), the best encoding is (b,abab,ba,abab,a). Give an O(nmk) algorithm to find the length of the best encoding or return an appropriate answer if no encoding exists.
(a) Why does greedy not work?
(b) Dynamic programming may be useful here.
(c) Does the complexity give us any hints for what our dynamic programming state could
be? Remember that the final complexity is the product of the number of states and the time to calculate each state.
(d) What subproblems would lead to natural update steps? What if we considered the minimum strings required for the substring till position i?
Solution. Let s be the string that we want to encode, and let D be our dictionary.
First, do some initial pre-processing to get the lengths of each word in the dictionary w ∈ D and store this as length(w); also, divide into a separate dictionary for each word length. Define dp[j] to be the length of the best encoding for s[1, j] (the substring of s from character 1 to character j). Our base case is
dp[0] = 0,
which is correct since it takes 0 strings to encode 0 characters. Then, we can define our
recursion as
dp[j] = min(dp[l] + 1), l
wherel∈[0,j−1]suchthats[l+1,j]∈D. Ifnosuchlexists,wehavedp[j]=∞. Totake this minimum, we can just consider s[l + 1, j] and check if it equals w, for each word w in the dictionary of length l.
This recursion is correct since to encode s[1,j] optimally, there must exist some dictionary word at the end of the string if this encoding is possible. If a dictionary word exists at s[l + 1, j], then the number of dictionary words in the optimal encoding, given that you must use s[l + 1, j], is dp[l] + 1. This is because dp[l] is the length of the optimal encoding for s[1, l] and then we add one to account for s[l + 1, j]. Thus, we just need to find the l that minimizes dp[l] + 1, over all l such that s[l + 1, j] is a dictionary word, which is exactly what our algorithm does.
By definition of dp[j], our final answer is dp[n], since this is the length of the best encoding for s[1, n].
Run time: The initial preprocessing (counting word lengths) takes O(mk) time.
We must calculate dp[1],dp[2],...,dp[n]. Let’s consider how long it takes to calculate each
For each word w ∈ D, define lw := j − length(w). Recall that dp[j] = minl(dp[l] + 1) where l ∈ [0,j −1] such that s[l+1,j] ∈ D. There are m words in D, each of which needs to be checked exactly once in calculating dp[j], and checking string equality takes at most O(k) time to compare character by character, so calculating dp[j] is O(mk).
Since calculating dp[j] is O(mk), our overall algorithm has O(nmk) running time.
程序代写 CS代考 加QQ: 749389476