CS2852: Outcomes

CS2852

Outcomes

Key

In the outcomes, an item like (2_3) indicates that an objective was introduced in class on, for example, Week 2, Day 3.

An item like (2_3, 2_2) indicates tha the objective was introduced in class 2_3 in section 021 (the morning) and in class 2_2 in section 051 (the afternoon).

(L2) indicates that on Outcome is practiced in Lab 2.

Software Tips and Tricks

Excel

Add axis labels (titles) in excel

IntelliJ

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.
How to set up the default template
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.)
Print & use shortcuts from this handy IntelliJ Reference card
Using a Jar File that someone else wrote with your code
Creating a Jar File
- Video of how to create JAR file and ZIP File
- Dr. Taylor's class where he went over this
- Accessing files to read/write from your jar file: Ask me!
- Accessing libraries (.jar files) from your jar file: Ask me!

Enterprise Architect

Import code into EA to generate class diagrams quickly.

Week 1

Big-picture: What this class about

(For explanation of (1_1), see above.)

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

Interfaces

(1_1) Use the Collection<E> and List<E> interfaces defined in the Java Collection Framework
(1_1) Explain when to use Collection<E> instead of List<E> and vice versa
(1_1) Demonstrate correct use of generics when declaring Collection<E> and List<E> interfaces
(1_2, 1_1) Describe the implications of an interface extending another interface
(1_2) List two classes that implement the Collection<E> interface
(1_1), List two classes that implement the List<E> interface

Array Based Lists

(1_3) Describe key differences between an array and an ArrayList<E> object
(1_2) Implement classes and methods that make use of generics
(1_3) Interpret expressions using the ternary operator (expr ? expr : expr)
(1_2) Write an array-based implementation of the List<E> interface, including the following methods:
(L1) Implement small software systems that use one or more ArrayList<E> objects

Week 2

Big-O Notation and Algorithm Efficiency

(2_1) Explain the purpose of Big-O notation
(2_3) Describe the limitations of Big-O notation
(2_1,?) Be familiar with the formal definition of Big-O
(2_2) Using Big-O notation, determine the asymptotic time complexity of an algorithm with a conditional
(2_2) Using Big-O notation, determine the asymptotic time complexity of an algorithm with a loop
(2_3) Determine the asymptotic time complexity of an algorithm with a nested loop
(2_2) Using Big-O notation, determine the asymptotic time complexity of an algorithm that calls other methods with known asymptotic time complexity
(2_3) Use time complexity analysis to choose between two competing algorithms
(2_2) Describe the meaning of the following symbols: T(n), f(n), and O(f(n))
(2_2) (Q1) Given T(n) expressed as a polynomial, determine the Big-O notation
(2_2) 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()
(3_1) Describe key differences between our implementation and the ArrayList<E> implementation in the Java Collections Framework
(3_1) Describe differences in the JCF ArrayList implementation compared to the one created in lecture that affect the asymptotic time complexity of any of the methods

Linked Lists

(2_3) Describe key differences between an array based list and a linked list
(3_1) Describe advantages and disadvantages of a singly linked list verses a doubly linked list
(2_3) Write an singly linked list implementation of the List<E> interface, including the following methods:
(3_1) Describe key differences between a singly linked list and the LinkedList<E> class
(3_1) 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()
(3_1) 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
(L3) Implement small software systems that use one or more LinkedList<E> objects

Week 3

Iterators

(3_1) List the methods declared in the Iterator<E> interface
(3_1) List the methods declared in the Iterable<E> interface
(3_1) Implement the iterator() method in the ArrayList class (returning a fully functional iterator)
(HW) Implement the iterator() method in the LinkedList class (returning a fully functional iterator)
(3_2) Describe the big-O run-time of the methods iterator(), it.hasNext() and it.next(), as well as the for-each loop that uses them.
(3_1) Explain why the enhanced for loop only works on classes that implement the Iterable<E> interface
(3_1) (review) Write code using anonymous inner classes
(?, 3_1) Be familiar with the ListIterator<E> interface

Java Collection Framework and Testing

(8_1) Explain the purpose of the Java Collections Framework
(8_1) Be familiar with class/interface hierarchy for the Java Collections Framework
(5_2) Describe the following levels of testing: unit, integration, system, and acceptance
(5_2) Describe the differences between black-box testing and white-box testing
(5_2) List advantages and disadvantages of black-box testing verses white-box testing
(5_2) Develop tests that test boundary conditions

Week 4

Stacks

(5_1, 4_3) Enumerate and explain the methods that are part of a pure stack interface
(5_1, 4_3) Define LIFO and explain how it relates to a stack
(8_1) Explain how the Stack<E> class is implemented in the Java Collection Framework
(5_1, 4_3) Describe the design flaw found in the Stack<E> implementation found in the Java Collection Framework
(5_1, 4_3) Implement a class that provides an efficient implementation of the pure stack interface using an ArrayList<E>
(5_2, 4_3) Implement a class that provides an efficient implementation of the pure stack interface using a LinkedList<E>
(8_1) Define the term adaptor class and be able to implement a simple adaptor class, e.g., stack, queue
(5_1) Implement small software systems that use one or more stack data structures
(5_1) List at least two examples of when it makes sense to use a Stack

Week 5

Queues

(5_2, 4_3) Enumerate and explain the methods that are part of a pure queue interface
(5_2, 4_3) Define FIFO and explain how it relates to a queue
(5_2, 4_3) The Queue<E> interface has multiple methods for insertion, removal, and accessing the front element. Describe how these methods differ
(8_1) Describe the design flaw found in the Queue<E> interface found in the Java Collection Framework
(5_2, 5_1) Implement a class that provides an efficient implementation of the pure queue interface using a LinkedList<E>
(5_2, 4_3) Explain why an ArrayList<E> is not an appropriate choice when implementing a pure queue interface
(5_2) Explain how a circular queue differs from a standard queue
(5_2) Implement a class that provides an efficient implementation of a circular queue using an array
(5_2) Implement small software systems that use one or more queue data structures
(5_2, 4_3) List at least two examples of when it makes sense to use a Queue

Binary Search

(5_3) Verbally and graphically describe the binary search algorithm
(5_3) Explain why binary search of n sorted items takes O(log n) time.
(5_3) Write recursive pseudocode for the binary search algorithm.

Recursion

(6_1) For a given input, determine how many times a recursive method will call itself
(6_1) Explain the role of the base case and recursive step in recursive algorithms
(6_1) Use recursion to traverse a list
(6_1) Use recursion to search a sorted array
(6_1) Understand and apply recursion in algorithm development

Week 6

Binary Trees

(some of these, so far) Use the following terms to describe nodes in a tree: root, children, parent, sibling, leaf, ancestor, descendent
(6_3) Recognize empty trees and contents after any branch to be trees themselves, specifically subtrees
(6_3) Define node ~~level~~ depth recursively, starting with level 1 at the root. Define height as the maximum node level
(6_3) Describe the similarities and differences between a Binary Search Tree and Binary Search on a sorted array.
(?, 8_1) 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
(8_1) Explain the criteria for binary trees that are full, perfect, and complete
(8_1) Explain preorder, inorder, and postorder traversal of trees using words and figures
(8_1) 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 2-arg (left and right subtree) constructors~~
~~Implement BinaryTree<E> methods: get{Left,Right}Subtree, isLeaf, and preOrderTraverse/toString methods~~
(6) Define the tree terms root, leaf, and subtree

Week 7

Binary Search Trees

(6_3) Define the ordered relationship between parent and child nodes
(8-Q5) Implement a recursive contains() method
(6_3) Implement a recursive size() method
(6_3_HW) Implement a recursive height() method
(7_1) Describe how elements are added to a binary search tree
(9_2?, 9_1) Describe how elements are removed from a binary search tree

Week 8

Sets and Maps

(8_3) Use the Set<E> and Map<K, V> interfaces defined in the Java Collection Framework
(8_1; want to review) Choose the appropriate interface to use from the following choices: Collection<E>, List<E>, Set<E>, and Map<K, V>
(8_1) List two classes that implement the Map<K, V> interface
(8_1; want to review) Interpret and write Java code using the TreeMap and TreeSet classes
(7; Exam 2) 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

(8_3) Describe how elements are added to a hash table
(9_1,9_2) Describe how elements are removed from a hash table
(9_1) Explain the capacity of a hash table and how it is used
(9_1) Define the load factor of a hash table and explain how it is used
(8_3) Define a collision as it relates to hash tables and describe ways of coping with collisions
(8_3) Describe the open addressing method for dealing with collisions within a hash table
(8_3) Describe the chaining method for dealing with collisions within a hash table
(8_3) Write a hash table implementation (using chaining) that includes the following methods:
(8_3) Explain why the Object.hashCode() method must be overridden if the Object.equals() method is overridden
(9_1,9_2) Describe the criteria for a good hashCode() implementation
(9_1,9_2) Interpret and develop simple hashing functions
(9_1; want to review) Interpret and write Java code using the HashMap and HashSet classes
(9_1; want to review) 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

(9_2) Describe the impact that balance has on the performance of binary search trees
(?,9_3) Perform rotations on trees
Implement the leftRotate() and rightRotate() methods for a binary tree
(?,9_3) Explain the mechanism used in AVL trees to ensure that they remain balanced
(?,9_3) Illustrate the steps required to balance an AVL tree upon insertion of an additional element

Acknowledgements

Original outcomes by Dr. Taylor