Algorithm Design And Applications 1st Edition Michael T. Goodrich, Roberto Tamassia - Solutions

For each of the following statements about wavl trees, determine whether it is true or false. If you think it is true, provide a justification. If you think it is false, give a counterexample. a. A subtree of a wavl tree is itself a wavl tree. b. The sibling of an external node is either
Draw an example of a red-black tree that is not structurally equivalent to a wavl tree.
A mergeable heap supports operations insert(k, x), remove(k), unionWith(h), and min(), where the unionWith(h) operation performs a union of the mergeable heap h with the present one, destroying the old versions of both, and min() returns the element with minimum key. Describe a implementation of a
Draw an example red-black tree that is not an AVL tree. Your tree should have at least 6 nodes, but no more than 16.
Let T be a wavl tree storing n items, and let k be the key of an item in T. Show how to construct from T, in O(log n) time, two wavl trees T and T , such that T contains all the keys of T less than k, and T contains all the keys of T greater than k. This operation destroys T.
Is the rotation done in Figure 4.5 a single or a double rotation? What about the rotation in Figure 4.6? Figure 4.5Figure 4.6 44 44 32 78 T3 48 88 To T1 То T1 T3 (а) (b)
Show that at most one trinode restructure operation (which corresponds to one single or double rotation) is needed to restore balance after any insertion in an AVL tree.
What is the minimum number of nodes in a splay tree of height 9?
What is the minimum number of nodes in a wavl tree of height 7?
What is the minimum number of nodes in a red-black tree of height 8?
Suppose there is a computer game, Land-of-Candy (LoC), where a player moves through a three-dimensional world defined by the cells in an n × n × n array, C. Each cell, C[i, j, k], specifies the number of points that a player in LoC gets when they are at position (i, j, k). At the start of a game
Draw an example of an AVL tree such that a single remove operation could require Θ(log n) trinode restructurings (or rotations) from a leaf to the root in order to restore the height-balance property. (Use triangles to represent subtrees that are not affected by this operation.)
What is the minimum number of nodes in an AVL tree of height 7?
Suppose your neighbor, sweet Mrs. McGregor, has invited you to her house to help her with a computer problem. She has a huge collection of JPEG images of bunny rabbits stored on her computer and a shoebox full of 1 gigabyte USB drives. She is asking that you help her copy her images onto the drives
Describe how to perform the operation removeAllElements(k), which removes all elements with keys equal to k, in a balanced search tree T, and show that this method runs in time O(s log n), where n is the number of elements stored in the tree and s is the number of elements with key k.
Suppose you are hired as a consultant to a professor, Dr. Bob Loblaw, from the Sociology department. He is asking that you build him a software system that can maintain a set, P, of people from a country, Phishnonia, that he is studying. People in Phishnonia are free to come and go as they please,
Describe how to perform the operation findAllElements(k), which returns all the items with keys equal to k in a balanced search tree, and show that it runs in time O(log n + s), where n is the number of elements stored in the tree and s is the number of items returned.
Suppose you are working for a victim-support group to build a website for maintaining a set, S, containing the names of all the registered sex offenders in a given area. The system should be able to list out the names of the people in S ordered by their Zip codes, and, within each Zip code, ordered
Consider the insertion of items with the following keys (in the given order) into an initially empty splay tree: 0, 2, 4, 6, 8, 10, 12, 14, 16, 18. Draw the final tree that results.
Suppose a used car dealer, Jalopy Joe, has asked you to build a website for his car dealership. He wants this website to allow users to be able to search for a set of cars on his lot that are in their price range. That is, viewed abstractly, he would like you to build a system that can maintain an
Consider the insertion of items with the following keys (in the given order) into an initially empty wavl tree: 12, 44, 52, 58, 38, 27, 41, 11. Draw the final tree that results.
Consider the insertion of items with the following keys (in the given order) into an initially empty AVL tree: 30, 40, 24, 58, 48, 26, 11, 13. Draw the final tree that results.
Suppose you are working for a fast-growing startup company, which we will call “FastCo,” and it is your job to write a software package that can maintain the set, E, of all the employees working for FastCo. In particular, your software has to maintain, for each employee, x in E, the vital
Suppose you are working for a large dog adoption organization and are asked to build a website showing all the dogs that your organization currently knows of that are waiting to be placed in loving homes. You are being asked to create a separate web page for each such dog, with these pages ordered
What is H5, the 5th harmonic number?
Without using calculus (as in the previous exercise), show that, if n is a power of 2 greater than 1, then, for Hn, the nth harmonic number, Hn ≤ 1 + Hn/2Use this fact to conclude that Hn ≤ 1 + [log n], for any n ≥ 1.Data From Previous ExerciseUse the fact that, for a decreasing
If one has a set, S, of n items, where n is even, then the median item in S is the average of the ith and (i + 1)st smallest elements in S, where i = n/2. Describe an efficient algorithm for computing the median of such a set S that is stored in a binary search tree, T, where each node, v, in T is
Use the fact that, for a decreasing integrable function, f, to show that, for the nth harmonic number, Hn, ln n ≤ Hn ≤ 1 + ln n. cb+1 b f(x)dx < f (x)dx, r=a r=a-1 2=a
Suppose you are given a binary search tree, T, which is constructed by inserting the integers in the set {1, 2,...,n} in a random order into T, where all permutations of this set are equally likely. What is the average running time of then performing a select(i) operation on T?
Suppose that a binary search tree, T, is constructed by inserting the integers from 1 to n in this order. Give a big-Oh characterization of the number of comparisons that were done to construct T.
Suppose you are given a sorted set, S, of n items, stored in a binary search tree. How many different range queries can be done where both of the values, k1 and k2, in the query range [k1, k2] are members of S?
Describe the structure of a binary search tree, T, storing n items, such that T has height Ω(n1/2) yet the average depth of the nodes in T is O(log n).
The first-century historian, Flavius Josephus, recounts the story of how, when his band of 41 soldiers was trapped by the opposing Roman army, they chose group suicide over surrender. They collected themselves into a circle and repeatedly put to death every third man around the circle, closing up
Let S be an ordered set of n items stored in a binary search tree, T, of height h. Show how to perform the following method for S in O(h) time: countAllInRange(k1, k2): Compute and return the number of items in S with key k such that k1 ≤ k ≤ k2.
Draw the binary search tree that results from deleting items with keys 17, 28, 54, and 65, in this order, from the tree shown in Figure 3.7b. Figure 3.7b 44 88 17 97 32 65 28 54 82 76 29 80 78 (b)
Suppose you are building a first-person shooter game, where virtual zombies are climbing up a wall while the player, who is moving left and right in front of the wall, is trying to knock them down using various weapons. The position of each zombie is represented with a pair, (x, y), where x is the
Consider the reversal of the problem from the previous exercise. Now you are the recipient of such a message, containing a textural representation of a binary search tree as described in the previous exercise. Describe an algorithm running in O(n log n) time, or better, for reconstructing the
Describe how to perform an operation removeAllElements(k), which removes all key-value pairs in a binary search tree T that have a key equal to k, and show that this method runs in time O(h + s), where h is the height of T and s is the number of items returned.
Prove, by induction, that the height of a binary search tree containing n items is at least [log(n + 1)].
Draw the binary search trees of minimum and maximum heights that store all the integers in the range from 1 to 7, inclusive.
It is sometimes necessary to send a description of a binary search tree in text form, such as in an email or text message. Since it is a significant challenge to draw a binary search tree using text symbols, it is useful to have a completely textural way of representing a binary search tree.
Describe how to perform the operation findAllElements(k), as defined in the previous exercise, in an ordered set of key-value pairs implemented with a binary search tree T, and show that it runs in time O(h + s), where h is the height of T and s is the number of items returned.Data From Previous
Suppose T is a binary search tree of height 4 (including the external nodes) that is storing all the integers in the range from 1 to 15, inclusive. Suppose further that you do a search for the number 11. Explain why it is impossible for the sequence of numbers you encounter in this search to be (9,
Suppose you work for a computer game company, which is designing a first person shooting game. In this game, players stand just outside of a circular playing field and shoot at targets inside the circle. There are a lot of players and targets, however, so, for any given player, it only makes sense
Describe how to perform the operation findAllElements(k), which returns every element with a key equal to k (allowing for duplicates) in an ordered set of n keyvalue pairs stored in an ordered array, and show that it runs in time O(log n + s), where s is the number of elements returned.
Suppose you have a binary search tree, T, storing numbers in the range from 1 to 500, and you do a search for the integer 250. Which of the following sequences are possible sequences of numbers that were encountered in this search. For the ones that are possible, draw the search path, and, for the
Imagine that you work for a database company, which has a popular system for maintaining sorted sets. After a negative review in an influential technology website, the company has decided it needs to convert all of its indexing software from using sorted arrays to an indexing strategy based on
Let S and T be two ordered arrays, each with n items. Describe an O(log n)- time algorithm for finding the kth smallest key in the union of the keys from S and T (assuming no duplicates).
Insert items with the following keys (in the given order) into an initially empty binary search tree: 30, 40, 50, 24, 8, 58, 48, 26, 11, 13. Draw the tree that results.
Suppose you are asked to automate the prescription fulfillment system for a pharmacy, MailDrugs. When an order comes in, it is given as a sequence of requests, “x1 ml of drug y1,” “x2 ml of drug y2,” “x3 ml of drug y3,” and so on, where x1 < x2 < x3 < ··· < xk. MailDrugs
Suppose you are given the array A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], and you then perform the binary search algorithm given in this chapter to find the number 8. Which numbers in the array A are compared against the number 8?
Suppose you are given a sorted array, A, of n distinct integers in the range from 1 to n + 1, so there is exactly one integer in this range missing from A. Describe an O(log n)-time algorithm for finding the integer in this range that is not in A.
Define the internal path length, I(T), of a tree T to be the sum of the depths of all the internal nodes in T. Likewise, define the external path length, E(T), of a tree T to be the sum of the depths of all the external nodes in T. Show that if T is a binary tree with n internal nodes, then E(T) =
Let T be a binary tree with n nodes. Give a linear-time method that uses the methods of the BinaryTree interface to traverse the nodes of T by increasing values of the level numbering function p given in Exercise R-2.8. This traversal is known as the level order traversal.
Describe in pseudocode a nonrecursive method for performing an Euler tour traversal of a binary tree that runs in linear time and does not use a stack.
Let T be a binary tree with n nodes. Define a Roman node to be a node v in T, such that the number of descendants in v’s left subtree differ from the number of descendants in v’s right subtree by at most 5. Describe a linear-time method for finding each node v of T, such that v is not a Roman
Show how to represent an improper binary tree by means of a proper one.
Let a visit action in the Euler tour traversal be denoted by a pair (v, a), where v is the visited node and a is one of left, below, or right. Design an algorithm for performing operation tourNext(v, a), which returns the visit action (w, b) following (v, a). What is the worst-case running time of
The balance factor of an internal node v of a binary tree is the difference between the heights of the right and left subtrees of v. Show how to specialize the Euler tour traversal to print the balance factors of all the nodes of a binary tree.
Give an O(n)-time algorithm for computing the depth of all the nodes of a tree T, where n is the number of nodes of T.
Design an algorithm for drawing a binary tree, using quantities computed in a tree traversal.
Using an array-based list, describe an efficient way of putting a sequence representing a deck of n cards into random order. Use the function randomInt(n), which returns a random number between 0 and n − 1, inclusive. Your method should guarantee that every possible ordering is equally likely.
Describe the structure and pseudocode for an array-based implementation of an index-based list that achieves O(1) time for insertions and removals at index 0, as well as insertions and removals at the end of the list. Your implementation should also provide for a constant-time get method.
Let T be a binary tree with n nodes, and let p be the level numbering of the nodes of T, so that the root, r, is numbered as p(r)=1, and a node v has left child numbered 2p(v) and right child numbered 2p(v)+1, if they exist. a. Show that, for every node v of T, p(v) ≤ 2(n+1)/2 − 1. b.
Show that a stack and a queue can be used to realize any permutation. That is, suppose you are given an empty stack, S, and the numbers, 1, 2,...,n, in this order, initially stored in a queue, Q. Show how to use only these two structures, and at most a constant number of additional registers, to
Let T be a binary tree such that all the external nodes have the same depth. Let De be the sum of the depths of all the external nodes of T, and let Di be the sum of the depths of all the internal nodes of T. Find constants a and b such that where n is the number of nodes of T. De +1 = aD; +
Describe a recursive algorithm for enumerating all permutations of the numbers {1, 2,...,n}. What is the running time of your method?
Answer the following questions so as to justify Theorem 2.7. a. Draw a binary tree with height 7 and maximum number of external nodes. b. What is the minimum number of external nodes for a binary tree with height h? Justify your answer. c. What is the maximum number of external nodes
Describe how to implement a stack using two queues. What is the running time of the push() and pop() methods in this case?
Describe how to implement a queue using two stacks, so that the amortized running time for dequeue and enqueue is O(1), assuming that the stacks support constant-time push, pop, and size methods. What is the worst-case running time of the enqueue() and dequeue() methods in this case?
Suppose you work for a company, iPilgrim.com, whose n employees are organized in a tree T, so that each node is associated with an employee and each employee is considered a supervisor for all the employees (including themselves) in his or her subtree in T, as in the previous exercise. Furthermore,
Describe, in pseudocode, a link-hopping method for finding the middle node of a doubly linked list with header and trailer sentinels, and an odd number of real nodes between them. What is the running time of this method?
Describe, using pseudocode, an implementation of the method insertBefore(p, e), for a linked list, assuming the list is implemented using a doubly linked list.
Suppose you work for a company, iPuritan.com, that has strict rules for when two employees, x and y, may date one another, requiring approval from their lowestlevel common supervisor. The employees at iPuritan.com are organized in a tree, T, such that each node in T corresponds to an employee and
Suppose that a friend has implemented a deque, as defined in the previous exercise, using a singly linked list, but hasn’t given you the details, for example, of whether the links go forward or backward in the list or whether sentinel nodes are used. Nevertheless, show that one of the insertion
Solve the previous exercise using a queue instead of stack. That is, suppose you are given an array, A, containing n numbers in order, as in the previous exercise. Describe in pseudocode an efficient algorithm for reversing the order of the numbers in A using a single for-loop that indexes through
In the children’s game “hot potato,” a group of n children sit in a circle passing an object, called the “potato,” around the circle (say in a clockwise direction). The children continue passing the potato until a leader rings a bell, at which point the child holding the potato must leave
A double-ended queue, or deque, is a list that allows for insertions and removals at either its head or its tail. Describe a way to implement a deque using a doubly linked list, so that every operation runs in O(1) time.
Suppose you are given an array, A, containing n numbers in order. Describe in pseudocode an efficient algorithm for reversing the order of the numbers in A using a single for-loop that indexes through the cells of A, to insert each element into a stack, and then another for-loop that removes the
Suppose we have a set of n balls and we choose each one independently with probability 1/n1/2 to go into a basket. Derive an upper bound on the probability that there are more than 3n1/2 balls in the basket.
Suppose you have an array of n numbers and you select each one independently with probability 1/n1/2. Use the Chernoff bound to determine an upper bound on the probability that you would have more than 4n1/2 elements in this random sample.
Describe a recursive algorithm for finding both the minimum and the maximum elements in an array A of n elements. Your method should return a pair (a, b), where a is the minimum element and b is the maximum. What is the running time of your method?
Given the values of the maximum suffix sums, Mt = (t = 1, ··· , 11), for the array A = [−2, −4, 3, −1, 5, 6, −7, −2, 4, −3, 2].
Suppose you are processing a stream of bytes, one at a time, but you don’t know in advance how many there will be, as the last byte is a special EOF character. You only get to consider each byte once. Describe a scheme for choosing a byte in this stream at random so that every byte in the stream
Imagine that a magician has just given you a biased coin. It looks just like a normal coin, with a “heads” side and a “tails” side, but each time this coin is flipped, it is more likely to come up heads than tails. How can you use this coin to generate an unbiased sequence of independent
A certain town has exactly n married heterosexual couples. Every wife knows whether every other wife’s husband is cheating on his wife or not, but no wife knows if her own husband is cheating or not. In fact, if a wife ever learns that her husband is cheating on her, then she will poison him that
Show that if f(n) is O(g(n)) and d(n) is O(h(n)), then the summation f(n) + d(n) is O(g(n) + h(n)).
Given an integer k > 0 and an array, A, of n bits, describe an efficient algorithm for finding the shortest subarray of A that contains k 1’s. What is the running time of your method?
Perform a similar analysis for method Loop5 shown in Algorithm 1.21. Algorithm Loop1(n): s-0 for i + 1 to n do s-s+i Algorithm Loop2(n): p-1 for i - 1 to 2n do p-p.i Algorithm Loop3(n): p-1 for i +1 to n? do p- p.i Algorithm Loop4(n): for i - 1 to 2n do for j +1 to i do S-s+i Algorithm
Perform a similar analysis for method Loop4 shown in Algorithm 1.21. Algorithm Loop1(n): s-0 for i + 1 to n do s-s+i Algorithm Loop2(n): p-1 for i - 1 to 2n do p-p.i Algorithm Loop3(n): p-1 for i +1 to n? do p- p.i Algorithm Loop4(n): for i - 1 to 2n do for j +1 to i do S-s+i Algorithm
Perform a similar analysis for method Loop2 shown in Algorithm 1.21. Algorithm Loop1(n): s-0 for i + 1 to n do s-s+i Algorithm Loop2(n): p-1 for i - 1 to 2n do p-p.i Algorithm Loop3(n): p-1 for i +1 to n? do p- p.i Algorithm Loop4(n): for i - 1 to 2n do for j +1 to i do S-s+i Algorithm
Give a big-Oh characterization, in terms of n, of the running time of the Loop1 method shown in Algorithm 1.21. Algorithm Loop1(n): s-0 for i + 1 to n do s-s+i Algorithm Loop2(n): p-1 for i - 1 to 2n do p-p.i Algorithm Loop3(n): p-1 for i +1 to n? do p- p.i Algorithm Loop4(n): for i - 1 to 2n
Repeat the previous problem assuming B uses n √n operations. Data From Previous Problem.Algorithm A uses 10n log n operations, while algorithm B uses n2 operations. Determine the value n0 such that A is better than B for n ≥ n0.
Suppose you are given an array, A, of n positive integers. Describe an O(n) algorithm for removing all the even numbers from A. That is, if A has m odd numbers, then, after you are done, these odd numbers should occupy the first m cells of A in the same relative order they were in originally.
Suppose you are writing a simulator for a single-elimination sports tournament (like in NCAA Division-1 basketball). There are n teams at the beginning of the tournament and in each round of the tournament teams are paired up and the games for each pair are simulated. Winners progress to the next
Given an array, A, of n − 2 unique integers in the range from 1 to n, describe an O(n)-time method for finding the two integers in the range from 1 to n that are not in A. You may use only O(1) space in addition to the space used by A.
Given an array, A, of n positive integers, each of which appears in A exactly twice, except for one integer, x, describe an O(n)-time method for finding x using only a single variable besides A.
Given an array, A, of n integers, find the longest subarray of A such that all the numbers in that subarray are in sorted order. What is the running time of your method?
Given a string, S, of n digits in the range from 0 to 9, describe an efficient algorithm for converting S into the integer it represents. What is the running time of your algorithm?
Given an array, A, describe an efficient algorithm for reversing A. For example, if A = [3, 4, 1, 5], then its reversal is A = [5, 1, 4, 3]. You can only use O(1) memory in addition to that used by A itself. What is the running time of your algorithm?

Showing 600 - 700 of 819

Algorithm Design And Applications 1st Edition Michael T. Goodrich, Roberto Tamassia - Solutions

Step by Step Answers