CSC 427: Data Structures and Algorithm Analysis
Fall 2011

Course Overview

Object-Oriented Programming
  class design
    interacting classes, private data fields & public methods
    static, final, private methods
    generic classes and methods
    examples: Comparable, Iterable, Collection, Set, List
    implementing an interface, polymorphism
    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
      non-linear structure, TreeNode, recursive processing
      binary search tree, balanced variants (AVL tree, red-black tree)
      heaps for priority queue, heap sort
    hash table
      hash function, collisions, load factor, rehashing
      linear probing vs. chaining
      Iterable interface: iterator
      Iterator interface: next, hasNext, remove             
    List interface: get, set, add, remove, contains, indexOf, size, iterator, ...
    ArrayList implementation: uses dynamic array
    LinkedList implementation: uses doubly-linked list
    Collections static methods on Lists: binary_search, sort, shuffle, max
    Set interface: add, remove, contains, clear, size, iterator, ...
    TreeSet implementation: uses red-black tree, ordered by compareTo
    HashSet implementation: uses hash table with chaining
    Map interface: get, put, remove, containsKey, keySet, size, ...
    TreeMap implementation: uses red-black tree for key-value pairs
    HashMap implementation: uses hash table with chaining
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
    base case(s), recursive case(s), analysis via recurrence relation
  algorithmic approaches
    brute force: contest problems, generate & test, ...
    divide&conquer: binary search, merge sort, tree algorithms, ...
    transform&conquer: presorting, balanced BST algorithms, heaps, ...
    decrease&conquer: sequential search, selection sort, DFS, BFS, ...
    greedy: job scheduling, Dijkstra's algorithm, Huffman codes, ...
    backtracking: N-queens, blob count, Boggle, Sudoku, ...
    dynamic: binomial coefficient, World Series puzzle, making change, ...