[prev] 149 [next]

Summary

  • Alphabets and words
  • Pattern matching
    • Boyer-Moore, Knuth-Morris-Pratt
    • Tries
  • Text compression
    • Huffman code
  • Approximation
    • numerical problems
    • vertex cover
  • Analysis of randomised algorithms
    • probability of success
    • expected runtime
  • Randomised Quicksort
  • Karger's algorithm
  • Simulation

  • Suggested reading:
    • tries … Sedgewick, Ch. 15.2
    • approximation … Moffat, Ch. 9.4
    • randomisation … Moffat, Ch. 9.3, 9.5