Name USC NetID e g ttrojan CS 455 Final Exam Spring 2018 Bono May 8 2018 There are 9 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 double sided code handout that accompanies the exam If you need additional space to write any answers or for scratch work pages 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 4 points Divide and conquer algorithms are ones where part of the solution to a larger version of a problem involves dividing the problem in half roughly and solving that smaller version Which of the following algorithms listed below are divide and conquer algorithms circle the letter to the left of all that apply a linear search b mergesort c recursive isPalindrome reminder the method tells you whether its string argument is a word that reads the same forward and backward d binary seach e insertion sort f the merge algorithm reminder an efficient algorithm we discussed that takes two ordered lists and combines them to create one ordered list g maze search as done in assignment 3 Problem 2 8 points Consider a Map class to store a collection of key value pairs no duplicate keys with operations insert key remove key lookup key and printInOrder the last is to print all entries in order by key For A D assume a Map with n entries and give worst case time unless average case is better A How long would printInOrder take in big O terms if if the Map used an unordered array representation B How long would remove take if it used a balanced search tree representation C How long would lookup take if it used an ordered array representation i e ordered by keys D How long would insert take if it used an unordered linked list representation 2 USC NetID Problem 3 6 points Java Consider the following incorrect Java program that does not compile it produces an error related to exceptions Note it uses another class called DataObject you do not need to understand anything about how DataObject works to solve this problem Note see code handout for more information about the Scanner class Fix the program and enhance it as follows if the user gives a file name for a non existent file for example flkjm print the following message ERROR File does not exist flkjm Exiting program and exit the program immediately without crashing If the file does exist the program will operate normally Space is given below to make your modifications additions right in the code below public class MyProg public static DataObject readFile String fileName DataObject data new DataObject create an empty data object File inFile new File fileName Scanner fileScanner new Scanner inFile while fileScanner hasNext reads and puts stuff in data fileScanner close return data public static void main String args Scanner in new Scanner System in System out print Please enter a file name String fileName in next DataObject data readfile fileName data process data printResults System out 3 Problem 4 15 points A different way to represent the maze data for the Maze class of assignment 3 is to store only the set of wall locations in the maze In this problem you are going to write part of the implementation of the Maze class using this representation as a Java HashSet the instance variable walls is already defined for you below Implement 1 the initWalls private method called from the constructor below and 2 the hasWallAt public method For the purposes of this problem assume MazeCoord has been defined appropriately to be able to use it as the element type in a HashSet See code handout for more about the MazeCoord class and the Set interface Hint the number of rows in a 2D array arr is a length the number of columns is a 0 length public class Maze private Set MazeCoord walls the set of coords that are walls public static final boolean FREE false public static final boolean WALL true other constants and instance variables not shown Constructs a maze param mazeData the maze data A 2D array of values Maze FREE and Maze WALL see public FREE WALL constants above where the first index indicates the row e g mazeData row col public Maze boolean mazeData initWalls mazeData code to initialize the other instance variables not shown Initializes the walls variable from mazeData param mazeData the maze data A 2D array of values FREE and WALL see public FREE WALL constants above where the first index indicates the row e g mazeData row col private void initWalls boolean mazeData Returns true iff there is a wall at this location param loc the location in maze coordinates return whether there is a wall here PRE 0 loc getRow numRows and 0 loc getCol numCols public boolean hasWallAt MazeCoord loc other parts of the class not shown space for your answer on the next page 4 USC NetID Problem 4 cont public class Maze private Set MazeCoord walls the set of coords that are walls public static final boolean FREE false public static final boolean WALL true other parts of the class not shown Initializes the walls in the maze param mazeData the maze data A 2D array of values FREE and WALL see public FREE WALL constants above where the first index indicates the row e g mazeData row col private void initWalls boolean mazeData Returns true iff there is a wall at this location param loc the location in maze coordinates return whether there is a wall here PRE 0 loc getRow numRows and 0 loc getCol numCols public boolean hasWallAt MazeCoord loc 5 Problem 5 8 pts total Some of the answers in the answer bank below are for one of the four questions given Match the question with the correct answer s by filling in the space to the left of an answer with with one of A B C D or leave it blank if it is not an answer to any of the four questions That is there can be more than one answer for a particular question but each answer goes with at most one question A What are some of the ways a