CS2852: Data Structures

Week 1

Complete by 8am Friday of week 1 - be prepared to ask questions in class

1. Implement the ArrayList.remove(int index) method.
2. Implement the ArrayList.remove(Object target) method.

Week 2

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

1. Watch Introduction to ArrayLists video and prepare questions and feedback for your instructor
2. Watch Introduction to LinkedLists video and prepare questions and feedback for your instructor
3. Study Collection and List interfaces and prepare questions and feedback for your instructor
4. Study Array-Based Lists, ArrayList review and prepare questions and feedback for your instructor
5. Study Generics in Java and prepare questions and feedback for your instructor

Complete by 8am Friday of week 2 - 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;
   }
   

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

3. Give the Big-O time complexity for T(n) = 8 + 17n + 3n².

Week 3

Complete by lecture 1 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 lecture 2 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.

Week 4

Complete by 8am Monday of week 4 - be prepared to ask questions in class

1. Watch these to screencasts on Big-O time complexity: first and second and prepare questions and feedback for your instructor

Week 5

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

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) — Good
   • ([a + b] + c) — Good
   • (a + {b + c}) — Good
   • ((a + b) + c — Bad
   • ([a + b] + c] — Bad
   • (a + {b + c)} — Bad
2. Finish implementing the CircularQueue class we began in lecture.
3. Implement boolean binarySearch(List<E> list, E target) which returns true if the list contains target. You may assume that the list is sorted. You may not use recursion.

Week 6

1. Implement the size() method (along with a recursive method) for the BST class developed in lecture.
2. Implement the contains() method (along with a recursive method) for the BST class developed in lecture.
3. 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.

Week 7

1. Implement a recursive method, numberOfLeaves() that returns the number of leaf nodes in the tree.
2. Implement a recursive method, max() that returns the largest value of the tree.
3. Implement a recursive method, min() that returns the smallest value of the tree.
4. 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

1. Complete the following methods for the HashTable class we started in lecture: contains(), remove(), clear(), size(), and isEmpty().

Week 9

1. Modify the inner Node class from the BST 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.