lOMoARcPSD 37018844 Scan to open on Studocu Scan to open on Studocu CSCI570 Spring 2023 Exam1 Solution Rubrics CSCI570 Spring 2023 Exam1 Solution 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 CSCI 570 Spring 2023 Midterm 1 lOMoARcPSD 37018844 1 INSTRUCTIONS The duration of the exam is 140 minutes closed book and notes No space other than the pages on the exam booklet will be scanned for grading Do not write your solutions on the back of the pages If you require an additional page for a question you can use the extra Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn page provided at the end of this booklet However please indicate clearly that you are continuing the solution on the additional page lOMoARcPSD 37018844 2 Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn lOMoARcPSD 37018844 3 1 True False Questions 10 points Mark the following statements as T or F No need to provide any justi cation a T F Prim s algorithm cannot be applied to directed weighted graphs True b T F For a dynamic programming algorithm computing all values in a bottom up fashion is asymptotically faster than using recursion and memoization False A bottom up implementation must go through all of the subproblems and spend the time per subproblem for each Using recursion and memoization only spends time on the subproblems that it needs In fact the reverse may be true using recursion and memoization may be asymptotically faster than a bottom up implementation c T F In an undirected weighted graph the shortest path be tween two nodes always lies on some minimum spanning tree False One can provide a simple example of three nodes with weights 2 3 and 4 d T F For a graph with nonnegative edge weights when a node u is removed from the priority queue in Dijkstra s algorithm its distance label is correct i e equal to the length of the shortest su path True This is exactly the invariant maintained by Dijkstra s al gorithm e T F We have n operations each of which takes amortized O 1 Then the worst case running time for any single operation can be n2 Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn False Since the n operations have amortized running time O 1 their total running time is at most O n f T F The spanning tree of maximum weight in G is the mini mum spanning tree in a copy of G with all edge weights negated True Minimum spanning algorithms only consider relative edge order so they still work with negative edge weights to produce a minimum spanning tree The spanning tree T minimizes w T maximizes w T g T F Suppose G is a weighted undirected graph with positive edge weights where each edge e E has weight we and let G be a graph that is identical to G except that every edge e has weight w2 True One way to see this is that the ordering of edges by weights remains the same so the set of MSTs that can be output by Kruskal s is the same e Any MST of G is an MST of G h T F Let T n 3T n 3 O log n be a recurrence equation Then we can conclude that T n n log n by the Master theorem False Case 1 of the master theorem a 3 b 3 i T F Any function which is log log n is also log n False If a function is log n it can not be log log n j T F plog2 n n log2 n 1 True the right hand side is a constant lOMoARcPSD 37018844 4 Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn lOMoARcPSD 37018844 2 Multiple Choice Questions 10 points Please select the most appropriate choice Each multiple choice ques tion has a single correct answer a Suppose that a binomial heap H has a total of n nodes The maximum number of binomial trees H can contain is the following a f loor log n 1 b f loor n log n c f loor log n 1 d f loor log n a f loor log n 1 Since the binary representation of n has at most f loor log n 1 digits and each digit can represent a binomial tree b In the lecture we discussed the runtime complexity of Dijkstra s algorithm when it s implemented using a binary heap What would be the algorithm runtime complexity if we replace a bi nary heap by a Fibonacci heap Select the tightest upper bound a O E V log V b O E V c O V E log V d O E V log V d c The solution to the recurrence relation T n 8T n 4 O n log n by the Master theorem is a n2 b n2 log n c n log n d n log2 n a 5 Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn d Analyze the worst case complexity of the following code snippet and select the tightest upper bound for int i 1 i n i for int j 1 j i j j j 2 a O n b O log n c O n2 d O n log n d and select the tightest upper bound while n 0 for int i 0 i n i System out println n n 2 e Analyze the worst case complexity of the following code snippet a O n b O log n c O n2 d O n log n a Starting from n the inner for loop runs n times Second time it runs n 2 times and then n 4 times and so on n n 2 n 4 2 1 2n 1 O n lOMoARcPSD 37018844 6 Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn 3 Short Question 15 points Suppose there are two algorithms T1 and T2 The rst algorithm has a runtime complexity de ned by T1 n 5T1 n 2 O n2 The second algorithm has a runtime complexity de ned by T2 n x T2 n 4 O n2 log n where x 0 is an unknown positive real number What are the values of x such that T2 is asymptotically faster than T1 You may express your answer using inequalities for x Explain your answer When 0 x 25 This actually is broken into three cases 0 x 1 1 x 16 and 16 x 25 since each of them is solved di erently by the Master theorem An answer with range 0 x 25 is worth full credits 15 pts If the answer is di erent allocate the points based on the following criteria Range 1 x 16 6 5 pts Range 16 x 25 6 5 pts Range 0 x 1 2 pts Eg An answer with range …