CS570 Fall 2019: Analysis of Algorithms Exam I Points Points Problem 1 20 Problem 5 20 Problem 2 15 Problem 6 10 Problem 3 15 Problem 7 10 Problem 4 10 Total 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. [ 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 and algorithm B has a worst case running time of . It is possible for algorithm B to run faster than algorithm A when N à ∞2) 15 pts Which of the following equalities are true and why? a. True, LS<= for any n>=2. Hence holds b. False. . More precisely given any and c, when n>=Max( ) c. 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<= , then log n = log c + log n(log log n). Clearly this holds. e. True. , then 100 log n <= log c + = log c + n log 2. This holds.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 reasoning 4) Using the inequality for growth of functions (logarithmic < polynomial < exponential) is okay 5) Reasoning using limit n->infinity is correct if you get the limit calculations correct3) 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. Rubric: 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 points4) 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 - Concluding from that statement that they are each other’s only valid partner +3pts - If any unclear wording and for every erroneous statement -1pt 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