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

Provide the details of an array implementation of the list ADT.
Implement a heap-based priority queue that supports the following additional operation in linear time:replace Comparator(c): Replace the current comparator with c. After changing the comparator, the
Give complete C++ code for a new class, ShrinkingVector, that extends the ArrayVector class shown in Code Fragment 6.2 and adds a function, shrinkToFit, which replaces the underlying array with an
Provide the missing housekeeping functions (copy constructor, assignment operator, and destructor) for the class ArrayVector of Code Fragment 6.2.Data from in Code Fragment 6.2A vector implementation
Consider the following fragment of C++ code, assuming that the constructor Sequence creates an empty sequence of integer objects. Recall that division between integers performs truncation (for
Suppose we want to extend the Sequence abstract data type with functions index Of Element(e) and position Of Element(e), which respectively return the index and the position of the (first occurrence
Describe the structure and pseudo-code for an array-based implementation of the vector ADT that achieves O(1) time for insertions and removals at index 0, as well as insertions and removals at the
Describe an efficient way of putting a vector representing a deck of n cards into random order. You may use a function, randomInteger(n), which returns a random number between 0 and n−1, inclusive.
Design a circular node list ADT that abstracts a circularly linked list in the same way that the node list ADT abstracts a doubly linked list.
Show that only n−1 passes are needed in the execution of bubble-sort on a sequence with n elements.
Write a program that takes as input a rooted tree T and a node v of T and converts T to another tree with the same set of node adjacencies but now rooted at v.
Describe an algorithm for counting the number of left external nodes in a binary tree, using the Binary tree ADT.
What is the running time of algorithm height2(T,v) (Code Fragment 7.7) when called on a node v distinct from the root of T?Data from in Code Fragment 7.7A more efficient algorithm for computing the
Extend the concept of an Euler tour to an ordered tree that is not necessarily a binary tree.
Let T be a tree with n nodes. Define the lowest common ancestor (LCA) between two nodes v and w as the lowest node in T that has both v and w as descendents (where we allow a node to be a descendent
Let T be a tree with n nodes, and, for any node v in T, let dv denote the depth of v in T. The distance between two nodes v and w in T is dv+dw−2du, where u is the LCA u of v and w (as defined in
Suppose each node v of a binary tree T is labeled with its value ∫ (v) in a level numbering of T. Design a fast method for determining ∫ (u) for the lowest common ancestor (LCA), u, of two
Give a C++ implementation of a priority queue based on an unsorted list.
Develop a C++ implementation of a priority queue that is based on a heap and supports the locator-based functions.
Show that, given only the less-than operator (<) and the boolean operators and (&&), or (||), and not (!), it is possible to implement all of the other comparators: >, <=, >=, ==,
Describe, in detail, an implementation of a priority queue based on a sorted array. Show that this implementation achieves O(1) time for operations min and removeMin and O(n) time for operation
Write a program that can process a sequence of stock buy and sell orders as described in Exercise C-8.1.Data from in Exercise C-8.1An online computer system for trading stock needs to process orders
Implement the vector ADT by means of an extendable array used in a circular fashion, so that insertions and deletions at the beginning and end of the vector run in constant time.
Give a C++ code fragment for reversing an array.
Describe what changes need to be made to the extendable array implementation given in Code Fragment 6.2 in order to avoid unexpected termination due to an error. Specify the new types of exceptions
Describe what changes need to be made to the extendable array implementation given in Code Fragment 6.2 in order to shrink the size N of the array by half any time the number of elements in the
Implement the vector ADT using a doubly linked list. Show experimentally that this implementation is worse than the array-based approach.
Give a C++ code fragment for randomly permuting an array.
Give a C++ code fragment for circularly rotating an array by distance d.
Implement the sequence ADT by means of an extendable array used in a circular fashion, so that insertions and deletions at the beginning and end of the sequence run in constant time.
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),
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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)
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
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
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
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
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
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),
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
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))
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
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
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
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
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.

Showing 1 - 100 of 332