-*-Fundamental-*- THIS FILE CONTAINS SELECTED SOLUTIONS TO PROBLEMS ASSIGNED IN COSI 30B The notation sometimes uses LaTeX-like notation, e.g. x_i for x sub i; x^i for x super i; \SUM for summation sign; \PROD for product sign; etc. ------------------------------------------------------------------------- Selection Sort: Done in the stated way, best case is THETA(n^2) because of the necessity of finding min n times. Worst case is also THETA(n^2), so average case, too, is THETA(n^2) Exercise 1.3-6: The number of comparisons can be reduced, but the number of assignments (data moves) remains OMEGA(n^2) Problem 1-3d: This problem asks you to modify mergesort so as to count number of inversions in permutations. The answer given in class was glib and incorrect. Here's a better one: Imagine writing the original permuted data above its final locations, and connecting each original element to its destination with a line, either slanting left, if the element ends up earlier than it was; or vertical,if it ends up at the same place; or slanting right if it ends up later. Pictorially, an inversion is represented by two lines crossing. The total number of crossings is the number of inversions. Now the same description can be used during mergesort, where elements do their crossings in lg(n) rounds, rather than all at once. The count will still be correct, because elements always move TOWARDS their destinations during mergesort. In each recursive call to mergesort, an element starts out in one half of a subarray, called either L or R, and ends up in either L or R. These observations make it possible to do the count: 1. Elements in L never cross one another, ditto for R. (Because L and R are already sorted. 2. Through the lg(n) rounds elements progress only in the direction they're destined for. Therefore we can sum up the crossings through the rounds. 3. A crossing takes place only when an R element becomes an L element, and the number of L elements it crosses is exactly mid - l_index + 1. So these numbers are what we must sum. (By symmetry, we could also discuss L elements crossing R elements.) So Merge'(A, lo, mid, hi) while l_ptr and r_ptr in bounds do if A[l_ptr] <= A[r_ptr] B[k] <- A[l_ptr]; l_ptr <- l_ptr + 1; k <- k+1; else B[k <- A[r_ptr]; r_ptr <- r_ptr + 1; k <- k+1; inversions <- inversions + mid - l_ptr + 1; /* number of L elements crossed */ etc. In writing Merge, a number of people indexed R (the right subarray) with A[mid + i + j]. But this index increases whether L is copied or R is copied, so it will never finish an input like [1,3,2,4]. Also, any scheme where "inversions" is incremented by 1 each time is bound to run in worst-case OMEGA(n^2), so it can't work. 9.1-1: n-1, because every key must be compared to something. 9.1-3: At linear depth, there can be at most 2^{cn} leaves. But for any constant c, 2^{cn} is less than n!/2, less than n!/n = (n-1)!, and less than n!/2^n. Recall that lg(n!) = THETA(n^n) and take logs of n!/2, (n-1)!, and n!/2^n. 9.1-5: Again, you can't merge correctly if you don't test every key. 9.1-6: There are (k!)^{n/k} such permutation. The lg of this is (n/k)*klgk, which is the minimum depth at which that many leaves can occur. 9.2-3: Discussed in class; the sort is not stable. 9.2-4: I suppose they intend the temporary array C to be used. I'm sorry I asked. 9-1a): By determinism, each input permutation labels exactly one leaf. 12.1-2: Use the bit vector as a "characteristic function", in which a 0 in the i^{th} position denotes the absence of the i^{th} element and a 1 denotes its presence. 12.1-3: Let the k^{th} slot point to the respective objects with key k. 12.2-1: In a sequence independent trials, the expected number of "successes" is the probability of success times the number of trials. Let the trials consist of drawing pairs of keys, and "success" correspond to a collision. The number is either n(n-1) or n(n-1)/2, depending on how you read it. The probability of collision is 1/m. So n(n-1)/m or n(n-1)/2m. 12.2-3: For every order of insertions there is an order which gives the reverse list. This symmetry balances out the location of insertions. 12.4-1 and 12.4-4 are exercises. 13.1-1: exercise 13.1-5: A BST is built by comparisons; inorder traversal of a BST achieves sorting. So the total time MUST be at least nlgn. 13.2-2: Build a BST by inserting 1, 4, 2, 5. Then search for 5. 2 is in A but is not smaller than 1 which is in B. 17.1-3 Activity Selection counterexamples: a) least duration: (0,3), (3,6),(6,9),(9,12), (5,7); if you choose the (5,7) you can't get a solution of cardinality 4. b) fewest overlaps: (0,2),(2,4),(4,6),(6,8), three copies each of (1,3) and (5,7), one copy of (3,5). The last has fewest overlaps (two) but precludes the optimal solution using the first four. 17.2-1 Suppose the ratio v'/w' is maximal. Then v'/w' >= v/w for any other pair (v,w), so v'v/w' > v for any other (v,w). Suppose a solution does not contain the full w' weight of the best ratio. Then replacing an amount of any other w with more of w' will improve the value. 17.2-3 Again, if v'/w' is not used, it can replace any other v/w because w' < w, but it increases the value because v' > v. 17.3-2 The tree is one long limb with leaves hanging off. This is true for Fibonacci weights in general, because the recurrence F_{i+1} = F_{i} + F_{i-1} implies SUM_i F_i = F_{i+2} - 1. To prove this, write F_j as F_{j+1} - F_{j-1} and sum from 0 to i, remembering that F_{-1} = 0. 17.3-3 If the weights are distributed from the leaves upwards with each parent node getting the weights of its children, then weight w_i appears l_i times on the i^{th} path from leaf to root. Thus when all the interior node weights are summed, the result is SUM_i (w_i)*(l_i). 22.1-1 Exercise 22.3-1 The Finds in the Unions in line 3 return 1,2,3,....,16. The structures are 2 4 6 8 10 12 14 16 / / / / / / / / 1 3 5 7 9 11 13 15 For line 5: 2,4,6,...,16 and 4 8 12 16 /| /| /| /| 2 3 6 7 10 11 14 15 / / / / 1 5 9 13 Line 7 returns 4,8 and builds 4---->8 where 8 is parent of 4 /|\ /|\ 1 2 3 5 6 7 Line 8 returns 12, 16 and 12----->16 /| /|\ 10 11 13 14 15 / 9 and so on. 22.3-2: Use a trailing temp pointer which becomes the parent of each node on the search path. Then set temp <--- Find(x) 22.3-3: Build a binomial tree on n elements. Using union-by-rank, it will have height lgn and costs THETA(nlgn). Then do m-n finds on the handle, the deepest leaf in the tree. This costs mlgn. The total is OMEGA( (m+n)lgn ) which is OMEGA(mlgn) if m >> n. 36.1-5 To "accept" a language, an algorithm (Turing Machine) halts on all x in L, but may not halt on x not in L. If on "yes" instances the algorithm always halts in time < cn^k, then another algorithm can be designed to stop itself after cn^k steps, and thus decide the language. 36.1-6 The trick here is to devise a procedure that creates a super polynomial object in polynomial calls. But remember that the sizeof an integer n is lg(n), so doubling works: lg(n) doublings give a factor of 2^{lg(n)} which is n, exponential in lg(n). Squaring works even better (or worse): MAIN(n) SQUARE(x) x <-- 2; x <-- x*x i <-- n; while( i >= 1 ) x <-- SQUARE(x) i <-- i/2 endwhile SQUARE takes about 3 lg(x) bit operations, so is linear in sizeof(x) MAIN takes lg(n) iterations, so is linear in sizeof(n) The result is 2^2^{lg(n)} = 2^n, superexponential in lg(n) For the converse, observe that if the called procedure is polynomial, and the number of calls is constant, the size remains in the base of the expression, and can not appear in the exponent. 36.2-3 Given a directed graph, choose a vertex. Eliminate all of its outgoing edges, then replace them one by one. For at least one edge, the polytime algorithm must report the existence of a HAM-CYCLE. Retain this edge and repeat the process for its successor node, and so on. After all nodes have been visited, you have a HAM-CYCLE, in order, at a cost of at most E*p(E), where E was the original number of edges.