CSC 427: Data Structures and Algorithm Analysis
Fall 2008

Course Overview


Object-Oriented Programming
  class design
    interacting classes, private data fields & public methods
    static, final, private methods
    generic classes and methods
  interfaces
    examples: Comparable, Iterable, Collection, Set, List
    implementing an interface, polymorphism
  inheritance
    extending a class, overriding methods, polymorphism
    calling super from a derived class
  GUI design/building
    
Data Structures
  previous structures: array, ArrayList, LinkedList, Stack, Queue
  low-level data structures
    linked lists
      singly-linked vs. doubly linked, ListNode, header node(s)
    trees
      non-linear structure, TreeNode, recursive processing
      binary tree, binary search tree
        balanced tree variants: AVL tree, red-black tree
    hash table
      hash function, collisions, clustering, load factor, rehashing
      linear probing vs. quadratic probing vs. chaining
    iterators
      Iterable interface: iterator
      Iterator interface: next, hasNext, remove             
  Lists
    List interface: get, set, add, remove, contains, indexOf, size, iterator, ...
    ArrayList implementation: uses dynamic array
      O(1) get/set, O(1) add/remove from end, O(N) get/set/add/remove from index, 
      O(N) contains/indexOf
    LinkedList implementation: uses doubly-linked list
      O(1) get/set/add/remove at either end, O(N) get/set/add/remove from index,
      O(N) contains/indexOf
    Collections static methods: binary_search, sort, shuffle, max
  Sets
    Set interface: add, remove, contains, clear, size, iterator, ...
    TreeSet implementation: uses red-black tree, ordered by compareTo
      O(log N) add/remove/contains, iteration follows compareTo ordering
    HashSet implementation: uses hash table with chaining
      O(1) add/remove/contains (on average), iteration follows no ordering
  Maps    
    Map interface: get, put, remove, containsKey, keySet, size, ...
    TreeMap implementation: uses red-black tree for key-value pairs
      O(log N) get/put/remove/containsKey, keySet returns TreeSet of keys
    HashMap implementation: uses hash table with chaining
      O(1) get/put/remove/containsKey (on average); keySet returns HashSet
    
Algorithm Analysis
  big-Oh notation
    formal definition, rate-of-growth analysis, asymptotic behavior
  searching & sorting
    sequential search vs. binary search
    insertion sort vs. selection sort vs. merge sort vs. heap sort
    specialized sorts: frequency counts, radix sort
  recursion
    base case(s), recursive case(s), analysis via recurrence relation
  algorithmic approaches
    divide&conquer: binary search, merge sort, tree algorithms, ...
    greedy: optimal optimal change (U.S.), job scheduling, ...
    backtracking: N-queens, blob count, Boggle, Sudoku, ...
    dynamic: optimal change, binomial coefficient, ...