EECS2011-Assignment 3 Solved

Problem 1:  [15%]   ( [GTG] Exercise R-8.11, page 350 )
Draw an arithmetic expression tree that has four external nodes, storing the numbers 1, 5, 6, and 7 (with each number stored in a distinct external node, but not necessarily in this order), and has three internal nodes, each storing an operator from the set { +, –, *, / }, so that the value of the root is 21.   Any of these operators may be used more than once, and they are real  (not integer) operators, i.e., they may operate on and return fractions.
Problem 2:  [35%]   ( [GTG] Exercise C-8.57, page 355 )
Let 𝑇 be a given binary tree with 𝑛 nodes. The distance between two nodes 𝑝 and 𝑞 in 𝑇 is the number of edges along the unique simple path between 𝑝 and 𝑞, i.e., 𝑑𝑝+ 𝑑𝑞 – 2𝑑𝑎, where 𝑎 is the lowest common ancestor (LCA) of 𝑝 and 𝑞, and 𝑑𝑥 denotes the depth of node 𝑥 in 𝑇.    The diameter of 𝑇 is the maximum distance between two nodes in 𝑇 (i.e., the distance between the farthest pair of nodes in 𝑇).    Give an efficient algorithm for computing the diameter of 𝑇 and analyze its running time.     

 

[Note: Each node of T stores an element and a pair of references to its left and right children. Other than that, nodes of T do not have any additional space to store extra information, not even their depths. Also, you should not attempt to create a clone of T with extra spaces in the clone nodes.     Hint:  use a post-order traversal of T with strengthened post-condition. As an example, see how we use a composite Result type as the return type in the EulerTour algorithm , LS8, pp: 20-21.] 
1

Problem 3:  [20%]   ( [GTG] Exercise C-9.38, page 398 )
Tamarindo Airlines wants to give a first-class upgrade coupon to the top log 𝑛 of their  frequent flyers,  based on the number of miles accumulated, where 𝑛 is the number of the airlines’ frequent flyers. The algorithm they currently use, which runs in 𝑂(𝑛 log 𝑛) time, sorts the flyers by the number of miles flown and then scans the sorted list to pick the top log 𝑛 flyers.      

They have hired you as  their chief software engineer.

Give an algorithm that identifies the top log 𝑛 flyers in  𝑂(𝑛) time. 
Problem 4:  [30%]  Dynamic Median Finder (DMF): 

We want to design a DMF ADT that maintains a collection of comparable elements and supports  the following operations on the collection:   

•            insert(e):          inserts a given element 𝑒 in 𝑂(log 𝑛) time,

•            getMed():        returns the median  in 𝑂(1) time,  

•            removeMed():             removes and returns the median  in 𝑂(log 𝑛) time,     where 𝑛 denotes the current number of elements in the collection.

Give an implementation of the DMF ADT using two heaps as the only instance variables.

 

 [The median of a collection of 𝑛 elements is the 𝑛/2 𝑡ℎ smallest element (ties broken arbitrarily).    For instance,  the median of  4, 9, 1  is 4, the median of  9, 3, 3  is  3, the median of  9, 9, 1, 2   is  2, and the median of   17, -4, 13, -7, 13, 15, 5, 2  is  5.]   
What files to submit: 

 

•     a3sol.pdf :  Describe solutions to the problems with detailed explanations and illustrations     of your algorithmic  design ideas,  all your pseudo-codes, convincing proofs      of correctness and time complexity analysis.