Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 83
Текст из файла (страница 83)
The analysis is left as Exercise 17.4-2.In summary, since the amortized cost of each operation is bounded above by a constant, theactual time for any sequence of n operations on a dynamic table is O(n).Exercises 17.4-1Suppose that we wish to implement a dynamic, open-address hash table. Why might weconsider the table to be full when its load factor reaches some value α that is strictly less than1? Describe briefly how to make insertion into a dynamic, open-address hash table run in sucha way that the expected value of the amortized cost per insertion is O(1). Why is the expectedvalue of the actual cost per insertion not necessarily O(1) for all insertions?Exercises 17.4-2Show that if αi-1 ≥ 1/2 and the ith operation on a dynamic table is TABLE-DELETE, then theamortized cost of the operation with respect to the potential function (17.6) is bounded aboveby a constant.Exercises 17.4-3Suppose that instead of contracting a table by halving its size when its load factor drops below1/4, we contract it by multiplying its size by 2/3 when its load factor drops below 1/3.
Usingthe potential functionΦ(T) = |2 · num[T] - size[T]| ,show that the amortized cost of a TABLE-DELETE that uses this strategy is bounded aboveby a constant.Problems 17-1: Bit-reversed binary counterChapter 30 examines an important algorithm called the Fast Fourier Transform, or FFT. Thefirst step of the FFT algorithm performs a bit-reversal permutation on an input array A[0 n- 1] whose length is n = 2k for some nonnegative integer k.
This permutation swaps elementswhose indices have binary representations that are the reverse of each other.We can express each index a as a k-bit sequencedefinerevk( ak-1, ak-2, ..., a0 ) =thus,a0, a1, ..., ak-1 ;ak-1, ak-2, ..., a0 , where. WeFor example, if n = 16 (or, equivalently, k = 4), then revk(3) = 12, since the 4-bitrepresentation of 3 is 0011, which when reversed gives 1100, the 4-bit representation of 12.a.
Given a function revk that runs in Φ(k) time, write an algorithm to perform the bitreversal permutation on an array of length n = 2k in O(nk) time.We can use an algorithm based on an amortized analysis to improve the running time of thebit-reversal permutation. We maintain a "bit-reversed counter" and a procedure BITREVERSED-INCREMENT that, when given a bit-reversed-counter value a, producesrevk(revk(a) + 1). If k = 4, for example, and the bit-reversed counter starts at 0, then successivecalls to BIT-REVERSED-INCREMENT produce the sequence0000, 1000, 0100, 1100, 0010, 1010, ...
= 0, 8, 4, 12, 2, 10, ... .b. Assume that the words in your computer store k-bit values and that in unit time, yourcomputer can manipulate the binary values with operations such as shifting left orright by arbitrary amounts, bitwise-AND, bitwise-OR, etc. Describe animplementation of the BIT-REVERSED-INCREMENT procedure that allows the bitreversal permutation on an n-element array to be performed in a total of O(n) time.c.
Suppose that you can shift a word left or right by only one bit in unit time. Is it stillpossible to implement an O(n)-time bit-reversal permutation?Problems 17-2: Making binary search dynamicBinary search of a sorted array takes logarithmic search time, but the time to insert a newelement is linear in the size of the array. We can improve the time for insertion by keepingseveral sorted arrays.Specifically, suppose that we wish to support SEARCH and INSERT on a set of n elements.Let k = ⌈lg(n + 1)⌉, and let the binary representation of n be nk-1, nk-2, ..., n0 . We have ksorted arrays A0, A1, ..., Ak-1, where for i = 0, 1, ..., k - 1, the length of array Ai is 2i. Each arrayis either full or empty, depending on whether ni = 1 or ni = 0, respectively.
The total number. Although each individual array isof elements held in all k arrays is thereforesorted, there is no particular relationship between elements in different arrays.a. Describe how to perform the SEARCH operation for this data structure. Analyze itsworst-case running time.b. Describe how to insert a new element into this data structure. Analyze its worst-caseand amortized running times.c.
Discuss how to implement DELETE.Problems 17-3: Amortized weight-balanced treesConsider an ordinary binary search tree augmented by adding to each node x the field size[x]giving the number of keys stored in the subtree rooted at x. Let α be a constant in the range1/2 ≤ α < 1. We say that a given node x is α-balanced if size[left[x]] ≤ α · size[x]andsize[right[x]] ≤ α · size[x].The tree as a whole is α-balanced if every node in the tree is α-balanced. The followingamortized approach to maintaining weight-balanced trees was suggested by G.
Varghese.a. A 1/2-balanced tree is, in a sense, as balanced as it can be. Given a node x in anarbitrary binary search tree, show how to rebuild the subtree rooted at x so that itbecomes 1/2-balanced. Your algorithm should run in time Θ(size[x]), and it can useO(size[x]) auxiliary storage.b. Show that performing a search in an n-node α-balanced binary search tree takes O(lgn) worst-case time.For the remainder of this problem, assume that the constant α is strictly greater than 1/2.Suppose that INSERT and DELETE are implemented as usual for an n-node binary searchtree, except that after every such operation, if any node in the tree is no longer α-balanced,then the subtree rooted at the highest such node in the tree is "rebuilt" so that it becomes 1/2balanced.We shall analyze this rebuilding scheme using the potential method. For a node x in a binarysearch tree T , we define∆(x) = |size[left[x]] - size[right[x]]| ,and we define the potential of T aswhere c is a sufficiently large constant that depends on α.c.
Argue that any binary search tree has nonnegative potential and that a 1/2-balancedtree has potential 0.d. Suppose that m units of potential can pay for rebuilding an m-node subtree. How largemust c be in terms of α in order for it to take O(1) amortized time to rebuild a subtreethat is not α-balanced?e. Show that inserting a node into or deleting a node from an n-node α-balanced treecosts O(lg n) amortized time.Problems 17-4: The cost of restructuring red-black treesThere are four basic operations on red-black trees that perform structural modifications: nodeinsertions, node deletions, rotations, and color modifications.
We have seen that RB-INSERTand RB-DELETE use only O(1) rotations, node insertions, and node deletions to maintain thered-black properties, but they may make many more color modifications.a. Describe a legal red-black tree with n nodes such that calling RB-INSERT to add the(n + 1)st node causes Ω(lg n) color modifications.
Then describe a legal red-black treewith n nodes for which calling RB-DELETE on a particular node causes Ω(lg n) colormodifications.Although the worst-case number of color modifications per operation can be logarithmic, weshall prove that any sequence of m RB-INSERT and RB-DELETE operations on an initiallyempty red-black tree causes O(m) structural modifications in the worst case.b. Some of the cases handled by the main loop of the code of both RB-INSERT-FIXUPand RB-DELETE-FIXUP are terminating: once encountered, they cause the loop toterminate after a constant number of additional operations. For each of the cases ofRB-INSERT-FIXUP and RB-DELETE-FIXUP, specify which are terminating andwhich are not. (Hint: Look at Figures 13.5, 13.6 and 13.7.)We shall first analyze the structural modifications when only insertions are performed.
Let Tbe a red-black tree, and define Φ(T) to be the number of red nodes in T . Assume that 1 unit ofpotential can pay for the structural modifications performed by any of the three cases of RBINSERT-FIXUP.c. Let T′ be the result of applying Case 1 of RB-INSERT-FIXUP to T . Argue that Φ(T′)= Φ(T) - 1.d. Node insertion into a red-black tree using RB-INSERT can be broken down into threeparts. List the structural modifications and potential changes resulting from lines 1–16of RB-INSERT, from nonterminating cases of RB-INSERT-FIXUP, and fromterminating cases of RB-INSERT-FIXUP.e. Using part (d), argue that the amortized number of structural modifications performedby any call of RB-INSERT is O(1).We now wish to prove that there are O(m) structural modifications when there are bothinsertions and deletions.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
