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[.].
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, a pointer p[.] to a player, and pointers left[.] and right[.] to left and right children. 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.
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!
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.
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.

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