CS2852
Data Structures
## Week 1 ### Interfaces * Use the [`Collection<E>`](http://docs.oracle.com/javase/8/docs/api/java/util/Collection.html) and [`List<E>`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html) interfaces defined in the Java Collection Framework * Explain when to use `Collection<E>` instead of `List<E>` and vice versa * Demonstrate correct use of generics when declaring `Collection<E>` and `List<E>` interfaces * Describe the implications of an interface extending another interface * List two classes that implement the `Collection<E>` interface * List two classes that implement the `List<E>` interface ### Array Based Lists * Describe key differences between an array and an [`ArrayList<E>`](http://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html) object * Implement classes and methods that make use of generics * Write an array-based implementation of the `List<E>` interface, including the following methods: * [`add(E)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#add-E-) * [`add(int, E)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#add-int-E-) * [`clear()`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#clear--) * [`contains(Object)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#contains-java.lang.Object-) * [`get(int)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#get-int-) * [`indexOf(Object)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#indexOf-java.lang.Object-) * [`isEmpty()`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#isEmpty--) * [`remove(int)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#remove-int-) * [`remove(Object)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#remove-java.lang.Object-) * [`set(int, E)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#set-int-E-) * [`size()`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#size--) * [`toArray()`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#toArray--) * Implement small software systems that use one or more `ArrayList<E>` objects * Describe key differences between the in class implementation and the [`java.util.ArrayList<E>`](http://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html) implementation * Describe differences in the `java.util.ArrayList` implementation compared to the one created in lecture that affect the asymptotic time complexity of any of the methods ## Week 2 ### Big-O Notation and Algorithm Efficiency * Explain the purpose of Big-O notation * Describe the limitations of Big-O notation * Be familiar with the formal definition of Big-O * Using Big-O notation, determine the asymptotic time complexity of an algorithm with a conditional * Using Big-O notation, determine the asymptotic time complexity of an algorithm with a loop * Determine the asymptotic time complexity of an algorithm with a nested loop * Using Big-O notation, determine the asymptotic time complexity of an algorithm that calls other methods with known asymptotic time complexity * Use time complexity analysis to choose between two competing algorithms * Describe the meaning of the following symbols: **T(n)**, **f(n)**, and **O(f(n))** * Given **T(n)** expressed as a polynomial, determine the Big-O notation * Determine the asymptotic time complexity of the following methods from the `ArrayList<E>` class: `add(E)`, `add(int, E)`, `clear()`, `contains(Object)`, `get(int)`, `indexOf(Object)`, `isEmpty()`, `remove(int)`, `remove(Object)`, `set(int, E)`, and `size()` ### Linked Lists * Describe key differences between an array based list and a linked list * Describe advantages and disadvantages of a singly linked list verses a doubly linked list * Write an singly linked list implementation of the `List<E>` interface, including the following methods: * [`add(E)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#add-E-) * [`add(int, E)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#add-int-E-) * [`clear()`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#clear--) * [`contains(Object)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#contains-java.lang.Object-) * [`get(int)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#get-int-) * [`indexOf(Object)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#indexOf-java.lang.Object-) * [`isEmpty()`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#isEmpty--) * [`remove(int)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#remove-int-) * [`remove(Object)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#remove-java.lang.Object-) * [`set(int, E)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#set-int-E-) * [`size()`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#size--) * [`toArray()`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#toArray--) * Describe key differences between a singly linked list and the [`LinkedList<E>`](http://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html) class * Determine the asymptotic time complexity of the following methods from a singly linked list class developed in lecture: `add(E)`, `add(int, E)`, `clear()`, `contains(Object)`, `get(int)`, `indexOf(Object)`, `isEmpty()`, `remove(int)`, `remove(Object)`, `set(int, E)`, and `size()` * Describe differences in the JCF `LinkedList` implementation compared to the one created in lecture that affect the asymptotic time complexity of any of the methods * Implement small software systems that use one or more `LinkedList<E>` objects ## Week 3 ### Iterators * List the methods declared in the [`Iterator<E>`](http://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html) interface * List the methods declared in the [`Iterable<E>`](http://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html) interface * Implement the [`iterator()`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#iterator--) method in the `ArrayList` class (returning a fully functional iterator) * Implement the [`iterator()`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#iterator--) method in the `LinkedList` class (returning a fully functional iterator) * Explain why the enhanced for loop only works on classes that implement the `Iterable<E>` interface * Be familiar with the [`ListIterator<E>`](http://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html) interface ### Java Collection Framework and Testing * Explain the purpose of the Java Collections Framework * Be familiar with class/interface hierarchy for the Java Collections Framework * Describe the following levels of testing: unit, integration, system, and acceptance * Describe the differences between black-box testing and white-box testing * List advantages and disadvantages of black-box testing verses white-box testing * Develop tests that test boundary conditions ## Week 4 ### Stacks * Enumerate and explain the methods that are part of a **pure stack** interface * Define LIFO and explain how it relates to a stack * Explain how the [`Stack<E>`](http://docs.oracle.com/javase/8/docs/api/java/util/Stack.html) class is implemented in the Java Collection Framework * Describe the design flaw found in the `Stack<E>` implementation found in the Java Collection Framework * Implement a class that provides an efficient implementation of the pure stack interface using an `ArrayList<E>` * Implement a class that provides an efficient implementation of the pure stack interface using a `LinkedList<E>` * Define the term **adaptor class** and be able to implement a simple adaptor class, e.g., stack, queue * Implement small software systems that use one or more stack data structures * List at least two examples of when it makes sense to use a `Stack` ## Week 5 ### Queues * Enumerate and explain the methods that are part of a **pure queue** interface * Define FIFO and explain how it relates to a queue * The [`Queue<E>`](http://docs.oracle.com/javase/8/docs/api/java/util/Queue.html) interface has multiple methods for insertion, removal, and accessing the front element. Describe how these methods differ. * Describe the design flaw found in the `Queue<E>` interface found in the Java Collection Framework * Implement a class that provides an efficient implementation of the pure queue interface using a `LinkedList<E>` * Explain why an `ArrayList<E>` is not an appropriate choice when implementing a pure queue interface * Explain how a circular queue differs from a standard queue * Implement a class that provides an efficient implementation of a circular queue using an array * Implement small software systems that use one or more queue data structures * List at least two examples of when it makes sense to use a `Queue` ### Recursion * For a given input, determine how many times a recursive method will call itself * Explain the role of the base case and recursive step in recursive algorithms * Use recursion to traverse a list * Use recursion to search a sorted array * Understand and apply recursion in algorithm development ## Week 6 ### Binary Trees * Use the following terms to describe nodes in a tree: root, children, parent, sibling, leaf, ancestor, descendent * Recognize empty trees and contents after any branch to be trees themselves, specifically subtrees * Define node level recursively, starting with level 1 at the root. Define height as the maximum node level * Define binary tree (contrasted with a general tree) and explain the use of common types of binary trees: expression trees, Huffman trees, binary search trees * Explain the criteria for binary trees that are full, perfect, and complete * Explain preorder, inorder, and postorder traversal of trees using words and figures * Explain the significance of each of these orders when applied to expression trees ### Binary Tree Implementation * Develop a `BinaryTree<E>` class with no-arg, one-arg (root node) and 3-arg (root node as well as left and right subtrees) constructors * Implement `BinaryTree<E>` methods: get{Left,Right}Subtree, isLeaf, and preOrderTraverse/toString methods ## Week 7 ### Binary Search Trees * Define the ordered relationship between parent and child nodes * Implement a recursive `contains()` method * Implement a recursive `size()` method * Implement a recursive `height()` method * Describe how elements are added to a binary search tree * Describe how elements are removed from a binary search tree ## Week 8 ### Sets and Maps * Use the [`Set<E>`](http://docs.oracle.com/javase/8/docs/api/java/util/Set.html) and [`Map<K, V>`](http://docs.oracle.com/javase/8/docs/api/java/util/Map.html) interfaces defined in the Java Collection Framework * Choose the appropriate interface to use from the following choices: `Collection<E>`, `List<E>`, `Set<E>`, and `Map<K, V>` * List two classes that implement the `Map<K, V>` interface * Interpret and write Java code using the `TreeMap` and `TreeSet` classes * State and explain the asymptotic time complexity of the following methods from a `TreeSet`: `add(E)`, `clear()`, `contains(Object)`, `isEmpty()`, `remove(Object)`, and `size()` ### Hash Tables * Describe how elements are added to a hash table * Describe how elements are removed from a hash table * Explain the **capacity** of a hash table and how it is used * Define the **load factor** of a hash table and explain how it is used * Define a **collision** as it relates to hash tables and describe ways of coping with collisions * Describe the **open addressing** method for dealing with collisions within a hash table * Describe the **chaining** method for dealing with collisions within a hash table * Write a hash table implementation (using chaining) that includes the following methods: * [`add(E)`](http://docs.oracle.com/javase/8/docs/api/java/util/Set.html#add-E-) * [`clear()`](http://docs.oracle.com/javase/8/docs/api/java/util/Set.html#clear--) * [`contains(Object)`](http://docs.oracle.com/javase/8/docs/api/java/util/Set.html#contains-java.lang.Object-) * [`isEmpty()`](http://docs.oracle.com/javase/8/docs/api/java/util/Set.html#isEmpty--) * [`remove(Object)`](http://docs.oracle.com/javase/8/docs/api/java/util/Set.html#remove-java.lang.Object-) * [`size()`](http://docs.oracle.com/javase/8/docs/api/java/util/Set.html#size--) * Explain why the `Object.hashCode()` method must be overridden if the `Object.equals()` method is overridden * Describe the criteria for a good `hashCode()` implementation * Interpret and develop simple hashing functions * Interpret and write Java code using the `HashMap` and `HashSet` classes * State and explain the asymptotic time complexity of the following methods from a `HashSet`: `add(E)`, `clear()`, `contains(Object)`, `isEmpty()`, `remove(Object)`, and `size()` ## Week 9 ### Balanced Trees * Describe the impact that balance has on the performance of binary search trees * Implement the `leftRotate()` and `rightRotate()` methods for a binary tree * Explain the mechanism used in AVL trees to ensure that they remain balanced * Illustrate the steps required to balance an AVL tree upon insertion of an additional element <!--- * List the invariants associated with Red-Black trees * Explain how the Red-Black tree invariants maintain a binary search tree with O(log n) performance for `add()`, `contains()`, and `remove()` * Illustrate the steps required to balance a Red-Black tree upon insertion of an additional element ---> ### Deep verses Shallow Copies * Distinguish between copying a reference and copying an object * Demonstrate proper use of `==` and `.equals()` * Describe approaches to making deep copies, e.g., `clone()` and copy constructors

Tuesday, 20-Feb-2018 05:56:50 EST