Midterm Solution

Master Theorem If T(n) = aT(n/b) + O(nd) for constants a 0, b 1, d ≥ 0, then T(n) = O(nd) if d logb a O(nd logn) if d = logb a O(nlogb a) if d < logb a
1. [5 points] Mergesort, the partitioning algorithm used in quicksort, binary search, Karatsuba squaring (multiplying a big integer by itself using the Karatsuba algorithm), and grade school squaring (multiplying a big integer by itself using the grade school algorithm) are implemented in different programming languages. Each implementation is then carefully timed to determine its average case running time on arrays of different lengths. A different computer is used to time each implementation. The results of the five timing experiments are summarized below, along with timing experiments for one other algorithm. All timings are expressed in the same (unspecified) units. Length of array 1 2 3 4 5 6 400 1 61 10 .001 10 53 800 3 120 39 .002 22 54 1600 8 238 161 .003 47 53 3200 28 484 642 .005 100 55 6400 80 960 2550 .005 214 52 Identify the timing experiment that corresponds to each algorithm by writing 1, 2, 3, 4, 5, or 6 in each box below. (You will not use one of the numbers.) Algorithm Experiment Mergesort Partitioning Binary search Karatsuba Squaring Grade School Squaring
2. [5 points] Consider the following method: public static int f (int n) { int total = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j+=2) { total++; } } return total; } What does f(2*k) return? Assume that k 0. Give your answer in terms of k. You answer must not contain a summation. Answer
3. [6 points] For each pair of functions below, write • Θ(g) if f is Θ(g) Otherwise, write • O(g) if f is O(g) or • Ω(g) if f is Ω(g) f g Answer nlogn log(n!) 200n n3 −200n2 n1/3 logn 2n 22n 3n 3n+2 (logn)2 logn
4. [4 points] Using Θ() notation, give the worst case complexity of each of these algorithms. Algorithm Worst case Quickselect in an n-element array Partitioning an n-element array Lookup in an n-element binary search tree Appending to an n-element doubly-linked list
5. [4 points] Consider the following four functions: • f1(n) = log(nn) • f3(n) = n2 • f2(n) = log(2n) • f4(n) = √n Put these functions in order of increasing asymptotic complexity by writing f1, f2, f3, and f4 in the appropriate boxes below. Lowest asymptotic complexity Next highest asymptotic complexity Next highest asymptotic complexity Highest asymptotic complexity
6. [6 points] Use the Master Theorem to find an upper bound on the following three recurrences: T1(n) = 2T1(n/4) + O(n1/2) T2(n) = 4T2(n/2) + O(n) T3(n) = T3(n/3) + O(n2) Recurrence Bound T1 T2 T3
7. [8 points] Consider this function g, which operates on an array of integers. The helper function extract is also defined. // Does a curious computation on an array int g (int[] A) { if (A.length == 0) { return 0; } else if (A.length == 1) { return A[0]; } else { int n = A.length; return g(extract(A, n/5, 2*n/5)) + g(extract(A, 3*n/5, 4*n/5)); } } // Returns an array containing A[lo] through A[hi-1]. int[] extract (int[] A, int lo, int hi) { int size = Math.max(0, hi-lo); int[] result = new int[size]; for (int i = 0; i < size; i++) { result[i] = A[lo + i]; } return result; } Find a recurrence relation of the form T(n) = aT(n/b) + O(nd) that gives a tight upper bound on the amount of time required to compute g(A) when A is an n-element array. Below, give your values for a, b, and d. Also, use the Master Theorem to find an O() bound for the recurrence. Answer a b d Bound 5
8. [8 points] Use O() notation to give the tightest possible upper bounds on the worst-case times required to answer each of the following questions about a directed graph G consisting of V vertices and E edges. Answer each question once assuming that the graph is represented as an adjacency matrix (two-dimensional array) and again assuming that the graph is represented as an adjacency list (array of linked lists). Question Matrix List Does every vertex have an edge to itself? Is there a vertex with no edges out? Now using Ω() notation, give the tightest possible lower bounds on the best-case times on the same problems. Question Matrix List Does every vertex have an edge to itself? Is there a vertex with no edges out?
9. [4 points] Use O() notation to give the tightest possible upper bounds on the worst-case times required to answer each of the following questions about a directed, weighted graph G consisting of V vertices and E edges. Answer each question once assuming that the graph is represented as an adjacency matrix (two-dimensional array) and again assuming that the graph is represented as an adjacency list (array of linked lists). The lightest path is the path with the lowest total edge weights. You may assume the edge weights are non-negative. Question Matrix List Is the graph a DAG? What is the lightest path from vertex u to vertex v?
10. [8 points] Let G be a connected, undirected graph on which a breadth-first search has been performed. Classify the following statements as true (for all G) or false (for at least one G). Statement True or False? Every number in the dist array is less than V The prev array contains no duplicates If the dist array did not exist, it could be computed from the prev array If there is a 5 in the dist array, there will also be a 4 in the dist array
11. [8 points] Suppose that the strongly-connected components algorithm that we studied in class is run on a directed graph G. Let n be the number of times that the explore method is called, not counting the recursive calls that are called from inside explore. Let s be the number of strongly-connected components in G. Classify each of the following assertions as true (for all G) or false (for at least one G). Assertion True or False? n = 2s n ≤ 2s n s n = s
12. [4 points] Let G be a weighted, directed graph with V vertices and E edges. None of the weights are negative. At most how many update operations must be applied to G by Dijkstra’s algorithm before it terminates? Answer 7 The directed graph X diagrammed below is the subject of the next two questions. ?? ?? G ??? ?? J @ @ @ @R ?? ?? F? ?? ?? E @ @ @ @R ?? ?? I @ @ @ @R ?? ?? B ?? ?? D ? ? ?? ?? C @ @ @ @R ?? ?? H ? ?? ?? A
13. [8 points] Find the strongly connected components of X. For each strongly connected component, list the vertices that make up that component in one box of the table below. But wait, there’s an extra constraint. Put components that are sources in X’s meta-graph in the first column, components that are sinks in X’s meta-graph in the second column, and all other components in the third column. For example, if you decide that H, C, and A form a strongly-connected component, and that it is a sink in the meta-graph, you would write “HCA” in one of the boxes in the column labeled “Sinks”. You will not need to use all of the boxes. Sources Sinks Others
14. [8 points] Suppose that you do a depth-first search of X. Suppose also that whenever there is an arbitrary choice of vertices to visit (in either dfs or explore), you always pick the one that comes first in the alphabet. Give the pre and post numbers as requested below. Pre number of B Post number of C Pre number of D Post number of E Pre number of F Post number of G Pre number of H Post number of J The next two questions concern this undirected, weighted graph Y . ? ?? G ? ?? D ? ?? A ? ?? H ? ?? E ? ?? B ? ?? I ? ?? F ? ?? C 1 1 4 3 1 3 1 5 3 8 5 1
15. [8 points] Suppose Dijkstra’s algorithm is used on Y to find a shortest paths tree rooted at vertex H. The first vertex to be removed from the priority queue via a deleteMin operation will be H. What will be the second, fourth, sixth, and eighth vertices removed? (If an arbitrary vertex must ever be chosen, choose the one that comes earlier in the alphabet.) Vertex Answer Second vertex Fourth vertex Sixth vertex Eighth vertex
16. [6 points] Suppose that the Bellman-Ford algorithm is used on Y to find the shortest paths tree that is rooted at H. Assume that the algorithm uses the early termination optimization discussed in class. Answer the following questions. Question Answer The number of iterations required by Bellman-Ford is determined in part by the order in which the edges are considered. Including the final iteration during which nothing changes, what is the fewest number of iterations that Bellman-Ford could possibly take when finding the shortest path tree? Including the final iteration during which nothing changes, what is the largest number of iterations that Bellman-Ford could possibly take when finding the shortest path tree?