Skip to content

Instantly share code, notes, and snippets.

@peterkhayes
Last active May 6, 2016 01:33
Show Gist options
  • Save peterkhayes/fcb7548ef7cde329c460 to your computer and use it in GitHub Desktop.
Save peterkhayes/fcb7548ef7cde329c460 to your computer and use it in GitHub Desktop.
Lecture notes for Intermediate Data Structures talk
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment