Data Structures And Algorithms In C++ 2nd Edition Michael T. Goodrich, Roberto Tamassia, David M. Mount - Solutions

Rose claims that the order in which a fixed set of entries is inserted into an AVL tree does not matter—the same AVL tree results every time. Give a small example that proves she is wrong.
Describe the changes that would need to be made to the binary search tree implementation given in the book to allow it to be used to support an ordered dictionary, where we allow for different entries with equal keys.
Form a three-programmer team and have each member implement a map using a different search tree data structure. Perform a cooperative experimental study to compare the speed of these three implementations.
Let M be an ordered map with n entries implemented by means of an AVL tree. Show how to implement the following operation on M in time O(logn+s), where s is the size of the iterator returned.find All In Range(k1,k2): Return an iterator of all the entries in M with key k such that k1 ≤ k ≤ k2.
Implement the map ADT using a splay tree, and compare its performance experimentally with the STL map class, which uses a red-black tree.
Explain why performing a rotation in an n-node binary tree represented using a vector takes Ω(n) time.
Let M be an ordered map with n entries. Show how to modify the AVL tree to implement the following function for M in time O(log n). count All In Range(k1,k2): Compute and return the number of entries in M with key k such that k1 ≤ k ≤ k2.
Prepare an implementation of splay trees that uses bottom-up splaying as described in this chapter and another that uses top-down splaying as described in Exercise C-10.23. Perform extensive experimental studies to see which implementation is better in practice, if any.Data from in Exercise
Implement a binary search tree data structure so that it can support the dictionary ADT, where different entries can have equal keys. In addition, implement the functions entry Set Preorder(), entry Set Inorder(), and entry Set Postorder(), which produce an iterable collection of the entries
Cal claims that a (2,4) tree storing a set of entries will always have the same structure, regardless of the order in which the entries are inserted. Show that he is wrong.
Show that at most one trinode restructuring operation is needed to restore balance after any insertion in an AVL tree.
The mergeable heap ADT consists of operations insert(k,x), removeMin(), union With(h), and min(), where the union With(h) operation performs a union of the mergeable heap h with the present one, destroying the old versions of both. Describe a concrete implementation of the mergeable heap ADT that
Repeat the previous problem for red-black trees T and U.Data from in Previous ProblemLet T and U be (2,4) trees storing n and m entries, respectively, such that all the entries in T have keys less than the keys of all the entries in U. Describe an O(log n+logm) time method for joining T and U into
Explain how to use an AVL tree or a red-black tree to sort n comparable elements in O(nlog n) time in the worst case.
Explain how to implement a vector of n elements so that the functions insert and at take O(logn) time in the worst case.
Describe an efficient algorithm for converting a dictionary, D, implemented with a linked list, into a map, M, implemented with a linked list, so that each key in D has an entry in M, and the relative order of entries in M is the same as their relative order in D.
Design and implement two versions of the bucket-sort algorithm in C++, one for sorting an array of char values and one for sorting an array of short values. Experimentally compare the performance of your implementations with the sorting algorithm of the Standard Template Library.
Suppose S is a list of n bits, that is, n 0’s and 1’s. How long will it take to sort S with the merge-sort algorithm? What about quick-sort?
Suppose S is a list of n bits, that is, n 0’s and 1’s. How long will it take to sort S stably with the bucket-sort algorithm?
In the merge-sort tree shown in Figures 11.2 through 11.4, some edges are drawn as arrows. What is the meaning of a downward arrow? How about an upward arrow?Data from in Figures 11.2 85 85 24 24 63 63 45 เส (a) 45 ร้อ 17 (c) 17 31 31 96 96 50 50 163
Suppose that we represent sets with balanced search trees. Describe and analyze algorithms for each of the functions in the set ADT, assuming that one of the two sets is much smaller than the other.
Implement merge-sort and deterministic quick-sort and perform a series of benchmarking tests to see which one is faster. Your tests should include sequences that are “random” as well as “almost” sorted.
Give a complete justification of Proposition 11.1.Data from in Proposition 11.1The merge-sort tree associated with an execution of mergesort on a sequence of size n has height ⌈log n⌉. We leave the justification of Proposition 11.1 as a simple exercise (R-11.4). We use this proposition to
Give a complete pseudo-code description of the recursive merge-sort algorithm that takes an array as its input and output.
Design and implement an animation for one of the sorting algorithms described in this chapter. Your animation should illustrate the key properties of this algorithm in an intuitive manner.
Implement the randomized quick-sort and quick-select algorithms, and design a series of experiments to test their relative speeds.
Suppose we are given two n-element sorted sequences A and B that should not be viewed as sets (that is, A and B may contain duplicate entries). Describe an O(n)-time method for computing a sequence representing the set A∪B (with no duplicates).
Implement an extended set ADT that includes the functions union(B), intersect(B), subtract(B), size(), empty(), plus the functions equals(B), contains(e), insert(e), and remove(e) with obvious meaning.
Describe a nonrecursive, in-place version of the quick-sort algorithm. The algorithm should still be based on the same divide-and-conquer approach, but use an explicit stack to process subproblems.
Implement the tree-based union/find partition data structure with both the union-by-size and path-compression heuristics.
Given an array A of n entries with keys equal to 0 or 1, describe an in-place function for ordering A so that all the 0’s are before every 1.
Suppose we are given an n-element sequence S such that each element in S represents a different vote for president, where each vote is given as an integer representing a particular candidate. Design an O(nlog n)- time algorithm to see who wins the election S represents, assuming the candidate with
Describe a randomized version of in-place quick-sort in pseudo code.
Consider the voting problem from Exercise C-11.13, but now suppose that we know the number k < n of candidates running. Describe an O(nlog k)- time algorithm for determining who wins the election.Data from in Exercise C-11.13Suppose we are given an n-element sequence S such that each element in
Show that the probability that any given input element x belongs to more than 2log n subproblems in size group i, for randomized quick-sort, is at most 1/n2.
Consider the voting problem from Exercise C-11.13, but now suppose a candidate wins only if he or she gets a majority of the votes cast. Design and analyze a fast algorithm for determining the winner if there is one.Data from in Exercise C-11.13Suppose we are given an n-element sequence S such that
Bella has a comparison-based sorting algorithm that sorts the first k elements in sequence of size n in O(n) time. Give a big-Oh characterization of the biggest that k can be?
Given an array A of n integers in the range [0,n2 −1], describe a simple function for sorting A in O(n) time.
Let S1, S2, . . . ,Sk be k different sequences whose elements have integer keys in the range [0,N −1], for some parameter N ≥ 2. Describe an algorithm running in O(n+N) time for sorting all the sequences (not as a union), where n denotes the total size of all the sequences.
Is the bucket-sort algorithm in-place? Why or why not?
Show that the worst-case running time of quick-select on an n-element sequence is Ω(n2).
Let S be a sequence of n insert and removeMin operations, where all the keys involved are integers in the range [0,n−1]. Describe an algorithm running in O(nlog∗ n) for determining the answer to each removeMin.
Implement the LCS algorithm and use it to compute the best sequence alignment between some DNA strings that you can get online from Gen- Bank.
Perform an experimental analysis, using documents found on the Internet, of the efficiency (number of character comparisons performed) of the brute-force and BM pattern matching algorithms for varying-length patterns.
Give an example of a text T of length n and a pattern P of length m that force the brute-force pattern matching algorithm to have a running time that is Ω(nm).
Perform an experimental comparison of the relative speeds of the bruteforce, KMP, and BM pattern matching algorithms. Document the time taken for coding up each of these algorithms as well as their relative running times on documents found on the Internet that are then searched using varying-length
Compute a table representing the last function used in the BM pattern matching algorithm for the pattern string"the quick brown fox jumped over a lazy cat"assuming the following alphabet (which starts with the space character):∑= { ,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}.
Create a class that implements a prefix trie for an ASCII string. The class should have a constructor that takes as an argument a string and a function for pattern matching on the string.
Compute a table representing the KMP failure function for the pattern string "cgtacgttcgtac".
Draw an adjacency list and adjacency matrix representation of the undirected graph shown in Figure 13.1.Data from in Figure 13.1 Snoeyink Goodrich Mount Vitter Chiang Tollis Tamassia Preparata
Draw a standard trie for the following set of strings: {abab,baba,ccccc,bbaaaa,caa,bbaacc,cbcc,cbca}.
Write a program that takes two character strings (which could be, for example, representations of DNA strands) and computes their edit distance, showing the corresponding pieces. Data from in Exercise C-12.20Define the edit distance between two strings X and Y of length n and m, respectively,
Draw a compressed trie for the set of strings given in Exercise R 12.10.Data from in Exercise R 12.10.Draw a standard trie for the following set of strings:{abab,baba,ccccc,bbaaaa,caa,bbaacc,cbcc,cbca}.
What is the longest prefix of the string "cgtacgttcgtacg" that is also a suffix of this string?
Give an efficient algorithm for deleting a string from a compressed trie and analyze its running time.
Let T be a text string of length n. Describe an O(n)-time method for finding the longest prefix of T that is a substring of the reversal of T.
Describe, in pseudo-code, an O(n+m)-time algorithm for computing all the connected components of an undirected graph G with n vertices and m edges.
Design a greedy algorithm for making change after someone buys some candy costing x cents and the customer gives the clerk $1. Your algorithm should try to minimize the number of coins returned.a. Show that your greedy algorithm returns the minimum number of coins if the coins have denominations
Write a class implementing a simplified graph ADT that has only functions relevant to undirected graphs and does not include update functions using the adjacency matrix structure. Your class should include a constructor that takes two collections (for example, sequences)—a collection V of vertex
Implement the simplified graph ADT described in Project P-13.1 using the adjacency list structure.Data from in Project P-13.1Write a class implementing a simplified graph ADT that has only functions relevant to undirected graphs and does not include update functions using the adjacency matrix
Implement the simplified graph ADT described in Project P-13.1 using the edge list structure.Data from in Project P-13.1Write a class implementing a simplified graph ADT that has only functions relevant to undirected graphs and does not include update functions using the adjacency matrix structure.
Repeat the previous problem and then remove one edge from the graph. Show that now there is a single (nonsimple) path that includes all the edges of your graph. Data from in Previous ProblemDraw a simple connected directed graph with 8 vertices and 16 edges such that the in-degree and
Extend the class of Project P-13.2 to support all the functions of the graph ADT (including functions for directed edges).Data from in Project P-13.2Write a class implementing a simplified graph ADT that has only functions relevant to undirected graphs and does not include update functions
Implement a generic BFS traversal using the template method pattern.
Suppose we represent a graph G having n vertices and m edges with the edge list structure. Why, in this case, does the insertVertex function run in O(1) time while the eraseVertex function runs in O(m) time?
Implement the topological sorting algorithm.
Implement the Floyd-Warshall transitive closure algorithm.
Design an experimental comparison of repeated DFS traversals versus the Floyd-Warshall algorithm for computing the transitive closure of a digraph.
Draw the transitive closure of the directed graph shown in Figure 13.2.Data from in Figure 13.2Example of a directed graph representing a flight network. The endpoints of edge UA 120 are LAX and ORD; hence, LAX and ORD are adjacent. The in-degree of DFW is 3, and the out-degree of DFWis 2.
Implement Dijkstra’s algorithm assuming that the edge weights are integers.
Implement Kruskal’s algorithm assuming that the edge weights are integers.
Implement the Prim-Jarn´ık algorithm assuming that the edge weights are integers.
Show how to modify the pseudo-code for Dijkstra’s algorithm for the case when the graph may contain parallel edges and self-loops.
Show that if all the weights in a connected weighted graph G are distinct, then there is exactly one minimum spanning tree for G.
Draw a simple, connected, undirected, weighted graph with 8 vertices and 16 edges, each with unique edge weights. Illustrate the execution of Kruskal’s algorithm on this graph. 7 16 5 8 00 15 9 10 2 13 14 3 11 6 1 12
Describe the meaning of the graphical conventions used in Figure 13.6 illustrating a DFS traversal. What do the colors blue and black refer to? What do the arrows signify? How about thick lines and dashed lines?Data from in Figure 13.6Example of depth-first search traversal on a graph
Repeat the previous problem for the Prim-Jarn´ık algorithm.Draw a simple, connected, undirected, weighted graph with 8 vertices and 16 edges, each with unique edge weights. Illustrate the execution of Kruskal’s algorithm on this graph. 7 16 5 8 00 15 9 10 2 13 14 3 11 6 1 12
Given a complete binary tree T with n nodes, consider a directed graph G having the nodes of T as its vertices. For each parent-child pair in T, create a directed edge in G from the parent to the child. Show that the transitive closure of G has O(nlogn) edges.
Recalling the definition of a complete graph from Exercise R-13.31, what does a breadth-first search tree of a complete graph look like?Data from in Exercise R-13.31A simple undirected graph is complete if it contains an edge between every pair of distinct vertices. What does a depth-first search
If we implemented the stack S from the previous problem with an array, as described in this chapter, then what is the current value of the top member variable?
Implement a templated C++ class Vector that manipulates a numeric vector. Your class should be templated with any numerical scalar type T, which supports the operations + (addition), − (subtraction), and * (multiplication). In addition, type T should have constructors T(0), which produces the
Show that n is O(nlog n).
Show that n2 is Ω(nlog n).
Show that n log n is Ω(n).
Explain how you can implement all the functions of the deque ADT using two stacks.
Give an implementation of the deque ADT using an array, so that each of the update functions run in O(1) time.
Describe how to implement a capacity-limited stack, which uses the functions of a capacity-limited deque to perform the functions of the stack ADT in ways that do not throw exceptions when we attempt to perform a push on a full stack or a pop on an empty stack.
Describe how to implement a capacity-limited queue, which uses the functions of a capacity-limited deque to perform the functions of the queue ADT in ways that do not throw exceptions when we attempt to perform a enqueue on a full queue or a dequeue on an empty queue.
Implement the stack ADT in a fully generic manner (through the use of templates) by means of a singly linked list. (Give your implementation “from scratch,” without the use of any classes from the Standard Template Library or data structures presented earlier in this book.)
Suppose an initially empty stack S has performed a total of 25 push operations, 12 top operations, and 10 pop operations, 3 of which generated a StackEmpty exception that was caught and ignored. What is the current size of S?
Implement the stack ADT in a fully generic manner using the STL vector class.
Describe how to implement the stack ADT using two queues. What is the running time of the push and pop functions in this case?
Implement the queue ADT in a fully generic manner using a dynamically allocated C++ array.
Describe the output of the following series of stack operations: push(5), push(3), pop(), push(2), push(8), pop(), pop(), push(9), push(1), pop(), push(7), push(6), pop(), pop(), push(4), pop(), pop().
Suppose we have an n×n two-dimensional array A that we want to use to store integers, but we don’t want to spend the O(n2) work to initialize it to all 0’s, because we already know that we are only going to use up to n of these cells in our algorithm, which itself runs in O(n) time (not
Implement the queue ADT with a singly linked list.
Implement the deque ADT with an array used in a circular fashion.
Implement the deque ADT with a doubly linked list.
Implement the Stack and Queue interfaces with a unique class that is derived from class LinkedDeque (Code Fragment 5.21).Data from in Code Fragment 5.21The class structure for class LinkedDeque.We have not bothered to provide an explicit destructor, because the DLinkedList class provides its own
Describe the output for the following sequence of queue operations: enqueue(5), enqueue(3), dequeue(), enqueue(2), enqueue(8), dequeue(), dequeue(), enqueue(9), enqueue(1), dequeue(), enqueue(7), enqueue(6), dequeue(), dequeue(), enqueue(4), dequeue(), dequeue().

Showing 300 - 400 of 502

Data Structures And Algorithms In C++ 2nd Edition Michael T. Goodrich, Roberto Tamassia, David M. Mount - Solutions

Step by Step Answers