a 4. (20%) Consider a large organization whose employees are organized in a hierarchical organization structure. Specifi

[answerhappygod]

A 4 20 Consider A Large Organization Whose Employees Are Organized In A Hierarchical Organization Structure Specifi 1 (142.94 KiB) Viewed 48 times

a 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. H is the prime superior of the organization and he reports to no one. We use the notation M(1,y) to denote that employee y is the immediate supervisor of 1. We also say that I is a staff member of y. We further define the superior relation, denoted by S(1,y), between two employees recursively as follows: (a) If M(I, y), then S(1,y). (If y is the immediate supervisor of 1, then y is a superior of r.) (b) If S(1, 2) and M(z,y), then S(1,y). (If y is the immediate supervisor of an employee z who is a superior of 1, then y is a superior of 1.) fr Note that the relations M and S are not reflexive, i.e., no one is his/her own supervisor or superior. Also, if S(r,y), 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 c-y pairs, where I and y are the IDs of two employees such that MI,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 (1,y): returns "true" if employee y is a superior of employee r; returns "false" otherwise. (c) (closest common superior) ccs(11,12): returns "null" if 11 is a superior of 12 or vice versa; otherwise returns employee z who is (i) a common superior of 11 and 19 and (ii) the one with the lowest rank among all such common superiors in the organization hierarchy. (That is, any other common superior of 11 and 12 is a superior of z.) (d) (degrees of separation) ds(11,12): returns the number of message passings that is needed for Iį 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 (ccs) of 11 and 12, then it takes a +b messages for Iı to communicate with 12, where a is the number of levels in the organization hierarchy between 11 and z, and b is that between 19 and z. 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. n