Algorithms Summary

• Sorting
• quicksort, heapsort, mergesort
  
• Shortest Path
• Dijstra's Algorithm -- O(E V log V) -- priority queue
  
• Approximate Algorithms
• NP-complete problems, e.g. TSP
  
• Find a path that is at most 10% longer than the shortest path.
  
• Random Algorithms
• Quicksort -- average O(N log N)
  
• Find median number -- average O(N)
  
• Compression
• LZW, MP3, JPG
  
• Maximum Flow, Minimum Cut
• Fastest flow of supplies through rail network.
• Minimum change needed to disrupt flow.
• How to assign N employees to M jobs so that every job gets done.
  
• Sequence Comparison
• Use DP to get O(N*M) instead of exponential.