midterm2-sol

CS 61B Midterm 2 Spring 2023 Thursday March 16, 2023 Intro: Welcome to CS61B Midterm 2 Solutions! Your name: Solutions Your SID: Login: sp23-s Location: SID of Person to your Left: Right: Write the statement “I have neither given nor received any assistance in the taking of this exam.” below. Signature: Tips: • For answers which involve filling in a ⃝ or □ , please fill in the shape completely. If you change your response, erase as completely as possible . Incomplete marks may affect your score. • ⃝ indicates that only one circle should be filled in. • □ indicates that more than one box may be filled in. • You may not need to use all provided lines, but we will not give credit for solutions that go over number of provided lines. • You may not use ternary operators, lambdas, streams, or multiple assignment. • There may be partial credit for incomplete answers. Write as much of the solution as you can, but bear in mind that we may deduct points if your answers are much more complicated than necessary. • There are a lot of problems on this exam. Work through the ones with which you are comfortable first. Do not get overly captivated by interesting design issues or complex corner cases you’re not sure about. • Not all information provided in a problem may be useful, and you may not need all lines. • Unless otherwise stated, all given code on this exam should compile. All code has been compiled and executed before printing, but in the unlikely event that we do happen to catch any bugs in the exam, we’ll announce a fix. Unless we specifically give you the option, the correct answer is not ‘does not compile’.

Q1: Taiko Time! (1100 Points) public class Taiko { private String name; private int size; public Taiko(String name, int size) { this .name = name; this .size = size; } public String play() { return "BOOM"; } public String getName() { return name; } } public class Chu extends Taiko { public Chu(String name, int size) { super (name, size); } public String play() { return "don kon"; } } public class Shime extends Taiko { public Shime(String name, int size) { super (name, size); } public String play() { return super .play(); } } (a) Suppose that Crystal plans to take out the equipment items one by one, starting from the item she most recently put in. Which data structure should she use? *$ Set *$ LLRB *$ Heap *$ Map '! Stack (b) We will use a Queue to represent the equipment in the organize function below. Crystal would like to categorize each item in equipment as either a Chu or Shime and add it to its respective collection (mapping name to Chu in chus or putting a Shime into shimes ). You may assume that all elements in equipment are Chu s and Shime s. You may destructively alter the attributes of the Queue<> Equipment . public class Cages { private Map<String, Chu> chus = new TreeMap<>(); private Set<Shime> shimes = new HashSet<>(); 2

Q2: BSTIterator (700 Points) (a) Given a Binary Search Tree, if we want to yield the keys in sorted order, what kind of tree traversal should be implemented? . *$ Level-order '! In-Order *$ Pre-order *$ Post-order (b) Given the following BST implementation, complete the BSTIterator implementation such that it yields the keys in sorted order. You may assume that no elements are added or removed to the BST after the iterator is instantiated. You may not instantiate any classes other than Iterator s . Note: Collections.emptyIterator() returns an empty Iterator (not null !). public class BST<K extends Comparable<K>> { private Node root; private class Node { K key; Node left; Node right; Node(K key) { this .key = key; } } public Iterator<K> iterator() { return new BSTIterator( root ); } private class BSTIterator implements Iterator<K> { Iterator<K> iterLeft; K current; Iterator<K> iterRight; BSTIterator(Node n) { if (n == null ) { iterLeft = Collections.emptyIterator(); current = null ; iterRight = Collections.emptyIterator(); } else { iterLeft = new BSTIterator(n.left) ; current = n.key ; iterRight = new BSTIterator(n.right) ; } } 4

@Override public boolean hasNext() { return iterLeft.hasNext() || current != null || iterRight.hasNext() ; } @Override public K next() { if (!hasNext()) { throw new NoSuchElementException(); } if (iterLeft.hasNext()) { return iterLeft.next() ; } else if (current != null ) { K result = current ; current = null ; return result ; } else { return iterRight.next() ; } } } } 5

Q4: Two Tree, Three Tree, Red Tree, Black Tree (1100 Points) Your answer must fit in the box. No points will be awarded for answers outside the box. (a) What is the maximum number of leaf nodes for a 2-3 Tree with height 5? (A tree’s height is the greatest number of edges from the root to a leaf of the tree.) 243 (b) What is the maximum number of elements for a 2-3 Tree with height 4? 242 For parts c - d, consider the following valid 2-3 Tree 5 1 7 8 (c) What is the minimum number of elements to insert to trigger a change in height? 3 (d) What is the maximum number of distinct elements that can be successfully inserted without chang- ing the height of the tree ? 4 For parts e - g, the operations are independent of each other . A single add operation is performed on a Left-Leaning Red-Black Tree. Which of the following are true? (e) If a rotateLeft operation happened, it is immediately followed by a rotateRight operation (i.e. no operations happened between the rotateLeft and rotateRight operation): . *$ Always True '! Sometimes True *$ Never True (f) If a rotateRight operation happened, it is immediately followed by a colorFlip operation (i.e. no operations happened between the rotateRight and colorFlip operation): . '! Always True *$ Sometimes True *$ Never True (g) If a colorFlip operation happened, it is immediately followed by a colorFlip operation. (i.e. no operations happened between the colorFlip and second colorFlip operation): . *$ Always True '! Sometimes True *$ Never True 7

(h) Which of the following are not well-formed 2-3 tree(s)? Select all that apply. . ■ (i) □ (ii) ■ (iii) □ (iv) ■ (v) (i) (ii) (iii) (iv) (v) 8

Q6: Hash-ish (900 Points) Part 1: Classify each of the string hash functions that have no compile errors as follows. Incorrect : The function is not a valid hash function, or is buggy. If this is the case, write 10 words or less explaining why the hash function is invalid. Ineffective : The hash function is valid, but it is easy to find collisions (two words with the same hash, and new words with the same hash as a given word). If you select this, write 2 distinct words less than 6 characters that yield the same hash. Correct : The hash function is valid, and it is not easy to find collisions. You may select this option on only one of the answers below. (a) public int hashCode() { Random random = new Random(); return this .length * random.nextInt(); } '! Incorrect *$ Ineffective *$ Correct Random without seed is nondeterministic (b) public int hashCode() { Random random = new Random( this .hashCode()); return random.nextInt(); } '! Incorrect *$ Ineffective *$ Correct Recursively loop calling hashCode (c) public int hashCode() { return 0; } *$ Incorrect '! Ineffective *$ Correct pot tea (d) public int hashCode() { Random random = new Random(0); int val = 0; for ( char c : this .toCharArray()) { val += c * random.nextInt(); } return val; } *$ Incorrect *$ Ineffective '! Correct (e) public int hashcode() { int val = 0; for ( char c : this .toCharArray()) { val += c; } return val; } *$ Incorrect '! Ineffective *$ Correct tea eat 10

Part 2: You are an evil hacker, and have come across a HashMap of instructor names (which are Strings). • You are able to insert new elements to the HashMap, and time how long it takes for that insertion to run. You may NOT use any other functions of the HashMap, or modify the hash function used. • You know how the HashMap is implemented and the hash function used for strings, but don’t know the data in this particular HashMap. • The HashMap uses linked lists for its bins, and resizes when numberOfElements / numberOfBins exceeds a certain threshold. • The HashMap already has a few values in it before you insert anything. You do not know anything about these values, but you do know that not all of them have the same hash. • You may assume the hash function distributes values evenly. Classify each of the following actions as follows: Possible : It is sometimes impossible to do this if strings use a correct hash function, but it is always possible to do this if strings use an ineffective hash function (per the definition in 1). Impossible : Even if strings use an ineffective hash function, it is sometimes impossible to do this. (a) Determine how many names were originally in the HashMap '! Possible *$ Impossible We can add names repeatedly until a resize occurs. When a resize occurs, the add operation will take significantly longer than normal, so we can time each operation to determine whether it’s a resize or not. Once two or three resizes happen, we can deduce how many names were originally in the list (b) Determine if ”Justin” is in the HashMap, without inserting ”Justin” yourself *$ Possible '! Impossible With the restrictions we’ve provided, it is impossible to distinguish ”Justin” from another value that has the same hash. Therefore, we can’t determine for sure if ”Justin” is in the table. (c) Make it arbitrarily slow for other people to access any name in the HashMap *$ Possible '! Impossible Since accesses are amortized constant, we can only do this if we knew the hashes of all elements originally in the table. It’s impossible to get that data, so this is impossible. (d) Assume that ”Justin” and ”Josh” were already inserted into the HashMap. Make it arbitrarily slow to access ”Justin”, but still fast to access ”Josh” (assuming that ”Justin” and ”Josh” have the same hash) *$ Possible '! Impossible Since ”Josh” and ”Justin” are already in the table, they start off a fixed distance from each other in their linked list bucket. We can try to add more elements with the same hash, but we can’t get them between existing elements, so accessing ”Justin” and ”Josh” will always take about the same amount of time. 11

Q7: SHeap (900 Points) We are given the following array representing a min-heap containing 7 values, where each symbol rep- resents a distinct number . There is no implicit ordering with the symbols. The last array position is initially unused. (For convenience, we have numbered the array elements starting from 1 rather than 0) Index 0 1 2 3 4 5 6 7 8 Value NULL ! @ # $ % ? & Answer the following questions about the heap after removing the minimum value. (a) Which indice(s) might contain the value & in the resulting min-heap? □ 1 ■ 2 ■ 3 ■ 4 ■ 5 ■ 6 □ 7 □ 8 (b) Which indice(s) might contain the value % in the resulting min-heap? □ 1 ■ 2 □ 3 □ 4 ■ 5 □ 6 □ 7 □ 8 (c) Which symbol(s) could be at index 4 in the resulting heap? □ ! □ @ □ # ■ $ □ % □ ? ■ & Now return to the original heap (without the min element removed). Suppose we want to insert the element ✓ into the heap. (d) Where in the array (at what indices) might ✓ end up? ■ 1 ■ 2 □ 3 ■ 4 □ 5 □ 6 □ 7 ■ 8 (e) Which symbols(s) could be at index 2 in the resulting min-heap? ■ ! ■ @ □ # □ $ □ % □ ? □ & ■ ✓ (f) Which indice(s) in the resulting array might contain the 3rd smallest value? □ 1 ■ 2 ■ 3 ■ 4 ■ 5 ■ 6 ■ 7 □ 8 13

Q8: Combinatorial Explosion (1500 Points) Consider the following functions: public static int multiply( int a, int b) { int val = 0; for ( int i = 0; i < a; i += 1) { val = val + b; } return val; } public static int fact( int n) { if (n == 0) { return 1; } return multiply(n, fact(n - 1)); } public static int multiplyAll(List<Integer> lst) { Stack<Integer> values = new Stack<>(lst); while (values.size() > 1) { int i = values.remove(); int j = values.remove(); values.insert(multiply(i, j)); } return values.remove(); } public static int grahamHelper( int base, int pow, int iter) { if (iter == 0) { return multiply(base, pow); } if (pow == 0) { return base; } return grahamHelper(base, grahamHelper(base, pow - 1, iter), iter - 1); } public static int grahamCracker( int n) { g = grahamHelper(3, 3, 4); for ( int i = 1; i < 64; i += 1) { g = grahamHelper(3, 3, g); } return g; } 14

The previous functions are copied to this page for your convenience: public static int multiply( int a, int b) { int val = 0; for ( int i = 0; i < a; i += 1) { val = val + b; } return val; } public static int fact( int n) { if (n == 0) { return 1; } return multiply(n, fact(n - 1)); } public static int multiplyAll(List<Integer> lst) { Stack<Integer> values = new Stack<>(lst); while (values.size() > 1) { int i = values.remove(); int j = values.remove(); values.insert(multiply(i, j)); } return values.remove(); } public static int grahamHelper( int base, int pow, int iter) { if (iter == 0) { return multiply(base, pow); } if (pow == 0) { return base; } return grahamHelper(base, grahamHelper(base, pow - 1, iter), iter - 1); } public static int grahamCracker( int n) { g = grahamHelper(3, 3, 4); for ( int i = 1; i < 64; i += 1) { g = grahamHelper(3, 3, g); } return g; } 16

What would the asymptotic runtime of this program be if we make the following changes? Each subpart is independent; changes made in an earlier subpart do not propagate to later subparts. (d) What is the asymptotic runtime of fact in terms of N if the definition of multiply was replaced with the following line: return a * b; ? *$ Θ(1) *$ Θ(log N ) '! Θ( N ) *$ Θ( N log N ) *$ Θ( N 2 ) *$ Θ(( N − 1)!) *$ Θ( N !) *$ Θ(2 N ) *$ Θ( N N − 1 ) *$ Θ( N N ) This reduces multiplication runtime to Θ(1), so we can compute the factorial in Θ( N ) time. (e) Which of the following correctly describes the runtime of fact in terms of N if we swapped the arguments of multiply , so that the last line read return multiply(fact(n-1), n); ? Select all that apply. □ Θ(1) □ Θ(log N ) □ Θ( N ) □ Θ( N log N ) □ Θ( N 2 ) ■ Θ(( N − 1)!) □ Θ( N !) □ Θ(2 N ) □ Θ( N N − 1 ) □ Θ( N N ) □ O (1) □ O (log N ) □ O ( N ) □ O ( N log N ) □ O ( N 2 ) ■ O (( N − 1)!) ■ O ( N !) □ O (2 N ) ■ O ( N N − 1 ) ■ O (( N N ) If we reorder the inputs, we instead call multiply on inputs 1 , 2! , 3! , · · · , ( N − 1)!. This grows exponen- tially, so the sum is Θ(( N − 1)!). A few things to note here: Θ(( N − 1)!) is NOT the same as Θ( N !), since they differ by a factor of N . Further, 2 N grows slower than N !, since N ! = N ∗ ( N − 1) ∗ ... , while 2 N = 2 ∗ 2 ∗ ... ; all the components of N ! grow much larger than 2. (f) Which of the following correctly describe the best-case and worst-case asymptotic runtime of multiplyAll in terms of N , if we replaced the stack with a queue . As before, lst has N elements, all of which are less than N . Select all that apply. Best Case: □ Θ(1) □ Θ(log N ) ■ Θ( N ) □ Θ( N log N ) □ Θ( N 2 ) □ Θ(( N − 1)!) □ Θ( N !) □ Θ(2 N ) □ Θ( N N − 1 ) □ Θ( N N ) □ O (1) □ O (log N ) ■ O ( N ) ■ O ( N log N ) ■ O ( N 2 ) ■ O (( N − 1)!) ■ O ( N !) ■ O (2 N ) ■ O ( N N − 1 ) ■ O (( N N ) As before, the best case is when all elements are 1, in which case all multiplications are just 1 ∗ 1, which runs in constant time; thus, our runtime is Θ( N ) Worst Case: □ Θ(1) □ Θ(log N ) □ Θ( N ) □ Θ( N log N ) □ Θ( N 2 ) □ Θ(( N − 1)!) □ Θ( N !) □ Θ(2 N ) □ Θ( N N − 1 ) □ Θ( N N ) □ O (1) □ O (log N ) □ O ( N ) □ O ( N log N ) □ O ( N 2 ) ■ O (( N − 1)!) ■ O ( N !) □ O (2 N ) ■ O ( N N − 1 ) ■ O ( N N ) Our worst-case runtime would be when all elements are N; in this case, the queue does affect our asymptotic runtime. Assume first that N is a power of 2. The first N/ 2 steps multiply N ∗ N , and yield a queue with N/ 2 elements, each of which are N 2 . Similarly, the next N/ 4 steps multiply N 2 ∗ N 2 , and yield a queue with N/ 4 elements, each of which are N 4 , and so on. We can draw this as a complete binary tree, where the leaf nodes are the original N elements, and all other nodes signify the result of multiplying the two children, as in the following image. For simplicity, we have labeled each node with the result of its multiplication 17

Nothing on this page is worth any points. Q9: 61Brief 61Battle (0 Points) The shortest recorded war in history happened in 1896 and lasted for only 38 minutes, after which one side surrendered. What were the 2 countries involved in the war? United Kingdom and Zanzibar Sultanate Q10: Compensation (0 Points) We forgot a fun question on the last exam, so now you get two! Find a polynomial with integer coefficients that is satisfied by 2 + √ 3 but is NOT satisfied by 2 − √ 3, or prove that no such polynomial exists. No such polynomial exists. Let k = 2 + √ 3, j = 2 − √ 3. Then k 2 = 7 + 4 √ 3, so k 2 − 4 k + 1 = 0. Let f ( x ) be a polynomial with integer coefficients such that f ( k ) = 0, and let g ( x ) = x 2 − 4 x + 1. By polynomial division, f ( x ) = g ( x ) ∗ h ( x ) + r ( x ) for some polynomial h with integer coefficients and some polynomial r with integer coefficients and degree 1 or less. Then f ( k ) = g ( k ) ∗ h ( k ) + r ( k ) = 0 ∗ h ( k ) + r ( k ), so r ( k ) = 0. If r ( x ) = a + bx , then 0 = a + bk , so either a = b = 0, or k is rational. k is not rational, so r ( x ) = 0. Thus, f ( j ) = g ( j ) ∗ h ( j ) + r ( j ) = 0 ∗ h ( j ) + 0 = 0. Feedback (0 Points) Leave any feedback, comments, concerns, or drawings below! Mitchell Lane 19