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

Draw a representation of an initially empty vector A after performing the following sequence of operations: insert(0,4), insert(0,3), insert(0,2), insert(2,1), insert(1,5), insert(1,6), insert(3,7), insert(0,8).
Show that, using an extendable array that grows and shrinks as in the previous exercise, the following series of 2n operations takes O(n) time: (i) n push operations on a vector with initial capacity N = 1; (ii) n pop (removal of the last element) operations.
Provide a fully generic version of the class ArrayVector of Code Fragment 6.2 using a templated class.Data from in Code Fragment 6.2A vector implementation using an extendable array.The member data for class ArrayVector consists of the array storage A, the current number n of elements in the
Implement the sequence ADT by means of a singly linked list.
Give an adapter class to support the Stack interface using the functions of the vector ADT.
Write a complete adapter class that implements the sequence ADT using an STL vector object.
Show how to improve the implementation of function insert(i,e) in Code Fragment 6.5 so that, in case of an overflow, the elements are copied into their final place in the new array.Data from in Code Fragment 6.5Themember functions reserve and insert for class ArrayVector.In terms of efficiency,
Give a templated C++ function sum(v) that returns the sum of elements in an STL vector v. Use an STL iterator to enumerate the elements of v. Assume that the element type of v is any numeric type that supports the + operator.
Describe an implementation of the functions insertBack and insertFront realized by using combinations of only the functions empty and insert.
Draw pictures illustrating each of the major steps in the algorithms for functions insert(p,e), insertFront(e), and insertBack(e) of Code Fragment 6.5.Data from in Code Fragment 6.5Themember functions reserve and insert for class ArrayVector. In terms of efficiency, this array replacement strategy
The following questions refer to the tree of Figure 7.3.Data from in Figure 7.3a. Which node is the root?b. What are the internal nodes?c. How many descendents does node cs016/ have?d. How many ancestors does node cs016/ have?e. What are the siblings of node homeworks/?f. Which nodes are in the
Give a pseudo-code description of an implementation of the bubble-sort algorithm that uses only two stacks and, at most, five additional variables to sort a collection of objects stored initially in one of the stacks. You may operate on the stacks using only functions of the stack ADT. The final
Give pseudo-code describing how to implement all the operations in the sequence ADT using an array used in a circular fashion. What is the running time for each of these functions?
Using the Sequence interface functions, describe a recursive function for determining if a sequence S of n integer objects contains a given integer k. Your function should not contain any loops. How much space does your function use in addition to the space used for S?
Briefly describe how to perform a new sequence function make First(p) that moves an element of a sequence S at position p to be the first element in S while keeping the relative ordering of the remaining elements in S unchanged. Your function should run in O(1) time if S is implemented with a
Given a list L of n positive integers, each represented with k = ⌈logn⌉+1 bits, describe an O(n)-time function for finding a k-bit integer not in L.
Given a list L of n arbitrary integers, design an O(n)-time function for finding an integer that cannot be formed as the sum of two integers in L.
Show that there are more than 2n different potentially improper binary trees with n internal nodes, where two trees are considered different if they can be drawn as different looking trees.
Find the value of the arithmetic expression associated with each subtree of the binary tree of Figure 7.11.Data from in Figure 7.11A binary tree representing an arithmetic expression. This tree represents the expression ((((3+1)×3)/((9−5)+2))−((3×(7−4))+6)). The value associated with the
Give a fully generic implementation of the class Linked Binary Tree using class templates and taking into account error conditions.
For each node v in a tree T, let pre(v) be the rank of v in a preorder traversal of T, let post(v) be the rank of v in a postorder traversal of T, let depth(v) be the depth of v, and let desc(v) be the number of descendents of v, not counting v itself. Derive a formula defining post(v) in terms of
Implement the binary tree ADT using a vector.
A slicing floorplan is a decomposition of a rectangle with horizontal and vertical sides using horizontal and vertical cuts (see Figure 7.24(a)). A slicing floorplan can be represented by a binary tree, called a slicing tree, whose internal nodes represent the cuts, and whose external nodes
Let T be a tree whose nodes store strings. Give an algorithm that computes and prints, for every internal node v of T, the string stored at v and the height of the subtree rooted at v.
Implement the binary tree ADT using a linked structure.
Let T be an n-node improper binary tree (that is, each internal node has one or two children). Describe how to represent T by means of a proper binary tree T′ with O(n) nodes.
Design algorithms for the following operations for a binary tree T.• preorderNext(v): return the node visited after node v in a preorder traversal of T.• inorderNext(v): return the node visited after node v in an inorder traversal of T.• postorderNext(v): return the node visited after node v
Implement the binary tree representation of the tree ADT. You may reuse the Linked Binary Tree implementation of a binary tree.
The update operations expand External and remove Above External do not permit the creation of an improper binary tree. Give pseudo-code descriptions for alternate update operations suitable for improper binary trees. You may need to define new query operations as well.
As mentioned in Exercise C-5.8, postfix notation is an unambiguous way of writing an arithmetic expression without parentheses. It is defined so that if “(exp1) ◦(exp2)” is a normal (infix) fully parenthesized expression with operation “◦,” then its postfix equivalent is
Given a proper binary tree T, define the reflection of T to be the binary tree T′ such that each node v in T is also in T′, but the left child of v in T is v’s right child in T′ and the right child of v in T is v’s left child in T′. Show that a preorder traversal of a proper binary tree
Describe a generalization of the Euler tour traversal of trees such that each internal node has three children. Describe how you could use this traversal to compute the height of each node in such a tree.
Design an algorithm for drawing general trees that generalizes the inorder traversal approach for drawing binary trees.
Consider a variation of the linked data structure for binary trees where each node object has pointers to the node objects of the children but not to the node object of the parent. Describe an implementation of the functions of a binary tree with this data structure and analyze the time complexity
Justify Table 7.1, summarizing the running time of the functions of a tree represented with a linked structure, by providing, for each function, a description of its implementation, and an analysis of its running time.Data from in Table 7.1Running times of the functions of an n-node linked tree
Design an alternative implementation of the linked data structure for binary trees using a class for nodes that specializes into subclasses for an internal node, an external node, and the root node.
Describe, in pseudo-code, an algorithm for computing the number of descendents of each node of a binary tree. The algorithm should be based on the Euler tour traversal.
Let T be a (possibly improper) binary tree with n nodes, and let D be the sum of the depths of all the external nodes of T. Show that if T has the minimum number of external nodes possible, then D is O(n) and if T has the maximum number of external nodes possible, then D is O(nlogn).
Describe a nonrecursive method for evaluating a binary tree representing an arithmetic expression.
The path length of a tree T is the sum of the depths of all the nodes in T. Describe a linear-time method for computing the path length of a tree T (which is not necessarily binary).
What are the running times of each of the functions of the (standard) priority queue ADT if we implement it by adapting the STL priority queue?
Show how to implement the stack ADT using only a priority queue and one additional member variable.
Implement the in-place heap-sort algorithm. Compare its running time with that of the standard heap-sort that uses an external heap.
Explain how to implement a priority queue based on the composition method (of storing key-element pairs) by adapting a priority queue based on the comparator approach.
Show how to implement the (standard) queue ADT using only a priority queue and one additional member variable.
Suppose you label each node v of a binary tree T with a key equal to the preorder rank of v. Under what circumstances is T a heap?
Show the output from the following sequence of priority queue ADT operations. The entries are key-element pairs, where sorting is based on the key value: insert(5,a), insert(4,b), insert(7, i), insert(1,d), removeMin(), insert(3, j), insert(6,c), removeMin(), removeMin(), insert(8,g), remove-
Although it is correct to use a “reverse” comparator with our priority queue ADT so that we retrieve and remove an element with the maximum key each time, it is confusing to have an element with the maximum key returned by a function named “removeMin.” Write a short adapter class that can
Illustrate the performance of the selection-sort algorithm on the following input sequence: (22,15,36,44,10,3,9,13,29,25).
At which nodes of a heap can an entry with the largest key be stored?
Illustrate the performance of the heap-sort algorithm on the following input sequence: (2,5,16,4,10,23,39,18,26,15).
Show all the steps of the algorithm for removing key 16 from the heap of Figure 8.3.Data from in Figure 8.3 (15,K) (5,A) (9,F) (4,C) (16,X))( (25,J)) ((14,E)) ((12,H)) (7,Q) (6,Z) (11,S)) ((8,W) (20,B)
Let T be a complete binary tree such that node v stores the key-entry pairs ( ∫ (v),0), where ∫ (v) is the level number of v. Is tree T a heap? Why or why not?
Explain why the case where the right child of r is internal and the left child is external was not considered in the description of down-heap bubbling.
Suppose the internal nodes of two binary trees, T1 and T2 respectively, hold items that satisfy the heap-order property. Describe a method for combining these two trees into a tree T, whose internal nodes hold the union of the items in T1 and T2 and also satisfy the heap-order property. Your
Give an alternate description of the in-place heap-sort algorithm that uses a standard comparator instead of a reverse one.
Describe efficient algorithms for performing operations remove(e) on an adaptable priority queue realized by means of an unsorted list with location aware entries.
Give a pseudo-code description of a nonrecursive in-place heap-sort algorithm.
Describe how you could perform each of the additional functions of the ordered map ADT using a skip list.
Describe how to use a skip list to implement the vector ADT, so that index based insertions and removals both run in O(logn) expected time.
Write an implementation of the dictionary ADT using a linked list.
What is the worst-case running time for inserting n key-value entries into an initially empty map M that is implemented with a list?
Suppose we are given two ordered dictionaries S and T, each with n items, and that S and T are implemented by means of array-based ordered sequences. Describe an O(log2 n)-time algorithm for finding the kth smallest key in the union of the keys from S and T (assuming no duplicates).
Write an implementation of the map ADT using a vector.
What is the worst-case asymptotic running time for performing n (correct) erase() operations on a map, implemented with an ordered search table, that initially contains 2n entries?
Implement a class that implements a version of an ordered dictionary ADT using a skip list. Be sure to carefully define and implement dictionary versions of corresponding functions of the ordered map ADT.
Describe how to use a skip-list map to implement the dictionary ADT, allowing the user to insert different entries with equal keys.
Design a variation of binary search for performing find All(k) in an ordered dictionary implemented with an ordered array, and show that it runs in time O(logn+s), where n is the number of elements in the dictionary and s is the size of the iterator returned.
Implement the map ADT with a hash table with separate-chaining collision handling (do not adapt any of the STL classes).
Describe how an ordered list implemented as a doubly linked list could be used to implement the map ADT.
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 algorithm, we allocate a 2M cell Boolean array A, such that cell i is associated with the integer i.
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 from using the hash function, h(i) = (3i+5) mod 11, to hash the keys 12, 44, 13, 88, 23, 94, 11, 39,
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 number of elements. Your structure should perform all the ordered dictionary operations in O(log k+ s)
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 possibility of different entries with equal keys.
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 is the number of entries returned, and the remaining operations of the dictionary ADT in O(1)
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 the bag. Show that both of these functions can be done in O(1) time.
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 requests.
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)? Show all of the random choices your algorithm made in this case.
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 modification and the algorithm for finding the median assuming all keys are distinct.
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 right subtree. What must a subtree of a binary search tree containing only equal keys look like in
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 the height of T and s is the size of the collection returned.
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 time O(h+s), where h is the height of T and s is the size of the iterator returned.
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 entries in the map and s is the size of the iterator returned.

Showing 200 - 300 of 502

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

Step by Step Answers