Chapter 4Michelle Bodnar, Andrew LohrFebruary 5, 2018Exercise 4.1-1It will return the least negative position. As each of the cross sums arecomputed, the most positive one must have the shortest possible lengths. Thealgorithm doesn’t consider length zero sub arrays, so it must have length 1.Exercise 4.1-2Algorithm 1 Brute Force Algorithm to Solve Maximum Subarray Problemlef t = 1right = 1max = A[1]curSum = 0for i = 1 to n do // Increment left end of subarraycurSum = 0for j = i to n do // Increment right end of subarraycurSum = curSum + A[j]if curSum > max thenmax = curSumlef t = iright = jend ifend forend forExercise 4.1-3The crossover point is at around a length 20 array, however, the times wereincredibly noisy and I think that there was a garbage collection during the run,so it is not reliable. It would probably be more effective to use an actual profilerfor measuring runtimes. By switching over the way the recursive algorithmhandles the base case, the recursive algorithm is now better for smaller values ofn. The chart included has really strange runtimes for the brute force algorithm.These times were obtained on a Core 2 duo P8700 and java 1.8.0.51.1In the chart of runtimes, the x axis is the length of the array input. The yaxis is the measured runtime in nanoseconds.Exercise 4.1-4First do a linear scan of the input array to see if it contains any positiveentries. If it does, run the algorithm as usual. Otherwise, return the emptysubarray with sum 0 and terminate the algorithm.Exercise 4.1-5See the algorithm labeled linear time maximum subarray.Exercise 4.2-12Algorithm 2 linear time maximum subarray(A)1: M = −∞2: lowM, highM= null3: Mr= 04: lowr= 15: for i from 1 to A.length do6: Mr+ = A[i]7: if Mr> M then8: lowM= lowr9: highM= i10: M = Mr11: end if12: if Mr< 0 then13: Mr= 014: lowr= i + 115: end if16: end for17: return (lowM, highM, M)S1= 8 − 2 = 6S2= 1 + 3 = 4S3= 7 + 5 = 12S4= 4 − 6 = −2S5= 1 + 5 = 6S6= 6 + 2 = 8S7= 3 − 5 = −2S8= 4 + 2 = 6S9= 1 − 7 = −6S10= 6 + 8 = 14P1= 6P2= 8P3= 72P4= −10P5= 48P6= −12P7= −843C11= 48 − 10 − 8 − 12 = 18C12= 6 + 8 = 14C21= 72 − 10 = 62C22= 48 + 6 − 72 + 84 = 66So, we get the final result:18 1462 66Exercise 4.2-2As usual, we will assume that n is an exact power of 2 and A and B are nby n matrices. Let A[i..j][k..m] denote the submatrix of A consisting of rows ithrough j and columns k through m.Exercise 4.2-3You could pad out the input matrices to be powers of two and then run thegiven algorithm. Padding out the the next largest power of two (call it m) willat most double the value of n because each power of two is off from each otherby a factor of two. So, this will have runtimemlg 7≤ (2n)lg 7= 7nlg 7∈ O(nlg 7)andmlg 7≥ nlg 7∈ Ω(nlg 7)Putting these together, we get the runtime is Θ(nlg 7).Exercise 4.2-4Assume that n = 3mfor some m. Then, using block matrix multiplication,we obtain the recursive running time T (n) = kT (n/3) +O(1). Using the Mastertheorem, we need the largest integer k such that log3k < lg 7. This is given byk = 21.Exercise 4.2-5If we take the three algorithms and divide the number of multiplicationsby the side length of the matrices raised to lg(7), we approximately get the4Algorithm 3 Strassen(A, B)if A.length == 1 thenreturn A[1] · B[1]end ifLet C be a new n by n matrixA11 = A[1..n/2][1..n/2]A12 = A[1..n/2][n/2 + 1..n]A21 = A[n/2 + 1..n][1..n/2]A22 = A[n/2 + 1..n][n/2 + 1..n]B11 = B[1..n/2][1..n/2]B12 = B[1..n/2][n/2 + 1..n]B21 = B[n/2 + 1..n][1..n/2]B22 = B[n/2 + 1..n][n/2 + 1..n]S1= B12 − B22S2= A11 + A12S3= A21 + A22S4= B21 − B11S5= A11 + A22S6= B11 + B22S7= A12 − A22S8= B21 + B22S9= A11 − A21S10= B11 + B12P1= Strassen(A11, S1)P2= Strassen(S2, B22)P3= Strassen(S3, B11)P4= Strassen(A22, S4)P5= Strassen(S5, S6)P6= Strassen(S7, S8)P7= Strassen(S9, S10)C[1..n/2][1..n/2] = P5+ P4− P2+ P6C[1..n/2][n/2 + 1..n] = P1+ P2C[n/2 + 1..n][1..n/2] = P3+ P4C[n/2 + 1..n][n/2 + 1..n] = P5+ P1− P3− P7return C5following values374539634167This means that, if used as base cases for a Strassen Algorithm, the first onewill perform best for very large matrices.Exercise 4.2-6By considering block matrix multiplication and using Strassen’s algorithm asa subroutine, we can multiply a kn×n matrix by an n×kn matrix in Θ(k2nlog 7)time. With the order reversed, we can do it in Θ(knlog 7) time.Exercise 4.2-7We can see that the final result should be(a + bi)(c + di) = ac − bd + (cb + ad)iWe will be multiplyingP1= (a + b)c = ac + bcP2= b(c + d) = bc + bdP3= (a − b)d = ad + bdThen, we can recover the real part by taking P1−P2and the imaginary partby taking P2+ P3.Exercise 4.3-1Inductively assume T (n) ≤ cn2, were c is taken to be max(1, T (1)) thenT (n) = T (n −1) + n ≤ c(n −1)2+ n = cn2+ (1 −2c)n + 1 ≤ cn2+ 2 −2c ≤ cn2The first inequality comes from the inductive hypothesis, the second from thefact that n ≥ 1 and 1 − 2c < 0. The last from the fact that c ≥ 1.Exercise 4.3-2We’ll show T (n) ≤ 3 log n − 1, which will imply T (n) = O(log n).T (n) = T (dn/2e) + 1≤ 3 log(dn/2e) − 1 + 1≤ 3 log(3n/4)= 3 log n + 3 log(3/4)≤ 3 log n + log(1/2)= 3 log n − 1.6Exercise 4.3-3Inductively assume that T (n) ≤ cn lg n where c = max(T (2)/2, 1). Then,T (n) = 2T (bn/2c) + n ≤ 2cbn/2clg(bn/2c) + n≤ cn lg(n/2) + n = cn(lg(n) − 1) + n = cn(lg(n) − 1 +1c) ≤ cn lg(n)And so, T (n) ∈ O(n lg(n)).Now, inductively assume that T(n) ≥ c0n lg(n) where c0= min(1/3, T (2)/2).T (n) = 2T (bn/2c) + n ≥ 2c0bn/2clg(bn/2c) + n ≥ c0(n − 1) lg((n − 1)/2) + n= c0(n − 1)(lg(n) − 1 − lg(n/(n − 1))) + n= c0n(lg(n) − 1 − lg(n/(n − 1)) +1c0) − c0(lg(n) − 1 − lg(n/(n − 1)))≥ c0n(lg(n) − 2 +1c0−(lg(n − 1) − 1)n) ≥ c0n(lg(n) − 3 +1c0) ≥ c0n lg(n)So, T (n) ∈ Ω(n). Together with the first part of this problem, we get thatT (n) ∈ Θ(n).Exercise 4.3-4We’ll use the induction hypothesis T (n) ≤ 2n log n + 1. First observe thatthis means T (1) = 1, so the base case is satisfied. Then we haveT (n) = 2T (bn/2c) + n≤ 2((2n/2) log(n/2) + 1) + n= 2n log(n) − 2n log 2 + 2 + n= 2n log(n) + 1 + n + 1 − 2n≤ 2n log(n) + 1.Exercise 4.3-5If n is even, then that step of the induction is the same as the “inexact”recurrence for merge sort. So, suppose that n is odd, then, the recurrence isT (n) = T ((n + 1)/2) + T ((n − 1)/2) + Θ(n). However, shifting the …
View Full Document
Unlocking...