Big Java, Enhanced Early Objects 7th Edition Cay S Horstmann - Solutions

A deque (double-ended queue) is a data structure with operations addFirst, remove- First, addLast, removeLast, and size. Implement a deque as a circular array, so that these operations have amortized constant time.
Implement a hash table with open addressing. When removing an element that is followed by other elements with the same hash code, replace it with the last such element and rehash the remaining elements of the probing sequence.
Modify Exercise ••• P16.14 to use quadratic probing. The ith index in the probing sequence is computed as (h + i2) % L.Data from exercise 16.14Implement a hash table with open addressing. When removing an element that is followed by other elements with the same hash code, replace it with the
Modify Exercise ••• P16.14 to use double hashing. The ith index in the probing sequence is computed as (h + i h2(k)) % L, where k is the original hash key before compression and h2 is a function mapping integers to non-zero values. A common choice is h2(k) = 1 + k % q for a prime q less than
Modify Exercise ••• P16.14 so that you mark removed elements with an “inactive”element. You can’t use null—that is already used for empty elements. Instead, declare a static variable:Data from exercise P16.14 Implement a hash table with open addressing. When removing an element that
What are all possible shapes of trees of height h with one leaf? Of height 2 with k leaves?
Describe a recursive algorithm for finding the maximum number of siblings in a tree.
Describe a recursive algorithm for finding the total path length of a tree. The total path length is the sum of the lengths of all paths from the root to the leaves. (The length of a path is the number of nodes on the path.) What is the efficiency of your algorithm?
Show that a binary tree with l leaves has at least l – 1 interior nodes, and exactly l – 1 interior nodes if all of them have two children.
What is the difference between a binary tree and a binary search tree? Give examples of each.
What is the difference between a balanced tree and an unbalanced tree? Give examples of each.
The following elements are inserted into a binary search tree. Make a drawing that shows the resulting tree after each insertion.Adam Eve Romeo Juliet Tom Diana Harry
Insert the elements of Exercise • R17.7 in opposite order. Then determine how the BinarySearchTree.print method from Section 17.4.1 prints out both the tree from Exercise • R17.7 and this tree. Explain how the printouts are related.Data from exercise R17.7The following elements are
Consider the following tree. In which order are the nodes printed by the Binary-SearchTree.print method? The numbers identify the nodes. The data stored in the nodes is not shown. 1 8 6 10
Design an algorithm for finding the kth element (in sort order) of a binary search tree. How efficient is your algorithm?
Design an O(log(n)) algorithm for finding the kth element in a binary search tree, provided that each node has an instance variable containing the size of the subtree.Also describe how these instance variables can be maintained by the insertion and removal operations without affecting their big-Oh
Design an algorithm for deciding whether two binary trees have the same shape. What is the running time of your algorithm?
Insert the following eleven words into a binary search tree:Mary had a little lamb. Its fleece was white as snow.Draw the resulting tree.
What is the result of printing the tree from Exercise • R17.13 using preorder, inorder, and postorder traversal?Data from exercise R17.13Insert the following eleven words into a binary search tree:Mary had a little lamb. Its fleece was white as snow.Draw the resulting tree.
Locate nodes with no children, one child, and two children in the tree of ExerciseR17.13 . For each of them, show the tree of size 10 that is obtained after removing the node.Data from exercise R17.13Insert the following eleven words into a binary search tree:Mary had a little lamb. Its
Repeat Exercise • R17.13 for a red-black tree.Data from exercise R17.13 Insert the following eleven words into a binary search tree:Mary had a little lamb. Its fleece was white as snow.Draw the resulting tree.
Repeat Exercise •• R17.15 for a red-black tree.Data from exercise R17.15 Locate nodes with no children, one child, and two children in the tree of Exercise R17.13 . For each of them, show the tree of size 10 that is obtained after removing the node.
Show that a red-black tree with black height bh has at least 2bh –1 nodes. Look at the root. A black child has black height bh – 1. A red child must have two black children of black height bh – 1.
Let rbts(bh) be the number of red-black trees with black height bh. Give a recursive formula for rbts(bh) in terms of rbts(bh – 1). How many red-black trees have heights 1, 2, and 3? Hint: Look at the hint for Exercise •• R17.18 .Data from exercise R17.18Show that a red-black tree with
What is the maximum number of nodes in a red-black tree with black height bh?
Show that any red-black tree must have fewer interior red nodes than it has black nodes.
Show that the “black root” rule for red-black trees is not essential. That is, if one allows trees with a red root, insertion and deletion still occur in O(log(n)) time.
Many textbooks use “dummy nodes”—black nodes with two null children—instead of regular null references in red-black trees. In this representation, all non-dummy nodes of a red-black tree have two children. How does this simplify the description of the removal algorithm?
Why does Figure 21 show all possible configurations of a double-red violation?Figure 21 13 722 13 5 t 13. t 12 t
Could a priority queue be implemented efficiently as a binary search tree? Give a detailed argument for your answer.•••
Will preorder, inorder, or postorder traversal print a heap in sorted order? Why or why not?
Prove that a heap of height h contains at least 2h–1 elements but less than 2h ele ments.
Suppose the heap nodes are stored in an array, starting with index 1. Prove that the child nodes of the heap node with index i have index 2 · i and 2 · i + 1, and the parent node of the heap node with index i has index i/2.
Simulate the heapsort algorithm manually to sort the array 11 27 8 14 45 6 24 81 29 33 Show all steps.
Write a method that counts the number of all leaves in a tree.
Add a method countNodesWithOneChild to the BinaryTree class.
Add a method swapChildren that swaps all left and right children to the BinaryTree class.
Implement the animal guessing game described in Section 17.2.1. Start with the tree in Figure 4, but present the leaves as “Is it a(n) X?” If it wasn’t, ask the user what the animal was, and ask for a question that is true for that animal but false for X. For example,Figure 4 Is it a mammal?
Reimplement the addNode method of the Node class in BinarySearchTree as a static method of the BinarySearchTree class:If parent is null, return newNode. Otherwise, recursively add newNode to parent and return parent. Your implementation should replace the three null checks in the add and original
Write a method of the BinarySearchTree class:that returns the smallest element of a tree. You will also need to add a method to the Node class. Comparable smallest()
Add methods: void preorder (Visitor v) void inorder (Visitor v) void postorder (Visitor v) to the BinaryTree class of Section 17.2.3.
Using a visitor, compute the average value of the elements in a binary tree filled with Integer objects.
Add a method void depthFirst(Visitor v) to the Tree class of Section 17.4. Keep visiting until the visit method returns false.
Implement an inorder method for the BinaryTree class of Section 17.2 so that it stops visiting when the visit method returns false. ( Have inorder return false when visit returns false.)
Write a method for the RedBlackTree class of Worked Example 17.2 that checks that the tree fulfills the rules for a red-black tree.Data from worked example 17.2 The code for fixing up a double-red violation is quite long. Recall that there are four possible arrangements of the double red nodes:
Modify the implementation of the MinHeap class so that the parent and child index positions and elements are computed directly, without calling helper methods.
Time the results of heapsort and merge sort. Which algorithm behaves better in practice?
A general tree (in which each node can have arbitrarily many children) can be implemented as a binary tree in this way: For each node with n children, use a chain of n binary nodes. Each left reference points to a child and each right reference points to the next node in the chain. Using the binary
A general tree in which all non-leaf nodes have null data can be implemented as a list of lists. For example, the treeis the list [[A, B], C, [D]].Using the list implementation from Section 16.1.8, implement a tree class with the same interface as the one in Section 17.1. Use n instanceof List to
Continue Exercise •• E17.4 and write the tree to a file when the program exits. Load the file when the program starts again.Data from exercise E17.4Implement the animal guessing game described in Section 17.2.1. Start with the tree in Figure 4, but present the leaves as “Is it a(n) X?” If
Change the BinarySearchTree.print method of Section 17.3.4 to print the tree as a tree shape. You can print the tree sideways. Extra credit if you instead display the tree with the root node centered on the top.
In the BinarySearchTree class of Section 17.3.4, modify the remove method so that a node with two chil dren is replaced by the largest child of the left subtree.
Reimplement the remove method in the RedBlackTree class of Worked Example 17.2 so that the node is first removed using the binary search tree removal algorithm, and the tree is rebalanced after removal.Data from worked example 17.2.The code for fixing up a double-red violation is quite long. Recall
The ID3 algorithm describes how to build a decision tree for a given a set of sample facts. The tree asks the most important questions first. We have a set of criteria (such as “Is it a mammal?”) and an objective that we want to decide (such as “Can it swim?”). Each fact has a value for
Modify the expression evaluator from Section 13.5 to produce an expression tree. (Note that the resulting tree is a binary tree but not a binary search tree.) Then use postorder traversal to evaluate the expression, using a stack for the intermediate results.
Implement an iterator for the BinarySearchTree class that visits the nodes in sorted order. In the constructor, keep pushing left nodes on a stack until you reach null. In each call to next, deliver the top of the stack as the visited node, but first push the left nodes in its right subtree. A m D
Implement an iterator for the RedBlackTree class in Worked Example 17.2 that visits the nodes in sorted order. Take advantage of the parent links.Data from worked example 17.2.The code for fixing up a double-red violation is quite long. Recall that there are four possible arrangements of the
Modify the implementation of the MinHeap class in Section 17.6 so that the 0 element of the array is not wasted.
What is a type parameter?
What is the difference between a generic class and an ordinary class?
What is the difference between a generic class and a generic method?
Why is it necessary to provide type arguments when instantiating a generic class, but not when invoking an instantiation of a generic method?
Find an example of a non-static generic method in the standard Java library.
Find four examples of a generic class with two type parameters in the standard Java library.
Find an example of a generic class in the standard library that is not a collection class.
Why is a bound required for the type parameter T in the following method? int binarySearch (T[] a, T key)
Why is a bound not required for the type parameter E in the HashSet class?
What is an ArrayList>?
Explain the type bounds of the following method of the Collections class.Why doesn’t T extends Comparable or T extends Comparable suffice? public static
What happens when you pass an ArrayList to a method with an ArrayList parameter variable? Try it out and explain.
What happens when you pass an ArrayList to a method with an ArrayList parameter variable, and the method stores an object of type BankAccount into the array list? Try it out and explain.
What is the result of the following test?Try it out and explain. ArrayList accounts = new ArrayList (); if (accounts instanceof ArrayList ) .
The ArrayList class in the standard Java library must manage an array of objects of type E, yet it is not legal to construct a generic array of type E[] in Java. Locate the implementation of the ArrayList class in the library source code that is a part of the JDK. Explain how this problem is
Modify the generic Pair class so that both values have the same type.
Add a method swap to the Pair class of Exercise • E18.1 that swaps the first and second elements of the pair.Data from exercise Modify the generic Pair class so that both values have the same type.
Implement a static generic method PairUtil.swap whose argument is a Pair object, using the generic class declared in Section 18.2. The method should return a new pair, with the first and second element swapped.
Implement a static generic method that, given a Map, yields a List of the key/value pairs in the map.
Implement a generic version of the binary search algorithm.
Implement a generic version of the selection sort algorithm.
Implement a generic version of the merge sort algorithm. Your program should compile without warnings.
Implement a generic version of the LinkedList class of Section 16.1.
Turn the HashSet implementation of Section 16.4 into a generic class. Use an array list instead of an array to store the buckets.
Provide suitable hashCode and equals methods for the Pair class of Section 18.2 and implement a HashMap class, using a HashSet.
Implement a generic version of the permutation generator in Section 13.4. Generate all permutations of a List.
Write a generic static method print that prints the elements of any object that implements the Iterable interface. The elements should be separated by commas. Place your method into an appropriate utility class.
Turn the MinHeap class of Section 17.6 into a generic class. As with the TreeSet class of the standard library, allow a Comparator to compare elements. If no compara tor is supplied, assume that the element type implements the Comparable interface.
Make the Measurer interface from Section 10.4 into a generic interface. Provide a static method T max(T[] values, Measurer meas).
Provide a static method void append(ArrayLista, ArrayListb) that appends the elements of b to a.
Modify the method of Exercise • E18.15 so that the second array list can contain elements of a subclass. For example, if people is an ArrayList and students is an ArrayList, then append(people, students) should compile but append(students, people) should not.Data from exercise E18.15 Provide a
Modify the method of Exercise • E18.15 so that it leaves the first array list unchanged and returns a new array list containing the elements of both array lists.Data from exercise E8.15Provide a static method void append(ArrayLista, ArrayListb) that appends the elements of b to a.
Modify the method of Exercise •• E18.17 so that it receives and returns arrays, not array lists. Arrays.copyOf.Data from exercise E8.17Modify the method of Exercise • E18.15 so that it leaves the first array list unchanged and returns a new array list containing the elements of both array
Provide a static method that reverses the elements of a generic array list.
Provide a static method that returns the reverse of a generic array list, without modifying the original list.
Provide a static method that checks whether a generic array list is a palindrome; that is, whether the values at index i and n - 1 - i are equal to each other, where n is the size of the array list.
Provide a static method that checks whether the elements of a generic array list are in increasing order. The elements must be comparable.
Write a static generic method PairUtil.minmax that computes the minimum and maximum elements of an array of type T and returns a pair containing the minimum and maximum value. Require that the array elements implement the Measurable interface of Section 10.1.2.
Repeat Exercise •• P18.1 but require that the array elements implement the Comparable interface.Data from exercise P18.1 Write a static generic method PairUtil.minmax that computes the minimum and maximum elements of an array of type T and returns a pair containing the minimum and maximum
Repeat Exercise •• P18.2, but refine the bound of the type parameter to extend the generic Comparable type.Data from exercise P18.2 Repeat Exercise •• P18.1 but require that the array elements implement the Comparable interface.
Make the Measurable interface from Section 10.1.2 into a generic interface. Provide a static method that returns the largest element of an ArrayList, provided that the elements are instances of Measurable. Be sure to return a value of type T.
Enhance Exercise •• P18.4 so that the elements of the ArrayList can implement Measurable for appropriate types U.Data from exercise P18.4 Make the Measurable interface from Section 10.1.2 into a generic interface. Provide a static method that returns the largest element of an ArrayList,

Showing 100 - 200 of 791

Big Java, Enhanced Early Objects 7th Edition Cay S Horstmann - Solutions

Step by Step Answers