Test 2 ReviewPROBLEM 1 : (Short Ones)A. Why should you use a HashMap rather than a TreeMap? Choose the best answer.I. To conserve memory.II. Because the performance of get and put is betterIII. Because the Java library implementation is optimized.IV. To guarantee that lookups (get) will be faster than inserts (put).V. Because it supports a fast sort implementation.B. Suppose that I take a sorted linked list of N integers, and break it into a list of M equal-sized sortedlists of integers (that is, put the first N/M integers into the first list, the next N/M into the second,etc.). What is the worst-case time for finding whether an integer x is in anywhere in this list of lists?If for some fixed N, you can choose M, what M should you choose for maximum lookup speed?C. In order to use the class Point containing fields x and y in a HashSet, you are considering multiple hashfunctions. Of these hash functions, which one would give the best performance in a HashSet? Assumethat your points are likely to be between (0, 0) and (1280, 1024) (the size of the average computermonitor).A. public int hashCode () { return super.hashCode(); }B. public int hashCode () { return 42; }C. public int hashCode () { return x; }D. public int hashCode () { return x + y; }E. public int hashCode () { return x * 3 + y; }F. public int hashCode () { return x * 1000 + y; }G. Given the following recursive method mystery:int mystery(int n){if (n < 0)return -mystery(-n);else if (n < 10)return n;elsereturn mystery(n/10 + n % 10);}What are would following calls evaluate to?I. mystery(7)II. mystery(-512)H. True or False State whether the following statement is true or false. If false, you should give a specificcounterexample.I. A certain hash table contains N integer keys, all distinct, and each of its buckets contains at mostK elements. Assuming that the hashing function and the equality test require constant time, thetime required to find all keys in the hash table that are between L and U is O(K × (U − L)) inthe worst case.II. Instead of using a heap, we use a sorted ArrayList to represent a priority queue. The worst-casebig-Oh of add and poll do not change.PROBLEM 2 : (Hash (6 pts))In the Markov assignment, the WordNgram class encapsulated N words/strings so that the group of N wordscan be treated as a key in a map.public class WordNgram implements Comparable<WordNgram>{private String[] myWords;[ methods deleted ]/*** Return true if this N-gram is the same as the parameter: all words the same.* @param o is the WordNgram to which this one is compared* @return true if o is equal to this N-gram*/public boolean equals(Object o){WordNgram wg = (WordNgram) o;if (myWords.length != wg.myWords.length)return false;for(int k = 0; k < myWords.length; k++)if (!myWords[k].equals(wg.myWords[k]))return false;return true;}}In this problem, you will answer questions about possible implementations of hashCode.A. Will get and put still work in a HashMap is the WordNGram’s hashCode implementation is as follows?Explain why or why not. What will be the average run-time for get and put if there are n WordNGramsstored in the HashMap.public int hashCode(){// TODO return a better hash valuereturn 15;}2B. Why is the following hashCode implementation flawed?public int hashCode(){int result = 0;for(int k = 0; k < myWords.length; k++)result += myWords[k].hashCode();}PROBLEM 3 : (Reverse (9 points))Each of the Java functions on the left take a string s as input, and returns its reverse. For each of thefollowing, state the recurrence (if applicable) and give the big-Oh complexity bound.Recall that concatenating two strings in Java takes time proportional to the sum of their lengths, andextracting a substring takes constant time.A. public static String reverse1(String s) {int N = s.length();String reverse = ";for (int i = 0; i < N; i++)reverse = s.charAt(i) + reverse;return reverse;}B. public static String reverse2(String s) {int N = s.length();if (N <= 1) return s;String left = s.substring(0, N/2);String right = s.substring(N/2, N);return reverse2(right) + reverse2(left);}C. public static String reverse3(String s) {int N = s.length();char[] a = new char[N];for (int i = 0; i < N; i++)a[i] = s.charAt(N-i-1);return new String(a);}PROBLEM 4 : (Boggle)The game of Boggle is usually played using sixteen letter cubes. A letter cube can be represented as a stringof length 6, one character for each face on the cube. Given a list of letter cubes and a target word, you wantto determine whether it is possible to spell that word using those letter cubes, where each cube can be usedat most once in spelling the word.Examples: given the list of cubes {"etaoin", "shrdlu", "qwerty"}, it is possible to spell the words "as"and law! but not "weld" or "toe".Write a recursive, backtracking method canSpell that takes a target word along with an ArrayList of lettercubes. The function should return true if it is possible to spell the word using the cubes in the list andfalse if otherwise. Assume that the word and letter cubes will only contain lowercase letters.public static boolean canSpell(String word, ArrayList<String> cubes){3PROBLEM 5 : (Puzzle Hunt)You are given a matrix of positive integers to represent a game board, where the (0, 0) entry is the upper leftcorner. The number in each location is the number of squares you can advance in any of the four primarycompass directions, provided that move does not take you off the board. You are interested in the totalnumber of distinct ways one could travel from the upper left corner to the lower right corner, given theconstraint that no single path should ever visit the same location twice.Consider the initial game board to the left, and notice that the upper left corner is occupied by a 2. Thatmeans you can take either two steps to the right, or two steps down (but not two steps to the left or above,because that would carry you off the board). Suppose you opt to go right so that you find yourself in theconfiguration to the right. Problem 3: How Many Permutations Are Words?Below you are given a variation on the code produced in lecture for recursivelygenerating and printing the permutations of a string. You are to make the followingchanges to this function:• Instead of printing, the function should return the number of permutations that forma valid word (as reported by a Lexicon object, just as you did for Boggle).• The function should not count the same word more than once (e.g. if input is"lepap", count the
View Full Document
Unlocking...