Homework

Week 1

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

Week 2

Start with this implementation of the ArrayList.java developed in class.

1. Implement the ArrayList.set(int index) method.
2. Implement the ArrayList.remove(int index) method.
3. Implement the ArrayList.toArray() method.

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 \).

2. Study Linked Lists and prepare questions and feedback for your instructor Start with the LinkedList.java the code developed in class. Implement the following methods:

3. get(int)

4. set(int, E)

5. add(int, E)

6. contains(Object)

7. remove(int)

8. remove(Object)

9. indexOf(Object)

10. toArray()

11. Study Iterators and prepare questions and feedback for your instructor

12. Implement the ArrayList::ArrayListIterator.remove() method.

13. Implement the LinkedList.iterator() method and the complete inner class that implements the Iterator interface.

Week 4

Complete before Exam I

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

Week 5

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()
2. Implement the CircularQueue class introduced in lecture.
3. Implement a recursive method to create a String representation of an array of Strings.
4. bunnyEars
5. triangle
6. countHi

Week 6

In preparation for the week 6 quiz

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

1. Provide the asymptotic time complexity (and justification) for the following methods of the BST class developed in lecture: contains(), add(), size(), and height(). Provide answers for a BST that is balance and not balanced.
2. Implement the toString() method (along with a recursive method) for the BST class developed in lecture that returns a string containing all of the elements in sorted order.
3. Implement a recursive method, max() that returns the largest value of the tree.
4. Implement a recursive method, min() that returns the smallest value of the tree.
5. Implement a recursive method, numberOfLeaves() that returns the number of leaf nodes in the tree.
6. 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.]