Chapter #11 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

11.1 When do M consecutive insertions into a binomial queue take less than 2M time units? - Get solution

11.2 Suppose a binomial queue of N = 2k − 1 elements is built. Alternately perform M insert and deleteMin pairs. Clearly, each operation takes O(logN) time. Why does this not contradict the amortized bound of O(1) for insertion? - Get solution

11.3 Show that the amortized bound of O(logN) for the skew heap operations described in the text cannot be converted to a worst-case bound, by giving a sequence of operations that lead to a merge requiring (N) time. - Get solution

11.4 Show how to merge two skew heaps with one top-down pass and reduce the merge cost to O(1) amortized time. - Get solution

11.5 Extend skew heaps to support the decreaseKey operation in O(logN) amortized time. - Get solution

11.6 Implement Fibonacci heaps and compare their performance with that of binary heaps when used in Dijkstra’s algorithm. - Get solution


11.7 A standard implementation of Fibonacci heaps requires four links per node (parent, child, and two siblings). Show how to reduce the number of links, at the cost of at most a constant factor in the running time. - Get solution

11.8 Show that the amortized time of a zig-zig splay is at most 3(Rf (X) − Ri(X)). - Get solution

11.9 By changing the potential function, it is possible to prove different bounds for splaying. Let the weight function W(i) be some function assigned to each node in the tree, and let S(i) be the sum of the weights of all the nodes in the subtree rooted at i, including i itself. The special case W(i) = 1 for all nodes corresponds to the function used in the proof of the splaying bound. Let N be the number of
nodes in the tree, and let M be the number of accesses. Prove the following two theorems:
a. The total access time is O(M + (M + N) logN).
b. If qi is the number of times that item i is accessed, and qi > 0 for all i, then the
total access time is

Get solution

11.10 a. Show how to implement the merge operation on splay trees so that any sequence of N−1 merges starting from N single-element trees takes O(N log2 N) time.
b. Improve the bound to O(N logN). - Get solution

11.11 In Chapter 5, we described rehashing: When a table becomes more than half full,a new table twice as large is constructed, and the entire old table is rehashed. Give a formal amortized analysis, with potential function, to show that the amortized cost of an insertion is still O(1). - Get solution

11.12 What is the maximum depth of a Fibonacci heap? - Get solution

11.13 A deque with heap order is a data structure consisting of a list of items, on which
the following operations are possible:
push(x): Insert item x on the front end of the deque.
pop(): Remove the front item from the deque and return it.
inject(x): Insert item x on the rear end of the deque.
eject(): Remove the rear item from the deque and return it.
findMin(): Return the smallest item from the deque (breaking ties arbitrarily).
a. Describe how to support these operations in constant amortized time per
operation.
b. Describe how to support these operations in constant worst-case time per
operation. - Get solution

11.14 Show that the binomial queues actually support merging in O(1) amortized time. Define the potential of a binomial queue to be the number of trees plus the rank of the largest tree. - Get solution

11.15 Suppose that in an attempt to save time, we splay on every second tree operation.
Does the amortized cost remain logarithmic? - Get solution

11.16 Using the potential function in the proof of the splay tree bound, what is the maximum and minimum potential of a splay tree? By how much can the potential function decrease in one splay? By how much can the potential function increase in one splay? You may give Big-Oh answers. - Get solution

11.17 As a result of a splay, most of the nodes on the access path are moved halfway towards the root, while a couple of nodes on the path move down one level. This suggests using the sum over all nodes of the logarithm of each node’s depth as a potential function.
a. What is the maximum value of the potential function?
b. What is the minimum value of the potential function?
c. The difference in the answers to parts (a) and (b) gives some indication that this potential function isn’t too good. Show that a splaying operation could increase the potential by (N/ logN). - Get solution

Chapter #7 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

7.1 Sort the sequence 3, 1, 4, 1, 5, 9, 2, 6, 5 using insertion sort. - Get solution

7.2 What is the running time of insertion sort if all elements are equal? - Get solution

7.3 Suppose we exchange elements a[i] and a[i+k], which were originally out of order.
Prove that at least 1 and at most 2k − 1 inversions are removed. - Get solution

7.4 Show the result of running Shellsort on the input 9, 8, 7, 6, 5, 4, 3, 2, 1 using the increments {1, 3, 7}. - Get solution

7.5 a. What is the running time of Shellsort using the two-increment sequence {1, 2}?
b. Show that for any N, there exists a three-increment sequence such that Shellsort - Get solution

- Get solution

7.7 Prove that if a k-sorted file is then h-sorted, it remains k-sorted. - Sol. Not available

- Get solution

7.9 Determine the running time of Shellsort for
a. sorted input
b. reverse-ordered input - Get solution

7.10 Do either of the following modifications to the Shellsort routine coded in Figure 7.4
affect the worst-case running time?
a. Before line 11, subtract one from gap if it is even.
b. Before line 11, add one to gap if it is even. - Get solution

7.11 Show how heapsort processes the input 142, 543, 123, 65, 453, 879, 572, 434,
111, 242, 811, 102. - Get solution


7.13 Show that there are inputs that force every percolateDown in heapsort to go all the
way to a leaf. (Hint: Work backward.) - Get solution

7.14 Rewrite heapsort so that it sorts only items that are in the range low to high which
are passed as additional parameters.
Solution: If the root is stored in position low, then the left child of node i is stored at position 2i + 1 - low. This requires a small change to the heapsort code.

7.15 Sort 3, 1, 4, 1, 5, 9, 2, 6 using mergesort. - Get solution

7.16 How would you implement mergesort without using recursion? - Get solution

7.17 Determine the running time of mergesort for
a. sorted input
b. reverse-ordered input
c. random input - Get solution

7.18 Sol. Not available

7.19 Sort 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 using quicksort with median-of-three partitioning
and a cutoff of 3. - Get solution

7.20 Using the quicksort implementation in this chapter, determine the running time of
quicksort for
a. sorted input
b. reverse-ordered input
c. random input - Get solution

7.21 Repeat Exercise 7.20 when the pivot is chosen as
a. the first element
b. the larger of the first two distinct elements
c. a random element
d. the average of all elements in the set - Get solution

7.22 a. For the quicksort implementation in this chapter, what is the running time when
all keys are equal?
b. Suppose we change the partitioning strategy so that neither i nor j stops when
an element with the same key as the pivot is found. What fixes need to be made
in the code to guarantee that quicksort works, and what is the running time,
when all keys are equal?
c. Suppose we change the partitioning strategy so that i stops at an element with
the same key as the pivot, but j does not stop in a similar case. What fixes need
to be made in the code to guarantee that quicksort works, and when all keys are
equal, what is the running time of quicksort? - Get solution

7.23 Suppose we choose the element in the middle position of the array as the pivot.
Does this make it unlikely that quicksort will require quadratic time? - Get solution

7.24 Construct a permutation of 20 elements that is as bad as possible for quicksort using median-of-three partitioning and a cutoff of 3. - Get solution

7.26 Continuing from Exercise 7.25, after part (a),
a. Perform a test so that the smaller subarray is processed by the first recursive call,
while the larger subarray is processed by the second recursive call.
b. Remove the tail recursion by writing a while loop and altering left or right, as
necessary.
c. Prove that the number of recursive calls is logarithmic in the worst case. - Get solution

7.27 Suppose the recursive quicksort receives an int parameter, depth, from the driver
that is initially approximately 2 logN.
a. Modify the recursive quicksort to call heapsort on its current subarray if the level
of recursion has reached depth. (Hint: Decrement depth as you make recursive
calls; when it is 0, switch to heapsort.)
b. Prove that the worst-case running time of this algorithm is O(N logN).
c. Conduct experiments to determine how often heapsort gets called.
d. Implement this technique in conjunction with tail-recursion removal in Exercise 7.25.
e. Explain why the technique in Exercise 7.26 would no longer be needed. - Sol. 7.27 Not available

7.28 When implementing quicksort, if the array contains lots of duplicates, it may be better to perform a three-way partition (into elements less than, equal to, and greater than the pivot), to make smaller recursive calls. Assume three-way comparisons, as provided by the compareTo method.
a. Give an algorithm that performs a three-way in-place partition of an N-element subarray using only N − 1 three-way comparisons. If there are d items equal to the pivot, you may use d additional Comparable swaps, above and beyond the two-way partitioning algorithm. (Hint: As i and j move toward each other, maintain five groups of elements as shown below):
EQUAL SMALL UNKNOWN LARGE EQUAL
i j
b. Prove that using the algorithm above, sorting an N-element array that contains
only d different values, takes O(dN) time. - Get 7.28a Solution / Sol. 7.28. b. Not available

7.37 Consider the following algorithm for sorting six numbers:
Sort the first three numbers using Algorithm A.
Sort the second three numbers using Algorithm B.
Merge the two sorted groups using Algorithm C.
Show that this algorithm is suboptimal, regardless of the choices for Algorithms A,
B, and C. - Get solution

7.38 Write a program that reads N points in a plane and outputs any group of four
or more colinear points (i.e., points on the same line). The obvious brute-force
algorithm requires O(N4) time. However, there is a better algorithm that makes use
of sorting and runs in O(N2 logN) time. - Get solution

7.42 Give a linear-time algorithm to sort N fractions, each of whose numerators and denominators are integers between 1 and N. - Get solution

7.43 Suppose arrays A and B are both sorted and both contain N elements. Give an O(logN) algorithm to find the median of A ∪ B. - Get solution

7.44 Suppose you have an array of N elements containing only two distinct keys, true and false. Give an O(N) algorithm to rearrange the list so that all false elements precede the true elements. You may use only constant extra space. - Get solution

7.45 Suppose you have an array of N elements, containing three distinct keys, true, false, and maybe. Give an O(N) algorithm to rearrange the list so that all false elements precede maybe elements, which in turn precede true elements. You may use only constant extra space. - Get solution

7.46 a. Prove that any comparison-based algorithm to sort 4 elements requires 5 comparisons.
b. Give an algorithm to sort 4 elements in 5 comparisons. - Get solution

7.47 a. Prove that 7 comparisons are required to sort 5 elements using any comparison based
algorithm.
b. Give an algorithm to sort 5 elements with 7 comparisons. - Get solution

7.51 Suppose we implement the median of three routine as follows: Find the median of a[left], a[center], a[right], and swap it with a[right]. Proceed with the normal partitioning step starting i at left and j at right-1 (instead of left+1 and right-2).
a. Suppose the input is 2, 3, 4, . . . ,N −1,N, 1. For this input, what is the running time of this version of quicksort?
b. Suppose the input is in reverse order. For this input, what is the running time of this version of quicksort? - Get solution

7.52 Prove that any comparison-based sorting algorithm requires (N logN) comparisons on average. - Get solution

7.53 We are given an array that contains N numbers. We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input is 8, 4, 1, 6, and K is 10, then the answer is yes (4 and 6). A number may be used twice.
Do the following:
a. Give an O(N2) algorithm to solve this problem.
b. Give an O(N logN) algorithm to solve this problem. (Hint: Sort the items first.
After that is done, you can solve the problem in linear time.)
c. Code both solutions and compare the running times of your algorithms. - Get solution

7.55 Repeat Exercise 7.53 for three numbers. Try to design an O(N2) algorithm. - Get solution

Chapter #6 Solutions - Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

Available Solutions for the following Chapter 6 exercises:

6.1 Can both insert and findMin be implemented in constant time? - Get solution

6.2 a. Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time, into an initially empty binary heap.
b. Show the result of using the linear-time algorithm to build a binary heap using the same input. - Get solution

6.3 Show the result of performing three deleteMin operations in the heap of the previous exercise. - Get solution

6.4 A complete binary tree of N elements uses array positions 1 to N. Suppose we try
to use an array representation of a binary tree that is not complete. Determine how
large the array must be for the following:
a. a binary tree that has two extra levels (that is, it is very slightly unbalanced)
b. a binary tree that has a deepest node at depth 2 logN
c. a binary tree that has a deepest node at depth 4.1 logN
d. the worst-case binary tree  - Get solution

6.5 Rewrite the BinaryHeap insert method by placing a reference to the inserted item in
position 0. - Get solution

6.6 How many nodes are in the large heap in Figure 6.13?  - Get solution

- Get 6.7 solution

- Get 6.9 solution

6.10 a. Give an algorithm to find all nodes less than some value, X, in a binary heap.
Your algorithm should run in O(K), where K is the number of nodes output.
b. Does your algorithm extend to any of the other heap structures discussed in this chapter?
c. Give an algorithm that finds an - Get solution


6.12 Write a program to take N elements and do the following:
a. Insert them into a heap one by one.
b. Build a heap in linear time. - Get solution

Compare the running time of both algorithms for sorted, reverse-ordered, and
random inputs.

6.13 Each deleteMin operation uses 2 logN comparisons in the worst case.
a. Propose a scheme so that the deleteMin operation uses only logN + log logN +
O(1) comparisons between elements. This need not imply less data movement.
b. Extend your scheme in part (a) so that only logN + log log logN + O(1)
comparisons are performed.
c. How far can you take this idea?
d. Do the savings in comparisons compensate for the increased complexity of your algorithm?  - Get solution

6.14 If a d-heap is stored as an array, for an entry located in position i, where are the parents and children? - Get solution

6.15 Suppose we need to perform M percolateUps and N deleteMins on a d-heap that initially has N elements.
a. What is the total running time of all operations in terms of M, N, and d?
b. If d = 2, what is the running time of all heap operations?
c. If d = (N), what is the total running time?
d. What choice of d minimizes the total running time? - Get solution

6.16 Suppose that binary heaps are represented using explicit links. Give a simple algorithm to find the tree node that is at implicit position i. - Get solution

6.17 Suppose that binary heaps are represented using explicit links. Consider the problem of merging binary heap lhs with rhs. Assume both heaps are perfect binary
trees, containing 2l − 1 and 2r − 1 nodes, respectively.
a. Give an O(logN) algorithm to merge the two heaps if l = r.
b. Give an O(logN) algorithm to merge the two heaps if |l − r| = 1.
c. Give an O(log2 N) algorithm to merge the two heaps regardless of l and r. - Get solution


6.19 Merge the two leftist heaps in Figure 6.58. - Get solution

6.20 Show the result of inserting keys 1 to 15 in order into an initially empty leftist heap. - Get solution

6.21 Prove or disprove: A perfectly balanced tree forms if keys 1 to 2k − 1 are inserted in order into an initially empty leftist heap. - Get solution


6.22 Give an example of input that generates the best leftist heap. - Get solution

6.23 a. Can leftist heaps efficiently support decreaseKey?
b. What changes, if any (if possible), are required to do this? - Get solution

6.24 One way to delete nodes from a known position in a leftist heap is to use a lazy strategy. To delete a node, merely mark it deleted. When a findMin or deleteMin is performed, there is a potential problem if the root is marked deleted, since then the node has to be actually deleted and the real minimum needs to be found, which may involve deleting other marked nodes. In this strategy, deletes cost one unit, but the cost of a deleteMin or findMin depends on the number of nodes that are marked deleted. Suppose that after a deleteMin or findMin there are k fewer marked nodes than before the operation.
a. Show how to perform the deleteMin in O(k logN) time.
b. Propose an implementation, with an analysis to show that the time to perform the deleteMin is O(k log(2N/k)). - Get solution

6.25 We can perform buildHeap in linear time for leftist heaps by considering each
element as a one-node leftist heap, placing all these heaps on a queue, and performing
the following step: Until only one heap is on the queue, dequeue two
heaps, merge them, and enqueue the result.
a. Prove that this algorithm is O(N) in the worst case.
b. Why might this algorithm be preferable to the algorithm described in the text? - Get solution

6.26 Merge the two skew heaps in Figure 6.58. - Get solution

6.27 Show the result of inserting keys 1 to 15 in order into a skew heap. - Get solution

6.28 Prove or disprove: A perfectly balanced tree forms if the keys 1 to 2k−1 are inserted in order into an initially empty skew heap. - Get solution

6.29 A skew heap of N elements can be built using the standard binary heap algorithm.
Can we use the same merging strategy described in Exercise 6.25 for skew heaps to get an O(N) running time? - Get solution

6.30 Prove that a binomial tree Bk has binomial trees B0, B1, . . . , Bk−1 as children of the
root. - Get solution

6.31 Prove that a binomial tree of height k has kd nodes at depth d. - Get solution

6.32 Merge the two binomial queues in Figure 6.59. - Get solution

6.33 a. Show that N inserts into an initially empty binomial queue takes O(N) time in the worst case.
b. Give an algorithm to build a binomial queue of N elements, using at most N−1 comparisons between elements.
c. Propose an algorithm to insert M nodes into a binomial queue of N elements in O(M + logN) worst-case time. Prove your bound. - Get solution

6.38 Suppose we want to add the decreaseAllKeys() operation to the heap repertoire.
The result of this operation is that all keys in the heap have their value decreased by an amount. For the heap implementation of your choice, explain the necessary modifications so that all other  operations retain their running times and decreaseAllKeys runs in O(1). - Get solution

6.39 Which of the two selection algorithms has the better time bound? - Get solution

Chapter #5 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

5.1 Given input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function
h(x) = x mod 10, show the resulting:
a. Separate chaining hash table.
b. Hash table using linear probing.
c. Hash table using quadratic probing.
d. Hash table with second hash function h2(x) = 7 − (x mod 7). Get solution

5.2 Show the result of rehashing the hash tables in Exercise 5.1.   Get solution

5.4 A large number of deletions in a separate chaining hash table can cause the table to be fairly empty, which wastes space. In this case, we can rehash to a table half as large. Assume that we rehash to a larger table when there are twice as many elements as the table size. How empty should the table be before we rehash to a smaller table? Get solution

5.5 Reimplement separate chaining hash tables using singly linked lists instead of using
java.util.LinkedList.  Get solution

5.6 The isEmpty routine for quadratic probing has not been written. Can you implement
it by returning the expression currentSize==0?

Sol: No; this does not take deletions into account.

5.7 In the quadratic probing hash table, suppose that instead of inserting a new item into the location suggested by findPos, we insert it into the first inactive cell on the search path (thus, it is possible to reclaim a cell that is marked “deleted,” potentially saving space).
a. Rewrite the insertion algorithm to use this observation. Do this by having find-
Pos maintain, with an additional variable, the location of the first inactive cell it
encounters. (Solution Not available)
b. Explain the circumstances under which the revised algorithm is faster than the
original algorithm. Can it be slower?

Sol:  If the number of deleted cells is small, then we spend extra time looking for inactive cells that are not likely to be found. If the number of deleted cells is large, then we may get improvement.

5.8 Suppose instead of quadratic probing, we use “cubic probing”; here the ith probe
is at hash(x) + i3. Does cubic probing improve on quadratic probing?  Get solution

5.9 The hash function in Figure 5.4 makes repeated calls to key.length( ) in the for
loop. Is it worth computing this once prior to entering the loop?
Sol: In a good library implementation, the length method should be inlined.

5.10 What are the advantages and disadvantages of the various collision resolution
strategies?  Get solution

5.12 Rehashing requires recomputing the hash function for all items in the hash table.
Since computing the hash function is expensive, suppose objects provide a hash member function of their own, and each object stores the result in an additional data member the first time the hash function is computed for it. Show how such a scheme would apply for the Employee class in Figure 5.8, and explain under what circumstances the remembered hash value remains valid in each Employee.
Sol: The old values would remain valid if the hashed values were less than the old table size.

5.13 Write a program to implement the following strategy for multiplying two sparse polynomials P1, P2 of size M and N, respectively. Each polynomial is represented as a linked list of objects consisting of a coefficient and an exponent (Exercise 3.12).
We multiply each term in P1 by a term in P2 for a total of MN operations. One method is to sort these terms and combine like terms, but this requires sorting MN records, which could be expensive, especially in small-memory environments.
Alternatively, we could merge terms as they are computed and then sort the result.
a. Write a program to implement the alternative strategy.
b. If the output polynomial has about O(M + N) terms, what is the running time
of both methods?  Get solution

5.14 Describe a procedure that avoids initializing a hash table (at the expense of
memory).  Get solution

5.16 Java 7 adds syntax that allows a switch statement to work with the String type
(instead of the primitive integer types). Explain how hash tables can be used by the
compiler to implement this language addition.  Get solution


5.19 Under certain assumptions, the expected cost of an insertion into a hash table with
secondary clustering is given by 1/(1−λ)−λ−ln(1−λ). Unfortunately, this formula
is not accurate for quadratic probing. However, assuming that it is, determine the
following:
a. The expected cost of an unsuccessful search.
b. The expected cost of a successful search.   Get solution

5.20 Implement a generic Map that supports the put and get operations. The implementation
will store a hash table of pairs (key, definition). Figure 5.55 provides the Map
specification (minus some details).  Get solution

Get 5.22 solution

5.23 If a hopscotch table with parameter MAX_DIST has load factor 0.5, what is the
approximate probability that an insertion requires a rehash?   Get solution

Chapter #4 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

Available Solutions for the following Chapter 4 exercises:

Questions 4.1 to 4.3 refer to the tree in Figure 4.70.
4.1 For the tree in Figure 4.70:
a. Which node is the root?
b. Which nodes are leaves?   Get solution

4.2 For each node in the tree of Figure 4.70:
a. Name the parent node.
b. List the children.
c. List the siblings.
d. Compute the depth.
e. Compute the height.  Get solution


4.3 What is the depth of the tree in Figure 4.70?
Sol: 4.

4.4 Show that in a binary tree of N nodes, there are N + 1 null links representing children. Get solution

4.8 Give the prefix, infix, and postfix expressions corresponding to the tree in Figure 4.71. Get solution


4.9 a. Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search tree.
b. Show the result of deleting the root. Get solution


4.10 Write a program that lists all files in a directory and their sizes. Mimic the routine in the online code.   Get solution


4.11 Write an implementation of the TreeSet class, with associated iterators using a
binary search tree. Add to each node a link to the parent node.   Get solution


4.13 Write an implementation of the TreeSet class, with associated iterators, using a
binary search tree. Add to each node a link to the next smallest and next largest
node. To make your code simpler, add a header and tail node which are not part of
the binary search tree, but help make the linked list part of the code simpler.    Get solution


4.14 Suppose you want to perform an experiment to verify the problems that can be caused by random insert/remove pairs. Here is a strategy that is not perfectly random,but close enough. You build a tree with N elements by inserting N elements chosen at random from the range 1 to M = αN. You then perform N2 pairs of insertions followed by deletions. Assume the existence of a routine, randomInteger(a, b), which returns a uniform random integer between a and b inclusive.
a. Explain how to generate a random integer between 1 and M that is not alreadyin the tree (so a random insertion can be performed). In terms of N and α, what is the running time of this operation?
b. Explain how to generate a random integer between 1 and M that is already in the tree (so a random deletion can be performed). What is the running time of this operation?
c. What is a good choice of α? Why?   Get solution


4.18 a. Give a precise expression for the minimum number of nodes in an AVL tree of
height h.
b. What is the minimum number of nodes in an AVL tree of height 15?   Get solution


4.19 Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree.  Get solution

Get 4.20 solution

4.21 Write the remaining procedures to implement AVL single and double rotations.  Get solution

4.24 Show that the deletion algorithm in Figure 4.44 is correct, and explain what happens if > is used instead of >= at lines 32 and 38 in Figure 4.39. - Get solution

4.25 a. How many bits are required per node to store the height of a node in an N-node
AVL tree?
b. What is the smallest AVL tree that overflows an 8-bit height counter?   Get solution


4.26 Write the methods to perform the double rotation without the inefficiency of doing two single rotations. Get solution


4.27 Show the result of accessing the keys 3, 9, 1, 5 in order in the splay tree in Figure 4.72.  Get solution


4.28 Show the result of deleting the element with key 6 in the resulting splay tree for the
previous exercise.  Get solution

b. Show that if all nodes in a splay tree are accessed in sequential order, then the
total access time is O(N), regardless of the initial tree.  Get solution


4.31 Write efficient methods that take only a reference to the root of a binary tree, T, and
compute:
a. The number of nodes in T.
b. The number of leaves in T.
c. The number of full nodes in T.
What is the running time of your routines?     Get solution


4.32 Design a recursive linear-time algorithm that tests whether a binary tree satisfies the search tree order property at every node.   Get solution


4.33 Write a recursive method that takes a reference to the root node of a tree T and returns a reference to the root node of the tree that results from removing all leaves from T.  Get solution


4.34 Write a method to generate an N-node random binary search tree with distinct keys 1 through N. What is the running time of your routine?  Get solution


4.35 Write a method to generate the AVL tree of height h with fewest nodes. What is the running time of your method?   Get solution

Get 4.36 solution

4.37 Write a method that takes as input a binary search tree, T, and two keys k1 and k2, which are ordered so that k1 ≤ k2, and prints all elements X in the tree such that k1 ≤ Key(X) ≤ k2. Do not assume any information about the type of keys except that they can be ordered (consistently). Your program should run in O(K + logN) average time, where K is the number of keys printed. Bound the running time of your algorithm.  Get solution


4.38 The larger binary trees in this chapter were generated automatically by a program.
This was done by assigning an (x, y) coordinate to each tree node, drawing a circle around each coordinate (this is hard to see in some pictures), and connecting each node to its parent. Assume you have a binary search tree stored in memory (perhaps generated by one of the routines above) and that each node has two extra fields to store the coordinates.
a. The x coordinate can be computed by assigning the inorder traversal number.
Write a routine to do this for each node in the tree.
b. The y coordinate can be computed by using the negative of the depth of the node. Write a routine to do this for each node in the tree.
c. In terms of some imaginary unit, what will the dimensions of the picture be?
How can you adjust the units so that the tree is always roughly two-thirds as high as it is wide?   
d. Prove that using this system no lines cross, and that for any node, X, all elements in X’s left subtree appear to the left of X and all elements in X’s right subtree appear to the right of X.   Get solution


4.44 Show how the tree in Figure 4.73 is represented using a child/sibling link  implementation.  Get solution

4.46 Two binary trees are similar if they are both empty or both nonempty and have
similar left and right subtrees. Write a method to decide whether two binary trees
are similar. What is the running time of your method?   Get solution


4.48 a. Show that via AVL single rotations, any binary search tree T1 can be transformed into another search tree T2 (with the same items).
b. Give an algorithm to perform this transformation using O(N logN) rotations on average.
c. Show that this transformation can be done with O(N) rotations, worst case.  Get solution


4.49 Suppose we want to add the operation findKth to our repertoire. The operation findKth(k) returns the kth smallest item in the tree. Assume all items are distinct.
Explain how to modify the binary search tree to support this operation in O(logN) average time, without sacrificing the time bounds of any other operation.  Get solution


4.50 Since a binary search tree with N nodes has N + 1 null references, half the space allocated in a binary search tree for link information is wasted. Suppose that if a node has a null left child, we make its left child link to its inorder predecessor, and if a node has a null right child, we make its right child link to its inorder successor.This is known as a threaded tree, and the extra links are called threads.
a. How can we distinguish threads from real children links? Sol: You need an extra bit for each thread.

c. What is the advantage of using threaded trees?   Sol:  You can do tree traversals somewhat easier and without recursion. The disadvantage is that it reeks of old-style hacking.

IX: {Series |(} {2}
IX: {Series!geometric|(} {4}
IX: {Euler’s constant} {4}
IX: {Series!geometric|)} {4}
IX: {Series!arithmetic|(} {4}
IX: {Series!arithmetic|)} {5}
IX: {Series!harmonic|(} {5}
IX: {Euler’s constant} {5}
IX: {Series!harmonic|)} {5}
IX: {Series|)} {5}    Get solution

Chapter #2 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

Available Solutions for the following Chapter 2 exercises:


2.1 Order the following functions by growth rate: N, ,N, N1.5, N2, N logN,
N log logN, N log2 N, N log(N2), 2/N, 2N, 2N/2, 37, N2 logN, N3. Indicate which
functions grow at the same rate. Get solution

2.2 Suppose T1(N) = O(f (N)) and T2(N) = O(f (N)). Which of the following are true?
a. T1(N) + T2(N) = O(f (N))
b. T1(N) − T2(N) = o(f (N))
c.
T1(N)
T2(N) = O(1)
d. T1(N) = O(T2(N)) Get solution

2.3 Which function grows faster: N logN or N1+(/,logN, ( > 0? Get solution

2.4 Prove that for any constant, k, logk N = o(N).  Get solution

2.5 Find two functions f (N) and g(N) such that neither f (N) = O(g(N)) nor g(N) = O(f (N)). Get solution

2.6 In a recent court case, a judge cited a city for contempt and ordered a fine of $2 for the first day. Each subsequent day, until the city followed the judge’s order, the fine was squared (that is, the fine progressed as follows: $2, $4, $16, $256, $65, 536, . . .).
a. What would be the fine on day N?
b. How many days would it take the fine to reach D dollars? (A Big-Oh answer will do.)  Get solution

2.7 For each of the following six program fragments:
a. Give an analysis of the running time (Big-Oh will do).
b. Implement the code in Java, and give the running time for several values of N.
c. Compare your analysis with the actual running times.
(1) sum = 0;
for( i = 0; i < n; i++ )
sum++;
(2) sum = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < n; j++ )
sum++;
(3) sum = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < n * n; j++ )
sum++;
(4) sum = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < i; j++ )
sum++;
Exercises 51
(5) sum = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < i * i; j++ )
for( k = 0; k < j; k++ )
sum++;
(6) sum = 0;
for( i = 1; i < n; i++ )
for( j = 1; j < i * i; j++ )
if( j % i == 0 )
for( k = 0; k < j; k++ )
sum++;   Get solution

2.8 Suppose you need to generate a random permutation of the first N integers.
For example, {4, 3, 1, 5, 2} and {3, 1, 4, 2, 5} are legal permutations, but{5, 4, 1, 2, 1} is not, because one number (1) is duplicated and another (3) is missing. This routine is often used in simulation of algorithms.We assume the existence of a random number generator, r, with method randInt(i, j), that generates integers between i and j with equal probability. Here are three algorithms:
1. Fill the array a from a[0] to a[n-1] as follows: To fill a[i], generate random numbers until you get one that is not already in a[0], a[1], . . . , a[i-1].
2. Same as algorithm (1), but keep an extra array called the used array. When a random number, ran, is first put in the array a, set used[ran] = true. This means that when filling a[i] with a random number, you can test in one step to see whether the random number has been used, instead of the  (possibly) i steps in the first algorithm.
3. Fill the array such that a[i] = i + 1. Then
for( i = 1; i < n; i++ )
swapReferences( a[ i ], a[ randInt( 0, i ) ] );
a. Prove that all three algorithms generate only legal permutations and that all permutations are equally likely.
b. Give as accurate (Big-Oh) an analysis as you can of the expected running time of each algorithm.
c. Write (separate) programs to execute each algorithm 10 times, to get a good average. Run program (1) for N = 250, 500, 1,000, 2,000; program (2) for N = 25,000, 50,000, 100,000, 200,000, 400,000, 800,000; and program (3) for N = 100,000, 200,000, 400,000, 800,000, 1,600,000, 3,200,000, 6,400,000.
d. Compare your analysis with the actual running times.
e. What is the worst-case running time of each algorithm?  Get solution


2.9 Complete the table in Figure 2.2 with estimates for the running times that were too long to simulate. Interpolate the running times for these algorithms and estimate the time required to compute the maximum subsequence sum of 1 million numbers. What assumptions have you made?  Get solution



2.10 Determine, for the typical algorithms that you use to perform calculations by hand,
the running time to do the following:
a. Add two N-digit integers.
b. Multiply two N-digit integers.
c. Divide two N-digit integers.   Get solution


2.11 An algorithm takes 0.5 ms for input size 100. How long will it take for input size
500 if the running time is the following (assume low-order terms are negligible):
a. linear
b. O(N logN)
c. quadratic
d. cubic    Get solution


2.12 An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in
1 min if the running time is the following (assume low-order terms are negligible):
a. linear
b. O(N logN)
c. quadratic
d. cubic   Get solution

Get 2.13 solution

2.15 Give an efficient algorithm to determine if there exists an integer i such that Ai = i in an array of integers A1 < A2 < A3 < · · · < AN. What is the running time of your algorithm? Get solution

c. Let B equal the number of bits in the binary representation of N. What is the
value of B?
d. In terms of B, what is the worst-case running time of your program?
e. Compare the running times to determine if a 20-bit number and a 40-bit number
are prime.
f. Is it more reasonable to give the running time in terms of N or B? Why?   Get solution

2.26 A majority element in an array, A, of size N is an element that appears more than N/2 times (thus, there is at most one). For example, the array 3, 3, 4, 2, 4, 4, 2, 4, 4 has a majority element (4), whereas the array
3, 3, 4, 2, 4, 4, 2, 4 does not. If there is no majority element, your program should indicate this. Here
is a sketch of an algorithm to solve the problem:
First, a candidate majority element is found (this is the harder part). This candidate is the
only element that could possibly be the majority element. The second step determines if
this candidate is actually the majority. This is just a sequential search through the array. To
find a candidate in the array, A, form a second array, B. Then compare A1 and A2. If they
are equal, add one of these to B; otherwise do nothing. Then compare A3 and A4. Again if
they are equal, add one of these to B; otherwise do nothing. Continue in this fashion until
the entire array is read. Then recursively find a candidate for B; this is the candidate for
A (why?).
a. How does the recursion terminate?
#b. How is the case where N is odd handled?
#c. What is the running time of the algorithm?
d. How can we avoid using an extra array B?
#e. Write a program to compute the majority element.     Get solution

2.27 The input is an N by N matrix of numbers that is already in memory. Each individual row is increasing from left to right. Each individual column is increasing from top to bottom. Give an O(N) worst-case algorithm that decides if a number X is in the matrix.  Get solution


2.28 Design efficient algorithms that take an array of positive numbers a, and determine:
a. the maximum value of a[j]+a[i], with j ) i.
b. the maximum value of a[j]-a[i], with j ) i.
c. the maximum value of a[j]*a[i], with j ) i.
d. the maximum value of a[j]/a[i], with j ) i.   Get solution


#2.29 Why is it important to assume that integers in our computer model have a fixed size?  Get solution

2.31 Suppose that line 15 in the binary search routine had the statement low = mid instead of low = mid + 1. Would the routine still work?  Get solution

Chapter #1 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

Get the Chapter 1 solutions for the exercises 1.4, 1.5, 1.7 - 1.12. of Data Structures and Algorithms of Weiss book Here.
We offer the solutions from only the above specified exercises.


-------------------------------------------------------------------------
Available Solutions for the following Chapter 1 exercises:

1.4 C allows statements of the form #include filename which reads filename and inserts its contents in place of the include statement.
Include statements may be nested; in other words, the file filename may itself contain an include statement, but, obviously, a file can’t include itself in any chain.
Write a program that reads in a file and outputs the file as modified by the include statements.


1.5 Write a recursive method that returns the number of 1’s in the binary representation
of N. Use the fact that this is equal to the number of 1’s in the representation of N/2,
plus 1, if N is odd.

1.7 Prove the following formulas:
a. log X < X for all X > 0
b. log(AB) = B log A