# Homework

## Week 1

- CodingBat double23
- CodingBat swapEnds
- CodingBat front11
- 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.

- Implement the
`ArrayList.add(int index, E element)`

method. - Implement the
`ArrayList.contains(Object target)`

method. - Implement the
`ArrayList.get(int index)`

method. - Implement the
`ArrayList.set(int index)`

method. - Implement the
`ArrayList.remove(int index)`

method. - Implement the
`ArrayList.remove(Object target)`

method.

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

- Study Collection and List interfaces and prepare questions and feedback for your instructor
- Study Array-Based Lists, ArrayList review and prepare questions and feedback for your instructor
- 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

- 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; }

- 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; }

- 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

- Study Iterators and prepare questions and feedback for your instructor
- Study Linked Lists and prepare questions and feedback for your instructor
- Implement the
`ArrayList::ArrayListIterator.remove()`

method. - Implement the
`LinkedList.add(int, E)`

method.

### Complete by Wednesday of week 3 - be prepared to ask questions in class

- 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:

`get(int)`

`set(int, E)`

`add(int, E)`

`remove(int)`

`indexOf(Object)`

`toArray()`

## Week 4

### Complete by 8am Wednesday of week 4

- Implement a
`Stack`

class with three methods using an array to store items on the stack:`E push(E element)`

`E peek()`

`E pop()`

- 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

- Implement a
`Queue`

class with three methods using an`LinkedList`

to store items on the queue:`boolean offer(E element)`

`E peek()`

`E poll()`

- 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. - Implement the
`CircularQueue`

class introduced in lecture.

## Week 5

### Complete by lecture 3 of week 5 - be prepared to ask questions in class

- Implement a recursive method to create a
`String`

representation of an array of`String`

s. - bunnyEars
- triangle
- countHi

## Week 6

### Complete by lecture 1 of week 6 - be prepared to ask questions in class

`boolean binarySearch(List<E> list, E target)`

which returns true if the`list`

contains`target`

. You may assume that the list is sorted.- changeXY
- noX
- pairStar
- array220
- countPairs
- nestParen
- strCopies
- groupSum (optional)
- groupSum6 (optional)

## Week 7

### Complete before Monday of week 7 - be prepared to ask questions in class

- Implement the
`size()`

method (along with a recursive method) for the`BinarySearchTree`

class developed in lecture. - Implement the
`contains()`

method (along with a recursive method) for the`BinarySearchTree`

class developed in lecture. - 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. - Implement a recursive method,
`max()`

that returns the largest value of the tree. - 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

- Implement a recursive method,
`numberOfLeaves()`

that returns the number of leaf nodes in the tree. - Just for fun: Implement a recursive method,
`getIthLargest()`

that returns the i^{th}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.

- For the implementations provided, give the Big-O time complexity for the
following methods:
`isEmpty()`

`size()`

`contains()`

`add()`

`remove()`

`clear()`

- Are
`null`

elements allowed in the hash table? - Rewrite any of the methods from the first problem that are not $O(1)$.
- Modify
`add()`

so that the load factor for the hash table never exceeds $0.75$. - Add a method,
`numberOfCollisions()`

, that returns the total number of collisions in the hash table. - Add a method,
`largestBucketSize()`

, that returns the size of the largest bucket. - Add a method,
`numberOfEmptyBuckets()`

, that does what it says. - 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

- 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. - Implement a recursive
`height(Node<E> subroot)`

method that will return the height of the subtree (zero if passed`null`

) - Implement,
`balanceFactor(Node<E> subroot)`

, that returns the difference between the height of the left subtree and the height of the right subtree. - 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. - Assume
`leftRotate()`

has also been implemented. Modify the`add()`

implementation such that the BST does not violate the rules associated with an AVL tree - Give an example of when a deep copy is required. Explain what would go wrong if a shallow copy is performed instead.