1 Name: _________________________________________ USC netID (e.g., ttrojan):______________________________ CS 455 Final Exam Spring 2015 [Bono] May 13, 2015 There are 10 problems on the exam, with 73 points total available. There are 10 pages to the exam, including this one; make sure you have all of them. For on-campus students: if you need additional space to write any answers, you may use the backs of exam pages (just direct us to look there). Note: if you give multiple answers for a problem, we will only grade the first one. Avoid this issue by labeling and circling your final answers and crossing out any other answers you changed your mind about (though it’s fine if you show your work). Put your name and USC Net ID at the top of the exam. Please read over the whole test before beginning. Good luck! value score Problem 1 6 pts. Problem 2-5 12 pts. Problem 6 9 pts. Problem 7 5 pts. Problem 8 6 pts. Problem 9 20 pts. Problem 10 15 pts. TOTAL 73 pts.2 Problem 1 [6 points] The following Java code attempts to use recursion to compute the maximum value in an array of numbers, but it has a bug: // max: Computes the maximum value in array nums // PRE: nums.length >= 1 public static int max(int[] nums) { return maxR(nums, 0); } // maxR (recursive helper function for max) // Computes the maximum value in the sub-array of nums in positions startLoc // through nums.length-1 // PRE: nums.length >= 1 private static int maxR(int[] nums, int startLoc) { int maxSoFar = 0; if (startLoc == nums.length) { return maxSoFar; } if (nums[startLoc] > maxSoFar) { maxSoFar = nums[startLoc]; } return maxR(nums, startLoc + 1); } Part A. Give a sample input array for max and the corresponding return value for max, such that the code above computes the wrong value for that array: nums: max(nums): Part B. Give a sample input array for max and the corresponding return value for max, such that the code above computes the correct value for that array: nums: max(nums):3 Problem 2 [2 points] Not counting any eliminated in the first iteration, roughly how many elements are eliminated from further consideration in the second loop iteration of a binary search in an array of n elements (i.e., assuming we didn't find the value in that iteration)? Problem 3 [2 points] What is true about the first k elements in the array before pass k of insertion sort? (circle the answer that best describes what is known) a. they are k values in sorted order b. they are the k smallest values c. they are the k smallest values in sorted order d. none of the above Problem 4 [4 points] If you wanted to sort an array of Strings in decreasing order by length using the Java Arrays.sort method you would also need what additional code (besides the call to the sort method)? (describe briefly– do not write code) Problem 5 [4 points] The Java ListIterator interface (used for iterating over a LinkedList) includes methods hasNext() and next(). The Iterator interface (used for iterating over a Set) also has methods hasNext() and next(). In addition, the ListIterator interface also has the following method (where ElmtType is the type of an element in the LinkedList): // Replaces the last element returned by next with the specified element public void set(ElmtType newVal) . . . Why is this method not provided in the Iterator interface?4 Problem 6 [9 points] Consider the following Java code to compute the number of occurrences of each score from an array of scores: // Returns an array of the number of occurrences of each score from // scores array. // E.g., after we call it as follows: // int[] counts = getCounts(scores, 100); // counts[0] is the number of 0's in scores, // counts[1] is the number of 1's in scores, . . . , // counts[100] is the number of 100's in scores // PRE: all the elements in scores are in the range [0,maxScore] public static int[] getCounts(ArrayList<Integer> scores, int maxScore) { int[] counts = new int[maxScore+1]; // all values init'd to 0 for (int i = 0; i < scores.size(); i++) { for (int score = 0; score <= maxScore; score++) { if (scores.get(i) == score) { counts[score]++; } } } return counts; } Part A [2]. What is the worst case big-O time for the current getCounts method in terms of scores.size() and maxScore? Part B [5]. Modify the getCounts function to improve the big-O running time. You can make your modifications directly in the code above, using arrows to show where your new code should be inserted, crossing out code that you would get rid of, etc. Part C [2]. What is the worst case big-O time for your new version of getCounts?5 Problem 7 [5 points] (Java) Consider a spell-checker that finds misspellings in a document, along with the number of times each misspelling occurred, and prints them out in alphabetical order. Example input document: hte bigest burger wase the best burger and hte wort bruger was teh smallest bruger hte gril prefered the big burger Example output: bigest 1 bruger 2 gril 1 hte 3 prefered 1 teh 1 wase 1 wort 1 Write variable declaration(s) for storing the data to solve this problem, such that we can use this data structure to solve this problem efficiently; also explain your approach via the prompts below. You may use Java library classes. Note: The spell-checker will also have at its disposal a dictionary of English words stored in a HashSet. Variable declaration(s): Description of what problem data is stored in this data structure and how it's organized: Description of how we are using the data structure to solve the problem (1-2 sentences maximum; do not write code):6 Problem 8 [6 points] Suppose we are creating a Queue class in C++. This Queue class will be for a queue of ints (i.e., it won't be a template class). Furthermore suppose we have a main program that uses the Queue class, and the whole program is in a single file, whose contents is shown here (some details left off so it all fits here). The different program elements are numbered at right for your convenience. (Note: unlike the later Queue problem, this one does not use any additional outside class or struct in its implementation.) #include <iostream> (1) using namespace std; (2) class Queue { public: Queue(); bool isEmpty() const; int front() const; void enQ(int val); int deQ(); private: .