1. (a) F_{5+2} = 13. (b) ,---(B) / | ,--(C) | / (A)----(D)----(E) | \ | `--(F)----(G) | \ | `--(H) | | ,--(J) \ / `---(I)----(K) \ `--(L)----(M) (c) If a node has k children, and those children have degrees 0, 0, 1, 2, ..., k-3, k-2, then each of these children must have had (at the time it was made a child) degrees 0, 1, 2, ..., k-2, k-1, and all but one of these children must have had its degree reduced later (causing it to be flagged). If a node has no children, we can't tell whether it originally had no children (and is unflagged) or whether it had one child that was subsequently removed (causing it to be flagged), but every other node but the root must be flagged. Therefore, the nodes that must have their flag set to true are D, F, I, and L. (At least one of B and C, at least one of G and H, and at least one of J and K must also have its flag set to true, but we don't know which one.) 2. (a) The maximum is achieved when each item forms a one-node tree; in this case, there are 100 trees. (b) The maximum number of children is nine. A node with nine children has at least F_{11}=89 nodes in its tree, which is still less than 100. But if a node had ten children it would have at least 144 nodes in its tree, not possible when there are only 100 nodes in the whole forest. 3. (a) Yes. The new potential t+f still decreases by t units each time we decrease the number of trees by one, and the time to perform a delete-min operation is proportional to O(log n) plus the number of reductions in trees that it performs. So with the new potential function, it is still the case that when a delete-min performs more than O(log n) steps, the excess time is cancelled by a matching decrease in the potential function. (b) No. With the new potential function, promoting a flagged node to be a new tree root does not change the potential function: the number of flagged nodes decreases but the number of roots increases by the same amount. So, the total change in potential caused by a decrease-key operation is O(1), rather than being a negative number proportional to the amount of time actually spent in the operation. Thus, the time spent is not cancelled by the change in potential and the total amortized time is not constant. 4. (a) O(n log n). There are O(n) delete-min operations and O(n) decrease-key operations, each of which takes O(log n) time. (b) O(n log n). There are O(n) delete-min operations and O(n) decrease-key operations; the decrease-key operations are faster using Fibonacci heaps, but the delete-min operations still take O(log n) amortized time, so the total is still O(n log n). (The point here is that Fibonacci heaps only provide an improvement over binary heaps when the input graph is not sparse. Here it is a sparse graph so there is no improvement in the O-notation.) (c) n^2 - n. The shortest path from the start node to any other node may have at most n - 1 edges, and each edge has length at most n, so the total length of all of these edges is at most (n - 1)*n. (d) O(n log log n). With van emde Boaz trees, each operation takes time O(log log(n^2 - n)) = O(log log n). (log(n^2) = 2 log(n), and log(2 log(n)) = 1 + log log n).