Question 1.

		    4
	    2	            7
	  1   3   	  6   8
	0       	5       9
	
Question 2.

static Node instertT(Node h, int i){
	if(h == null)
		return new Node(i,null,null);
	if(i < h.item)
		h.l = insertT(h.l,i);
	if(i > h.item)
		h.r = insertT(h.r,i);
	return h;
}

Question 3.

In linear-probing all items are inserted into the table itself.  When a collision occurs, the item is inserted in the next available spot in table.

public void remove(Item x){
	int i = hash(x.key(),M);
	while(st[i] != null){
		if(equals(x.key(),st[i].key()))
			break;
		else
			i = (i+1)%M;
	}
	if(st[i] == null)  //item not found
		return;
	st[i] = null; // delete this item
	N--; //decrement number items
	for(int j = i+1; st[j] != null; j = (j+1)%M){
		x = st[j]; st[j] = null; insert(x); N--; //remove and reinsert each following item (until we get to empty slot)
	}
}

Question 4.

static int partition(int A[], int l, int r){
	int pivot = A[r], i = l-1, j = r;
	while(true){
		while(A[++i] < pivot){}
		while(j > l && A[--j] > pivot){}
		if(i < j)
			exch(A,i,j);
		else
			break;
	}
}

Note: this code is subtle, you need to make sure you don't get stuck when A[i] = A[j] = pivot
(i and j need to keep advancing, hence you increment/decrement them before checking the
conditional, otherwise you get an infinite loop).  Also, i will not run out of bounds because 
it will stop at r because A[r] = pivot, j must be <= i at this point so loop will break. You
need an explicit check to make sure j stops at l, i must be >= j at this point so loop will break.

Question 5.

In each step we assume that elements in positions 0,1,...,p are sorted, and "insert" A[p+1] into the correct place among them.  Insertion sort is stable.

static void insert_sort(int A[], int l, int r){
	int i;
	for(i = r; i > l; i--) compExch(a, i-1, i); //Think about what this does (answer below)
	for(int p = 1; p <=r; p++){
		int tmp = A[p]; //tmp is element to insert
		for(j = p; A[j-1] > tmp; j--) //slide over elements one by one until we can insert tmp
			A[j] = A[j-1];
		A[j] = tmp; //insert tmp
	}
}

Note: in the beginning we slide smallest element into the first position, this makes sure j never runs out of bounds.

Question 6.

Call the set of edges of the minimum spanning tree T.

Prim's algorithm works as follows: initialize T to be empty, and initialize a set of vertices P "included" so far to contain the source vertex.
In each iteration find edge e = (u,v) of minimum weight such that u is in P and v is not in P, add e to T and add v to P.  Stop when the
size of P is equal to the number of vertices in the graph  (after n-1 iterations).  Return T.  

(Think about why this works: in each iteration some edge connecting a vertex in P to a vertex not in P must be in the spanning tree, and we choose
edge with smallest weight.)

In the example given, the edges will be added to T in this order:

3-7
3-9
1-9
1-4
7-8
2-9
5-2
0-5
0-6

Question 7.

Call the set of edges of the minimum spanning tree T.

Kruskal's algorithm works as follows: initialize T to be empty.  In each iteration add edge with smallest weight to T, such that the
subgraph determined by T contains no cycles.  Stop when all vertices of the graph are in a single component (in the subgraph determined
by T) (after n-1 iterations).  Return T. You can think of the algorithm this way: each vertex of the graph is initially in a separate component.  
Whenever you add an edge to T, you merge two components.  You stop when there is only one component left (containing all the vertices in the graph). 


In the example given, the edges will be added to T in this order:

3-7
1-4
3-9
1-9
7-8
0-5
5-2
2-9
0-6

Question 8.

This is exactly like BFS, except that you don't need to check whether the "neighbors" of a node have been visited.

static void traverse(Tree3 t){
	Queue Q = new Queue();
	Q.put(t);
	while(!Q.isEmpty()){
		Tree3 t = Q.get();
		println("visiting " + t.i);
		if(t.l != null) //make sure that it's not null
			Q.put(t.l);
		if(t.m != null) //make sure that it's not null
			Q.put(t.m);
		if(t.r != null) //make sure that it's not null
			Q.put(t.r);
	}
}

Question 9.

static Node joinR(Node a, Node b){
	if(b == null)
		return a;
	a = insertT(a,b.item); // insertT is defined in Question 2
	a = joinR(a,b.l);
	a = joinR(a,b.r);
	return a;
}