2013 Data Structure Homework Chapter 13, 14, 15
13.3 Show the resulting heap after each of the following alterations is made,
consecutively, to the following heap:
- add (29);
- add (30);
- remove();
- remove();
13.4 For the following character frequencies, create the heap of character-frequency pairs (highest priority = lowest frequency):
a:5,000
b: 2,000
c: 10,000
d: 8,000
e: 22,000
f: 49,000
g: 4,000
13.8 Must a Huffman tree be a two-tree? Explain.
Yes. During each loop in the creation of the Huffman tree, the front two elements are removed from the priority queue and become the right and left subtrees in a partially completed Huffman tree. So every non-leaf has two children, and the tree is a two-tree.
14.1Why does the HashMap class use singly-linked lists instead of the LinkedList class?
The singly-linked (instead of doubly-linked) lists are used to save space. Each Entry object in a (doubly) LinkedList object has a previous field. The space for that field would be wasted because that field would not be used in any HashMap (or Entry or HashIterator) method.
14.2Suppose you have a HashMap object, and you want to insert an element unless it is already there. How could you accomplish this?
Hint: The put method will insert the element even if it is already there (in which case,the new value will replace the old value).
if (!myMap.containsKey (myKey))
myMap.put (myKey, myValue);
14.7We noted in Chapter 12 that the term dictionary, viewed as an arbitrary collection of key-value pairs, is a synonym for map. If you were going to create a real dictionary, would you prefer to store the elements in a TreeMap object or in a HashMap object? Explain.
A HashMap object would be faster, on average, (we make the Uniform Hashing Assumption). But with a HashMap object, there might be, in the unlikely worst case, a linear-in-n linked list at one index. Then a TreeMap object would be much faster. In addition to the key and value fields, each entry in a HashMap object has hashand next fields, which requires slightly less space than a TreeMap object, in which each entry has key, value, parent, left and right fields.
14.8 In open-addressing, with the quotient-offset collision handler,insert the following keys into a table of size 13:
20
33
49
22
26
202
140
508
9
Here are the relevant remainders and quotients:
key key % 13 key / 13
20 7 1
33 7 2
4910 3
22 9 1
26 0 2
202 7 15
14010 10
508 1 39
9 9 0
indexkey
0 26
1508
2 202
3
4140
5
6
7 20
8
9 33
10 49
11 22
12 9
15.1a.Draw a picture of the following undirected graph:
Vertices: A, B, C, D, E
Edges: {A, B}, {C, D}, {D, A}, {B, D}, {B, E}
15.3Suppose we have the following undirected graph:
B
A C E
D
Assume the vertices were inserted into the graph in alphabetical order.
a.Perform a breadth-first traversal of the undirected graph.
b.Perform a depth-first traversal of the undirected graph.
a.Perform a breadth-first traversal of the undirected graph.
queuevertex returned by next( )
A
B, C, DA
C, DB
D, EC
ED
E
The iteration would visit A, B, C, D, E in that order.
b.Perform a depth-first traversal of the undirected graph.
stack (top vertex is shown leftmost)vertex returned by next( )
A
D, C, BA
C, BD
E, BC
BE
B
The iteration would visit A, D, C, E, B in that order.
15.6For the network given in Exercise 15.5, use Dijkstra's algorithm (getShortestPath) to find the shortest path from A to H.
Initially, we have
weightSumpredecessorpq
A, 0.0A<A, 0.0>
B, 12.0null
C, 3.0null
D, 10000.0null
E, 6.0null
F, 10000.0null
G, 10000.0null
H, 10000.0null
The pair <A, 0.0> is removed from pq. Since that pair’s weight is less than or equal to A’s weightSum value, the weightSum and predecessor of each neighbor of A are updated, and the neighbor and its total weight (so far) are added to pq.
weightSumpredecessorpq
A, 0.0A<C, 3.0>
B, 12.0A<E, 6.0>
C, 3.0A<B, 12.0>
D, 10000.0null
E, 6.0A
F, 10000.0null
G, 10000.0null
H, 10000.0null
When <C, 3.0> is removed from pq, the information on vertex F is updated, and <F, 21.0> is added to pq:
weightSumpredecessorpq
A, 0.0A<E, 6.0>
B, 12.0A<B, 12.0>
C, 3.0A<F, 21.0>
D, 10000.0null
E, 6.0A
F, 21.0C
G, 10000.0null
H, 10000.0null
When <E, 6.0> is removed from pq, the information on vertices B and G is updated, and both <B, 11.0> and <G, 28.0> are added to pq:
weightSumpredecessorpq
A, 0.0A<B, 11.0>
B, 11.0E<B, 12.0>
C, 3.0A<F, 21.0>
D, 10000.0null<G, 28.0>
E, 6.0A
F, 21.0C
G, 28.0E
H, 10000.0null
When <B, 11.0> is removed from pq, the information on vertex D is updated, and <D, 16.0> is added to pq:
weightSumpredecessorpq
A, 0.0A<B, 12.0>
B, 11.0E<D, 16.0>
C, 3.0A<F, 21.0>
D, 16.0B<G, 28.0>
E, 6.0A
F, 21.0C
G, 28.0E
H, 10000.0null
When <B, 12.0> is removed from pq, nothing is updated. When <D, 16.0> is removed from pq, the information on vertices F and H is updated, and both <F, 20.0> and <H, 35.0> are added to pq:
weightSumpredecessorpq
A, 0.0A<F, 20.0>
B, 11.0E<F, 21.0>
C, 3.0A<G, 28.0>
D, 16.0B<H, 35.0>
E, 6.0A
F, 20.0D
G, 28.0E
H, 35.0D
When <F, 20.0> is removed from pq, the information on vertex H is updated, and <H, 30.0> is added to pq:
weightSumpredecessorpq
A, 0.0A<F, 21.0>
B, 11.0E<G, 28.0>
C, 3.0A<H, 30.0>
D, 16.0B<H, 35.0>
E, 6.0A
F, 20.0D
G, 28.0E
H, 30.0F
When <F, 21.0> is removed from pq, nothing happens. When <G, 28.0> is removed from pq, nothing happens. When <H, 30.0> is removed from pq, the shortest (that is, lowest-total-weight) path from A to H is printed, starting with H and pre-pending the predecessors:
A, E, B, D, F, H