CS2852
Homework
## Week 1 ### Complete by 8am Friday of week 1 - be prepared to ask questions in class 1. Implement the `ArrayList.remove(int index)` method. 1. Implement the `ArrayList.remove(Object target)` method. ## Week 2 ### Complete by 8am Monday of week 2 - be prepared to ask questions in class 1. Watch [Introduction to ArrayLists video](lectures/2852arrayListIntro.mp4) and prepare questions and feedback for your instructor 1. Watch [Introduction to LinkedLists video](lectures/2852linkedListIntro.mp4) and prepare questions and feedback for your instructor 1. Study [Collection and List interfaces](http://msoe.taylorial.com/cs2852/Jcf) and prepare questions and feedback for your instructor 1. Study [Array-Based Lists, ArrayList review](http://msoe.taylorial.com/cs2852/ArrayList) and prepare questions and feedback for your instructor 1. Study [Generics in Java](http://msoe.taylorial.com/cs2852/Generics) and prepare questions and feedback for your instructor ### Complete by 8am Friday of week 2 - be prepared to ask questions in class 1. Give the Big-O time complexity for the following algorithm. Justify your answer. ``` public static boolean areUnique(List<String> strings) { boolean areUnique = true; for(int i=0; areUnique && i<strings.size(); ++i) { for(int j=0; areUnique && j<strings.size(); ++j) { if(i!=j && strings.get(i).equals(strings.get(j)) { areUnique = false; } } } return areUnique; } ``` 1. Give the Big-O time complexity for the following algorithm. Justify your answer. ``` public static boolean areUnique(List<String> strings) { boolean areUnique = true; for(int i=0; areUnique && i<strings.size(); ++i) { for(int j=i+1; areUnique && j<strings.size(); ++j) { if(strings.get(i).equals(strings.get(j)) { areUnique = false; } } } return areUnique; } ``` 1. Give the Big-O time complexity for $T(n) = 8 + 17n + 3n^2$. ## Week 3 ### Complete by lecture 1 of week 3 - be prepared to ask questions in class 1. Study [Iterators](http://msoe.taylorial.com/cs2852/Iterators) and prepare questions and feedback for your instructor 1. Study [Linked Lists](http://msoe.taylorial.com/cs2852/LinkedList) and prepare questions and feedback for your instructor 1. Implement the `ArrayList::ArrayListIterator.remove()` method. 1. Implement the `LinkedList.add(int, E)` method. ### Complete by lecture 2 of week 3 - be prepared to ask questions in class 1. Implement the `LinkedList.iterator()` method and the complete inner class that implements the `Iterator` interface. ## Week 4 ### Complete by 8am Monday of week 4 1. Watch these two screencasts on Big-O time complexity: [first](lectures/2852-bigOa.mp4) and [second](lectures/2852-bigOb.mp4) and prepare questions and feedback for your instructor ## Week 5 ### Complete by lecture 1 of week 5 - be prepared to ask questions in class 1. Implement a `Stack` class with three methods using an array to store items on the stack: * `E push(E element)` * `E peek()` * `E pop()` 1. Implement a method, `parenChecker`, that accepts a `String` and returns `true` if the parenthesization is legal. The method must make use of the `Stack` developed in lecture. * `((a + b) + c)` &mdash; Good * `([a + b] + c)` &mdash; Good * `(a + {b + c})` &mdash; Good * `((a + b) + c` &mdash; Bad * `([a + b] + c]` &mdash; Bad * `(a + {b + c)}` &mdash; Bad 1. Implement a `Queue` class with three methods using an `LinkedList` to store items on the queue: * `boolean offer(E element)` * `E peek()` * `E poll()` 1. Implement a `Stack` class with three methods using a `Node` class that stores a reference to an element and the node below it in the stack. 1. Finish implementing the `CircularQueue` class we began in lecture. ### Complete by lecture 3 of week 5 - be prepared to ask questions in class 1. Implement `boolean binarySearch(List<E> list, E target)` which returns true if the `list` contains `target`. You may assume that the list is sorted. 1. [bunnyEars](http://codingbat.com/prob/p183649) 1. [triangle](http://codingbat.com/prob/p194781) 1. [countHi](http://codingbat.com/prob/p184029) 1. [changeXY](http://codingbat.com/prob/p101372) 1. [noX](http://codingbat.com/prob/p118230) 1. [pairStar](http://codingbat.com/prob/p158175) 1. [array220](http://codingbat.com/prob/p173469) 1. [countPairs](http://codingbat.com/prob/p154048) 1. [nestParen](http://codingbat.com/prob/p183174) 1. [strCopies](http://codingbat.com/prob/p118182) 1. [groupSum](http://codingbat.com/prob/p145416) (optional) 1. [groupSum6](http://codingbat.com/prob/p199368) (optional) ## Week 6 ### Complete before lab of week 6 - be prepared to answer quiz questions related to these 1. Implement the `size()` method (along with a recursive method) for the `BinarySearchTree` class developed in lecture. 1. Implement the `contains()` method (along with a recursive method) for the `BinarySearchTree` class developed in lecture. 1. Implement the `toString()` method (along with a recursive method) for the `BinarySearchTree` class developed in lecture that returns a string containing all of the elements in sorted order. 1. Implement a recursive method, `max()` that returns the largest value of the tree. 1. Implement a recursive method, `min()` that returns the smallest value of the tree. ## Week 7 1. Implement a recursive method, `numberOfLeaves()` that returns the number of leaf nodes in the tree. 1. Just for fun: Implement a recursive method, `getIthLargest()` that returns the i<sup>th</sup> largest value of the tree. [This one is a bit more challenging. You would not be expected implement this on a quiz or exam.] ## Week 8 All of these questions are related to the [`HashTable`](HashTable.pdf) class. 1. For the implementations provided, give the Big-O time complexity for the following methods: * `isEmpty()` * `size()` * `contains()` * `add()` * `remove()` * `clear()` 1. Are `null` elements allowed in the hash table? 1. Rewrite any of the methods from the first problem that are not $O(1)$. 1. Modify `add()` so that the load factor for the hash table never exceeds $0.75$. 1. Add a method, `numberOfCollisions()`, that returns the total number of collisions in the hash table. 1. Add a method, `largestBucketSize()`, that returns the size of the largest bucket. 1. Add a method, `numberOfEmptyBuckets()`, that does what it says. 1. Add a method, `setLoadFactor()`, that will change the load factor threshold for the hash table and ensure that the current hash table does not exceed the threshold. ## Week 9 1. Modify the inner `Node` class from the `BinarySearchTree` class to have one addtional attribute: `Node<E> parent`, that refers to the parent of the node. 1. Implement a recursive `height(Node<E> subroot)` method that will return the height of the subtree (zero if passed `null`) 1. Implement, `balanceFactor(Node<E> subroot)`, that returns the difference between the height of the left subtree and the height of the right subtree. 1. Implement `rightRotate(Node<E> subroot)`, which performs a right rotation around `subroot` and returns a reference to the node that takes the place of `subroot` in the tree. 1. Assume `leftRotate()` has also been implemented. Modify the `add()` implementation such that the BST does not violate the rules associated with an AVL tree 1. Give an example of when a deep copy is required. Explain what would go wrong if a shallow copy is performed instead. <!--- --->

Thursday, 10-May-2018 17:17:52 EDT