Monday, September 03, 2012

Algorithms beyond school

I was working on a list of algorithms a new college graduate ought to know to either

  • Do well in an interview
  • Make quick progress through the learning curve

Here is the list I have so far, I would appreciate comments on what else to add

  1. Population Counting
  2. Multi-precision Arithmetic
  3. Fast Fourier Transform
  4. Fast Prime Number Generation
  5. Quicksort
  6. Union-Find
  7. String searching (KMP, Regular Expressions)
  8. Polynomial Multiplication
  9. Calculation of Pi
  10. 8 Queens Problem
  11. Instance of a turing machine simulation
  12. Tries
  13. Radix Tree
  14. Red Black Tree
  15. Huffman's algorithm
  16. Graphs - DFS, BFS
  17. Graphs - Bipartite
  18. Minimum Spanning Tree
  19. Hashing algorithms
  20. Linear programming?
  21. Classes of problems - P/NP/?
  22. Vertex Cover?
  23. Synchronization (locks/mutex/spin locks)
  24. Lockless algorithms
How does the list look?



Dynamic programming for the binomial coefficient

More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don'...