CS570 Fall 2019: Analysis of Algorithms Exam IPointsPointsProblem 120Problem 520Problem 215Problem 610Problem 315Problem 710Problem 410Total100Instructions:1. This is a 2-hr exam. Closed book and notes2. If a description to an algorithm or a proof is required please limit your description or proof towithin 150 words, preferably not exceeding the space allotted for that question.3. No space other than the pages in the exam booklet will be scanned for grading.4. If you require an additional page for a question, you can use the extra page provided within thisbooklet. However please indicate clearly that you are continuing the solution on the additionalpage.5. Do not detach any sheets from the booklet. Detached sheets will not be scanned.6. If using a pencil to write the answers, make sure you apply enough pressure so your answers arereadable in the scanned copy of your exam.7. Do not write your answers in cursive scripts.1) 20 ptsMark the following statements as TRUE or FALSE. No need to provide any justification.[ TRUE/FALSE ]If path P is the shortest path from u to v and w is a node on the path, then the part of path P from uto w is also the shortest path between u to w.[ TRUE/FALSE ]Consider an alternate version of the interval scheduling problem where there is a positive rewardfor each job/interval. The following greedy algorithm always gets the maximum possible reward:Sort the jobs by reward and schedule them one by one starting with the highest reward, rejectingany that overlap with jobs already scheduled.[ TRUE/FALSE ]Dijkstra’s algorithm may not terminate if the graph contains negative-weight edges.[ TRUE/FALSE ]If a data structure supports an operation ‘X’ such that a sequence of n ‘X’ operations takestime to perform in the worst case, then the amortized time of the ‘X’ operation is, while the actual time of a single ‘X’ operation could be as high as .[ TRUE/FALSE ]In an unweighted graph where the shortest distance between any two vertices is at most T, any BFStree has depth at most T, but a DFS tree might have a larger depth.[ TRUE/FALSE ]Starting with a node u in a graph G, run DFS and BFS to obtain search trees T and T’ respectively.The number of children of u in T cannot be greater than the number of children of u in T’.[ TRUE/FALSE ]In class, we proved that a binary heap can be constructed in linear time by showing that theamortized cost of the insert operation in a binary heap is O(1).[ TRUE/FALSE ]Let T and T’ be distinct Minimum Spanning Trees of a graph G. Then T and T’ must have at leastone common edge[ TRUE/FALSE ]Let G be a connected bipartite graph with n nodes and m edges. Then, m log m = O(n2log n)[ TRUE/FALSE ]We know that algorithm A has a worst case running time of and algorithm B has aworst case running time of . It is possible for algorithm B to run faster than algorithm Awhen n → ∞2) 15 ptsWhich of the following equalities are true and why?a.b.c.d.e.3) 15 ptsGiven a n×n matrix where each of the rows and columns are sorted in ascending order, findthe k-th smallest element in the matrix using a min-heap data structure. You may assumethat k < n. Your algorithm must run in time O(n + k log n).4) 10 ptsProve or disprove the following statement:For a given stable matching problem, if miand wjappear as a pair when menpropose and they also appear as a pair when women propose, then miand wjmust be paired in all possible stable matchings.general stable matching vs gale shapley5) 20 ptsTom is looking to buy a new smartphone, and is looking at the upcomingphone releases. Each phone i releases to the public at some time tiand is givensoftware support for some number of years si. Tom wants to buy as fewphones as possible over the rest of his (unfortunately finite) lifetime. Assuming that weknow the date of Tom’s demise and all the phone release data until that time,a) design an efficient algorithm to minimize the number of phones Tom needs to buy forthe rest of his life while ensuring that he never goes without an unsupported phone. (10pts)b) Prove the correctness of your solution. (10 pts)6) 10 ptsConsider the divide and conquer solution described in class to find the closest pair of pointsin a 2D plane. Assume that we did not have a driver routine to sort the points. So ourrecursive function did not receive the points in sorted orders of their X and Y coordinatesand the sorting had to be done for each subproblem (at every level). What would be theworst-case complexity of this algorithm assuming that the rest of the algorithm remains thesame?7) 10 ptsa) Sam is trying to compute the complexity of merge-sort. In writing the recurrencerelation, he erroneously considers the complexity of the merging step to be O(n2) instead ofO(n). Assuming no other mistakes, what is the complexity of merge-sort he ends up with?(5 points)b) Show that the number of nodes in the highest-order binomial tree in a binomial heapwith n elements is (n). (5 points)Additional SpaceAdditional