PROBLEM 2 Skyline A great skyline must have variations. Define the left skyline function, denoted ne(s), of a skyline s as the total number of times that a building is taller than one of its left neighbors. The right skyline function nr(-), is defined analogously. The skyline s below has 4 buildings, and n2(s) 3 and nr(s) 3 because building 2 is taller than building 1 and building 4 is taller than buildings 3 and 1, and alternatively, building 1 is taller than 3, and building 2 is taller than 3 and 4 As another example, this skyline has ng - 19, the contribution of each building is listed below the building LeftNifty (A!!....) We will design and analyze a divide and conquer algorithm that computes the right and left skyline functions of a skyline s with n buildings. The input A[1,...,n] consists of the heights of each building along a street in left to right order; assume all buildings have unique heights (a) The left skyline function is the sum of 3 terms: the score of the left half, the score of the right half, and the number of pairs of buildings, one on the left half and one on the right half such that the right one is taller than the left one. In divide and conquer algorithms, we can recursively compute the first two terms so we just need to focus on the third term. Describe how you can compute the third irsm in ()(nr) time. Solution: (b) We need to compute the third term faster. First we sort the buildings on each half in increasing heights. Then we merge the two sorted lists into one as in mergesort. If a building B is ranked u in the sorted list of buildings in the right half and ranked v in the sorted list of all buildings, how many buildings are there in the left half that are shorter than B? Solution: PROBLEM 2 Skyline A great skyline must have variations. Define the left skyline function, denoted ne(s), of a skyline s as the total number of times that a building is taller than one of its left neighbors. The right skyline function nr(-), is defined analogously. The skyline s below has 4 buildings, and n2(s) 3 and nr(s) 3 because building 2 is taller than building 1 and building 4 is taller than buildings 3 and 1, and alternatively, building 1 is taller than 3, and building 2 is taller than 3 and 4 As another example, this skyline has ng - 19, the contribution of each building is listed below the building LeftNifty (A!!....) We will design and analyze a divide and conquer algorithm that computes the right and left skyline functions of a skyline s with n buildings. The input A[1,...,n] consists of the heights of each building along a street in left to right order; assume all buildings have unique heights (a) The left skyline function is the sum of 3 terms: the score of the left half, the score of the right half, and the number of pairs of buildings, one on the left half and one on the right half such that the right one is taller than the left one. In divide and conquer algorithms, we can recursively compute the first two terms so we just need to focus on the third term. Describe how you can compute the third irsm in ()(nr) time. Solution: (b) We need to compute the third term faster. First we sort the buildings on each half in increasing heights. Then we merge the two sorted lists into one as in mergesort. If a building B is ranked u in the sorted list of buildings in the right half and ranked v in the sorted list of all buildings, how many buildings are there in the left half that are shorter than B? Solution