skseth / algorithms

Based mostly on the excellent lectures on Algorithms: Design and Analysis, Part 1 from Coursera.

#Review List

• Divide and Conquer

  • Merge Sort & Inversions
  • Complexity Notation - O, omega, theta and small-o
  • Strassens Matrix Multiplication Algorithm
  • Closest-Pair (optional)
  • Master Method

• Quicksort

  • Probability Review - Sample Spaces, Events, Random Variables, Expected Value, Linearity of Expectations
  • Partition Algorithm - invariant, correctness, running time
  • Choosing a good pivot
  • Quicksort with Randomized Pivot
  • Proof of Quicksort average running time
  • Any comparison-based sort takes n log n

• Selection

  • Randomized Selection avg O(n)
  • Deterministic Selection

• Graphs

  • Graphs - Basic definitions
  • Graphs - Karger's Minimum Cut Algorithm
  • Probability Review - Conditional Probability
  • MinCut optimizations for randomized algorithms
  • Shortest Path
  • Topological Sort
  • SCC - Kosaraju's algorithm
  • Djikstra's Algorithm

#TODO Convert to rst - maths equations cleanup Theory Problems summary Review Problem Sets Clean up Code

Inversions - try common approach Strassens Algo - write code Closest-Pair Quicksort Pivot Partition proof by induction Quicksort - prove that 25-75 split will result in O(n log n performance) Quicksort - read formal proof Quicksort with repeated elements Quicksort randomized Leighman-Leighton notes on maths for compscience Graph Algorithms - adapt for disconnected graphs Proof of BFS being shortest distance Proof that SCCs form a DAG Proof that BST min/max/delete/pred/succ/size functionality RB Trees - rotation implementation AVL Trees Splay Trees - self-adjusting trees B-Trees / B+ Trees Read up hash tables in Algorithm book Universal Hashing optional videos Universal Hashing number theory proof Bloom Filter implementation Bloom filter k,b derivation

Family Tree Visualization - http://vis.berkeley.edu/courses/cs294-10-sp10/wiki/images/f/f2/Family_Tree_Visualization_-_Final_Paper.pdf Structure of the Web Small World Property - Core exhibits this. Six degrees of separation. http://en.wikipedia.org/wiki/Small-world_experiment - Milgram's experiments Networks, Crowds and Markets - Easley & Kreinberg Purely functional data structures Amortization of algorithms

https://www.youtube.com/watch?v=pNhBQJN44YQ http://www.slideshare.net/vkostyukov/purely-functional-data-structures-in-scala-26175521 https://reprog.wordpress.com/2010/05/25/how-slow-are-functional-implementations-of-quicksort/ http://www.informit.com/articles/printerfriendly/1407357 http://arxiv.org/pdf/1312.4666.pdf