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?



1 comment:

Balbir Singh said...

Hmm.. I wonder if I should focus on conversations with a system programmer with some tips on what a system programmer should know!

Examples

Calling conventions
ABI
Math in the processor
Linking/Loading
and more...

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'...