CS2852
Outcomes
<h2>Software Tips and Tricks</h2> <h3>IntelliJ</h3> <ul> <li>How to set up the editor so it's more like Word or Notepad when you click on line-endings. Just use Ctl-Right, Ctl-Left. Or ask me.</li> <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->Appearance. Checkbox: Show line numbers. (Thanks to Pat & Nate for showing me how to do this.)</li> <li>Print &amp; 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 -&gt; Code Style -&gt; 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> * (&#x2713;) Have an idea <bold>what</bold> data-structures look like (roughly) * (&#x2713;) Explain <bold>why</bold> data-structures are so important for computer programs.</li> ### Interfaces * (&#x2713;) 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 * (&#x2713;) Explain when to use `Collection<E>` instead of `List<E>` and vice versa * (&#x2713;) Demonstrate correct use of generics when declaring `Collection<E>` and `List<E>` interfaces * (&#x2713;) Describe the implications of an interface extending another interface * (&#x2713;) List two classes that implement the `Collection<E>` interface * (&#x2713;) List two classes that implement the `List<E>` interface ### Array Based Lists * (&#x2713;) Describe key differences between an array and an [`ArrayList<E>`](http://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html) object * (&#x2713;) Implement classes and methods that make use of generics * (&#x2713;) Write an array-based implementation of the `List<E>` interface, including the following methods: * (&#x2713;) [`add(E)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#add-E-) * (&#x2713;) [`add(int, E)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#add-int-E-) * (&#x2713;) [`clear()`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#clear--) * (&#x2713;) [`contains(Object)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#contains-java.lang.Object-) * (&#x2713;) [`get(int)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#get-int-) * (&#x2713;) [`indexOf(Object)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#indexOf-java.lang.Object-) * (&#x2713;) [`isEmpty()`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#isEmpty--) * (&#x2713;) [`remove(int)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#remove-int-) * (&#x2713;) [`remove(Object)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#remove-java.lang.Object-) * (&#x2713;) [`set(int, E)`](http://docs.oracle.com/javase/8/docs/api/java/util/List.html#set-int-E-) * (&#x2713;) [`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--) * (&#x2713;) Implement small software systems that use one or more `ArrayList<E>` objects * (&#x2713;) 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 * (&#x2713;) 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 * (&#x2713;) Explain the purpose of Big-O notation * (&#x2713;) Describe the limitations of Big-O notation * (&#x2713;) Be familiar with the formal definition of Big-O * (&#x2713;) Using Big-O notation, determine the asymptotic time complexity of an algorithm with a conditional * (&#x2713;) Using Big-O notation, determine the asymptotic time complexity of an algorithm with a loop * (&#x2713;) 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 * (&#x2713;) Use time complexity analysis to choose between two competing algorithms * (&#x2713;) Describe the meaning of the following symbols: **T(n)**, **f(n)**, and **O(f(n))** * (&#x2713;) Given **T(n)** expressed as a polynomial, determine the Big-O notation * (&#x2713;) 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 * (&#x2713;) Describe key differences between an array based list and a linked list * (&#x2713;) Describe advantages and disadvantages of a singly linked list verses a doubly linked list * (&#x2713;) 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--) * (&#x2713;) 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 * (&#x2713;) 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()` * (&#x2713;) 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 * (&#x2713;) Implement small software systems that use one or more `LinkedList<E>` objects ## Week 3 ### Iterators * (&#x2713;) List the methods declared in the [`Iterator<E>`](http://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html) interface * (&#x2713;) 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) * (&#x2713;) 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) * (&#x2713;) 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 * (&#x2713;) Explain the purpose of the Java Collections Framework * Be familiar with class/interface hierarchy for the Java Collections Framework * (&#x2713;) Describe the following levels of testing: unit, integration, system, and acceptance * (&#x2713;) Describe the differences between black-box testing and white-box testing * (&#x2713;) List advantages and disadvantages of black-box testing verses white-box testing * (&#x2713;) Develop tests that test boundary conditions ## Week 4 ### Stacks * (&#x2713;) Enumerate and explain the methods that are part of a **pure stack** interface * (&#x2713;) Define LIFO and explain how it relates to a stack * (&#x2713;) 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 * (&#x2713;) Describe the design flaw found in the `Stack<E>` implementation found in the Java Collection Framework * (&#x2713;) 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 * (&#x2713;) Implement small software systems that use one or more stack data structures * (&#x2713;) List at least two examples of when it makes sense to use a `Stack` ## Week 5 ### Queues * (&#x2713;) Enumerate and explain the methods that are part of a **pure queue** interface * (&#x2713;) Define FIFO and explain how it relates to a queue * (&#x2713;) 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. * (&#x2713;) Describe the design flaw found in the `Queue<E>` interface found in the Java Collection Framework * (&#x2713;) Implement a class that provides an efficient implementation of the pure queue interface using a `LinkedList<E>` * (&#x2713;) Explain why an `ArrayList<E>` is not an appropriate choice when implementing a pure queue interface * (&#x2713;) Explain how a circular queue differs from a standard queue * (&#x2713;) Implement a class that provides an efficient implementation of a circular queue using an array * (&#x2713;) Implement small software systems that use one or more queue data structures * (&#x2713;) List at least two examples of when it makes sense to use a `Queue` ### Recursion * (&#x2713;) For a given input, determine how many times a recursive method will call itself * (&#x2713;) Explain the role of the base case and recursive step in recursive algorithms * (&#x2713;) Use recursion to traverse a list * (&#x2713;) Use recursion to search a sorted array * (&#x2713;) Understand and apply recursion in algorithm development ## Week 6 ### Binary Trees * (&#x2713;) Use the following terms to describe nodes in a tree: root, children, parent, sibling, leaf, ancestor, descendent * (&#x2713;) Recognize empty trees and contents after any branch to be trees themselves, specifically subtrees * (&#x2713;) 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 * (&#x2713;) Explain the criteria for binary trees that are full, perfect, and complete * (&#x2713;) Explain preorder, inorder, and postorder traversal of trees using words and figures * (&#x2713;) Explain the significance of each of these orders when applied to expression trees ### Binary Tree Implementation * (&#x2713;) 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 * (&#x2713;) Implement `BinaryTree<E>` methods: get{Left,Right}Subtree, isLeaf, and preOrderTraverse/toString methods ## Week 7 ### Binary Search Trees * (&#x2713;) Define the ordered relationship between parent and child nodes * Implement a recursive `contains()` method * (&#x2713;) Implement a recursive `size()` method * Implement a recursive `height()` method * (&#x2713;) 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 * (&#x2713;) 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 * (&#x2713;) Choose the appropriate interface to use from the following choices: `Collection<E>`, `List<E>`, `Set<E>`, and `Map<K, V>` * (&#x2713;) List two classes that implement the `Map<K, V>` interface * (&#x2713;) Interpret and write Java code using the `TreeMap` and `TreeSet` classes * (&#x2713;) 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 * (&#x2713;) Describe how elements are added to a hash table * Describe how elements are removed from a hash table * (&#x2713;) Explain the **capacity** of a hash table and how it is used * (&#x2713;) Define the **load factor** of a hash table and explain how it is used * (&#x2713;) Define a **collision** as it relates to hash tables and describe ways of coping with collisions * (&#x2713;) Describe the **open addressing** method for dealing with collisions within a hash table * (&#x2713;) Describe the **chaining** method for dealing with collisions within a hash table * Write a hash table implementation (using chaining) that includes the following methods: * (&#x2713;) [`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>