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 #3 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

Available Solutions for the following Chapter 3 exercises:

3.1 You are given a list, L, and another list, P, containing integers sorted in ascending
order. The operation printLots(L,P) will print the elements in L that are in positions
specified by P. For instance, if P = 1, 3, 4, 6, the elements in positions 1, 3, 4, and 6
in L are printed. Write the procedure printLots(L,P). You may use only the public
Collections API container operations. What is the running time of your procedure? Get solution


3.2 Swap two adjacent elements by adjusting only the links (and not the data) using:
a. Singly linked lists.
b. Doubly linked lists. Get solution


3.3 Implement the contains routine for MyLinkedList. Get solution


3.4 Given two sorted lists, L1 and L2, write a procedure to compute L1 1 L2 using only
the basic list operations. Get solution


3.5 Given two sorted lists, L1 and L2, write a procedure to compute L1 2 L2 using only
the basic list operations. Get solution


3.6 The Josephus problem is the following game: N people, numbered 1 to N, are sitting
in a circle. Starting at person 1, a hot potato is passed. After M passes, the person
holding the hot potato is eliminated, the circle closes ranks, and the game continues
with the person who was sitting after the eliminated person picking up the hot
potato. The last remaining person wins. Thus, if M = 0 and N = 5, players are
eliminated in order, and player 5 wins. IfM = 1 and N = 5, the order of elimination
is 2, 4, 1, 5.
Exercises 97
a. Write a program to solve the Josephus problem for general values of M and N.
Try to make your program as efficient as possible. Make sure you dispose of
cells.
b. What is the running time of your program? Get solution


3.7 What is the running time of the following code?
public static List<Integer> makeList( int N )
{
ArrayList<Integer> lst = new ArrayList<>( );
for( int i = 0; i < N; i++ )
{
lst.add( i );
lst.trimToSize( );
}
} Get solution


3.8 The following routine removes the first half of the list passed as a parameter:
public static void removeFirstHalf( List<?> lst )
{
int theSize = lst.size( ) / 2;
for( int i = 0; i < theSize; i++ )
lst.remove( 0 );
}
a. Why is theSize saved prior to entering the for loop?
b. What is the running time of removeFirstHalf if lst is an ArrayList?
c. What is the running time of removeFirstHalf if lst is a LinkedList?
d. Does using an iterator make removeHalf faster for either type of List? Get solution


3.9 Provide an implementation of an addAll method for the MyArrayList class. Method
addAll adds all items in the specified collection given by items to the end of the
MyArrayList. Also provide the running time of your implementation. The method
signature for you to use is slightly different than the one in the Java Collections API,
and is as follows:
public void addAll( Iterable<? extends AnyType> items ) Get solution


3.10 Provide an implementation of a removeAll method for the MyLinkedList class.
Method removeAll removes all items in the specified collection given by items
from the MyLinkedList. Also provide the running time of your implementation.
The method signature for you to use is slightly different than the one in the Java
Collections API, and is as follows:
public void removeAll( Iterable<? extends AnyType> items )
98 Chapter 3 Lists, Stacks, and Queues Get solution


3.11 Assume that a singly linked list is implemented with a header node, but no tail
node, and that it maintains only a reference to the header node. Write a class that
includes methods to
a. return the size of the linked list
b. print the linked list
c. test if a value x is contained in the linked list
d. add a value x if it is not already contained in the linked list
e. remove a value x if it is contained in the linked list Get solution


3.12 Repeat Exercise 3.11, maintaining the singly linked list in sorted order. Get solution


3.13 Add support for a ListIterator to the MyArrayList class. The ListIterator interface
in java.util has more methods than are shown in Section 3.3.5. Notice that
you will write a listIterator method to return a newly constructed ListIterator,
and further, that the existing iterator method can return a newly constructed
ListIterator. Thus you will change ArrayListIterator so that it implements
ListIterator instead of Iterator. Throw an UnsupportedOperationException for
methods not listed in Section 3.3.5. Get solution


3.14 Add support for a ListIterator to the MyLinkedList class, as was done in
Exercise 3.13. Get solution

3.16 An alternative to providing a ListIterator is to provide a method with signature
Iterator<AnyType> reverseIterator( )
that returns an Iterator, initialized to the last item, and for which next and hasNext
are implemented to be consistent with the iterator advancing toward the front of
the list, rather than the back. Then you could print a MyArrayList L in reverse by
using the code
Iterator<AnyType> ritr = L.reverseIterator( );
while( ritr.hasNext( ) )
System.out.println( ritr.next( ) );
Implement an ArrayListReverseIterator class, with this logic, and have reverseIterator
return a newly constructed ArrayListReverseIterator. Get solution


3.18 For MyLinkedList, implement addFirst, addLast, removeFirst, removeLast, getFirst, and getLast Get solution


3.19 Rewrite the MyLinkedList class without using header and tail nodes and describe
the differences between the class and the class provided in Section 3.5. Get solution


3.20 An alternative to the deletion strategy we have given is to use lazy deletion. To delete an element, we merely mark it deleted (using an extra bit field). The number of deleted and nondeleted elements in the list is kept as part of the data structure. If there are as many deleted elements as nondeleted elements, we traverse the entire list, performing the standard deletion algorithm on all marked nodes.
a. List the advantages and disadvantages of lazy deletion.
b. Write routines to implement the standard linked list operations using lazy deletion. Get solution


3.22 Write a program to evaluate a postfix expression. Get solution


3.23 a. Write a program to convert an infix expression that includes (, ), +, -, *, and / to postfix.
b. Add the exponentiation operator to your repertoire.
c. Write a program to convert a postfix expression to infix. Get solution


3.24 Write routines to implement two stacks using only one array. Your stack routines should not declare an overflow unless every slot in the array is used.
clue: Two stacks can be implemented in an array by having one grow from the low end of the array up, and the other from the high end down.


3.25 #a. Propose a data structure that supports the stack push and pop operations and a third operation findMin, which returns the smallest element in the data structure, all in O(1) worst-case time.
#b. Prove that if we add the fourth operation deleteMin which finds and removes the smallest element, then at least one of the operations must take %(logN) time.
(This requires reading Chapter 7.) Get solution


3.26 Show how to implement three stacks in one array. Get solution


3.27 If the recursive routine in Section 2.4 used to compute Fibonacci numbers is run for N = 50, is stack space likely to run out? Why or why not? Get solution


3.28 A deque is a data structure consisting of a list of items, on which the following operations are possible:
push(x): Insert itemx on the front end of the deque.
pop(): Remove the front item from the deque and return it.
inject(x): Insert itemx on the rear end of the deque.
eject(): Remove the rear item from the deque and return it.
Write routines to support the deque that take O(1) time per operation. Get solution


3.29 Write an algorithm for printing a singly linked list in reverse, using only constant extra space. This instruction implies that you cannot use recursion, but you may assume that your algorithm is a list member function. Get solution


3.30 a. Write an array implementation of self-adjusting lists. In a self-adjusting list, all
insertions are performed at the front. A self-adjusting list adds a find operation,
and when an element is accessed by a find, it is moved to the front of the list
without changing the relative order of the other items. (Not available)
b. Write a linked list implementation of self-adjusting lists. (Not available)
#c. Suppose each element has a fixed probability, pi, of being accessed. Show that
the elements with highest access probability are expected to be close to the front.

Sol: This follows well-known statistical theorems. See Sleator and Tarjan’s paper in Chapter 11 for references.


3.31 Efficiently implement a stack class using a singly linked list, with no header or tail
nodes. Get solution


3.32 Efficiently implement a queue class using a singly linked list, with no header or tail
nodes. Get solution


3.33 Efficiently implement a queue class using a circular array. Get solution


3.34 A linked list contains a cycle if, starting from some node p, following a sufficient number of next links brings us back to node p. p does not have to be the first node in the list. Assume that you are given a linked list that contains N nodes. However, the value of N is unknown.
a. Design an O(N) algorithm to determine if the list contains a cycle. You may use O(N) extra space.
#b. Repeat part (a), but use only O(1) extra space. (Hint: Use two iterators that are initially at the start of the list, but advance at different speeds.) Get solution


3.35 One way to implement a queue is to use a circular linked list. In a circular linked list, the last node’s next link links to the first node. Assume the list does not contain a header and that we can maintain, at most, one iterator corresponding to a node in the list. For which of the following representations can all basic queue operations be performed in constant worst-case time? Justify your answers.
a. Maintain an iterator that corresponds to the first item in the list.

Sol: Does not work in constant time for insertions at the end. 

b. Maintain an iterator that corresponds to the last item in the list.
Sol: Because of the circularity, we can access the front item in constant time, so this works.



3.36 Suppose we have a reference to a node in a singly linked list that is guaranteed not to be the last node in the list. We do not have references to any other nodes (except by following links). Describe an O(1) algorithm that logically removes the value stored in such a node from the linked list, maintaining the integrity of the linked list. (Hint: Involve the next node.) Get solution


3.37 Suppose that a singly linked list is implemented with both a header and a tail node.
Describe constant-time algorithms to
a. Insert item x before position p (given by an iterator).
b. Remove the item stored at position p (given by an iterator). 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