Questions and Answers of Data Structures And Algorithms In C++

The hash table dictionary implementation requires that we find a prime number between a number M and a number 2M. Implement a function for finding such a prime by using the sieve algorithm. In this
Implement the ordered map ADT using a skip list.
Given a collection C of n cost-performance pairs (c, p), describe an algorithm for finding the maxima pairs of C in O(nlogn) time.
Implement a dictionary that supports location-aware entries by means of an ordered list.
Show the result of Exercise R-9.7, assuming collisions are handled by quadratic probing, up to the point where the method fails.Data from in Exercise R-9.7Draw the 11-entry hash table that results
Design a C++ class that implements the skip-list data structure. Use this class to create implementations of both the map and dictionary ADTs, including location-aware functions for the dictionary.
Describe an efficient ordered dictionary structure for storing n elements that have an associated set of k < n keys that come from a total order. That is, the set of keys is smaller than the
Describe a set of operations for an ordered dictionary ADT that would correspond to the functions of the ordered map ADT. Be sure to define the meaning of the functions so that they can deal with the
Describe an efficient dictionary structure for storing n entries whose r < n keys have distinct hash codes. Your structure should perform operation find All in O(1+s) expected time, where s
Describe an efficient data structure for implementing the bag ADT, which supports a function add(e), for adding an element e to the bag, and a function remove, which removes an arbitrary element in
Write a C++ class that simulates the best-fit, worst-fit, first-fit, and next fit algorithms for memory management. Determine experimentally which method is the best under various sequences of memory
Describe, in detail, add and remove algorithms for an (a,b) tree.
Write a C++ class that implements all the functions of the ordered map ADT by means of an (a,b) tree, where a and b are integer constants passed as parameters to a constructor.
Implement an external-memory sorting algorithm and compare it experimentally to any internal-memory sorting algorithm.
Consider an initially empty memory cache consisting of four pages. How many page misses can the random algorithm incur on the following page request sequence: (2, 3, 4, 1, 2, 5, 1, 3, 5, 4, 1, 2, 3)?
Draw the result of inserting, into an initially empty order-7 B-tree, the keys (4, 40, 23, 50, 11, 34, 62, 78, 66, 22, 90, 59, 25, 72, 64, 77, 39, 12).
Show that (X−A)∪(X−B)=X−(A∩B), for any three sets X, A, and B.
Show that the best-case running time of quick-sort on a sequence of size n with distinct elements is O(nlog n).
Describe, in pseudo-code, how to perform path compression on a path of length h in O(h) time in a tree-based partition union/find structure.
Describe an in-place version of the quick-select algorithm in pseudo-code.
Explain why a hash table is not suited to implement the ordered dictionary ADT.
What is the worst-case running time for inserting n items into an initially empty hash table, where collisions are resolved by chaining? What is the best case?
Give a pseudo-code description of the erase operation in a skip list.
Argue why location-aware entries are not really needed for a dictionary implemented with a good hash table.
Describe a modification to the binary search tree data structure that would allow you to find the median entry, that is the entry with rank ⌊n/2⌋, in a binary search tree. Describe both the
We defined a binary search tree so that keys equal to a node’s key can be in either the left or right subtree of that node. Suppose we change the definition so that we restrict equal keys to the
Design a variation of algorithm TreeSearch for performing the operation find All(k) in an ordered dictionary implemented with a binary search tree T, and show that it runs in time O(h+s), where h is
Describe how to perform an operation eraseAll(k), which removes all the entries whose keys equal k in an ordered dictionary implemented with a binary search tree T, and show that this method runs in
Jack claims that the order in which a fixed set of entries is inserted into a binary search tree does not matter—the same tree results every time. Give a small example that proves he is wrong.
Show how to perform an operation, eraseAll(k), which removes all entries with keys equal to K, in an ordered dictionary implemented with an AVL tree in time O(s log n), where n is the number of
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
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
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
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
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
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
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,
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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.
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
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
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
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
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
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
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;
Implement Dijkstra’s algorithm assuming that the edge weights are integers.

Showing 100 - 200 of 332