Answer Happy

4. (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. is the prime superior of the organization and he reports to no one. We use the notation Nir,y) to denote that employee y is the immediate supervisor of. We also say that is a staff member of y. We further define the superior relation, denoted by Stry), between two employees recursively as follows: (a) If M(x,y), then S(an, y). (If y is the immediate supervisor of r then y is a superior of a.) (b) If S(, 2) and Me,y), then S(r, y). (If y is the immediate supervisor of an employee who is a superior of e, then y is a superior of x.) Note that the relations M and s are not reflexive, i.e. no one is his her own supervisor or superior. Also, if say), we say that a is a subordinale 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 2-y pairs, where and y are the IDs of two employees such that M, 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 (a, y): returns "true" if employee y is a superior of employee z; returns "false" otherwise, (c) (closest common superior) cos(2): returns null" ifri is a superior of xg or vice versa; otherwise returns employee z who is (i) a common superior of rı and 22 and (ii) the one with the lowest rank among all such common superiors in the organization hierarchy. (That is, any other common superior of and x2 is a superior of z.) (d) (degrees of separation) ds (0, 2): returns the number of message passings that is needed for 2 to communicate with 2 assuming that each employee only communi- cates directly with his/her immediate supervisor subordinate. In particular, if s is the closest common superior (ees) of and 22, then it takes a +b messages for 21 to communicate with r2, where a is the nuz ber of levels in the organization hierarchy between 1 and z, and b is that between r2 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-O.