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?



Ranking and Unranking permutations

I've been a big fan of Skiena's Algorithm Design Manual , I recently found my first edition of the book (although I own the third ed...