Answer Happy

5. (20%) Consider a large organization whose employees are organized in a hierarchical organization structure. Specifically, each employee r has a unique immediate supervisor y. The only exception is a specific employee, H, who is the head of the organization. H is the prime superior of the organization and he reports to no one. We use the notation M(z,y) to denote that employee y is the immediate supervisor of r. We also say that is a staff member of y. We further define the superior relation, denoted by S(x,y), between two employees recursively as follows: (a) If M(x,y), then S(x,y). (If y is the immediate supervisor of r, then y is a superior of r.) (b) If S(1, 2) and M(z,y), then S(x,y). (If y is the immediate supervisor of an employee who is a superior of 1, then y is a superior of 1.) Note that the relations M and are not reflexive, i.e., no one is his/her own supervisor or superior. Also, if S(x,y), we say that is a subordinate of y. Each employee is given a unique numerical ID. You are given a file which contains a list of all instances of M. That is, the file is a list of D-y pairs, where u and y are the IDs of two employees such that Mx,y). Your task is to design a data structure for representing the organization hierarchy. Your data structure should be designed to support the following operations/queries efficiently. (a) build(): builds the data structure you designed using the data file as input. (b) is superior(x,y): returns "true" if employee y is a superior of employee r; returns "false" otherwise. (e) (closest common superior) cos(11, 12): returns "nullif n is a superior of 12 or vice versa; otherwise returns employee z who is (i) a common superior of 2 and 12 and (ii) the one with the lowest rank among all such common superiors in the organization hierarchy. (That is, any other common superior of 1 and ro is a superior of 2.) (d) (degrees of separation) ds(11,12): returns the number of message passings that is needed for 1 to communicate with 12, assuming that each employee only communi- cates directly with his/her immediate supervisor/subordinate. In particular, if z is the closest common superior (ocs) of 21 and 12, then it takes a +b messages for rto communicate with 12. where a is the number of levels in the organization hierarchy between 1 and 2, and b is that between 12 and . Let n be the number of employees and m be the number of levels in the organization hierarchy. Briefly describe your data structure. Also, for each of the above operations, give an algorithm outline and its time complexity in Big-0.