CSC 427: Data Structures and Algorithm Analysis
Fall 2011

Midterm 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

Data Structures
  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	
      Iterator interface: hasNext, next, remove
      ListIterator interface: hasPrevious, previous, add, set
  Sets & Maps
    Set interface (extends Collection)
      TreeSet: O(log N) add/remove/search
      HashSet: O(1) add/remove/search expected*, O(N) worst case
    Map interface
      TreeMap: O(log N) add/remove/search
      HashMap: O(1) add/remove/search expected*, O(N) worst case
  extending data structures via inheritance
    List --> ArrayList --> SortedArrayList
Algorithm Design and Analysis
  big-Oh notation
    intuitive definition, formal definition
    rate-of-growth analysis
    sequential search: O(N) worst/average case, O(1) best case
    binary search: O(log N) worst/average case, O(1) best case
    insertion sort: O(N2) worst/average case, O(N) 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)
    base case(s), recursive case(s)
    analysis via recurrence relation
  brute force algorithms
    examples: league standings, quiz grades
    exhaustive search: string matching
    generate & test: N-queens, Traveling Salesman, Knapsack
  divide-and-conquer algorithms
    examples: merge sort, quick sort, closest points
      nodes & edges, root, parent/child, leaf, subtree
      recursive tree traversal