Points 20 10 10 Points 20 15 15 10 Total Problem 5 Problem 6 Problem 7 100 CS570 Fall 2019 Analysis of Algorithms Exam I Problem 1 Problem 2 Problem 3 Problem 4 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 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 We know that algorithm A has a worst case running time of a worst case running time of A when N It is possible for algorithm B to run faster than algorithm and algorithm B has 2 15 pts Which of the following equalities are true and why True LS for any n 2 Hence holds a c b False More precisely given any and c when n Max False Taking log preserves inequality If then log log n log c 4 log log log n Clearly log log n log log log n hence it is false d True Note that taking log preserves inequality If n log c log n log log n Clearly this holds then log n e then True log c n log 2 This holds 100 log n log c Rubric For each subpart 1 3 if you get true false incorrect 2 2 if you get the true false correct 3 1 if you mention no reasoning or if you do not mention the correct 4 Using the inequality for growth of functions logarithmic polynomial 5 Reasoning using limit n infinity is correct if you get the limit reasoning exponential is okay calculations correct 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 Solution 1 Build a min heap containing the first element of each row and then run deleteMin to return the smallest element can also be done with first element of each column 2 If the element from the i th row was deleted then Insert another remaining element in the same row to the min heap Repeat the procedure k times 3 The total running time is O n k log n Minheap is built in O n Insert and deleteMin operations both take log n since there are n elements in the heap To find the kth smallest elements we require k 1 delete and insert operations 1 Do not explicitly explain the algorithm 8 points 2 Not clear about the min heap 5 points 3 Wrong calculation of time complexity 5 points 4 Build the heap without explain the algorithm 5 points Rubric 4 10 pts Prove or disprove the following statement For a given stable matching problem if m and w appear as a pair when men propose and they also appear as a pair when women propose then m and w must be paired in all possible stable matchings Proof In this case m and w are each other s best and worst valid partners This means that they only have one valid partner Alternatively Because m and w are each other s best valid partners proof by contradiction that they are each other s only valid partners Assume a stable matching exists where m and w are not paired We know m is w s best valid partner so w must prefer m to her current partner Likewise w is m s best valid partner so m must prefer w to his current partner Thus an instability exists contradicting our assumption Thus no stable matching exists where m and w aren t paired and thus they are each other s only valid partner Rubric Deciding that the statement is true 3pts Mentioning that they are each other s best and worst valid partners 4pts o If only mention one of these 2pts If any unclear wording and for every erroneous statement 1pt Concluding from that statement that they are each other s only valid partner 3pts Rubric Alternate Deciding that the statement is true 3pts Mentioning that they are each other s best valid partners 3pts Valid complete contradiction proof 4pts If any unclear wording and for every erroneous statement 1pt Assuming the statement is false and attempting to disprove 0pts 5 20 pts Tom is looking to buy a new smartphone and is looking at the upcoming phone releases Each …