## Week 1

### GUI Components

- List at least three types of objects that can be contained in a
`Parent`

object - Design and implement a graphical user interface (GUI) programs using the
`Label`

and`Button`

classes from the JavaFX package

## Week 2

### Event-Driven Programming

- Derive from the
`Application`

class and create a simple GUI application - Create a
`FlowPane`

and add multiple components to the pane - Explain what it means to "register an event handler"
- Write a method reference representing an instance method of a particular object
- Use a method reference to register an event handler to a
`Button`

or`TextField`

- Explain the role of the
`ActionEvent`

passed to the method reference - Determine the source of the event that called an event handler
- Describe the event-delegation model and explain the role of the event source object and the event listener
- List two classes whose instances are the source of events (e.g.,
`Button`

) - List two classes whose instances are event objects (e.g.,
`ActionEvent`

) - Implement the
`EventHandler`

interface as an inner class - Implement an
`EventHandler`

as a lambda expression

### GUI Components

- Differentiate between layout panes such as:
`GridPane`

,`FlowPane`

,`HBox`

, and`VBox`

- Use the layout panes listed above to arrange components on a scene

## Week 3

### FX Markup Language

- Describe the differences between creating JavaFX applications using imperative programming and using FXML with declarative style programming
- Use scene builder to create an FXML file describing a GUI layout
- Implement controller classes and make appropriate modifications to FXML files to provide functionality to UI controls such as
`Button`

and`TextField`

classes - Use
`Alert`

and`TextInputDialog`

classes to interact with the user.

### Functional Programming

- Describe when it is appropriate to replace code with a lambda expression
- Explain the characteristics of and purpose for a functional interface
- Use lambda expressions to implement the
`Predicate`

,`Function`

,`Consumer`

, and`Comparator`

interfaces - Use a method reference in place of a lambda expression
- Explain how functional programming differs from object oriented programming
- Describe the purpose of the
`Stream`

interface - Make use of the
`Iterable.forEach()`

method - Be familiar with the following methods from the
`Stream`

interface:`collect()`

,`count()`

,`distinct()`

,`filter()`

,`map()`

,`max()`

,`min()`

,`limit()`

,`skip()`

,`sorted()`

, and`toArray()`

- Use
`Collectors.toList()`

with the`collect()`

method - Obtain a
`Stream<String>`

from a file

## Week 4

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

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

### 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: - 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

## Week 5

### 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 6

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

## Week 7

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

### 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`

### 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`

## Week 8

### 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 9

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

### 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 10

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

## Week 11

### 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 12

### Sorting

- Stuff

## Week 13

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

## Week 14

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

# CS2013

## Basic Analysis

- Explain what is meant by "best", "expected", and "worst" case behavior of an algorithm. [AL|Basic Analysis|1]
- In the context of specific algorithms, identify the characteristics of data and/or other conditions or assumptions that lead to different behaviors. [AL|Basic Analysis|2]
- Determine informally the time and
**space complexity**of simple algorithms. [AL|Basic Analysis|3] - State the formal definition of big O. [AL|Basic Analysis|4]
- List and contrast standard complexity classes. [AL|Basic Analysis|5]
- Perform empirical studies to validate hypotheses about runtime stemming from mathematical analysis Run algorithms on input of various sizes and compare performance. [AL|Basic Analysis|6]
**Give examples that illustrate time-space trade-offs of algorithms.**[AL|Basic Analysis|7]

## Fundamental Data Structures and Algorithms

- Implement basic numerical algorithms. [AL|Fundamental Data Structures and Algorithms|1]
- Implement simple search algorithms and explain the differences in their time complexities. [AL|Fundamental Data Structures and Algorithms|2]
**Be able to implement common quadratic and O(N log N) sorting algorithms.**[AL|Fundamental Data Structures and Algorithms|3]- Describe the implementation of hash tables, including collision avoidance and resolution. [AL|Fundamental Data Structures and Algorithms|4]
- Discuss factors other than computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data. [AL|Fundamental Data Structures and Algorithms|6]
- Explain how tree balance affects the efficiency of various binary search tree operations. [AL|Fundamental Data Structures and Algorithms|7]
- Demonstrate the ability to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in a particular context. [AL|Fundamental Data Structures and Algorithms|9]

## Fundamental Concepts

- Construct a simple user interface using a standard API. [GV|Fundamental Concepts|4]
**Describe the differences between lossy and lossless image compression techniques, for example as reflected in common graphics image file formats such as JPG, PNG, MP3, MP4, and GIF.**[GV|Fundamental Concepts|5]

## Object-Oriented Programming

- Correctly reason about control flow in a program using dynamic dispatch. [PL|Object-Oriented Programming|3]
- Define and use iterators and other operations on aggregates, including operations that take functions as arguments, in multiple programming languages, selecting the most natural idioms for each language. [PL|Object-Oriented Programming|7]

## Functional Programming

- Write basic algorithms that avoid assigning to mutable state or considering reference equality. [PL|Functional Programming|1]
- Write useful functions that take and return other functions. [PL|Functional Programming|2]
- Compare and contrast (1) the procedural/functional approach–defining a function for each operation with the function body providing a case for each data variant–and (2) the object-oriented approach–defining a class for each data variant with the class definition providing a method for each operation Understand both as defining a matrix of operations and variants. [PL|Functional Programming|3]
- Define and use iterators and other operations on aggregates, including operations that take functions as arguments, ~~in multiple programming languages, selecting the most natural idioms for each language.~~ [PL|Functional Programming|6]

## Event-Driven and Reactive Programming

- Write event handlers for use in reactive systems, such as GUIs. [PL|Event-Driven and Reactive Programming|1]
- Explain why an event-driven programming style is natural in domains where programs react to external events. [PL|Event-Driven and Reactive Programming|2]
- Describe an interactive system in terms of a model, a view, and a controller. [PL|Event-Driven and Reactive Programming|3]

## Algorithms and Design

- Implement, test, and debug simple recursive functions and procedures. [SDF|Algorithms and Design|5]
- Determine whether a recursive or iterative solution is most appropriate for a problem. [SDF|Algorithms and Design|6]

## Fundamental Programming Concepts

- Describe the concept of recursion and give examples of its use. [SDF|Fundamental Programming Concepts|8]
- Identify the base case and the general case of a recursively-defined problem. [SDF|Fundamental Programming Concepts|9]

## Fundamental Data Structures

- Discuss the appropriate use of built-in data structures. [SDF|Fundamental Data Structure|1]
- Describe common applications for each of the following data structures: stack, queue, priority queue, set, and map. [SDF|Fundamental Data Structure|2]
- Write programs that use each of the following data structures: arrays, records/structs, strings, linked lists, stacks, queues, sets, and maps. [SDF|Fundamental Data Structure|3]
- Compare alternative implementations of data structures with respect to performance. [SDF|Fundamental Data Structure|4]
- Describe how references allow for objects to be accessed in multiple ways. [SDF|Fundamental Data Structure|5]
**Compare and contrast the costs and benefits of dynamic and static data structure implementations.**[SDF|Fundamental Data Structure|6]- Choose the appropriate data structure for modeling a given problem. [SDF|Fundamental Data Structure|7]