Topics for Final Exam
Sorting algorithms
QuickSort
Understand and trace the recursive
algorithm
Pick the pivot using "median of
three"
Complexity in best, worst and average
cases
MergeSort
Understand and trace the recursive
algorithm
Understand and trace the merge method
Complexity of merge method and
MergeSort algorithm
InsertionSort
Understand and trace algorithm
define and be able to find
"inversions" in an array
Connect number of inversions with
complexity of sorts that work by swapping adjacent elements.
LinkedList class (Study code in text pp554-562)
nodes have previous and next references
dummy nodes at head and tail
purpose of modCount
trace code that inserts and removes Nodes
Stacks and Queues
Use methods in API
understand implementations using array or linked nodes
complexity of all methods depending on implementation
Maps and Sets
Use methods in API for these interfaces
Understand the hashCode() method and how it relates to the
hash implementations of maps and sets--HashMap and Hashset
Understand that the TreeMap and TreeSet implementations need
Comparable objects.
Understand how finite state machines work and how to use a
Map to model state transitions
Complexity for the major Map and Set methods depending on
implementation
Iterator interface
apply the "iterator pattern" to processing items in
a collection
Iterator semantics and the remove() method for iterators
Comparators and Comparable interfaces
understand the difference between these interfaces
Complexity
intuitive meaning of big Oh, big Theta, big Omega and little
oh
recognize when two functions have the same big theta
compute complexity of code involving "for" loops
Class Inheritance and implementing interfaces
Abstract classes
inner classes
Exceptions
RunTime vs checked exceptions
know how to use try-catch blocks
know how to create a new exception