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
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.
Complexity
in best, worst and average cases
Merge Sort
Understand and trace algorithm
Complexity in best, worst and
average cases
LinkedList class and Deque class Circle class
ArrayQueue implementation
Stacks and Queues
Use methods in API
understand implementations using array or linked nodes
complexity of all methods depending on implementation
Sets and Maps
Use methods in API for these interfaces
Know when and why it is necessary to
override equals and hashCode methods
Iterator and Iterable interfaces
apply the "iterator pattern" to processing items in
a collection, be able to use "enhanced" for loop
Iterator semantics and the remove() method for iterators
purpose of modCount for implementing iterators in List
classes
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
estimate time needed to run algorithm
given its complexity and execution time for one sample size.
Class Inheritance and implementing interfaces
Abstract classes
inner classes
the "has a" and "is a" relations and how
to use them to define java classes that model a problem domain.
Generic type parameters
How to use them with Collections in API
How to use them to create your own generic classes
How to use them with static methods that will compare objects
in a class that extend a Comparable. Look at the signature of methods in Sort.java
class in Weiss's code.