Name USC netID e g ttrojan CS 455 Final Exam Fall 2014 Bono December 16 2014 There are 6 problems on the exam with 75 points total available There are 9 pages to the exam including this one make sure you have all of them There is also a separate one page code handout 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 10 pts Problem 2 9 pts Problem 3 6 pts Problem 4 15 pts Problem 5 15 pts Problem 6 20 pts TOTAL 75 pts score 1 Problem 1 10 points The following Java code for insertion sort has a bug The comments will remind you how insertion sort is supposed to work sorts the array into increasing order using insertion sort algorithm public static void insertionSort int arr for int i 1 i arr length i each outer loop iteration inserts arr i into the correct location of the already sorted sub list arr 0 through arr i 1 int valueToInsert arr i int loc 0 while loc i arr loc valueToInsert find insertion location loc for int j loc j i j make room for the new value arr j 1 arr j arr loc valueToInsert put the value in correct location in sub list true here arr 0 through arr i is a sorted sub list Part A 3 Show the results of calling the current version of the function on the following array arr 3 9 2 after call to insertionSort arr arr Part B 5 Fix the code above Do not rewrite the whole method but rather make your changes right into the code above using arrows to show where your new code should be inserted crossing out code that you would get rid of etc The new version should do what the method comment says Part C 2 What s the big O worst case time for the code above 2 Problem 2 9 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 5 i int val s peek s push i s push val 2 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 Put the contents of the stack in the box below showing the top of the stack on the right top 3 Problem 3 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 Header file for the Table class contains Table class definition Table cpp Implementation file for the Table class contains Table method definitions grades cpp 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 g ggdb Wall grades o Table o o grades a Table o Table cpp Table h b g ggdb Wall c Table cpp grades o grades cpp Table h c g ggdb Wall c grades 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 there may be more than one valid order If no actions are done by that gmake call write up to date You may identify an action by its letter above i e a b or c Note the Unix shell prompt is shown as a below ls grades cpp Table cpp Table h Makefile output of ls gmake grades Actions done by this call to gmake gmake Table o Actions done by this call to gmake touch Table cpp Note touch changes the last modified date Alternatively you could edit the Table cpp file and save a changed version gmake Table o Actions done by this call to gmake 4 Problem 4 15 pts total Part A 13 Complete the implementation of the Java class ElapsedTime which represents some amount of time in hours and minutes such as 3 hours and 25 minutes not a time of day Such a class could be a useful building block in an applications such as a timer stopwatch or scheduling programs e g to schedule your DVR or flights for an airline The class allows us to create an elapsed time expressed using a number of hours and minutes or just total number of minutes it also allows us to increase an elapsed time by some amount of time to add two elapsed times together and to convert an elapsed time to a String form for printing or appending to longer messages The detailed specification for each method appears in its method comments below Furthermore you are restricted to use the internal representation for ElapsedTime shown in the starter code for the class internally we will store an elapsed time as its total number of minutes This representation actually would be one an implementer would likely use in a more fleshed out version of such a class because makes some operations easier to implement The class interface and space for your answer starts here and continues onto the next page ElapsedTime represents some amount of time in hours and minutes public class ElapsedTime Problem restriction do not change the private instance variable definitions private int totMinutes representation invariant totMinutes 0 Creates elapsed time of the given hours and minutes PRE hours 0 and minutes 0 public ElapsedTime int hours int minutes Creates elapsed time of the given total number of minutes PRE minutes 0 public ElapsedTime int totalMinutes 5 Problem 4 cont Increase the current elapsed time by the amount of time given by hours and minutes PRE hours 0 and minutes 0 public void increase int hours int minutes Returns the sum of this elapsed time and elapsed time b This method is not a mutator does not modify this Note the return type is an ElapsedTime object HINT Java rules allow this method to access private data of other ElapsedTime objects besides this for example b s private data public ElapsedTime add ElapsedTime b Returns a String form of the elapsed time using the format shown by example here 8hrs 32min public String toString Part B 2 Are ElapsedTime objects immutable If so why if not why not …