What is the running time of your method

Assignment Help Computer Engineering

Reference no: EM132144418

Question :

Suppose you work for a company, iPuritan.com, that has strict rules for when two employees, x and y, may date one another, requiring approval from their lowest-level common supervisor.

The employees at iPuritan.com are organized in a tree, T, such that each node in T corresponds to an employee and each employee, z, is considered a supervisor for all of the employees in the subtree of T rooted at z (including z itself).

The lowest-level common supervisor for x and y is the employee lowest in the organizational chart, T, that is a supervisor for both x and y.

Thus, to find a lowest-level common supervisor for the two employees, x and y, you need to find the lowest common ancestor (LCA) between the two nodes for x and y, which is the lowest node in T that has both x and y as descendants (where we allow a node to be a descendant of itself).

Given the nodes corresponding to the two employees x and y, describe an efficient algorithm for finding the supervisor who may approve whether or not x and y may date each other, that is, the LCA of x and y in T.

What is the running time of your method?

Reference no: EM132144418

Questions Cloud

What is the minimum clock period for which your processor : What is the minimum clock period for which your processor functions properly?

Undergraduates in a random sample : According to national data, about 14% of American college students earn a graduate degree

What type of probability distribution : (a) What type of probability distribution is appropriate for these data?

What percentage of the original computation can be sequence : Suppose you want to achieve a speedup of 90 times faster with 100 processors. What percentage of the original computation can be sequential?

What is the running time of your method : The employees at iPuritan.com are organized in a tree, T, such that each node in T corresponds to an employee and each employee, z.

How many datagrams would be required to send : Supposed datagrams are limited to 1600 bytes (including header, with header size = 40) between host A and destination host B.

Show the data-path for the small computer : If the CPU architecture supports 8-registers (R0, R1, ..., R8) and a maximum of 32-instructions.

What is the keyspace of the one-time pad for a ciphertext : Encode to this message and the key as bits. Encrypt with the one-time pad using XOR. What is the resulting ciphertext?

What would you need to do to run it just tonight as root : Suppose you wanted to delete the trash of all users just tonight at 11pm using the just created /root/deleteTrash.bash script.

User Account

All Pages