Second assignment--CS251--Winter 2000


Question 1 Tree algorithms. Given a preorder sequence a_1 a_2 ... a_n for a binary tree on n nodes, where each a_i is a bit pair indicating the presence of each of the two possible children, design a simple linear time (i.e., O(n)) algorithm for constructing a tree T (a root pointer), implemented by left[.], right[.].
Solution The strategy when processing a node is this: if there are two children, put the right child on "hold" in a stack S. Otherwise, do all the work you have to do.
   makenull (S)
   createnode (p)  
         (this will be the root for now)
         (p will be a traveling pointer)
   for i=1 to n do
      if a_i = (10) then createnode (q)
                         left[p] = q
			 right [p] = nil
			 p = q
      if a_i = (01) then createnode (q)
      			 left[p] = nil
                         right[p] = q
			 p = q
      if a_i = (11) then createnode (q)
                         createnode (r)
			 left[p] = q
			 right [p] = r
			 p = q
			 push (r, S)
      if a_i = (00) then left[p] = right[p] = nil
                         p = pop (S)
Question 2 Tournaments. We call a k-tournament a tournament between 2^k players, each having a preassigned value. The k-tournament is described by a complete binary tree (the k-tournament tree), in which the winner of each match moves up to occupy also the parent position. In a pointer-based implementation, we have for each cell, pointers left[.] and right[.] to left and right children, and a value [.]. Clearly, the player of maximal value occupies its original leaf position, and all its ancestors to the root. A k-tournament tree T has two attributes, size[T] (k, in this case), and root[T]. What is the height of the k-tournament tree? How many nodes are there? How many leaves are there? Give an O(1) time algorithm for merging two k-tournament trees into a (k+1)-tournament tree.
Solution The height is precisely k. The number of leaves is 2^k. The number of nodes is
	     2^k + 2^(k-1) + ... + 1 = 2^(k+1) -1.
	
To merge two k-tournament trees T1 and T2, we proceed as follows:
  mergetree(T1, T2)  (returns a tree T)
     create (T) (creates T)
     size[T] = size[T1]+1
     left[T] = T1  (or root[T1])
     right[T]= T2  (or root[T2])
     if value[T1] > value[T2]
	  then  value[T] = value[T1]
	  else  value[T] = value[T2]
     return T
Question 3 List of tournaments. Given n players, write n in binary form
b_k 2^k + b_(k-1) 2^(k-1) + ... + b_1 2^1 + b_0
and organize a tournament as follows: for each i for which b_i = 1, take the next 2^i players, and let them play an i-tournament, with results stored in an i-tournament tree. These tournament trees are all of different sizes and are placed in decreasing order of size in a linked list L, the list of tournaments data structure. Given n, what is the maximal number of trees in L? Write an algorithm for merging two lists L1 and L2 that represent n players and m players, respectively. The lists are already given. In the merge, make sure that the worst case time is O(log n + log m) (and prove it!). Note: the resulting list should follow the definition given above!
Solution The maximal number of trees is k+1, where k is the highest exponent. But clearly, 2^k ≤ n, so k ≤ log_2 n. To merge the lists we assume that each element in the list is a tree T with attributes root and size as in the previous question, and with attribute previous referring to the previous item in the list. It is easy to merge the sorted lists and form one big sorted list L in time equal to the sum of the lengths of the individual lists. The time taken thus far is O(log n + log m), by question 2. Next, we clean L up from small to large, removing duplicates. For L, we assume attributes previous[.], next[.] on the cells. The list operations push, pop, enqueue, dequeue, front, rear are also given.
 mergelist(L1, L2)  (will output a list L)

      makenull(L)
      T1 = front(L1)
      T2 = front(L2)   
          (get ready: two traveling pointers)
      while (T1 not nil) and (T2 not nil) do:
        if size[T1] < size[T2]
	     then enqueue (T1,L)
	          T1 = next[T1]
	else enqueue (T2,L)
	     T2 = next[T2]
      while (T1 not nil) do: enqueue (T1,L) 
                             T1 = next[T1]
      while (T2 not nil) do: enqueue (T2,L) 
                             T2 = next[T2]

      (at this point, L has the necessary elements)
      
      T = rear(L)   
          (T is a traveling pointer, rear to front)
      while (T not nil) do:
         if T, previous[T], and previous[previous[T]]
	 exist and have the same sizes
	   then T = previous[T]  (move a place forward)
	   else if T and previous[T] exist 
	       and have the same size
	         then  T3 = mergetree(T,previous[T])
		       replace T and previous[T] 
		            in the list by T3
		       T = T3
	   else T = previous[T]
             return L
Before the second phase each size can occur at most twice in L. By the carry (after a mergetree), there can be at most three consecutive equal integers. If such a situation occurs, we merge the two front elements of the three involved. Note that every iteration in the while loop takes time O(1). Thus, the total time is O(size of Q) = O(log n + log m).
Question 4 Priority queue: list of tournaments. The list of tournaments data structure can be used as an ADT mergeable priority queue (MPQ) which is defined by the operations INSERT, DELETEMAX, and MERGE (merge two priority queues). The last operation was implemented in the previous question. Write the algorithm for the former two operations, and show that each operation takes time not exceeding O(log n), where n is the number of players. Hint: try reducing both operations to the MERGE operation. Note: the standard heap implementation we saw in class cannot handle MERGE very well, so the list of tournaments data structure is more powerful.
Solution For insert(x,L) where L is a list of tournaments, and x is a value, we first create a one-element 0-tournament tree and place it in a list L1. Then we apply mergelist.
 insert(x,L2)   (returns a list L)
    create(T)
    value[T] = x
    left[T] = right[T] = nil
    previous[T] = nil
    L = T  
               (we now have a one-element list L)
    return mergelist(L,L2)
Deletemax (L) is harder. We first find the maximum by traversing the list and picking the maximal value among the root values. This takes time O(log_2 n) (by question 2), and the simple algorithm will be omitted. Assume that the tree with maximal root value is T. We delete it from L, remove the maximal element carefully in time bounded by the height of the tree. As the height is ≤ k ≤ log_2 n (question 2), the time of this procedure is O(log_2 n). Finally, the orphaned trees are all k-tournament trees that we can put in a new list L2. The new list L2 is then merged with the original list L. As we saw in the previous question, this takes time O(log_2 n + log_2 (n-1)).
 deletemax (L)  
     (returns updated L, reports maximal element)
   find T of maximal root value in list L
   delete T from L
   report value[T] (or: value[root[T]])
   create an orphaned tree list L2:
      makenull (L2)
      while (T not nil) and (left[T] not nil) do:
         if (value[left[T]] = value[T])
	     then enqueue (right[T], L2)
	          T = left[T]
	     else enqueue (left[T], L2)
	          T = right[T]
   return mergelist (L, L2)
 
Question 5 Analysis. Start with an empty list of tournaments, and insert a player at a time until all n players have been inserted. (This may require a slight modification of the insert operation of the previous question.) Using the strategy of attaching "time cost" to certain nodes or edges of the data structure, show that the total time is O(n). This is a difficult question, but the solution is simple and beautiful.
Solution Each time a player is inserted, we apply a mergelist operation. This involves in this case, placing one list after the other one, and running the second phase of mergelist. In that second phase, note that we can stop as soon as we detect two trees of different sizes. In each step, we perform one mergetree costing one time unit. In addition, let us give ourselves one time unit for housekeeping (concatenating the lists, and checking that the next tree size is larger). The sum of the latter costs is at most n, the number of elements. The former time costs can be handled by attaching the cost permanently to the two edges created in the mergetree. So the total cost is not more than half the number of edges created. But the number of edges created is not more than
  2 (b_k 2^k + ... + b_0 2^0) = 2n , 
where k is the size of the largest k-tournament tree (recall that this tree has 2^k leaves and ≤ 2^(k+1) elements).

Copyright © 2000 Luc Devroye. Email: luc@cs.mcgill.ca.