Data Structures and Algorithm Analysis in Java 3rd Edition solutions

Data Structures and Algorithm Analysis in Java 3
Prove that for any constant, k, logk N = o(N).

Data Structures and Algorithm Analysis in Java 3
Find the maximum flow in the network of Figure 9.81.

Data Structures and Algorithm Analysis in Java 3
Redo the binary search tree class to implement lazy deletion. Note carefully that this affects all of the routines. Especially challenging are findMin and findMax, which must now be done recursively.

Data Structures and Algorithm Analysis in Java 3
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

Data Structures and Algorithm Analysis in Java 3
Merge the two binomial queues in Figure 6.59.

Data Structures and Algorithm Analysis in Java 3
Write a program to solve the selection problem. Let K=N/2. Draw a table showing the running time of your program for various values of N.

Data Structures and Algorithm Analysis in Java 3
Show that X62 can be computed with only eight multiplications.

Data Structures and Algorithm Analysis in Java 3
Give the prefix, infix, and postfix expressions corresponding to the tree in Figure 4.71.

Data Structures and Algorithm Analysis in Java 3
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

Data Structures and Algorithm Analysis in Java 3
Give a linear-time algorithm to sort N fractions, each of whose numerators and denominators are integers between 1 and N.

Data Structures and Algorithm Analysis in Java 3
How much time is required to compute f(x) = N i=0 aixi : a. Using a simple routine to perform exponentiation? b. Using the routine in Section 2.4.4?

Data Structures and Algorithm Analysis in Java 3
Consider the following algorithm (known as Horners rule) to evaluate f(x) = N i=0 aixi : poly = 0; for( i = n; i >= 0; i-- ) poly = x * poly + a[i]; a. Show how the steps are performed by this algorithm for x = 3, f(x) = 4x4 + 8x3 + x + 2. b. Explain why this algorithm works. c. What is the running t

Data Structures and Algorithm Analysis in Java 3
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

Data Structures and Algorithm Analysis in Java 3
Suppose that binary heaps are represented using explicit links. Give a simple algorithm to find the tree node that is at implicit position i.

Data Structures and Algorithm Analysis in Java 3
a. Find the shortest path from A to all other vertices for the graph in Figure 9.82. b. Find the shortest unweighted path from B to all other vertices for the graph in Figure 9.82.

Data Structures and Algorithm Analysis in Java 3
Show the result of rehashing the hash tables in Exercise 5.1.

Data Structures and Algorithm Analysis in Java 3
8 A min-max heap is a data structure that supports both deleteMin and deleteMax in O(logN) per operation. The structure is identical to a binary heap, but the heaporder property is that for any node, X, at even depth, the element stored at X is smaller than the parent but larger than the grandparent

Data Structures and Algorithm Analysis in Java 3
The input is a list of league game scores (and there are no ties). If all teams have at least one win and a loss, we can generally prove, by a silly transitivity argument, that any team is better than any other. For instance, in the six-team league where everyone plays three games, suppose we have th

Data Structures and Algorithm Analysis in Java 3
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.

Data Structures and Algorithm Analysis in Java 3
Write a program to solve the word puzzle problem