Questions and Answers of Data Structures Algorithms

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
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
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
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
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
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
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
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
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
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
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
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
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
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 ≤
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
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.
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
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
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
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
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
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
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),
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
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
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
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
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,
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
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
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
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
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
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
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
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
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,
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
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
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
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
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.
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
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
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.
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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)
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

Showing 600 - 700 of 819