Points 20 14 12 12 10 15 17 100 CS570 Spring 2020 Analysis of Algorithms Practice Exam I Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Problem 7 Total Instructions 1 This is a 2 hr and 20 mins exam Closed book and notes 2 Any kind of cheating will lead to score 0 for the entire exam and be reported to SJACS 3 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 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 Given a binary max heap with n elements the time complexity of finding the smallest element is O log n TRUE FALSE A greedy algorithm considers the entire search space when making each step TRUE FALSE Suppose that for a graph G V E the average edge weight is w Then a minimum spanning tree of G will have weight at most V 1 w TRUE FALSE Consider two positively weighted graphs G1 V E w1 and G2 V E w2 with the same vertices and same edges such that for any edge e E we have w2 e w1 e 2 For any two vertices u V and v V any shortest path between u and v in 2 is also a shortest path in 1 TRUE FALSE If all edges in a connected undirected graph have unit cost then you can find the MST using BFS TRUE FALSE Breadth first search is an example of a divide and conquer algorithm TRUE FALSE For any cycle in a graph the cheapest edge in the cycle is in a minimum spanning tree TRUE FALSE 0 1 knapsack problem can be solved using dynamic programming in polynomial time TRUE FALSE DFS finds the longest paths from start vertex s to each vertex v in the graph TRUE FALSE The shortest path in a weighted DAG can be found in linear time 2 14 pts Arrange the following functions in increasing order of growth rate with g n following f n in your list if and only if f n O g n 2 log 1 3 log log log 3 log log log 22 1 001 3 12 pts Suppose that we have an undirected graph G V E Prove the following statements a If is a simple connected graph then 3 pts 1 2 b If is a simple graph with V 3 and then is a connected 1 2 2 graph 9 pts 4 12 pts Businessman Daniel has n containers c1 c2 cn of several varieties of fruits to ship Each container has different cost and depreciation expense Initial value of each container is v1 v2 vn and depreciation expense is given by d1 d2 dn Daniel has only one ship so he can transport only one container at a time Therefore if container ci happens to be in the j th shipment its value will depreciate to Can you help Daniel to ship all containers and maximize total value of containers after depreciation Provide proof of correctness and state the complexity of your algorithm 5 10 pts For each of the following recurrences give an expression in the Theta notation for the runtime T n if the recurrence can be solved with the Master Theorem Otherwise indicate that the Master Theorem does not apply 1 16 T n 3 4 2 3 T n 3 2 cos T n 4 2 log2 T n 2 3 2 3 5 8 2 2 log T n 6 15 pts Kuang is planning to go skiing in Big Bear Mountain The resort has n trails amd m resting bases As a professional skier he tries to find the minimum time he needs to get from the peak of the mountain to different resting bases Due to the safety issue Kuang must follow the following restrictions He starts skiing from the peak There are many ski trails connecting different resting bases as well as the peak however there is at most one trail connecting two of them For each ski trail in the mountain Kuang knows the time he needs to get downhill Kuang cannot ski uphill a Design a linear time algorithm to find the minimum time to get from the peak to all the other resting bases 10 pts b Show the time complexity of the algorithm 5 pts 7 17 pts There are several ways to formalize the notion of distance between strings One common formalization is called edit distance that focuses on transforming one string into the other by a series of edit operations The permitted operations are Delete Insert and Replace of a character in the first string We also permit Match denoting that two characters match each other Here is one possible alignment of DYNAMIC and STATIC R R D M R M M d y n a m i c s t a t i c The edit distance between two strings is defined as the minimum number of edit operations A transformation in terms of D I M R of one string to another is called an edit transcript The edit distance problem is to compute the edit distance between two given strings along with an optimal edit transcript Design a dynamic programming algorithm that calculates the edit distance between string X of length n and another string Y of length m a Define in plain English subproblems to be solved 3 pts b Write the recurrence relation for subproblems 5 pts c Write pseudo code to compute the minimum number of edit operations 4 pts d Compute the runtime of the above DP algorithm in terms of n 2 pts e Discuss how you would recover the edit transcript based on the DP table created in part c 3 pts