# Homework

## Week 1

1. CodingBat double23
2. CodingBat swapEnds
3. CodingBat front11
4. Repeat above problems using `ArrayList`s instead of arrays

## Week 2

### Complete and email to me by 8am Monday of week 2

Start with this implementation of the `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. Implement the `ArrayList.add(int index, E element)` method.
2. Implement the `ArrayList.contains(Object target)` method.
3. Implement the `ArrayList.get(int index)` method.
4. Implement the `ArrayList.set(int index)` method.
5. Implement the `ArrayList.remove(int index)` method.
6. Implement the `ArrayList.remove(Object target)` method.

### Complete by 8am Tuesday of week 2 - be prepared to ask questions in class

1. Study Collection and List interfaces and prepare questions and feedback for your instructor
2. Study Array-Based Lists, ArrayList review and prepare questions and feedback for your instructor
3. Study Generics in Java 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 and prepare questions and feedback for your instructor
2. Study Linked Lists and prepare questions and feedback for your instructor
3. Implement the `ArrayList::ArrayListIterator.remove()` method.
4. 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` 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)`
2. `set(int, E)`
3. `add(int, E)`
4. `remove(int)`
5. `indexOf(Object)`
6. `toArray()`

## Week 4

### 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()`
2. 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)` — Good
• `([a + b] + c)` — Good
• `(a + {b + c})` — Good
• `((a + b) + c` — Bad
• `([a + b] + c]` — Bad
• `(a + {b + c)}` — Bad
3. Implement a `Queue` class with three methods using an `LinkedList` to store items on the queue:
• `boolean offer(E element)`
• `E peek()`
• `E poll()`
4. 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.
5. 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.
2. bunnyEars
3. triangle
4. countHi

## 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.
2. changeXY
3. noX
4. pairStar
5. array220
6. countPairs
7. nestParen
8. strCopies
9. groupSum (optional)
10. groupSum6 (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.
2. Implement the `contains()` method (along with a recursive method) for the `BinarySearchTree` class developed in lecture.
3. 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.
4. Implement a recursive method, `max()` that returns the largest value of the tree.
5. 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.
2. Just for fun: Implement a recursive method, `getIthLargest()` that returns the ith 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` class.

1. For the implementations provided, give the Big-O time complexity for the following methods:
• `isEmpty()`
• `size()`
• `contains()`
• `add()`
• `remove()`
• `clear()`
2. Are `null` elements allowed in the hash table?
3. Rewrite any of the methods from the first problem that are not \$O(1)\$.
4. Modify `add()` so that the load factor for the hash table never exceeds \$0.75\$.
5. Add a method, `numberOfCollisions()`, that returns the total number of collisions in the hash table.
6. Add a method, `largestBucketSize()`, that returns the size of the largest bucket.
7. Add a method, `numberOfEmptyBuckets()`, that does what it says.
8. 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.
2. Implement a recursive `height(Node<E> subroot)` method that will return the height of the subtree (zero if passed `null`)
3. Implement, `balanceFactor(Node<E> subroot)`, that returns the difference between the height of the left subtree and the height of the right subtree.
4. 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.
5. Assume `leftRotate()` has also been implemented. Modify the `add()` implementation such that the BST does not violate the rules associated with an AVL tree
6. Give an example of when a deep copy is required. Explain what would go wrong if a shallow copy is performed instead.