CS570 Spring 2022 Analysis of Algorithms Exam I Problem 1 Problem 2 Problem 3 Problem 4 Points 20 9 6 8 Total Points 18 16 13 10 Problem 5 Problem 6 Problem 7 Problem 8 100 Instructions 1 This is a 2 hr exam Open book and notes No electronic devices or internet access 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 8 This exam is printed double sided Check and use the back of each page 1 20 pts Mark the following statements as TRUE or FALSE by circling the correct answer No need to provide any justification i TRUE FALSE If we add 1 unit to the cost of the two lowest cost edges in the graph G then the cost of the MST of G will increase by 2 units e g the first 3 lowest cost edges could have the same cost ii TRUE FALSE Every weighted undirected graph has at least one MST If the graph is not connected there is no MST iii TRUE FALSE We say that an algorithm runs in O 1 if it takes it constant time to run when the problem size n 1 iv TRUE FALSE A binary tree with k levels has 2k 1 nodes v TRUE FALSE The worst case time complexity of merge sort is O n2 vi TRUE FALSE The worst case runtime of binary search satisfies the recurrence relation T n 2T n 2 c where c is a constant vii TRUE FALSE If a directed acyclic graph with 4 nodes has a unique topological ordering ABCD then it must have at least 3 edges viii TRUE FALSE Prim s algorithm cannot handle negative cost edges ix TRUE FALSE A binary max heap can be converted into a min heap by reversing the order of the elements in the heap array x TRUE FALSE For n 3 a directed graph with n nodes and n edges can be strongly connected 2 9 pts Circle ALL correct answers no partial credit when missing some of the correct answers No need to provide any justification i If a binomial heap contains these three trees in the root list B0 B1 and B3 after 2 Extract min operations it will have the following trees in the root list 3 pts a a B0 and a B3 b a B1 and a B2 c a B0 a B1 and a B2 d None of the above ii What s the solution to the recurrence U n 2U n 2 n log n 2n 3 pts a U n n log n b U n n log2 n c U n n log log n d None of the above iii Let G V E be a weighted undirected connected graph Which of the following are true Choose all that are true 3 pts a Minimum edge in a graph is always part of a MST b Minimum edge in a cycle is always part of a MST c Maximum edge in a cycle is never part of a MST d Maximum edge in a graph is never part of a MST 3 6 pts For the given recurrence equations solve for T n if it can be found using the Master Method Else indicate that the Master Method does not apply Answer each has 1 5 points no explanation correct answer 0 75 i T n T n 2 2n a 1 b 2 f n 2n 0 25 point n n0 1 0 25 point 21 21 Case 3 Master Theorem f n 2n 1 c2n T n 2n 1 point 2 T n 1 point General case 2 f n n ii T n 5T n 5 n log n 1000n a 5 b 5 f n n log n 1000n 0 25 point n n1 n 0 25 point 55 n 55 1 2 2 22 T n 0 25 point iii T n 2T n 2 log2 n n1 n 0 25 point 22 n a 2 b 2 f n Case 1 1 point iv T n 49T n 7 n2 log n2 a 49 b 7 f n n2 log n2 1 5 point not applicable 0 5 points problem is not a correct form to apply master theorem T n aT n b f n The prerequisite regarding the positive f n is not satisfied 1 point 4 8 pts Analyze the worst case complexity of the following code snippets and provide a tight upper bound for each case No explanations necessary Each part has 2 pts i k 0 for i 1 to n k k 1 endfor ii k 1 for i 1 to n j 1 while j i k k 1 j j 2 endwhile endfor k 570 i 1 while i n i i k endwhile iii iv x 0 k 57075 for i 1 to min of n k for j 1 to log n x x k endfor endfor Solution The problem involves n addition therefore the complexity is O n i O n 2 points Any other answer gets 0 points ii O n log n 2 points request a regrade please iii O logk n or O log n 2 points Any other answer gets 0 points iv O log n 2 points The inner loop repeats for log n time If you answered O log n you should still get 2 points If you didn t get any point or you got only 1 point The number of times that 1 can be multiplied by k before it gets greater than n is logk n The outer loop is a constant number of iterations because k is constant if you answered O min n k log n you only get 1 point if you answered as follows you get 1 point if n k O n log n else O k log n 5 18 pts During Spring break which is m days long USC is making its alumni park available to charitable organizations for fundraising events However only 1 event can be hosted on each day from day 1 to m Each event lasts for exactly 1 day There are N prospective events For each event i there is a deadline Di denoting the last day on which it can be hosted and expected funds Fi denoting the funds it is expected to raise if it …