Page 491, Exercise 3

a. Code for Knuth Min 
 /* find the KnuthMin */

	 min = INT_MAX;

	 for (k = root[i][j-1]; k <= root[i+1][j]; k++)

	   if (cost[i][k-1] + cost[k][j] < min) {

		min = cost[i][k-1] + cost[k][j];

		minpos = k;

	    }

	 k = minpos;

	 cost[i][j] = weight[i][j] + cost[i][k-1] + cost[k][j];

	 root[i][j] = k;

b. The Obst function will take O(n2) because of the structure of the nested for loops.  This loop is commonly found in many types of programs.  In Chapter 1, we showed that this loop requires (N·(N-1))/2 iterations.  This obviously translates into O(n2).