CSC 321: Data Structures
Fall 2012

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
  interfaces, inheritance, polymorphism
  GUI building

Data Structures
    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
    Stack class (extends Collectio, implements List)
      FILO/LIFO list
      operations: push, pop, peek, empty
    Queue interface (extends Collection)
      FIFO/LILO list
      operations: add, remove, peek, empty
      implemented by LinkedList class
    linked structures
      nodes, references
      singly-linked lists, next references, front and/or back references
      doubly-linked lists, previous & next references, front & back
      dummy nodes
Algorithm Analysis
  best vs. average vs. worst case analysis
  big-Oh notation
    intuitive definition, formal definition
    rate-of-growth analysis
    big-Omega, big-Theta
    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
  counting techniques
    mappings, sequences
    rules: bijection, product, sum, generalized product, division
      inclusion/exclusion, pigeonhole principle