void towers(int n, peg from, peg to, peg aux) {
   if (n == 1)
      move(from, to);
   else {
      towers(n-1, from, aux, to);
      move(from, to);
      towers(n-1, aux, to, from);
   }
}


// knight's tour
void try(int i, index x, index y, bool *q) {
   int k = 0, u, v;

   do {
      k = k+1;       *q = false;
      u = x + a[k];  v = y + b[k];

      if ((u in x) && (v in s))
      if (h[u][v] == 0) {
         h[u][v] := i;

         if (i < nsq) {
            try(i+1, u, v, q);

            if (!*q)
               h[u][v] = 0;
         } else
            *q = true;
      }
   } while (!*q || (k != 8));
}


// 8 queens
void try(int icq, bool *q) {
   int j = 0;

   do {
      j = j+1;
      *q = false;

      if ( row[i] && tiltleft[icq +j] && tiltright[icq +7 -j] ) {
         set queen;

         if (solution not complete) {
            try (icq +1, q);
            if (!*q) cancel recording;
         } else {
            *q = true;
         }
      }
   } while (*q == false && candidate exists);
}


bool knapsack(int target, int candidate) {
   if (target == 0)
      return true;
   else if ((target < 0) || (candidate > n))
      return false;
   else // consider solutions with and without candidate
      if (knapsack(target - weights[candidate], candidate +1)) {
         cout << weights[candidate];
         return true;
      } else // only possible solution is without candidate
         return knapsack(target, candidate + 1);
}


// turnpike
bool place( vector<int> & x, DistSet d, int n, int left, int right ) {
   int dmax;
   bool found = false;

   if ( d.isEmpty() )
      return true;

   dmax = d.findMax();

   // Check if setting x[right] = dmax is feasible
   if ( | x[j] - dmax | in d for all 1 <= j < left and right < j <= n ) {
      x[right] = dmax;  // try x[right] = dmax
      for( 1<=j<left, right < j <=n )
         d.remove(| x[j] - dmax |);
      found = place (x, d, n, left, right-1);

      if (!found)       // backtrack
         for ( 1<=j<left, right<j<=n ) // undo the deletion
            d.insert( | x[j] - dmax | );
   }

   // if first attempt failed, try to see if setting
   // x[left] = x[n] - dmax is feasible
   if ( !found && ( | x[n] - dmax - x[j] | in d for all 1 <= j < left and right < j <= n ) {
      x[left] = x[n] - dmax;  // same logic as before
      for( 1<=j<left, right < j <=n )
         d.remove(| x[n] - dmax - x[j] |);
      found = place (x, d, n, left+1, right);

      if (!found)       // backtrack
         for ( 1<=j<left, right<j<=n ) // undo the deletion
            d.insert( | x[n] - dmax - x[j] | );
   }

   return found;
}

list copy (list L) {

	if(L == NULL) return L;
	else return cons(K -> key, copy(cdr(L)));
}

list append(list L, list M) {

	if(null(L))
		return M;
	else
		return cons(car(L), append(cdr(L),M));
}

bool member(int a, list x) {

	if(x == NULL)
		return false;
	else if ((x -> key) == a)
		return true;
	else return member(a, x -> next);

}


tree balance(n) {
   if ( n == 1 )
      return maketree(0, 0);
   else {
      nl = n/2;
      nr = n - nl - 1;

      tree left = balance(nl);
      tree right = balance(nr);

      return maketree(left, right);
   }
}

1) take one node as root
2) generate the left subtree from nl = n / 2 nodes
3) generate the right subtree from nr = n - nl - 1 nodes

void huffman(int lasttree) {
   int i, j, nr;

   while (lasttree > 1) {
      lightones(&i, &j);
      nr = create(i,j);
      FOREST[i].weight = FOREST[i].weight + FOREST[j].weight;
      FOREST.root = nr;
      FOREST[j] = lasttree;
      lasttree = lasttree - 1;
   }
}



int modhash(char key[], int ts) {
   int s = 0;

   while (key[i]) {
      s *= 27;
      s += key[i];
   }

   return ((ts+x) % ts);
}


void upheap(int a[], int k) {
   while ( (k > 1) && !(a[k/2] < a[k]) ) {
      swap(a[k], a[k/2]);
      k = k/2;
   }
}


void downheap(int a[], int k, int n) {
   while ( 2*k <= n ) {
      int j = 2*k;

      if ( (j < n) && (a[j] < a[j+1]) ) {
         j++;
      }

      if ( a[k] < a[j] ) {
         break;
      }

      swap(a[k], a[j]);
      k=j;
   }
}


void heapsort(int a[], int l, int r) {
   for (int i = (r-l+1)/2; i>=0; i--)
      downheap(a, i, r-l+1);

   for (int j = r-l; j>0; j--) {
      swap (a[0], a[j]);
      downheap(a, 0, j);
   }
}

ocholicious

void dijkstra(Table T) {
   vertex v, w;

   while (true) {
      v = smallest unknown distance vertex;
      if (v == NOT_A_VERTEX)
         break;

      T[v].known = true;

      for (each w adjacent to v)
         if (!T[w].known)
            if (T[v].dist + cvw < T[w].dist) {
               // update w
               decrease( T[w].dist to T[v].dist + cvw );
               T[w].path = v;
            }
   }
}


void graph::topsort() {
   vertex v, w;

   for (int counter = 0; counter < NUM_VERTICES; counter++) {
      v = findNewVertexOfDegreeZero();

      if (v== NOT_A_VERTEX)
         throw CycleFound();

      v.topNum = counter;

      for (each w adjacent to v)
         w.indegree--;
   }
}


void insertionSort(int a[], int sa) {
   int j;

   for (int p = 1; p < sa; p++) {
      int tmp = a[p];

      for (j = p; j> 0 && tmp < a[j-1]; j--)
         a[j] = a[j-1];

      a[j] = tmp;
   }
}

void preorder_g(GTREE t, int ind) {
	GTREE temp;
	
	temp = t[ind];
	while(temp != NULL) {
		printf("%c %d\n", temp -> d, temp -> child_no);
		preorder_g(t, temp -> child_no);
		temp = temp -> sib;
	}
}

study merge sort: merge calls itselt twice merge running time cost is O(N)
    (page 167)	  let T(N) be the unknown running time with input size N

T(1) = 1			T(N) = NLOGN + N = O(NLOGN)
T(N) = 2T(N/2) + N		T(N) = 2T(N/2) + N
				2T(N/2) = 2(2T(N/4) + N/2) = 4T(N/4) + N
T(N)/N = (T(N/2)/(N/2)) + 1     T(N) = 4T(N/4) + 2N
T(N)/N = (T(N/2)/(N/2)) + 1	4T(N/4) = 4(2T(N/8) + N/4) = 8T(N/8) + N
T(N)/N = (T(N/2)/(N/2)) + 1	T(N) = 8T(N/8) + 3N
	.			
	.			T(N) = (2^K) * T(N/(2^K)) + KN
T(2)/2 = T(1)/1 + 1		T(N) = N*T(1) + NLOGN = NLOGN + N
T(N)/N = T(1)/1 + logN