Download Midterm Exam, CMSC 420, Fall 2002: Algorithm Analysis and Data Structures - Prof. Dana S. and more Exams Data Structures and Algorithms in PDF only on Docsity! Midterm Exam, CMSC 420, Fall 2002 Name: Instructions: • Leave at least one empty seat between you and each of the other students. • This exam is open book, open notes (and closed neighbor :-) • Each question is worth 5 points, for a total of 100 points. • If you want any partial credit for wrong answers, you need to show your work. • Write only on the test sheets. If you run out of room, write on the back of the last page. Problem 1. Professor Prune has created an algorithm that does some kind of computation on an array. If the algorithm is called on an array of size n, then the number of comparison operations done by the algorithm will vary depending on which array of size n, but it will always be a number in the interval from 2n2 − n to n3 + 2n− 1, inclusive. 1. Let Cbest(n) and Cworst(n) be the worst-case and best-case values for the number of compar- isons done by the algorithm. Below, circle each true statement: Cbest(n) = O(n2) Cbest(n) = Ω(n2) Cbest(n) = Θ(n2) Cbest(n) = O(n2 lg n) Cbest(n) = Ω(n2 lg n) Cbest(n) = Θ(n2 lg n) Cbest(n) = O(n3) Cbest(n) = Ω(n3) Cbest(n) = Θ(n3) Cworst(n) = O(n2) Cworst(n) = Ω(n2) Cworst(n) = Θ(n2) Cworst(n) = O(n2 lg n) Cworst(n) = Ω(n2 lg n) Cworst(n) = Θ(n2 lg n) Cworst(n) = O(n3) Cworst(n) = Ω(n3) Cworst(n) = Θ(n3) 2. Let Iworst(n) be the total number of computer operations (including both comparison oper- ations and other operations) done by Professor Prune’s algorithm in the worst case on an array of size n. Is it possible to have Iworst(n) 6= O(Cworst(n))? Explain why or why not. 1 Problem 2. A tridiagonal matrix is a square matrix T [1..n, 1..n] in which T [i, j] is nonzero only if |i − j| ≤ 1. You are to develop a sequential storage allocation strategy for tridiagonal matrices that only allocates storage to the nonzero entries. 1. Draw a picture of the memory locations for a 4 × 4 tridiagonal matrix T [1..4, 1..4]. At each memory location, write a note saying which T [i, j] it represents. 2. How many storage locations will be needed to represent the nonzero elements of a tridiagonal matrix T [1..n, 1..n]? (Give an exact value, not a Θ or big-O value). 3. Write a formula that gives the location of an element T [i, j] of a tridiagonal matrix T [1..n, 1..n]. 2 Problem 4. Suppose a dictionary has n elements whose keys are K1,K2, . . . ,Kn. Suppose that for each LookUp operation, the argument is Ki with probability 1/2i. Then the optimal ordering for the keys is K1,K2, . . . ,Kn. Let Copt(n) be the expected number of comparisons for a successful search if the keys are stored in that order. 1. When a LookUp occurs, what is the probability that the search is unsuccessful? 2. What is Copt(4)? 3. For n ≥ 3, let C(n) be the expected number of comparisons for a successful search if the keys are stored in the order K2,K3,K1,K4, . . . ,Kn−1,Kn. What is C(n)− Copt(n)? 4. It can be proved that Copt(n) < 2 for every n. Use this to give a lower bound on C(n)/Copt(n). 5 6 Problem 4. 1. Write the KMPSkipArray matrix for the string “ABABA”. 2. Write the BMSkipArray matrix for the string ”ABABA”. Problem 5. Consider a target string that contains 200 occurrences of the character A, followed by the characters ABABA. Suppose we are searching for ABABA. 1. How many times will the Knuth-Morris-Pratt algorithm examine characters in the target? 7
