Homework

Week 1

1. CodingBat double23
2. CodingBat swapEnds
3. CodingBat front11
4. Repeat above problems using ArrayLists 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 Strings.
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 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.

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.