Chapter 2Michelle Bodnar, Andrew LohrJanuary 3, 2018Exercise 2.1-131 41 59 26 41 5831 41 59 26 41 5831 41 59 26 41 5826 31 41 59 41 5826 31 41 41 59 5826 31 41 41 58 59Exercise 2.1-2Algorithm 1 Non-increasing Insertion-Sort(A)1: for j = 2 to A.length do2: key = A[j]3: // Insert A[j] into the sorted sequence A[1..j − 1].4: i = j − 15: while i > 0 and A[i] < key do6: A[i + 1] = A[i]7: i = i − 18: end while9: A[i + 1] = key10: end forExercise 2.1-3On each iteration of the loop body, the invariant upon entering is that thereis no index k < j so that A[k] = v. In order to proceed to the next iteration ofthe loop, we need that for the current value of j, we do not have A[j] = v. Ifthe loop is exited by line 5, then we have just placed an acceptable value in ion the previous line. If the loop is exited by exhausting all possible values of j,then we know that there is no index that has value j, and so leaving N IL in iis correct.Exercise 2.1-41Algorithm 2 Linear-Search(A,v)1: i = NIL2: for j = 1 to A.length do3: if A[j] = v then4: i = j5: return i6: end if7: end for8: return iInput: two n-element arrays A and B containing the binary digits of twonumbers a and b.Output: an (n + 1)-element array C containing the binary digits of a + b.Algorithm 3 Adding n-bit Binary Integers1: carry = 02: for i=n to 1 do3: C[i + 1] = (A[i] + B[i] + carry) (mod 2)4: if A[i] + B[i] + carry ≥ 2 then5: carry = 16: else7: carry = 08: end if9: end for10: C[1] = carryExercise 2.2-1n3/1000 − 100n2− 100n + 3 ∈ Θ(n3)Exercise 2.2-2Input: An n-element array A.Output: The array A with its elements rearranged into increasing order.The loop invariant of selection sort is as follows: At each iteration of the forloop of lines 1 through 10, the subarray A[1..i − 1] contains the i − 1 smallestelements of A in increasing order. After n − 1 iterations of the loop, the n − 1smallest elements of A are in the first n − 1 positions of A in increasing order,so the nthelement is necessarily the largest element. Therefore we do not needto run the loop a final time. The best-case and worst-case running times ofselection sort are Θ(n2). This is because regardless of how the elements areinitially arranged, on the ithiteration of the main for loop the algorithm alwaysinspects each of the remaining n− i elements to find the smallest one remaining.2Algorithm 4 Selection Sort1: for i = 1 to n − 1 do2: min = i3: for j = i + 1 to n do4: // Find the index of the ithsmallest element5: if A[j] < A[min] then6: min = j7: end if8: end for9: Swap A[min] and A[i]10: end forThis yields a running time ofn−1Xi=1n − i = n(n − 1) −n−1Xi=1i = n2− n −n2− n2=n2− n2= Θ(n2).Exercise 2.2-3Suppose that every entry has a fixed probability p of being the elementlooked for. A different interpretation of the question is given at the end of thissolution. Then, we will only check k elements if the previous k − 1 positionswere not the element being looked for, and the kth position is the desired value.This means that the probabilty that the number of steps taken is k is p(1 − p)k.The last possibility is that none of the elements in the array match what weare looking for, in which case we look at all A.length many positions, and ithappens with probability (1 − p).By multiplying the number of steps in each case by the probability that thatcase happens, we get the expected value of:E(steps) = A.length(1 − p)A.length+A.lengthXk=1k(1 − p)k−1pThe worst case is obviously if you have to check all of the possible positions,in which case, it will take exactly A.length steps, so it is Θ(A.length).Now, we analyze the asyptotic behavior of the average-case. Consider thefollowing manipulations, where first, we rewrite the single summation as a dou-ble summation, and then use the geometric sum formula twice.3E(steps) = A.length(1 − p)A.length+A.lengthXk=1k(1 − p)k−1p= A.length(1 − p)A.length+A.lengthXs=1A.lengthXk=s(1 − p)k−1p= A.length(1 − p)A.length+A.lengthXs=1pA.lengthXk=s(1 − p)k−1= A.length(1 − p)A.length+A.lengthXs=1p(1 − p)s−1− (1 − p)A.length1 − (1 − p)= A.length(1 − p)A.length+A.lengthXs=1(1 − p)s−1− (1 − p)A.length= A.length(1 − p)A.length+A.lengthXs=1(1 − p)s−1−A.lengthXs=1(1 − p)A.length=A.lengthXs=1(1 − p)s−1=1 − (1 − p)A.length1 − (1 − p)=1p−(1 − p)A.lengthpSince(1−p)A.lengthp> 0, we have that E(steps) <1p. Also, since A.length ≥ 1,we haveE(steps) >1p−1 − pp= 1Therefore, since we have bounded above and below by a constant, we getthe somewhat unintuitive result that the expected runtime as a function ofA.length, where p is held constant is Θ(1).A different way of interpreting this statement of this question is that thereis exactly one element in the array that is the one you are looking for, andthen each position is equally likely to be the one containing that element. Inthis case, the worst case behavior is unchanged, and the expected runtime isPA.lengthi=1iA.length=A.length+12. This makes the asymptotics for the expectedcase Θ(A.length).Exercise 2.2-44For a good best-case running time, modify an algorithm to first randomlyproduce output and then check whether or not it satisfies the goal of the al-gorithm. If so, produce this output and halt. Otherwise, run the algorithm asusual. It is unlikely that this will be successful, but in the best-case the runningtime will only be as long as it takes to check a solution. For example, we couldmodify selection sort to first randomly permute the elements of A, then check ifthey are in sorted order. If they are, output A. Otherwise run selection sort asusual. In the best case, this modified algorithm will have running time Θ(n).Exercise 2.3-1If we start with reading across the bottom of the tree and then go up levelby level.3 41 52 26 38 57 9 493 41 26 52 38 57 9 493 26 41 52 9 38 49 573 9 26 38 41 49 52 57Exercise 2.3-2The following is a rewrite of MERGE which avoids the use of sentinels. Muchlike MERGE, it begins by copying the subarrays of A to be merged into arraysL and R. At each iteration of the while loop starting on line 13 it selects thenext smallest element from either L or R to place into A. It stops if either Lor R runs out of elements, at which point it copies the remainder of the othersubarray into the remaining spots of A.Exercise 2.3-3Since n is a power of two, we may write n = 2k. If k = 1, T (2) = 2 = 2 lg(2).Suppose it is true for k, we will show it is true for k + 1.T
View Full Document
Unlocking...