###
CSC 427: Data Structures and Algorithm Analysis

Fall 2007

Test 1 Review

Java review
class, object, fields, methods, private vs. public, parameters
variables, primitive vs. objects, expressions, if, if-else, while, for
object-oriented design: cohesion, coupling
String, Math, arrays, ArrayList, generics
interfaces, List, LinkedList, iterators
searching and sorting, algorithm efficiency, recursion
Stack class, Queue interface
inheritance, polymorphism
algorithm design and analysis
big-Oh notation
intuitive definition, formal definition
rate-of-growth analysis
searching
sequential search: O(N) worst/average case, O(1) best case
binary search: O(log N) worst/average case, O(1) best case
sorting
insertion sort: O(N^{2}) worst/average case, O(1) best case
selection sort: O(N^{2}) worst/average/best case
merge sort: O(N log N) worst/average/best case
quick sort: O(N log N) average/best case, O(N^{2}) worst case
specialized sorts
if limited range of values, sort via frequency list: O(range * N)
if can compare by digit/char, radix sort: O(maxLength * N)
recursion
base case(s), recursive case(s)
analysis via recurrence relation
inheritance and efficiency
derived classes
extending a class vs. implementing an interface
overriding methods, calling parent methods/constructors with super
polymorphism
List --> ArrayList --> SortedArrayList
divide-and-conquer algorithms
examples: merge sort, quick sort, Euclid's gcd, ...
Java Collections and list implementations
Collection interface, many useful static methods in Collections
List interface (extends Collection)
ArrayList (implements List): underlying array representation
O(1) add/remove at end, O(N) add/remove from beginning/middle
O(1) access, O(N) search
LinkedList (implements List): underlying doubly-linked list representation
O(1) add/remove at beginning/end, O(N) add/remove from middle
O(1) add/remove if have access to location, O(N) access/search
Set interface (extends Collection)
TreeSet (implements Set): O(log N) add/remove/search
HashSet (implements Set): O(1) add/remove/search expected*, O(N) worst case
Map interface
TreeMap (implements Map): O(log N) add/remove/search
HashMap (implements Map): O(1) add/remove/search expected*, O(N) worst case
iterators
Iterator interface: hasNext, next, remove
ListIterator interface: hasPrevious, previous, add, set