lOMoARcPSD 37018844 Scan to open on Studocu Scan to open on Studocu CS70 Midterm Exam 1 Fall 2015 Sol CS70 Midterm Exam 1 Fall 2015 Sol 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 Fall 2015 Exam I Analysis of Algorithms Name Student ID Email Address Check if DEN Student Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Problem 7 Problem 8 Total 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 Maximum 20 15 12 9 12 9 10 13 100 Received 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 Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn lOMoARcPSD 37018844 1 20 pts Mark the following statements as TRUE or FALSE No need to provide any justification TRUE In a connected undirected graph and using the same starting point the depth of any DFS tree is at least as much as the depth of any BFS tree and algorithm B has a running time of n FALSE Algorithm A has a running time of log n From this we can conclude that A can never run faster than B on the same input set FALSE Let T be a complete binary tree with n nodes Finding a path from the root of T to a given vertex v T using breadth first search takes O log n time TRUE Amortized cost of operations in a Fibonacci heap is at least as good as the worst case cost of those same operations in a binomial heap FALSE Master s Theorem can be used to calculate the running time of any recursive function FALSE Dijkstra s shortest path algorithm can be used to find shortest path in graphs with any edge weights FALSE Function f n 5n24n 6n43n is O n43n TRUE Stable Matching Suppose Jack prefers Rose to others and Rose prefers Jack to others The pair Jack Rose exists in every stable matching TRUE A DFS tree is a spanning tree TRUE A binary max heap can be built using an unsorted list of elements in O n time Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn lOMoARcPSD 37018844 2 15 pts Suppose that you want to get from vertex s to vertex t in a connected undirected graph G V E with positive edge costs but you would like to stop by vertex u if it is possible to do so without increasing the length of your path by more than a factor of a Describe an efficient algorithm in O E log V time that would determine an optimal s t path given your preference for stopping at u along the way if doing so is not prohibitively costly In other words your algorithm should either return the shortest path from s to t or the shortest path from s to t containing u depending on the situation If it helps imagine that there are free burgers at u b Show that your algorithm runs in O E log V Since the graph has positive edges one can use dijkstra algorithm for the shortest paths computation We run dijkstra twice once from s to find the shortest paths s to u and s to t and once from u to find the shortest path u to t The shortest path from s to t containing u is composed of the shortest path from s to u and the shortest path from u to t We can now compare the length of this path to the length of the shortest path from s to t and choose the one to return based on their lengths Since we are using dijkstra algorithm and the graph is connected the total running time is 2 O E log V which is equivalent to O E log V Downloaded by jjyt jjyt nl7jjytv1 mail matlabcode cn lOMoARcPSD 37018844 3 12 pts Assume the coastline of the country Lyniera is an infinite straight line There are islands off the coastline of Lyniera In order to keep a close eye on these islands the king of Lyniera decided to set up some radar bases along the coastline Each radar base is a point on the coastline which can cover a circular area around itself with radius d Let s use the x axis in a coordinate system as the coastline horizontal axis with the sea on the upper side of the x axis Each island is a point in the sea with coordinates x y Design a greedy algorithm to find the minimum number of radar bases needed to cover all the islands and give their locations on the coastline Prove the correctness of your algorithm Assume each island is within distance d of the coast Solution and we can get an interval on the x axis For each island draw a circle around it with radius where we are able to place a radar base to cover this island the intersection of the circle with the x axis So translate the input to a set of intervals along the x axis The problem is to find the minimum number of points so that each interval has a point inside it Greedy strategy Put a radar base at the right most point of the interval with smallest right end point which has not been covered yet Remove the intervals which includes the chosen end point Recursively do the same thing for the remaining intervals until all the intervals are removed Proof First prove the first radar base is put correctly Let the left most radar base in the optimal solution has x coordinate Note that as we placed our radar base at the right end point of the interval with smallest right must include the set of islands covered end point the set of islands covered by the base at by base at in the optimal which should also be an optimal solution by the base at solution because still covers all the islands Therefore there is an optimal solution that makes the same first choice as the greedy strategy does so our first choice is correct Now consider the small subproblem of covering all islands which have not been covered by our first base Inductively we can show that all future decisions must also be correct as they can be rephrased as finding the first base on a smaller subproblem Thus our greedy algorithm is optimal Thus we can make an exchange replace the base at Then the left most radar base in our …