New Semester Started Get 50% OFF Study Help! --h --m --s Claim Now

Question Answers

Textbooks

Find textbooks, questions and answers

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Study Help
Tutors
AI Study Planner NEW
Sell Books

Search
Sign In
Register

study help
computer science
practical introduction to data structures

Practical Introduction To Data Structures And Algorithm Analysis Java Edition 1st Edition Clifford A. Shaffer - Solutions

Implement a city database using the bintree. 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-coordinates. Your database should allow records to be inserted, deleted by name or coordinate, and searched by
Implement a city database using the point quadtree. 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-coordinates. Your database should allow records to be inserted, deleted by name or coordinate, and
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 D that should be equivalenced.What is the asymptotic complexity of this solution?Data from in
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 wide range of data sets. Describe which is easier to implement, which appears to be more space
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 are some power of two. Rectangles are assumed to have integer coordinates and integer width and
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 some strings might be very long while most are short.
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” would beA suffix tree is a PAT trie that contains all of the suffix strings for a givenstring, and
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 Input size n 10 40 5n log n 20n 10n 2n 201 50 5n log n 10n 15
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 20n20n 22 log2nlog2⁡n n2/3n2/3
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 in Section 2.2 for help in classifying n!n!T(n)=X.Data From Section 2.2: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 suppose that we are presented with a machine that is 64 times as fast. How many inputs could we process
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 \(n\) in one hour, what size input could the XYZ computer execute in one hour for each algorithm with
(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 size. That is, if \(T(n) = X\), then \(T(2n) = X^3\)
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 n0n0.(a) c1nc1n(b) c2n3+c3c2n3+c3(c) c4nlogn+c5nc4nlog⁡n+c5n(d) c6n2+c7n6c6n2+c7n6
(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 is correct. Justify your answer, using the method of limits discussed in Section 3.4 .5.(a) f(n) =
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 constant time, and sort takes n log n steps.h. Assume array A contains a random permutation of the
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 is likely to be the same as the answer you gave for the lower 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 bound is equal to the problem’s lower bound?
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 array. Be sure that your algorithm is O(log n), that is, do not resort to sequential search once an
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 array. Return ERROR if the least value in the array is greater than K.
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 smallest value in the array that is equal to or larger than X. Provide an algorithm that can determine n
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 the algorithm.(a) If we change the dividing point computation in function binary from i = (l + r) =2
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 functionbool compare(Piece a, Piece b, Side ad)that can tell, in constant time, whether piece a connects
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 current position is in the list.(a) L1.append(10);L1.append(20);L1.append(15);(b)
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 | 15, 5, 9).
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 is once again empty. Client is responsible for reclaiming storage used by the list elements. */
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 might seem to be to have curr point directly to the node containing the current element. However, if
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 should run in linear time on the length of the output list.
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 elements, but no concept of an absolute first or last position.(a) Modify the code of Figure 4.8 to
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 for each variable? Show that both sides of the equation balance in terms of their dimensional
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 array-based list’s array are as specified.(a) The data field is eight bytes, a pointer is four bytes,
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 efficient than the linked list for lists whose elements are of type int.(b) Calculate the break-even
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 { private static final int defaultSize = 10; private int maxSize; private int top; private E []
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. // Array-based queue implementation class AQueue implements Queue { private static final int defaultSize =
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, write an algorithm to determine if a string is a palindrome. Assume that the string is read from
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 the Fibonacci sequence: // Recursive Fibonacci generator static long fibr (int n) { // fibr (91) is
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 properly nested pairs of parentheses, but the string “)()(” does not, and the string “())”
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, because it can be done off-line prior to startup of the time-critical section, but the performance of the
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 an implementation that is both space and time efficient is to double the current size of the array
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 exponentiation operations. Limit exponents to be positive integers. What is the asymptotic running time for
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 employed to eliminate the additional space requirement, though it will complicate the implementation and
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 coordinates. Your database should allow records to be inserted, deleted by name or coordinate, and searched
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 character per stack element), with the length of the string stored in the stack element immediately above
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 implement it if it does not. A major design consideration is how to organize the collection of freelists,
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. Then, implement the dictionary ADT of Figure 4.27 using your bag implementation. /** The Dictionary
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 implementation must use the unsorted linked list and its access operations to implement the
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 { }; /** Reinitialize dictionary */ public void clear(); /** Insert a record @param k The key for the record being
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 { }; /** Reinitialize dictionary */ public void clear(); /** Insert a record @param k The key for the record being
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 implementations store data only at the leaf nodes, using the inter- nal nodes to provide structure
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 that if tree T is a full binary tree with n internal nodes, I is T’s internal path length, and E is
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 preorder enumeration for the tree of Figure 5.1 is ABDCEGFHI: The first node printed is the root. Then all
(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 printed is the root. Then all nodes of the left subtree are printed (in preorder) before any node of the
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, then all nodes of level 2, and so on.Consider making use of another data structure to help implement
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 multiple of five.
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 each pointer requires four bytes.(b) All nodes store data and two child pointers. The data field
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 inorder traversal, and a postorder traversal.
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 visit as few nodes in the BST as possible.
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 two given keys. Function printRange should visit as few nodes in the BST as possible.
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 smallest value in your modified BST.
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 5.20b. 2 5 6 3 7 (b) 5 2 7 3
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 implementation */ public class MaxHeap
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 distribution? Letter Frequency A 2 2 B C D 3 5 7 E F 11 13 17 G H I J KL 19 23 31 37 41
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 possible fixed length code for sixteen characters?
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 that must have been assigned.
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 worstcase performance?(b) For this alphabet, what is the best-case number of bits required by 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 sorted order.(5) An array-based list of unsorted records.For each of the following scenarios, which of
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 isLeaf (); public void traverse(); } class VarLeaf Node implements VarBinNode { // Leaf node private
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 Figure 5.7, the threaded binary tree stores with each node two additional bit fields that indicate if
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 integer x- and y-coordinates. The BST should be organized by city name. Your database should allow
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 generic traversal method. boolean checkBST (BSTNode root, Integer low, Integer high) { } if (root ==
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, int priority);int dequeue();void changeweight(int ObjectID, int newPriority);Method enqueue inserts a
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) time. Revise this algorithm to use a priority queue based on a min-heap instead of a list.In Figure

Showing 200 - 300 of 449

1
2
3
4
5

Step by Step Answers

Services

Sitemap
Fun
Definitions
Become Tutor
Used Textbooks
Study Help Categories
Recent Questions
Expert Questions
Campus Wear
Sell Your Books

Company Info

Security
Copyrights
Privacy Policy
Terms & Conditions
SolutionInn Fee
Scholarship
Online Quiz
Give Feedback, Get Rewards

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Student Discount
Campus Ambassador

Secure Payment

Download Our App

© 2026 SolutionInn. All Rights Reserved