CSC 321: Data Structures
Fall 2017

Final Review


Data Structures
  Java review, arrays, generics, iterators
    inheritance, interfaces, polymorphism
  Collections
    List interface: ArrayList, LinkedList
    Set Interface: TreeSet, HashSet
    Map interface: TreeMap, HashMap
    Stack class, Queue interface, PriorityQueue class
  low-level structures
    linked lists: singly vs. doubly, dummy nodes, iterators
    trees: hierarchical, recursive processing, binary search trees,
           heaps, heap sort, array implementation
    graphs: adjacency matrix vs. list
    hash tables: hash functions, load factor, rehashing
      collisions, clustering, probing vs. chaining
  
Math Structures
  functions & sets
    bijections, mappings, sequences, sets & subsets 
  linear structures
    lists, sets, maps
  nonlinear structures
    trees: root, leaf, child, path, height, weight, ...
      binary search trees, balanced trees (red-black, AVL), heaps, tries
    graphs: vertex, edge, adjacent, incident, degree, path, ...
      simple vs. directed, weighted vs. unweighted
      depth first search, breadth first search, finite state machines
  counting techniques
    bijection rule, product rule, sum rule, division rule,
    generalized product rule, n choose k, inclusion/exclusion rule,
    pigeonhole principle
  proof techniques
    direct proof, proof by contradiction, proof by induction
   
Algorithm Analysis
  algorithm analysis
    best vs. average vs. worst case analysis
    big-Oh notation, rate-of-growth analysis, big-Omega & big-Theta
    searching and sorting
      standard algorithm analysis, specialized sorting algorithms
  recursion
    recursive algorithms, recurrence relations
 
Assignments
  1. java review & design (robot navigation)
  2. queues & music (dulcimer)
  3. algorithm analysis (Lists & timings)
  4. linked structures (MidLinkedList)
  5. tries & dynamic structurews (Trie implementation)
  6. maps & finite state machines (FSM path finder/checker)