Name USC Student ID Number USC NetID e g ttrojan CS 455 Midterm Exam 2 Spring 2024 Bono Apr 2 2024 There are 6 problems on the exam with 63 points total available There are 10 pages to the exam 5 pages double sided including this one make sure you have all of them There is also a double sided one page code handout that accompanies the exam If you need additional space to write any answers or for scratch work pages 9 and 10 of the exam are left blank for that purpose If you use these pages for answers you just need to direct us to look there Do not detach any pages from this exam 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 USC ID number and username a k a NetID at the top of the exam Also put your NetID at the top right of the front side of each page of the exam even if you wrote nothing else on that page Please read over the whole test before beginning Good luck 1 Problem 1 10 points Below is a list where each item is a description of a problem to solve or the name of an algorithm that solves a problem Put the items in order from fastest running to slowest running in terms of big O time complexity of that algorithm or the fastest way of solving that problem if an algorithm isn t named If more than one item has the same time complexity you can list those ones in any order with respect to each other In your list just show the letter that identifies each algorithm don t rewrite the algorithm name Then circle each group of letters in the box that has the same time complexity e g one circle will be around the group of letters that takes O n Example of the form of the answer not the actual answer B A C D E F This question does not ask for big O times giving big O times without ordering them correctly will be worth little to no credit as will answers without the circles Show ordered list of letters with circled groups here A get the index of a particular value in an unsorted array fastest slowest D merge algorithm hint merge means to combine two ordered lists of length n to make one large ordered B mergesort C get kth element in an array list E selection sort F get the index of a particular value in a sorted linked list G get the kth element in a linked list H look up a key in a hash table I traverse a balanced search tree J get the index of a particular value in a sorted array 2 USC NetID Problem 2 5 points Consider the following static boolean method mystery Below the method body write a method comment for this method To make it easier we started the comment for you It should be no more than one or two sentences Recall that method comments are for the client of the method they describe what not how A line by line description of the code will receive no credit public static boolean mystery String str Stack Character s new Stack Character int i 0 while i str length str charAt i a s push str charAt i i while i str length str charAt i b s empty s pop i return i str length s empty Method comment for mystery complete the sentence below Returns true if and only if the specified string str 3 Problem 3 10 points Consider the following program that uses exceptions Note MyException defined below and FileNotFoundException are both subclasses of IOException public class ExcProb public static void main String args try ArrayList Integer nums readFile int total 0 int sum 0 for int i 0 i nums size i sum nums get i total if total 0 sum 24 total 3 System out println Average is sum double total catch MyException exc System out println Error exc getMessage catch IOException exc System out println Error D private static ArrayList Integer readFile throws IOException ArrayList Integer nums new ArrayList try Scanner inFile new Scanner new File data if inFile hasNext throw new MyException A while inFile hasNext if inFile hasNextInt throw new MyException B nums add inFile nextInt catch FileNotFoundException e System out println Error C return nums class MyException extends IOException public MyException note given message can be retrieved with inherited method getMessage public MyException String message super message problem continued next page 4 USC NetID Problem 3 cont these questions go with the code on the previous page Part A 2 Give the contents a sample data file such that the program does not print any error messages Part B 2 What is the exact output of the run of the program you described in Part A Part C 2 Give the contents of or describe a sample data file such that the program prints both an error message AND prints an Average is message Part D 2 What is the exact output of the run of the program you described in Part C Part E 2 Give the contents of or describe a sample data file such that Error B is printed by the program 5 Problem 4 8 points Consider the following function to modify each element in a list in the way specified by its updateFunction argument public static void updateAll List Integer list UnaryOperator Integer updateFunction list replaceAll updateFunction Note More about replaceAll and the UnaryOperator interface it uses is on the code handout Show a call to updateAll to replace all the even elements in a list of integers called myList with the value 0 Your answer needs to include any other code necessary to make it work Here s an example of the expected result of your function call myList before call to updateAll 2 4 5 6 7 myList after call to updateAll 0 0 5 0 7 6 USC NetID Problem 5 15 pts total Part A 14 Implement the static method getKeysWithValue that gets all keys that have a particular value in a Java Map We don t care what order the keys are in in the resulting arraylist More information about Maps on the code handout For example if map has the entries Yan 25 Song 34 Andy 25 Lin 92 Aarti 86 getKeysWithValue 25 map would return Yan Andy getKeysWithValue 92 map would return Lin getKeysWithValue 100 map would return public static ArrayList String getKeysWithValue int val Map String Integer map Part B 1 For this part assume we re running the code you wrote in part A on a TreeMap Give the big O worst case running time for your code as a function of n the number of entries in the map 7 Problem 6 15 points Write a recursive …