Data Structures and Algorithm Analysis in Java 3rd edition Mark A. Weiss - Solutions

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?
A deque 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
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.
Implement the contains routine for MyLinkedList.
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
Efficiently implement a stack class using a singly linked list, with no header or tail nodes.
Efficiently implement a queue class using a singly linked list, with no header or tail nodes.
Efficiently implement a queue class using a circular array.
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)
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
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,
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).
Given two sorted lists, L1 and L2, write a procedure to compute L1 ∩ L2 using only the basic list operations.
Given two sorted lists, L1 and L2, write a procedure to compute L1 ∪ L2 using only the basic list operations.
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
What is the running time of the following code?
The following routine removes the first half of the list passed as a parameter:
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
For the tree in Figure 4.70: a. Which node is the root? b. Which nodes are leaves?
Write a program that lists all files in a directory and their sizes. Mimic the routine in the online code.
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.
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
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
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?
Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree.
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.
Keys 1, 2, . . . , 2k − 1 are inserted in order into an initially empty AVL tree. Prove that the resulting tree is perfectly balanced.
Write the remaining procedures to implement AVL single and double rotations.
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.
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?
Write the methods to perform the double rotation without the inefficiency of doing two single rotations.
Show the result of accessing the keys 3, 9, 1, 5 in order in the splay tree in Figure 4.72.
Show the result of deleting the element with key 6 in the resulting splay tree for the previous exercise.
a. Show that if all nodes in a splay tree are accessed in sequential order, the resulting tree consists of a chain of left children. 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.
What is the depth of the tree in Figure 4.70?
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?
Design a recursive linear-time algorithm that tests whether a binary tree satisfies the search tree order property at every node.
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.
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?
Write a method to generate the AVL tree of height h with fewest nodes. What is the running time of your method?
Write a method to generate a perfectly balanced binary search tree of height h with keys 1 through 2h+1 − 1. What is the running time of your method?
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
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
Show that in a binary tree of N nodes, there are N + 1 null links representing children.
Show how the tree in Figure 4.73 is represented using a child/sibling link implementation.
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?
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
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
Show that the maximum number of nodes in a binary tree of height h is 2h+1 − 1.
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
Let f (N) be the average number of full nodes in a binary search tree.a. Determine the values of f(0) and f (1).b. Show that for N > 1Figure 4.75 Sample input for Exercise 4.53Euler's constant: .........4, 5Series: .....................2-5arithmetic: ................4-5geometric:
A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.
Suppose a binary tree has leaves l1, l2, . . . , lM at depths d1, d2, . . . , dM, respectively. Prove that ΣMi=1 2−di ≤ 1 and determine when the equality is true.
Give the prefix, infix, and postfix expressions corresponding to the tree in Figure 4.71.
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.
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).
What are the advantages and disadvantages of the various collision resolution strategies?
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
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
Describe a procedure that avoids initializing a hash table (at the expense of memory).
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.
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
Show the result of rehashing the hash tables in Exercise 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
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).
Prove Markov's Inequality: If X is any random variable and a > 0, then Pr( |X| ≥ a) ≤ E( |X| )/a. Show how this inequality can be applied to Theorems 5.2 and 5.3.
If a hopscotch table with parameter MAX_DIST has load factor 0.5, what is the approximate probability that an insertion requires a rehash?
Implement a hopscotch hash table and compare its performance with linear probing, separate chaining, and cuckoo hashing.
Implement the classic cuckoo hash table in which two separate tables are maintained. The simplest way to do this is to use a single array and modify the hash function to access either the top half or the bottom half.
Extend the classic cuckoo hash table to use d hash functions.
Show the result of inserting the keys 10111101, 00000010, 10011011, 10111110, 01111111, 01010001, 10010110, 00001011, 11001111, 10011110, 11011011, 00101011, 01100001, 11110000, 01101111 into an initially empty extendible hashing data structure with M = 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
Reimplement separate chaining hash tables using singly linked lists instead of using java.util.LinkedList.
The isEmpty routine for quadratic probing has not been written. Can you implement it by returning the expression currentSize==0?
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
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?
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?
Can both insert and findMin be implemented in constant time?
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 arbitrary item
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. Compare the running time of both algorithms for sorted, reverse-ordered, and random inputs.
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)
If a d-heap is stored as an array, for an entry located in position i, where are the parents and children?
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
Suppose that binary heaps are represented using explicit links. Give a simple algorithm to find the tree node that is at implicit position i.
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
Merge the two leftist heaps in Figure 6.58.
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.
Show the result of inserting keys 1 to 15 in order into an initially empty leftist heap.
Prove or disprove: A perfectly balanced tree forms if keys 1 to 2k − 1 are inserted in order into an initially empty leftist heap.
Give an example of input that generates the best leftist heap.
Can leftist heaps efficiently support decreaseKey?
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
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
Merge the two skew heaps in Figure 6.58.
Show the result of inserting keys 1 to 15 in order into a skew heap.
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.
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?
Show the result of performing three deleteMin operations in the heap of the previous exercise.
Prove that a binomial tree Bk has binomial trees B0, B1, . . . , Bk−1 as children of the root.
Prove that a binomial tree of height k has (kd) nodes at depth d.
Merge the two binomial queues in Figure 6.59.

Showing 300 - 400 of 575

Data Structures and Algorithm Analysis in Java 3rd edition Mark A. Weiss - Solutions

Step by Step Answers