<h2>Software Tips and Tricks</h2>
<h3>IntelliJ</h3>
<ul>
<li> <a href="http://screencast.com/t/mv9dUdq6dPK">How to set up the default template</a>
<li>How to put line numbers: Menu: File-> Settings. Tree: Editor -> General -> Appearance. Checkbox: Show line numbers. (Thanks to Pat & Nate for showing me how to do this.)</li>
<li>Print & use shortcuts from <a href='http://www.jetbrains.com/idea/docs/IntelliJIDEA8_ReferenceCard.pdf'>this handy IntelliJ Reference card</a></li>
<li><a href="http://msoe.us/taylor/se1021/Lab1">Using a Jar File that someone else wrote</a> with your code</li>
<li>To set up IntelliJ to not collapse imports to .\*:
<ul>
<li>Go to settings, then Editor -> Code Style -> Java, then the tab "imports".
<li>Find line "Class count to use import with '.\*'". Set to a high number.
</ul>
<li>Creating a Jar File
<ul>
<li><a href="http://screencast.com/t/NwdMml3A4d4">Video of how to create JAR file and ZIP File</a></li>
<li><a href="http://msoe.us/taylor/se1021/1021-0-2">Dr. Taylor's class where he went over this</a></li>
</ul></li>
</ul>
<h2>Week 1</h2>
<!-- Must convert all HTML to mark up or none Changing below above breaks it. -->
<h3>Big-picture: What this class about</h3>
* . Have an idea <bold>what</bold> data-structures look like (roughly)
* . Explain <bold>why</bold> data-structures are so important for computer programs.</li>
### 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
<h3>Acknowledgements</h3>
<p>Original outcomes by <a href="http://msoe.us/taylor/cs2852/Outcomes">Dr. Taylor</a></p>