CMSC 451 Summer 2005 Final Exam Total points 50 Total time 80 mins Instructions All homework instructions apply In particular you can assume any proposition stated in the book If you can not solve a problem completely put down all your ideas in a clear simple and concise manner You could receive partial credit Good luck 1 True or false questions For each claim from a to e state if the claim is true or false along with a brief one or two line description which supports your answer a 3 points Let G be an undirected graph with k components such that each component of G is a tree Let the number of nodes in G be n Then the number of edges in G is n k b 3 points Recall that a vertex cover for a graph is a set of vertices such that each edge has at least one end point in this set Let G be a bipartite graph with n vertices Then it has a vertex cover of size at most n2 c 3 points Let G be an undirected weighted graph with the property that it has a unique minimum spanning tree Then every cut in the graph has a unique edge with the least cost d 3 points Let G be an undirected graph with positive edge costs that are all distinct Then there is a unique shortest path between any two pair of vertices in G e 3 points Consider the following recurrence relation T n 2T n2 n3 if n 2 5000 if n 2 Then T n O n3 2 10 points For two distinct points p1 x1 y1 and p2 x2 y2 in the plane we say that p1 dominates p2 if x1 x2 and y1 y2 Given a set P p1 p2 pn of n points in the plane a point pi P is called a maximal point in P if pi is not dominated by any other point in P Assume that P is not given in any sorted order Design an O n log n time algorithm for computing all maximal 1 points in P Note You can assume that all X coordinates are distinct and all Y coordinates are distinct Zero points will be given for an O n2 time algorithm 3 10 points Exercise 3 Chapter 8 4 15 points Exercise 8 Chapter 6 part a carries 5 points and part b carries 10 points
View Full Document
Unlocking...