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 Problem 1 Problem 2 5 score 6 pts 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 1 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 2 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 3 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 4 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 5 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 3 private instance variables here Queue Queue bool Queue isEmpty const 4 int Queue front const other Queue method definitions here int main Queue q while cin val q enQ val 5 while q isEmpty cout q deQ problem continued next page 6 Problem 8 cont In the space provided below show what would be in each file for a version of this program that can use separate compilation That is we want to be able to compile the Queue module separately from the program that uses queues We re calling that client program qProg cpp Show everything that would need to go in each file …