Name USC NetID e g ttrojan CS 455 Final Exam Spring 2017 Bono May 10 2017 There are 7 problems on the exam with 74 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 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 10 pts Java Briefly describe two possible internal representations one could use in an implementation of the Java Map interface such that each of the representations is different than the two implementations that are provided in the Java library that we discussed this semester For each one you describe give the worst case big O time to do each of the Map operations listed below get the value associated with this key if no entry with this key exists returns null public ValueType get KeyType key inserts an entry or updates the value that goes with an existing key Returns the old value associated with the key or null if this key was not previously in the map public ValueType put KeyType key ValueType value remove the entry with this key returns the associated value or null if not found public ValueType remove KeyType key Description of representation 1 Big O times for representation 1 get put remove Description of representation 2 Big O times for representation 2 get 2 put remove USC NetID Problem 2 8 pts Java Implement the boolean Java method sortByScore which sorts an ArrayList of Student s so they are in decreasing order by score For students with the same score they must be in increasing order by name You must use the Java sort utility more info about that on the code handout and include any additional code necessary to make it work outside of the sortByScore method Here is an example of contents of such an ArrayList shown in the order it would be in after a call to sortByScore Jan 98 Lin 98 Ann 84 Fred 84 Moe 84 Zhou 80 Aarti 72 Here is the Student class it uses only shows interface since that s all we are using here This is an already completed class you may not modify Student for this problem public class Student public Student String name public String getName public int getScore public void changeScore int int score newScore private stuff not shown public static void sortByScore ArrayList Student students 3 Problem 3 19 pts total Part A 15 Java Write the complete class definition for a Java class for a Stack of ints that uses an array representation not ArrayList such that all stack operations run in amortized constant time or better Hint Use the strategy such that if you run out of space in the array you double its size The amortized part of the time is because of the need to increase the array size periodically You may not use any Java library classes or methods in your code except the the Arrays copyOf method described on the code handout You do not have to write method comments for your class The complete interface for the Stack class for this problem is shown by example below Note method names shown in bold Stack s new Stack creates an empty stack s push 3 pushes 3 onto the stack s push 0 pushes 0 onto the stack int val1 s pop pops top element from the stack and returns its value only legal on non empty stack int val s top returns the top element stack is unchanged only legal on non empty stack if s isEmpty returns true if stack is empty otherwise false System out println stack is empty Space for your answer is given on this and the next page 4 USC NetID Problem 3 cont additional space for your answer to Part A Part B Part B 4 Write a representation invariant for your class implementation 5 Problem 4 9 points C Consider the following buggy C function insertFront that attempts to insert a value in the front of a linked list and the program that uses it below See code handout for documentation of Node and ListType printList prints list using the format cab sit dog dad prints an empty list as PRE list is a well formed list void printList ListType list code not shown void insertFront ListType list const string val Node newGuy new Node val list next newGuy int main ListType myList new Node a insertFront myList b insertFront myList c insertFront myList d printList myList Part A In the space above draw a box and pointer diagram a k a memory diagram showing all variables objects and their state as they have changed during the code sequence up through the statement labeled do not show the stuff after that This includes showing insertFront s parameters you can name them list1 val1 in the first call and list2 val2 in the second call Part B What is the output of the program 6 USC NetID Problem 5 8 points C The following is a simplified version of the freq cpp program we did in lecture but that is now organized as a multi file program so that we can compile the histogram functions using histogram h and histogram cpp separately from this program that uses them freq cpp In the space provided below show what needs to be in histogram h in the blank box at the bottom of the page You may not change the contents of the other two files A full credit answer has what s needed and nothing more Note all places where functions from this program are called are shown in the code Note no fndef etc needed because no classes are defined include histogram h const int MAX 10 const int NUM COUNTS MAX 1 int main int counts NUM COUNTS initCounts counts NUM COUNTS readAndCompute counts NUM COUNTS printHist counts NUM COUNTS include histogram h include iostream using namespace std Some functions definitions are elided for brevity void initCounts int counts int size void readAndCompute int counts int size void printTicks int numTicks void printHist int counts int size printTicks freq cpp histogram cpp histogram h 7 Problem 6 5 pts C Consider the following class and in particular the add method that attempts …