lOMoARcPSD 37018844 Scan to open on Studocu Scan to open on Studocu CS570 Exam 1 Summer 2023 Solutions Rubrics CS570 Exam 1 Summer 2023 Solutions Rubrics Analysis of Algorithms University of Southern California Analysis of Algorithms University of Southern California Studocu is not sponsored or endorsed by any college or university Studocu is not sponsored or endorsed by any college or university Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn lOMoARcPSD 37018844 CS570 Spring 2023 Analysis of Algorithms Exam I Problem 1 Problem 2 Problem 3 Problem 4 Points 12 9 9 12 Total Points 16 18 24 Problem 5 Problem 6 Problem 7 100 Instructions 1 2 3 This is a 2 hr exam Closed book and notes No electronic devices or internet access A single 8 5X11 cheat sheet is allowed 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 No space other than the pages in the exam booklet will be scanned for grading 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 Do not detach any sheets from the booklet Detached sheets will not be scanned 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 Do not write your answers in cursive scripts This exam is printed double sided Check and use the back of each page 4 5 6 7 8 9 Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn lOMoARcPSD 37018844 12 pts 1 Mark the following statements as TRUE or FALSE by circling the correct answer No need to provide any justification TRUE FALSE A dynamic programming algorithm with a worst case runtime of O n2 takes O n2 space TRUE FALSE The Bellman Ford algorithm when used for finding the shortest path in a directed acyclic graph DAG with negative weight edges is guaranteed to correctly find a shortest path TRUE FALSE When inserting a new element into a binary max heap if the new element is larger than all existing elements in the max heap insertion will take O 1 time TRUE FALSE If and Then TRUE FALSE The top down pass in dynamic programming produces the value of the optimal solution whereas the bottom up pass produces the actual solution TRUE FALSE In a binary min heap the element with the maximum key value can be found in O log n time Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn lOMoARcPSD 37018844 9 pts 3 pts each Select ALL correct choices No partial credit 2 I After the Gale Shapley algorithm has been run between n men and n women with men proposing and a stable match has been found one man announces that his preference list was in reverse order and that the algorithm needs to be re run If the Gale Shapley algorithm is run again with men proposing with his preference order reversed what is the minimum number of pairings that would change from re running the algorithm a b c d e n n 2 2 1 0 II Which of the following techniques and algorithms can be classified as divide and conquer Binary search Bellman Ford running in a distributed environment as described in class Kruskal s algorithm Space efficient version of sequence alignment as described in class III To which of the following recurrence relations can the Master s theorem be directly applied Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn lOMoARcPSD 37018844 9 pts 3 Arrange the functions below in order of increasing running time according to Big O notation using equivalent and strict subset of Assume all logs are based 2 Points There will be a one point deduction for each inversion in your ordered list lg n2 lg n lgn lg n2n a b c 2lgn d 2n e f g 2n2 h n lgn Solution lg n2 lg n lgn 2lgn lg n2n 2n2 n lgn 2n Rubric 1 point per inversion Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn lOMoARcPSD 37018844 4 12 pts Given the undirected graph shown below Use Prim s algorithm to obtain an MST of this graph Use A as your starting a point Show the final MST and indicate the order in which you selected the edges MST A C A B B D D H D G G F F E cid 1 B D could also be C D or C H cid 1 Rubric 1 point for each wrong step b order in which you selected the edges B D could be replaced by C D or C H Rubric 1 point for each wrong step Use Kruskal s algorithm to obtain an MST Show the final MST and indicate the MST G F E F A C A B D H B D D G E F can be swapped with A C similarly D H with A B and B D with D G Is the MST in this graph unique If yes explain why If no show all edges that c can be part of an MST but don t have to be part of every MST No B D C D and C H Rubric 1 point for answering No 3 points for showing the 3 edges in the answer 1 for each wrong Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn lOMoARcPSD 37018844 16 pts 5 Alice has a knapsack with capacity C that she will fill exactly to capacity with her choice of items from k item types Each item type has a weight w i and value v i Alice has an unlimited supply of each item type in other words Alice may choose more than one item of the same type Design a DP algorithm to determine the worst case minimum value of items that will exactly fill up the knapsack and not leave any remaining space You can assume that such a combination of items exists a Define in plain English the subproblems to be solved 4 pts Let OPT i j min value of when choosing from first i items with total weight exactly j Rubric 1 point for not describing that subproblems solve for the minimum value 1 point for incorrectly describing what i represents 1 point for incorrectly describing what j represents 4 points if definition missing or entirely incorrect b Write a recurrence relation for the subproblems 4 pts If w i remaining capacity of the knapsack OPT i j min OPT i 1 j v i OPT i j w i Else OPT i j OPT i 1 j Rubric 1 point if not taking the min of the two cases 1 5 for each of the two cases i e include or not include item i 1 if not distinguished the case when w i j no penalty if handled via additional base cases Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn lOMoARcPSD 37018844 …