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
introduction to algorithms

Data Structures and Algorithms in Java 6th edition Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser - Solutions

Show the result of Exercise R-10.6, assuming collisions are handled by quadratic probing, up to the point where the method fails.
What is the worst-case time for putting n entries in an initially empty hash table, with collisions resolved by chaining? What is the best case?
Modify the Pair class from Code Fragment 2.17 on page 92 so that it provides a natural definition for both the equals( ) and hashCode( ) methods.
Consider lines 31€“33 of Code Fragment 10.8 in our implementation of the class ChainHashMap. We use the difference in the size of a secondary bucket before and after a call to bucket.remove(k) to update the variable n. If we replace those three lines with the following, does the class
Implement the containKey(k) method, as described in Exercise R-10.3, for the SortedTableClass.
Consider the following variant of the findIndex method of the SortedTableMap class, originally given in Code Fragment 10.11:Does this always produce the same result as the original version? Justify your answer. private int findlndex(K key, int low, int high) { if (high < low) return high + 1; int
What is the expected running time of the methods for maintaining a maxima set if we insert n pairs such that each pair has lower cost and performance than one before it? What is contained in the sorted map at the end of this series of operations? What if each pair had a lower cost and higher
Give a description, in pseudocode, for implementing the removeAll method for the set ADT, using only the other fundamental methods of the set.
Give a description, in pseudocode, for implementing the retainAll method for the set ADT, using only the other fundamental methods of the set.
If we let n denote the size of set S, and m denote the size of set T, what would be the running time of the operation S.addAll(T), as implemented on page 446, if both sets were implemented as skip lists?
If we let n denote the size of set S, and m denote the size of set T, what would be the running time of the operation S.addAll(T), as implemented on page 446, if both sets were implemented using hashing?
If we let n denote the size of set S, and m denote the size of set T, what would be the running time of the operation S.removeAll(T) when both sets are implemented using hashing?
If we let n denote the size of set S, and m denote the size of set T, what would be the running time of the operation S.retainAll(T) when both sets are implemented using hashing?
What abstraction would you use to manage a database of friends’ birthdays in order to support efficient queries such as “find all friends whose birthday is today” and “find the friend who will be the next to celebrate a birthday”?
Consider the goal of adding entry (k,v) to a map only if there does not yet exist some other entry with key k. For a map M (without null values), this might be accomplished as follows.if (M.get(k) == null)M.put(k, v);While this accomplishes the goal, its efficiency is less than ideal, as time will
Describe how to perform a removal from a hash table that uses linear probing to resolve collisions where we do not use a special marker to represent deleted elements. That is, we must rearrange the contents so that it appears that the removed entry was never inserted in the first place.
Although keys in a map are distinct, the binary search algorithm can be applied in a more general setting in which an array stores possibly duplicative elements in nondecreasing order. Consider the goal of identifying the index of the leftmost element with key greater than or equal to given k. Does
Suppose we are given two sorted search tables S and T, each with n entries (with S and T being implemented with arrays). 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).
Given a database D of n cost-performance pairs (c, p), describe an algorithm for finding the maxima pairs of C in O(nlogn) time.
Suppose that each row of an n×n array A consists of 1’s and 0’s such that, in any row of A, all the 1’s come before any 0’s in that row. Assuming A is already in memory, describe a method running in O(nlogn) time (not O(n2) time) for counting the number of 1’s in A.
Give a concrete implementation of the retainAll method for the set ADT, using only the other fundamental methods of the set. You are to assume that the underlying set implementation uses fail-fast iterators (see Section 7.4.2).
The operation get(k) for our multimap ADT is responsible for returning a collection of all values currently associated with key k. Design a variation of binary search for performing this operation on a sorted search table that includes duplicates, and show that it runs in time O(s+logn), where n is
Describe an efficient multimap structure for storing n entries that have an associated set of r < n keys that come from a total order. That is, the set of keys is smaller than the number of entries. Your structure should perform operation getAll in O(logr+s) expected time, where s is the number
Describe an efficient multimap structure for storing n entries whose r < n keys have distinct hash codes. Your structure should perform operation getAll in O(1 +s) expected time, where s is the number of entries returned, operation entrySet() in O(n) time, and the remaining operations of the
How many different binary search trees can store the keys {1,2,3}?
Dr. Amongus 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.
Dr. Amongus 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 he is wrong.
Our implementation of the treeSearch utility, from Code Fragment 11.3, relies on recursion. For a large unbalanced tree, it is possible that Java€™s call stack will reach its limit due to the recursive depth. Give an alternative implementation of that method that does not rely on the use
Is the search tree of Figure 11.22(a) a (2,4) tree? Why or why not?Figure 11.22(a) 22 5 10 25 3 4 23 24 6 8 14 27 11 13 17 (a)
Give a proof of Proposition 11.10Proposition 11.10The algorithm for deleting an entry from a red-black tree with n entries takes O(log n) time and performs O(log n) recolorings and at most two restructuring operations.
Consider the sequence of keys (5,16,22,45,2,10,18,30,50,12,1). Draw the result of inserting entries with these keys (in the given order) intoa. An initially empty (2,4) tree.b. An initially empty red-black tree.
Consider the set of keys K = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}.a. Draw a (2,4) tree storing K as its keys using the fewest number of nodes.b. Draw a (2,4) tree storing K as its keys using the greatest number of nodes.
Draw the AVL tree resulting from the insertion of an entry with key 52 into the AVL tree of Figure 11.13b. 4 62 44 78) х 50 88 Тз 48 54 T4 T2 (b)
Draw the AVL tree resulting from the removal of the entry with key 62 from the AVL tree of Figure 11.13b. 4 62 44 78) х 50 88 Тз 48 54 T4 T2 (b)
Consider a deletion operation in an AVL tree that triggers a trinode restructuring for the case in which both children of the node denoted as y have equal heights. Give a schematic figure, in the style of Figure 11.12, showing the tree before and after the deletion. What is the net effect of the
Communication security is extremely important in computer networks, and one way many network protocols achieve security is to encrypt messages. Typical cryptographic schemes for the secure transmission of messages over such networks are based on the fact that no efficient algorithms are known for
Describe a fast recursive algorithm for reversing a singly linked list L, so that the ordering of the nodes becomes opposite of what it was before.
The java.util.Collection interface includes a method, contains(o), that returns true if the collection contains any object that equals Object o. Implement such a method in the ArrayList class of Section 7.2.
The java.util.Collection interface includes a method, clear( ), that removes all elements from a collection. Implement such a method in the ArrayList class of Section 7.2.
Given the set of element {a,b,c,d,e, f } stored in a list, show the final state of the list, assuming we use the move-to-front heuristic and access the elements according to the following sequence: (a,b,c,d,e, f ,a,c, f ,b,d,e).
Suppose that we have made kn total accesses to the elements in a list L of n elements, for some integer k ≥ 1. What are the minimum and maximum number of elements that have been accessed fewer than k times?
Implement a resetCounts( ) method for the FavoritesList class that resets all elements’ access counts to zero (while leaving the order of the list unchanged).
Give an array-based list implementation, with fixed capacity, treating the array circularly so that it achieves O(1) time for insertions and removals at index 0, as well as insertions and removals at the end of the array list. Your implementation should also provide for a constant-time get method.
Modify our ArrayList implementation to support the Cloneable interface, as described in Section 3.6.
Suppose Bob has four cows that he wants to take across a bridge, but only one yoke, which can hold up to two cows, side by side, tied to the yoke. The yoke is too heavy for him to carry across the bridge, but he can tie (and untie) cows to it in no time at all. Of his four cows, Mazie can cross the
Alice has two circular queues,C and D, which can store integers. Bob givesAlice 50 odd integers and 50 even integers and insists that she stores all 100 integers in C and D. They then play a game where Bob picks C or D at random and then applies the rotate( ) method to the chosen queue a random
Al says he can prove that all sheep in a flock are the same color:Base case: One sheep. It is clearly the same color as itself.Induction step: A flock of n sheep. Take a sheep, a, out. The remaining n−1 are all the same color by induction. Now put sheep a back in and take out a different sheep,
Write a short recursive Java method that takes a character string s and outputs its reverse. For example, the reverse of 'pots&pans' would be 'snap&stop'.
Write a short recursive Java method that rearranges an array of integer values so that all the even values appear before all the odd values.
Given an unsorted array, A, of integers and an integer k, describe a recursive algorithm for rearranging the elements in A so that all elements less than or equal to k come before any elements larger than k. What is the running time of your algorithm on an array of n values?
Suppose you are given an array, A, containing n distinct integers that are listed in increasing order. Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if such a pair exists. What is the running time of your algorithm?
Isabel has an interesting way of summing up the values in an array A of n integers, where n is a power of two. She creates an array B of half the size of A and sets B[i] = A[2i]+ A[2i+ 1], for i = 0,1, . . . , (n/2)− 1. If B has size 1, then she outputs B[0]. Otherwise, she replaces A with B, and
Consider the implementation of CircularlyLinkedList.addFirst, in Code Fragment 3.16. The else body at lines 39 and 40 of that method relies on a locally declared variable, newest. Redesign that clause to avoid use of any local variable.
Give a justification of the running times shown in Table 7.1 for the methods of an array list implemented with a (nonexpanding) array.
The java.util.ArrayList includes a method, trimToSize( ), that replaces the underlying array with one whose capacity precisely equals the number of elements currently in the list. Implement such a method for our dynamic version of the ArrayList class from Section 7.2.
Redo the justification of Proposition 7.2 assuming that the the cost of growing the array from size k to size 2k is 3k cyber-dollars. How much should each push operation be charged to make the amortization work?
Suppose we are maintaining a collection C of elements such that, each time we add a new element to the collection, we copy the contents of C into a new array list of just the right size. What is the running time of adding n elements to an initially empty collection C in this case?
The add method for a dynamic array, as described in Code Fragment 7.5, has the following inefficiency. In the case when a resize occurs, the resize operation takes time to copy all the elements from the old array to a new array, and then the subsequent loop in the body of add shifts some of them to
Describe an implementation of the positional list methods addLast and addBefore realized by using only methods in the set {isEmpty, first, last, before, after, addAfter, addFirst}.
Suppose we want to extend the PositionalList abstract data type with a method, indexOf(p), that returns the current index of the element stored at position p. Show how to implement this method using only other methods of the Positional-List interface (not details of our LinkedPositionalList
Suppose we want to extend the PositionalList abstract data type with a method, findPosition(e), that returns the first position containing an element equal to e (or null if no such position exists). Show how to implement this method using only existing methods of the PositionalList interface (not
The LinkedPositionalList implementation of Code Fragments 7.9–7.12 does not do any error checking to test if a given position p is actually a member of the relevant list. Give a detailed explanation of the effect of a call L.addAfter(p, e) on a list L, yet with a position p that belongs to some
Give an algorithm for finding the second-to-last node in a singly linked list in which the last node is indicated by a null next reference.
Describe an algorithm for finding both the minimumand maximum of n numbers using fewer than 3n/2 comparisons.
Bob built a website and gave the URL only to his n friends, which he numbered from 1 to n. He told friend number i that he/she can visit the website at most i times. Now Bob has a counter, C, keeping track of the total number of visits to the site (but not the identities of who visits). What is the
An array A contains n−1 unique integers in the range [0,n−1], that is, there is one number from this range that is not in A. Design an O(n)-time algorithm for finding that number. You are only allowed to use O(1) additional space besides the array A itself.
Show that the summation Σni=1 logi is Ω(nlogn).
An evil king has n bottles of wine, and a spy has just poisoned one of them. Unfortunately, they do not know which one it is. The poison is very deadly; just one drop diluted even a billion to one will still kill. Even so, it takes a full month for the poison to take effect. Design a scheme for
Given an array A of n positive integers, each represented with k = ⌈logn⌉+1 bits, describe an O(n)-time method for finding a k-bit integer not in A.
Argue why any solution to the previous problem must run in Ω(n) time.
Given an array A of n arbitrary integers, design an O(n)-time method for finding an integer that cannot be formed as the sum of two integers in A.
Describe a recursive algorithm for finding the maximum element in an array, A, of n elements. What is your running time and space usage?
Explain how to modify the recursive binary search algorithm so that it returns the index of the target in the sequence or −1 (if the target is not found).
Describe a recursive algorithmfor computing the nth Harmonic number, defined as Hn = Σnk=1 1/k.
Describe a recursive algorithm for converting a string of digits into the integer it represents. For example, '13531' represents the integer 13,531.
Develop a nonrecursive implementation of the version of the power method from Code Fragment 5.9 that uses repeated squaring. 1 /** Computes the value of x raised to the nth power, for nonnegative integer n. */ 2 public static double power(double x, int n) { if (n == 0) return 1; else { double
Give a recursive algorithmto compute the product of two positive integers, m and n, using only addition and subtraction.
In Section 5.2 we prove by induction that the number of lines printed by a call to drawInterval(c) is 2c−1. Another interesting question is how many dashes are printed during that process. Prove by induction that the number of dashes printed by drawInterval(c) is 2c+1−c−2.
Show that logb f (n) is Θ(log f (n)) if b > 1 is a constant.
Show that Σni=1 i/2i < 2.
Give an example of a positive function f (n) such that f (n) is neither O(n) nor Ω(n).
Describe an efficient algorithm for finding the ten largest elements in an array of size n. What is the running time of your algorithm?
Assuming it is possible to sort n numbers in O(nlogn) time, show that it is possible to solve the three-way set disjointness problem in O(nlogn) time.
Al and Bob are arguing about their algorithms. Al claims his O(nlogn)-time method is always faster than Bob’s O(n2)-time method. To settle the issue, they perform a set of experiments. To Al’s dismay, they find that if n < 100, the O(n2)-time algorithm runs faster, and only when n ≥ 100 is
Given an n-element array X, Algorithm D calls Algorithm E on each element X[i]. Algorithm E runs in O(i) time when it is called on element X[i]. What is the worst-case running time of Algorithm D?
For each function f (n) and time t in the following table, determine the largest size n of a problem P that can be solved in time t if the algorithm for solving P takes f (n) microseconds (one entry is already completed).
Show that nlogn is Ω(n).
Show that n is O(nlogn).
Show that 2n+1 is O(2n).
Show that (n+1)5 is O(n5).
Show that if d(n) is O( f (n)) and e(n) is O(g(n)), then the product d(n)e(n) is O( f (n)g(n)).
Show that if d(n) is O( f (n)), then ad(n) is O( f (n)), for any constant a > 0.
Order the following functions by asymptotic growth rate.
Show that the following two statements are equivalent:(a) The running time of algorithm A is always O(f (n)).(b) In the worst case, the running time of algorithm A is O(f (n)).
What is the sum of all the even numbers from 0 to 2n, for any integer n ≥ 1?
Explain why the plot of the function nc is a straight line with slope c on a log-log scale.
Give an example of a function that is plotted the same on a log-log scale as it is on a standard scale.
The number of operations executed by algorithms A and B is 40n2 and 2n3, respectively. Determine n0 such that A is better than B for n ≥ n0.
The number of operations executed by algorithms A and B is 8nlogn and 2n2, respectively. Determine n0 such that A is better than B for n ≥ n0.
Describe in detail an algorithm for reversing a singly linked list L using only a constant amount of additional space.

Showing 1400 - 1500 of 1549

First
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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