Please see attachment.

1
    Describe a divide-and-conquer algorithm that computes the output of WhoTargetsWhom in O(n log n) time.
    Ans
    Divide and Conquer: Divide and Conquer it’s an algorithmic paradigm used to solve the problem using following steps:
Divide: This is basically breaks the problem into sub problems of same type. The sub problems should have represented a part of the original problems.
Conquer: The step receives the smaller sub problems to be solved. It is also receiving the recursively sub problems.
Combine: It will combine the answers. When the
Smaller sub problems are solved then this stage recursively combines the solution of the original problems.
Algorithm:
WHOTARGETSWHOM (Ht [1...n]):
for j <- 1 to n
L[j] <- None
for I <- 1 to j-1
if Ht [i] > Ht [j]
L[j] <- i
R[j] <- None
for k <- n down to j+1
if Ht[k] > Ht[j]
R[j] <- k
return...