Answer Happy

4. (20%) Consider a large organization whose employees are organized in a hierarchical organization structure. Specifically, each employee r has a unuque 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 Mix,y) to denote that employee y is the immediate supervisor of r. We also say that r is a staff member of y. We further define the superior relation, denoted by S(ry), between two employees recursively as follows: (a) If M(x,y), then S(z,y). (If y is the immediate supervisor of r, then y is a superior of 2) (b) If S(r, 2) and M. y), then S(r. y). (If y is the immediate supervisor of an employee £ who is a superior of r, then y is a superior of r.) Note that the relations M and S are not reflexive, i.e., no one is his/her own supervisor or superior. Also, if Siny), we say that I 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 r-y pairs, where x and y are the IDs of two employees such that M (3.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 x; returns "false" otherwise, (c) (closest common superior) ocs(11, 12): returns "null" ifa is a superior of x2 or vice versa; otherwise returns employee = who is 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 n and 22 is a superior of z.) (d) (degrees of separation) ds(0.2): returns the number of message passings that is needed for x 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 (cs) of , and . then it takes a+b messages for 1 to communicate with re, where a is the mumber of levels in the organization hierarchy between r and e, and b is that between 2 and E. Let n be the mumber of employees and w be the number of levels in the organization hierarchy. Briefly describe your data strucuure. Also, for each of the above operations, give an algorithm outline and its time complexity in Big-O.