CS2852
Homework
## Week 2 ### Complete and email to me by 8am Monday of week 2 Start with this implementation of the [`ArrayList.java`](https://gitlab.com/MSOE/y19q3cs2852/blob/c604474c862b314ca13a49b6d3230ccfdc9a588c/src/wk1/ArrayList.java) containing code developed in class. Also note, that implementations of the `indexOf()` and `toArray()` methods were added after class. You are free to implement all of the following, but focus first on the ones based on which side of the class you sat. 1. __Both sides of class__ Implement the `ArrayList.add(int index, E element)` method. 1. __Right side of class__ Implement the `ArrayList.contains(Object target)` method. 1. __Right side of class__ Implement the `ArrayList.get(int index)` method. 1. __Right side of class__ Implement the `ArrayList.set(int index)` method. 1. __Left side of class__ Implement the `ArrayList.remove(int index)` method. 1. __Left side of class__ Implement the `ArrayList.remove(Object target)` method. ### Complete by 8am Tuesday 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](https://taylorial.com/cs2852/Jcf.htm) and prepare questions and feedback for your instructor 1. Study [Array-Based Lists, ArrayList review](https://taylorial.com/cs2852/ArrayList.htm) and prepare questions and feedback for your instructor 1. Study [Generics in Java](https://taylorial.com/cs2852/Generics.htm) and prepare questions and feedback for your instructor ## Week 3 ### Complete by 8am Monday of week 3 - 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$. ### Complete by 8am Tuesday of week 3 - be prepared to ask questions in class 1. Study [Iterators](http://taylorial.com/cs2852/Iterators.htm) and prepare questions and feedback for your instructor 1. Study [Linked Lists](http://taylorial.com/cs2852/LinkedList.htm) 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 Wednesday 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. ### Complete by Friday of week 3 - as preparation for Exam I Start with this implementation of the [`LinkedList.java`](https://gitlab.com/MSOE/y19q3cs2852/blob/88051a45c80df87542b07e7bc037b3ec083c060a/src/wk2/LinkedList.java) containing code developed in class. Also note, that implementation of the `contains(Object)` method was added after class. Implement the following methods: 1. `get(int)` 1. `set(int, E)` 1. `add(int, E)` 1. `remove(int)` 1. `indexOf(Object)` 1. `toArray()` ## 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 ### Complete by 8am Wednesday of week 4 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. Implement the `CircularQueue` class introduced in lecture. ## Week 5 ### Complete by lecture 3 of week 5 - be prepared to ask questions in class 1. Implement a recursive method to create a `String` representation of an array of `String`s. 1. [bunnyEars](http://codingbat.com/prob/p183649) 1. [triangle](http://codingbat.com/prob/p194781) 1. [countHi](http://codingbat.com/prob/p184029) ## Week 6 ### Complete by lecture 1 of week 6 - be prepared to ask questions in class 1. `boolean binarySearch(List<E> list, E target)` which returns true if the `list` contains `target`. You may assume that the list is sorted. 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 7 ### Complete before Monday of week 7 - be prepared to ask questions in class 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. ### Complete before Wednesday of week 7 - be prepared to ask questions in class 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`](https://gitlab.com/MSOE/y19q3cs2852/blob/master/src/wk8/HashTable.java) 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.

Monday, 06-May-2019 07:44:16 CDT