CS570 Fall 2019 Analysis of Algorithms Exam I Problem 1 Problem 2 Problem 3 Problem 4 Points 20 15 15 10 Total Points 20 10 10 Problem 5 Problem 6 Problem 7 100 Instructions 1 This is a 2 hr exam Closed book and notes 2 If a description to an algorithm or a proof is required please limit your description or proof to within 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 this booklet However please indicate clearly that you are continuing the solution on the additional page 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 are readable in the scanned copy of your exam 7 Do not write your answers in cursive scripts 1 20 pts Mark 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 u to 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 reward for 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 rejecting any 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 takes time 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 BFS tree 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 the amortized 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 least one common edge TRUE FALSE Let G be a connected bipartite graph with n nodes and m edges Then m log m O n2 log n TRUE FALSE worst case running time of when n We know that algorithm A has a worst case running time of and algorithm B has a It is possible for algorithm B to run faster than algorithm A 2 15 pts Which of the following equalities are true and why a b c d e 3 15 pts Given a n n matrix where each of the rows and columns are sorted in ascending order find the k th smallest element in the matrix using a min heap data structure You may assume that k n Your algorithm must run in time O n k log n 4 10 pts Prove or disprove the following statement For a given stable matching problem if mi and wj appear as a pair when men propose and they also appear as a pair when women propose then mi and wj must be paired in all possible stable matchings 5 20 pts Tom is looking to buy a new smartphone and is looking at the upcoming phone releases Each phone i releases to the public at some time ti and is given software support for some number of years si Tom wants to buy as few phones as possible over the rest of his unfortunately finite lifetime Assuming that we know 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 for the rest of his life while ensuring that he never goes without an unsupported phone 10 pts b Prove the correctness of your solution 10 pts 6 10 pts Consider the divide and conquer solution described in class to find the closest pair of points in a 2D plane Assume that we did not have a driver routine to sort the points So our recursive function did not receive the points in sorted orders of their X and Y coordinates and the sorting had to be done for each subproblem at every level What would be the worst case complexity of this algorithm assuming that the rest of the algorithm remains the same 7 10 pts a Sam is trying to compute the complexity of merge sort In writing the recurrence relation he erroneously considers the complexity of the merging step to be O n2 instead of O 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 heap with n elements is n 5 points Additional Space Additional Space
View Full Document
Unlocking...