Questions and Answers of Practical Introduction To Data Structures

Use the PR quadtree to implement an efficient solution to Problem 6.5. That is, store the set of points in a PR quadtree. For each point, the PR quadtree is used to find those points within distance
Select any two of the point representations described in this chapter (i.e., the k-d tree, the PR quadtree, the bintree, and the point quadtree). Implement your two choices and compare them over a
Implement a representation for a collection of (two dimensional) rectangles using a quadtree based on regular decomposition. Assume that the space being represented is a square whose width and height
Use the trie data structure to devise a program to sort variable-length strings.The program’s running time should be proportional to the total number of letters in all of the strings. Note that
Define the set of suffix strings for a string S to be S, S without its first character,S without its first two characters, and so on. For example, the completeset of suffix strings for “HELLO”
For each of the five expressions of Figure 3.1, give the range of values of n for which that expression is most efficient. 1400 1200 1000 800 600 400 200 400 300 200 100 0 n! 2" 10 n! 5 20 27 2 30
Graph the following expressions. For expression, state the range of values of n for which that expression is the most efficient.4n24n2 log3nlog3⁡n 3n3n
Arrange the following expressions by growth rate from slowest to fastest.4n24n2t log3nlog3⁡nT(n)=8n n!n!t 3n3nn 20n20nt 22nlog2nlog2⁡nT(n)=X n2/3n2/3T(2n)=X2See Stirling’s approximation
(a) Suppose that a particular algorithm has time complexity \(T(n) = 3 \times 2^n\), and that executing an implementation of it on a particular machine takes \(t\) seconds for \(n\) inputs. Now
Hardware vendor XYZ Corp. claims that their latest computer will run 100 times faster than that of their competitor, Prunes, Inc. If the Prunes, Inc. computer can execute a program on input of size
(a) Find a growth rate that squares the run time when we double the input size. That is, if \(T(n) = X\), then \(T(2n) = X^2\)(b) Find a growth rate that cubes the run time when we double the input
Using the definition of big-Oh, show that 1 is in \(O(1)\) and that 1 is in \(Ω(n)\).
Using the definitions of big-Oh and Ω, find the upper and lower bounds for the following expressions. Be sure to state appropriate values for c and
(a) What is the smallest integer k such that \(\sqrt{n} = O(n^k)\)?(b) What is the smallest integer k such that \(n \log n = O(n^k)\)?
(a) Is 2n=Θ(3n)2n=O(3n)? Explain why or why not.(b) Is 2n=Θ(3n)2n=Θ(3n)? Explain why or why not.
For each of the following pairs of functions, either f(n)f(n) is in O(g(n))O(g(n)), \( f(n)) is in Ω (g(n)) Ω(g(n)), or f (n) = Θ (g(n) ) f(n)=Θ(g(n)). For each pair, determine which relationship
Determine Θ for the following code fragments in the average case. Assume that all variables are of type int.a. a = b + c; d = a + e;b.c.d.e.f.g. Assume that array A contains n values, Random takes
Show that big-Theta notation (Θ) defines an equivalence relation on the set of functions.
Give the best lower bound that you can for the following code fragment, as a function of the initial value of n.while (n > 1)if (ODD(n))n = 3 * n + 1;else n = n / 2;Do you think that the upper bound
Does every algorithm have a Θ running-time equation? In other words, are the upper and lower bounds for the running time (on any specified class of inputs) always the same?
Does every problem for which there exists some algorithm have a Θ running-time equation? In other words, for every problem, and for any specified class of inputs, is there some algorithm whose upper
Given an array storing integers ordered by value, modify the binary search routine to return the position of the first integer with value K in the situation where K can appear multiple times in the
Given an array storing integers ordered by value, modify the binary search routine to return the position of the integer with the greatest value less than K when K itself does not appear in the
Modify the binary search routine to support search in an array of infinite size. In particular, you are given as input a sorted array and a key value K to search for. Call n the position of the
It is possible to change the way that we pick the dividing point in a binary search, and still get a working search routine. However, where we pick the dividing point could affect the performance of
Design an algorithm to assemble a jigsaw puzzle. Assume that each piece has four sides, and that each piece’s final orientation is known (top, bottom, etc.). Assume that you have available a
Can the average case cost for an algorithm be worse than the worst case cost? Can it be better than the best case cost? Explain why or why not.
Prove that if an algorithm is Θ(f(n)) in the average case, then it is Ω(f(n)) in the worst case.
Prove that if an algorithm is Θ(f(n)) in the average case, then it is O(f(n)) in the best case.
Assume a list has the following configuration:Write a series of Java statements using the List ADT of Figure 4.1 to delete the element with value 15. (2, 23, 15, 5, 9).
Show the list configuration resulting from each series of list operations using the List ADT of Figure 4.1 . Assume that lists L1 and L2 are empty at the beginning of each series. Show where the
Write a series of Java statements that uses the List ADT of Figure 4.1 to create a list capable of holding twenty elements and which actually stores the list with the following configuration: (2, 23
Using the list ADT of Figure 4.1, write a function to interchange the current element and the one following it. /** List ADT */ public interface List { } /** Remove all contents from the list, so it
In the linked list implementation presented in Section 4.1 .2, the current position is implemented using a pointer to the element ahead of the logical current node. The more “natural” approach
Add to the LList class implementation a member function to reverse the order of the elements on the list. Your algorithm should run in Θ(n) time for a list of n elements.
Write a function to merge two linked lists. The input lists have their elements in sorted order, from smallest to highest. The output list should also be sorted from highest to lowest. Your algorithm
A circular linked list is one in which the next field for the last link node of the list points to the first link node of the list. This can be useful when you wish to have a relative positioning for
Section 4.1 .3 states “the space required by the array-based list implementation is Ω(n), but can be greater.” Explain why this is so.
Section 4.1.3 presents an equation for determining the break-even point for the space requirements of two implementations of lists. The variables are D, E, P, and n. What are the dimensional units
Use the space equation of Section 4.1.3 to determine the break-even point for an array-based list and linked list implementation for lists when the sizes for the data field, a pointer, and the
Determine the size of an int variable, a double variable, and a pointer on your computer.(a) Calculate the break-even point, as a function of n, beyond which the array-based list is more space
Modify the code of Figure 4.18 to implement two stacks sharing the same array, as shown in Figure 4.20 .Figure 4.18Figure 4.20 /** Array-based stack implementation */ class AStack implements Stack {
Modify the array-based queue definition of Figure 4.25 to use a separate Boolean member to keep track of whether the queue is empty, rather than require that one array position remain empty. //
A palindrome is a string that reads the same forwards as backwards. Using only a fixed number of stacks and queues, the stack and queue ADT functions, and a fixed number of int and char variables,
Reimplement function fibr from Exercise 2.11, using a stack to replace the recursive call as described in Section 4.2 .4.Data from in Exercise 2.11 2.11 Here is a simple recursive function to compute
Write a recursive algorithm to compute the value of the recurrence relationThen, rewrite your algorithm to simulate the recursive calls with a stack. T(n) = T([n/2])+T([n/2])+n; T(1) = 1.
Let Q be a non-empty queue, and let S be an empty stack. Using only the stack and queue ADT functions and a single element variable X, write an algorithm to reverse the order of the elements in Q.
A common problem for compilers and text editors is to determine if the parentheses (or other brackets) in a string are balanced and properly nested.For example, the string “((())())()” contains
Imagine that you are designing an application where you need to perform the operations Insert, Delete Maximum, and Delete Minimum. For this application, the cost of inserting is not important,
Write a function that reverses the order of an array of n items.
A deque (pronounced “deck”) is like a queue, except that items may be added and removed from both the front and the rear. Write either an array-based or linked implementation for the deque.
One solution to the problem of running out of space for an array-based list implementation is to replace the array with a larger array whenever the original array overflows. A good rule that leads to
Use singly linked lists to implement integers of unlimited size. Each node of the list should store one digit of the integer. You should implement addition, subtraction, multiplication, and
Implement doubly linked lists by storing the sum of the next and prev pointers in a single pointer variable as described in Example 4.1. Example 4.1 There is a space-saving technique that can be
Implement a city database using unordered lists. Each database record contains the name of the city (a string of arbitrary length) and the coordinates of the city expressed as integer x and y
Modify the code of Figure 4.18 to support storing variable-length strings of at most 255 characters.The stack array should have type char. A string is represented by a series of characters (one
Implement a collection of freelists for variable-length strings, as described at the end of Section 4.1.2. For each such freelist, you will need an access function to get it if it exists, and
Define an ADT for a bag (see Section 2.1 ) and create an array-based implementation for bags. Be sure that your bag ADT does not rely in any way on knowing or controlling the position of an element.
Implement the dictionary ADT of Figure 4.27 using an unsorted linked list as defined by class LList in Figure 4.8.Make the implementation as efficient as you can, given the restriction that your
Implement the dictionary ADT of Figure 4.27 based on stacks. Your implementation should declare and use two stacks. /** The Dictionary abstract class. */ public interface Dictionary { }; /**
Implement the dictionary ADT of Figure 4.27 based on queues. Your implementation should declare and use two queues. /** The Dictionary abstract class. */ public interface Dictionary { }; /**
Section 5.1 .1 claims that a full binary tree has the highest number of leaf nodes among all trees with n internal nodes. Prove that this is true. 5.1.1 The Full Binary Tree Theorem Some binary tree
Define the degree of a node as the number of its non-empty children. Prove by induction that the number of degree 2 nodes in any binary tree is one less than the number of leaves.
Define the internal path length for a tree as the sum of the depths of all internal nodes, while the external path length is the sum of the depths of all leaf nodes in the tree. Prove by induction
Explain why function preorder2 from Section 5.2 makes half as many recursive calls as function preorder. Explain why it makes twice as many accesses to left and right children.Section 5.2 The
(a) Modify the preorder traversal of Section 5.2 to perform an inorder traversal of a binary tree.Section 5.2 The preorder enumeration for the tree of Figure 5.1 is ABDCEGFHI: The first node
Write a recursive function named search that takes as input the pointer to the root of a binary tree (not a BST!) and a value K, and returns true if value K appears in the tree and false otherwise.
Write an algorithm that takes as input the pointer to the root of a binary tree and prints the node values of the tree in level order. Level order first prints the root, then all nodes of level 1,
Write a recursive function that returns the height of a binary tree.
Write a recursive function that returns a count of the number of leaf nodes in a binary tree.
Assume that a given BST stores integer values in its nodes. Write a recursive function that sums the values of all nodes in the tree.
Assume that a given BST stores integer values in its nodes. Write a recursive function that traverses a binary tree, and prints the value of every node who’s grandparent has a value that is a
Write a recursive function that traverses a binary tree, and prints the value of every node which has at least four great-grandchildren.
Compute the overhead fraction for each of the following full binary tree implementations.(a) All nodes store data, two child pointers, and a parent pointer. The data field requires four bytes and
Why is the BST Property defined so that nodes with values equal to the value of the root appear only in the right subtree, rather than allow equal-valued nodes to appear in either subtree?
(a) Show the BST that results from inserting the values 15, 20, 25, 18, 16, 5, and 7 (in that order).(b) Show the enumerations for the tree of (a) that result from doing a preorder traversal, an
Draw the BST that results from adding the value 5 to the BST shown in Figure 5.13 (a). 2 7 24 32) 37 (a) (42) 40 (42) (120)
Draw the BST that results from deleting the value 7 from the BST of Figure 5.13 (b). 2 7 (24) (42) (32) (b) (120) (42) (37 40
Write a function that prints out the node values for a BST in sorted order from highest to lowest.
Write a recursive function named smallcount that, given the pointer to the root of a BST and a key K, returns the number of nodes having key values less than or equal to K. Function smallcount should
Write a recursive function named printRange that, given the pointer to the root to a BST, a low key value, and a high key value, prints in sorted order all records whose key values fall between the
Describe a simple modification to the BST that will allow it to easily support finding the Kth smallest value in (log n) average case time. Then write a pseudo-code function for finding the Kth
What are the minimum and maximum number of elements in a heap of height h?
Where in a max-heap might the smallest element reside?
Show the max-heap that results from running buildHeap on the following values stored in an array: 10 5 12 3 2 1 8 7 94
(a) Show the heap that results from deleting the maximum value from the max-heap of Figure 5.20b.(b) Show the heap that results from deleting the element with value 5 from the max-heap of Figure
Revise the heap definition of Figure 5.19 to implement a min-heap. The member function removemax should be replaced by a new function called removemin. import java.lang. Comparable; /** Max-heap
Build the Huffman coding tree and determine the codes for the following set of letters and weights:What is the expected length in bits of a message containing n characters for this frequency
What will the Huffman coding tree look like for a set of sixteen characters all with equal weight? What is the average code length for a letter in this case?How does this differ from the smallest
A set of characters with varying weights is assigned Huffman codes. If one of the characters is assigned code 001, then,(a) Describe all codes that cannot have been assigned.(b) Describe all codes
Assume that a sample alphabet has the following weights:(a) For this alphabet, what is the worst-case number of bits required by the Huffman code for a string of n letters? What string(s) have the
You must keep track of some data. Your options are:(1) A linked-list maintained in sorted order.(2) A linked-list of unsorted records.(3) A binary search tree.(4) An array-based list maintained in
Reimplement the composite design for the binary tree node class of Figure 5.11 using a flyweight in place of null pointers to empty nodes.In Figure 5.11 public interface VarBinNode { public boolean
One way to deal with the “problem” of null pointers in binary trees is to use that space for some other purpose. One example is the threaded binary tree. Extending the node implementation of
Implement a city database using a BST to store the database records. Each database record contains the name of the city (a string of arbitrary length) and the coordinates of the city expressed as
Create a binary tree ADT that includes generic traversal methods that take a visitor, as described in Section 5.2. Write functions count and BSTcheck of Section 5.2 as visitors to be used with the
Implement a priority queue class based on the max-heap class implementation of Figure 5.19. The following methods should be supported for manipulating the priority queue:void enqueue(int ObjectID,
The Huffman coding tree function buildHuff of Figure 5.29 manipulates a sorted list. This could result in a (Θn2) algorithm, because placing an intermediate Huffman tree on the list could take Θ(n)
Complete the implementation of the Huffman coding tree, building on the code presented in Section 5.6. Include a function to compute and store in a table the codes for each letter, and functions to
Write an algorithm to determine if two general trees are identical. Make the algorithm as efficient as you can. Analyze your algorithm’s running time.

Showing 200 - 300 of 447