CS2852: Data Structures

• If the items are shown as "Due", you must complete them before attending class
• If the items are shown as "Complete by", you are encouraged to complete them prior to attending class, but you may still attend class without completing the assignment

Week 1

Due 7am Friday of week 1, email to your instructor

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².
4. Implement the ArrayList::ArrayListIterator.remove() method.
5. Implement the LinkedList.add(int, E) method.

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

One hour before lecture 2 of week 3, email to your instructor

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

Week 5

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

1. Done in class 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 the previous problem. For example:
   • ((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. Finish implementing the CircularQueue class we began in lecture.
5. 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 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.

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.