Week 1

Interfaces

• Use the Collection<E> and List<E> interfaces defined in the Java Collections 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

Related Videos

• Week 1 Outcomes Check / Interfaces Review
• Overview on Generics

Array Based Lists

• Describe key differences between an array and an ArrayList<E> 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)
  • add(int, E)
  • clear()
  • contains(Object)
  • get(int)
  • indexOf(Object)
  • isEmpty()
  • remove(int)
  • remove(Object)
  • set(int, E)
  • size()
  • 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> 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

Related Videos

• ArrayList Physical Demonstration
• ArrayList Overview
• Implementation of ArrayList Class
• java.util.ArrayList versus Our Implementation (also has graphical representation of class)
• Implementation of ArrayList Constructor
• Implementation of ArrayList size()/isEmpty()
• Implementation of ArrayList clear()
• Implementation of ArrayList add(E)
• Talking through ArrayList add(int, E)
• Implementation of ArrayList indexOf(Object)
• Implementation of ArrayList toArray()
• add(int, E)
• contains(Object)
• get(int)
• set(int, E)
• remove(int)
• remove(Object)

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()

Related Videos

• Big-O Introduction (audio only)
• Big-O on ArrayList (audio only)
• Detailed Analysis of areUnique() Method
• Formal Definition of Big-O
• Less detailed Big-O Analysis of areUnique() Method
• Big-O Analysis of a Tweaked areUnique() Method

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)
  • add(int, E)
  • clear()
  • contains(Object)
  • get(int)
  • indexOf(Object)
  • isEmpty()
  • remove(int)
  • remove(Object)
  • set(int, E)
  • size()
  • toArray()
• Describe key differences between a singly linked list and the LinkedList<E> 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

Related Videos

• LinkedList Overview
• Node class and LinkedList Constructor
• isEmpty()/size()

Note: It may be helpful to watch the unit and JUnit testing videos (see week 3 outcomes) before the remaining videos in this list.

• add()
• clear() and description on get()/set()/contains()
• add(int, E) and remove(Object)
• Big-O on LinkedList (audio only) only after doing LinkedList implementation

Week 3

Iterators

• List the methods declared in the Iterator<E> interface
• List the methods declared in the Iterable<E> interface
• Implement the iterator() method in the ArrayList class (returning a fully functional iterator)
• Implement the 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> interface

Related Videos

• Iterable Interface
• Iterator Interface
• Using Iterators
• Iterator Inner Class
• hasNext() Implementation
• next() Implementation
• Enhanced for Loop
• next() Revisited and LinkedList Hand Waving
• remove() Implementation

Java Collections 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

Related Videos

• Java Collections Framework
• Levels of Testing
• Unit Testing
• Testing with JUnit

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> class is implemented in the Java Collections Framework
• Describe the design flaw found in the Stack<E> implementation found in the Java Collections 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

Related Videos

• Stack Introduction
• Stack Review
• Adaptor Class
• Stack Applications

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> 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 Collections 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

Related Videos

• Queue Introduction
• Review of Queue
• Circular 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
• Use the compareTo() method from the Comparable interface to determine which of two objects is bigger
• Write a generic class which implements the Comparable interface appropriately
• Understand and apply recursion in algorithm development

Related Videos

• Intro to recursion
• When to stop / conditional break points
• 1 + 2 + ... + n
• Fibonacci Sequence
• Recursive toString() for arrays
• CodingBat: bunnyEars()
• CodingBat: triangle()
• CodingBat: countHi()
• Binary Search
• O(log n)
• Binary Search Interface with Generics
• Binary Search Implementation
• Running Binary Search and O() Analysis
• RandomAccess Marker Interface

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

Related Videos

• Binary Tree Introduction
• Full, Perfect, and Complete Trees
• Types of Trees
• Tree Traversals
• Application of Tree Traversals

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

Related Videos

• Binary Search Tree Introduction
• Binary Search Tree size()
• Binary Search Tree isEmpty()/clear()
• Binary Search Tree contains()
• Binary Search Tree add()
• In class activity — recursive add()
• Recursive add()
• Binary Search Tree remove()
• BiConsumer Functional Interface

Week 8

Sets and Maps

• Use the Set<E> and Map<K, V> interfaces defined in the Java Collections 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()

Related Videos

• Set<E> Interface
• Map<K, V> Interface
• Weekly Outcomes

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 operations:
  • add or update an element
  • clear the table
  • determine if the table contains the given key
  • determine if the table is empty
  • remove an element from the table
  • count the number of elements in the table
• 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()

Related Videos

• Mapping Objects to Integers
• Introduction to Hashtables
• The HashMap
• Changing the capacity of the Hashtable
• Weekly Outcomes
• Open Addressing
• Outcome Review
• HashTable structure
• size(), isEmpty(), clear(), and Constructor
• contains()
• Aside on String.hashCode()
• Uniqueness of hashCode() values and Q and A
• remove()
• add()
• add() continued

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

Related Videos

• Introduction and Weekly Outcomes
• Tree Rotations
• All Possible Unbalanced Tree Scenarios
• leftRotate() Implementation
• AVL Self-Balancing on add()/remove()
• Introduction/Final Exam Questions (bonus material)
• Red Black Tree Rules (bonus material)
• Red Black Tree Examples (bonus material)

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

Related Videos

• Shallow Copies
• Deeper Copies with Copy Constructor
• Deep Copy with Copy Constructor
• Deep Copy with .clone()
• Problems with .clone()

Videos Reviewing Big O

• Big O Review
• An Aside: O(), Omega(), and Theta()
• Big O for our Data Structures