CS2852
Outcomes

Software Tips and Tricks

IntelliJ

Week 1

Big-picture: What this class about

  • . Have an idea what data-structures look like (roughly)
  • . Explain why data-structures are so important for computer programs.

Interfaces

  • . Use the Collection<E> and List<E> 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

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:
  • . 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

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

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> 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> 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> and Map<K, V> 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:
  • 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

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

Acknowledgements

Original outcomes by Dr. Taylor