All Matches
Solution Library
Expert Answer
Textbooks
Search Textbook questions, tutors and Books
Oops, something went wrong!
Change your search query and then try again
Toggle navigation
FREE Trial
S
Books
FREE
Tutors
Study Help
Expert Questions
Accounting
General Management
Mathematics
Finance
Organizational Behaviour
Law
Physics
Operating System
Management Leadership
Sociology
Programming
Marketing
Database
Computer Network
Economics
Textbooks Solutions
Accounting
Managerial Accounting
Management Leadership
Cost Accounting
Statistics
Business Law
Corporate Finance
Finance
Economics
Auditing
Ask a Question
Search
Search
Sign In
Register
study help
computer science
introduction to algorithms
Questions and Answers of
Introduction to Algorithms
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 3133 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
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
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
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
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
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
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) ==
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
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
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
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
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
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
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
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
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
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 Javas call stack will reach its limit due to
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
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
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
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
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
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
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:
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
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
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
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
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
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
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
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 =
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
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
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
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
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
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
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).
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
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
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
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
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
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
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
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
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