This is only the reference solution.

1. Problem 2-4  (10 points)

	a. FALSE. f(n) = n, g(n) = n^2.

	b. FALSE. f(n) = n, g(n) = n^2.
				    1/n
	c. FALSE. f(n) = 2, g(n) = 2

	d. FALSE. f(n) = 2n, g(n) = n.

	e. FALSE. f(n) = 1/n.

	f. TRUE.
			  n
	g. FALSE. f(n) = 2

	h. TRUE.

2. Problem 20-2  (10)

	The main problem is that : the while have to loop O(E) times.
	You can think this for a graph whose edge weights are equal.
	So the worst case, it will loop O(E) times.

3. Problem 22-1  (10)

	a. 4 3 2 6 8 1
	
	b. You need to explain two points:

		1. why extracted[j]  = i

		2. Why merge K[j] and K[l]

	   This algorithm begins from 1 to n, so when entering the ith loop,
	we will process number i, we find the heap K[j] in which i lies in,
	At this time, number 1 - (i-1) has been processed, either put into
	some E or lies in the K[m+1], so when j = m+1 , it stays behind 
	the E[m], so it will not be deleted. When j < m+1, we know i will 
	be the minimum number in those heaps before E[j], so it will be 
	deleted as E[j], and it can not be deleted by E[l] (l < j),because
	it stays behind them.

	   And the other elments in the heap K[j] maybe deleted by E[j+1],
	so it will be merged with K[j+1], and if E[j+1] has been determined,
	it will also be deleted by E[l] (l > j+1), so we have to continue
	to merge them, so on.

	c. At first we have n MAKE-SET for each element from 1-n, and then
	merge them into k heaps, later we need n FIND and m-1 UNION, the
	operation extracted can be implemented in O(1), almost equals to
	FIND operation. So total togather we need :
	
		n	 MAKE-SET
		n-1	 UNION
		n+m	 FIND

	According to corollary 22.8 , the time complexity is :
			  *          *
		O((3n+m)lg n) = O(nlg n)  (m < n)

4. Problem 24-1 (15)
	
	a. From part c we know we can get a second-best minimum spanning 
	tree. So it must exist.

	b. We use DIS[V][V] to record the maxminum edge length. 

	Method1 :
		First construct adjacent list for this graph, and for each
	vertex, use DFS or BFS to get the value. This must be O(V*V).

	Method2 :
		Find MAX length edge e in T (O(n)), cut e from T , and
	we get T1, T2. So e must be the MAX length edge from any node
	in T1 to any node in T2, or from T2 to T1. And recursive for 
	T1 , T2.

		The time complexity f(n):
	
		f(n) = MAX{f(m) + f(n-m) + cn, 1= 2*S[i-1](s,v).

	d. WW[i](u,v) = W[i](u,v) + 2*S[i-1](s,u) - 2*S[i-1](s,v)
		      >= 2*(W[i-1](u,v) + S[i-1](s,u) -S[i-1](s,v))
	   because W[i-1](u,v) + S[i-1](s,u) >= S[i-1](s,v)
	   So, WW[i](u,v) >= 0

	e. Let DIS[i](s,v) represent the shortest path we get from WW[i],
	   and its path is (s v1 v2 ... vv v)

		DIS[i](s,v) = WW[i](s,v1)+WW[i](v1,v2)+ ... +WW[i](vv,v)
			   = W[i](s,v1) + W[i](v1,v2)+ ... + W[i](vv,v)+
			     2*S[i-1](s,s) - 2*S[i-1](s,v1)+
			     2*S[i-1](s,v1)- 2*S[i-1](s,v2)+
			        ...
		 	     2*S[i-1](s,vv)- 2*S[i-1](s,v)
			   = W[i](s,v1) +W[i](v1,v2) + ... +W[i](vv,v)
			     +2*S[i-1](s,s) -2*S[i-1](s,v)

		S[i-1](s,s) = 0
		Let DIS = W[i](s,v1) + .... + W[i](vv,v)

	   So, DIS = DIS[i](s,v) + 2*S[i-1](s,v)

	   Because DIS[i](s,v) is the shortest path, so DIS must also
	   be the shortest path, so
			D[i](s,v) = DIS[i](s,v) + 2D[i-1](s,v)

	  And from part c, we know that DIS[i](s,v) <= |E|

	f. So we can get D[i](s,v) from D[i-1](s,v) in O(E), because from 
	  part e, we know DIS[i](s,v) <= |E|.

	   So total together we need O(E*lgW)

7. Exercise 21.4-2

	Hint:

	We can get such relation:

	     n=	S[k] = S[k-1] + S[k-h]
		     >= 2*S[k-h]
		     >= 2*2*S[k-2h]
		     ....
		        (floor(k/h))
		     >=2 			
	     
	     So lgn >= k/h, k<= hlgn = O(lgn)

8.(10)
9.(10)	So easy!!!!!