You should be particularly sure to do problems 15 and 16, since these deal with topics that were not on any of the homework assignments.

** Answer: **
Preorder: L,K,A,J,B,C,I,H,E,D,F,G

Postorder: A,B,C,J,K,I,D,E,F,G,H,L.

Breadth-first: L,K,I,H,A,J,E,F,G,B,C,D

** Answer:** There is more than one way to do the deletes, so the final
answer is not unique, but here is one:

** Answer: **
If every internal node of T has 2 children then there is one node at the
root, 2 at depth 1, 4 at depth 2, 8 at depth 3, for a total of 15 nodes.
If every internal node of T has 1 child, then there is a total of 4 nodes.

** Answer: **
The first three levels (including the root) must be fully filled out, giving
a total of 7 nodes. The 4th level has between 1 node and 8 nodes. So the total
number of nodes in the heap is between 8 and 15.

** Answer:** False. The first node printed out in a preorder traversal
is the root, which is greater than the nodes in the left subtree. For
example, in the tree of question 2, the first node printed out is 15.

** Answer:** True. In a breadth-first traversal, the first node printed
out is the root, which is the smallest element in a min-heap.

** Answer:**
The implementation of a heap as an array follows the breadth-first order:
[2,3,5,10,8,7,22,11,13,20,24,16].

B. Show the result of executing deleteMin() and add(4) in sequence starting with the min heap below. (You may give your answer either in the form of a tree or in the form of an array.)

** Answer:**

A=[17, 2, 34, 23, 6, 11, 49, 7, 22, 33]

** Answer:**
[6,2,7,11,17,23,49,34,22,23]. The value returned is 4 (the index of 17).

[0.92, 0.15, 0.03, 0.71, 0.95, 0.43, 0.12, 0.69, 0.19, 0.52]

** Answer:**
Step 1. Go through the numbers and put each one into the corresponding bucket
in order.

Bucket 0.0-0.1: 0.03 Bucket 0.1-0.2: 0.15, 0.12, 0.19 Bucket 0.2-0.3: Bucket 0.3-0.4: Bucket 0.4-0.5: 0.43 Bucket 0.5-0.6: 0.52 Bucket 0.6-0.7: 0.69 Bucket 0.7-0.8: 0.71 Bucket 0.8-0.9: Bucket 0.9-1.0: 0.92, 0.95

Step 2: Sort the non-empty buckets. The only one that changes is

Bucket 0.1-0.2: 0.12, 0.15, 0.19

Step 3: String the buckets together.

[0.03, 0.12, 0.15, 0.19, 0.43, 0.52, 0.69, 0.71, 0.92, 0.95]

** Answer:**
N^{2} / N log(N) = N/log(N) = 1,000,000/20 = 50,000 times faster.

Assume that the values are all between 1 and M, that you have enough memory to construct an array of size M, and that you can create an array initialized to 0 in unit time. Given an algorithm to find the mode in time O(N). Note: This time bound should be valid even if M is much bigger than N

** Answer:** (Using 1-based indexing)

A = array of size M, initialized to 0; MODE = 1; // Most frequent value seen so far for (X in L) { A[X]++; if (A[X] > A[MODE]) MODE = X; } return MODE;

class Vertex { public String tag; public Edge firstOutarc; } class Edge { public Integer tag; public Vertex tail; public Vertex head; public Edge nextEdge; }Assume that the

Draw the objects with links that would be an implementation of the following directed graph:

** Answer:**

** Answer:**

--- | 1 | 4 |

--- | 2 | 3 |

--- | --- | --- |

** Answer:**

public void addEdge(Vertex v, in l) { Edge e = new Edge(); e.tag = l; e.head = v; e.tail = this; e.nextEdge = firstOutarc; firstOutarc = e; }

- If it is acyclic, give a topological sort.
- If it not acyclic, find a cycle.

** Answer:**
Graph 1: Acyclic. Topological sort: A, B, D, C.

Graph 2: Cyclic. Cycle: F,H,G,F

Graph 3: Acyclic. There are several different topological sorts.
I,J,K,L,M is one.

** Answer:**
There are four different possibilities. These are two:

B. Show the results of doing the following operations in sequence: Add 18, add 19, delete 8, delete 5, delete 11.

** Answer:**