Lecture notes for Intermediate Data Structures talk

gistfile1.txt

I) About me:
  a) Peter Hayes, engineer at ClassDojo
  b) Studied mathematical economics at Brown, used to be a high school math teacher
  c) Follow me on github/check out my npm.  don't follow my twitter

II) Introduction
  a) Topics today: heaps, quadtrees, graphs
  b) What are data structures for?
    1) Not just to store data - an unstructured blob can store data
    3) Rather: store data with *efficient* insertion, access, and retrieval
  c) Running times and big(O)
    1) Linear - the worst - lookup in an unsorted phonebook - examining every item
    2) Logarithmic - pretty good - lookup in a sorted phonebook - halving the problem each time
    3) Constant - the best - lookup in a digital contact book - an "oracle" for the answer
    4) What about insertion?
    
III) Heaps
  a) Motivation: priority queues and scheduling
  b) Other solutions: sorted/unsorted lists
  c) Heap properties
    1) Full binary tree
    2) All elements are greater (or less, in a min-heap) than elements below them
  d) Heap algorithm
  e) Implementation with Ahnentafel (ancestor table) array method
  
IV) Quadtrees
  a) Motivation: maps (Yelp, etc)
  b) Other solutions: big grid matrix
  c) Explanation of binary search trees and interval search
  d) Generalization to 2d
  e) Mention of box-quadtrees as alternative to point-quadtrees

V) Graphs
  a) Motivation: social networks, distributed systems, etc
  b) Modes of storage: Adjacency List and Adjacency Matrix - benefits of each
  c) Weighted vs unweighted
  d) Directed vs undirected
  e) Cyclic vs acyclic (and why it matters - traversals)
  f) Graph algorithms as time permits