Name USC NetID e g ttrojan CS 455 Final Exam Fall 2017 Bono Dec 12 2017 There are 9 problems on the exam with 80 points total available There are 12 pages to the exam 6 pages double sided including this one make sure you have all of them There is also a one page double sided code handout that accompanies the exam If you need additional space to write any answers or for scratch work pages 10 11 and 12 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 and USC 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 Please read over the whole test before beginning Good luck 1 Problem 1 7 pts Java The following method doesn t work as desired The method comment describes what it is supposed to do returns true iff the values in vals are in increasing order Array may have duplicate values e g 1 3 3 5 is in increasing order 3 and are in also in increasing order public static boolean isIncrOrder int vals for int i 0 i vals length 1 i if vals i vals i 1 return false else return true return false Part A Give example data for which isIncrOrder returns the wrong value and what that value is vals return value of isIncrOrder vals Part B Fix the code so it does what the comment says it does Do not rewrite the whole method but rather make your changes right into the code above using arrows to show where any new code should be inserted crossing out code that you would get rid of etc 2 USC NetID Problem 2 8 pts Java Consider the following two versions of a method to traverse a List printList1 and printList2 These methods will work for both LinkedList s and ArrayList s public static void printList1 List Integer list ListIterator Integer iter list listIterator while iter hasNext System out print iter next System out println public static void printList2 List Integer list for int i 0 i list size i System out print list get i System out println Next to each of the four calls to printList1 or printList2 below give the big O worst case time to run the code as a function of n the length of the list the calls are labeled A D ArrayList Integer anArrayList new ArrayList code to populate the array list LinkedList Integer aLinkedList new LinkedList code to populate the linked list printList1 anArrayList A printList2 anArrayList B printList1 aLinkedList C printList2 aLinkedList D 3 Problem 3 7 points Consider the following function that uses the Java Stack class public static void stackProb Stack Integer s new Stack Integer s push 1 for int i 2 i 4 i int val s peek s push i 2 s push val 1 System out print s pop System out println Part A What is the output of the function Part B Show the contents of the stack when the execution gets to the point labeled with an asterisk i e contents after the loop exits Put the contents of the stack in the box below showing the top of the stack on the right top Problem 4 6 pts total Assume you have an array of names with the following contents numbers above the line are indices 0 1 2 3 4 5 6 7 8 Flynn Gus Hank Jesse Marie Mike Saul Skyler Walter For each of the targets given below next to it list the names that the target would be compared with in a binary search on the array List them in the order that the comparisons would be done 1 target Mike 2 target Lydia 3 target Walter 4 USC NetID Problem 5 8 pts Java Consider a Java Map to store student data For each student it maps their name to their total score Note the exact kind of map used doesn t matter for this problem Map String Integer grades Read over the whole problem before answering More information about Maps on the code handout Part A Suppose you put the following entry in the map grades put Sam 82 Write code to correctly update this map entry so it has the value 99 instead Part B Suppose you then put the following entry in the map grades put Joe 88 Write code to correctly update this map entry so it has the key Zhou instead After your code runs the map will have the contents Sam Zhou 99 88 5 Problem 6 15 pts total Part A 14 Java 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 would return Yan Andy getKeysWithValue 25 map 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 code assume we re running the code on TreeMap Give the big O worst case running time for your code as a function of n the number of entries in the map 6 USC NetID Problem 7 6 pts total Assume we are trying to compile the C grades program we did for assignment 5 Here s a reminder of the file organization Table h Table cpp listFuncs h listFuncs cpp grades cpp Header file for the Table class contains Table class definition Implementation file for the Table class contains Table method definitions Header file for the Node struct and some list functions Implementation file for the Node struct and some list functions A program that uses the Table class contains main Consider the following Makefile for the program compile commands are labeled at the right for your convenience grades grades o Table o listFuncs o g ggdb Wall grades o Table o listFuncs o o grades a grades o grades cpp Table h b g ggdb Wall c grades cpp Table o Table cpp Table h listFuncs h c g ggdb Wall c Table cpp listFuncs o listFuncs cpp listFuncs h d g ggdb Wall c listFuncs cpp Consider the following sequence of Unix commands below I e assume they are done in the order shown with no other commands done in between After each of the gmake commands say what actions above would be done by gmake and in what order identifying an action by its letter i …