CSC 427: Data Structures and Algorithm Analysis
Fall 2006

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(N2) worst/average case, O(1) best case
    selection sort: O(N2) worst/average/best case
    merge sort: O(N log N) worst/average/best case
    quick sort: O(N log N) average/best case, O(N2) 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, ...
    divide-and-conquer characterizations: binary search, sum of list, ...

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): underlying ordered binary tree representation
      O(log N) add/remove/search
    HashSet (implements Set): underlying hash table representation
      O(1) add/remove/search on average, O(N) worst case
  Map interface
    TreeMap (implements Map): underlying ordered binary tree representation
      O(log N) add/remove/search
    HashMap (implements Map): underlying hash table representation
      O(1) add/remove/search on average, O(N) worst case
  iterators
    Iterator interface: hasNext, next, remove
    ListIterator interface: hasPrevious, previous, add, set