To 10 algorithms every software engineer should know by heart

  1. Bubble sort, or in-place insertion sort (or any O(n^2) sort).
  2. Quick sort or merge sort (or any O((log n) * n) sort).
  3. Building and searching a balanced binary tree (or any tree construction and traversal methods).
  4. Building and using a hash table.
  5. Finding an optimal hash for a static hash table.
  6. Approximate optimization (or search) by bifurcation (binary search).
  7. Dijkstra’s Algorithm (or any other graph search algorithms).
  8. LU decomposition (any method).
  9. Fisher-Yates Shuffle (and/or other set and permutation related algorithms).
  10. Minimum Spanning Trees (e.g. Prim’s Algorithm).

I can only think of these, but some of them have several variants. Anyone want to suggest more? I’m willing to edit.

Update: Thanks for all of the constructive comments! Perhaps I should have added a paragraph at the beginning to say: I don’t think they should necessarily know these algorithms by heart, but they should know that these algorithms exist, and know how to look them up and implement them. They should also know how these algorithms can affect the run-time complexity of their code. Most of the time in modern programming, we use code from libraries, and the software engineer can simply choose among several alternatives. For example, the C++ STL provides many container classes. The container can have a big impact on code performance. There are hundreds, if not thousands of libraries available to the modern software engineer. In that case, knowledge of the underlying algorithms can help them to make a better choice. In any case, even these very solved problems need to be written by someone, even if that someone is just writing a library to be used by others.

Another list suggestion:

Algorithms is not something that most programmers can beneficially memorize. I’ll list 10 ideas/concepts/techniques instead.

  1. Name things after what they are. Variables, methods, functions, modules—the best place to document something is its name.
  2. Make your code short. The fewer tokens and complexity, the less room for bugs.
  3. Put related things textually close.
  4. Hash tables. Use whenever appropriate.
  5. Modularization. Break up software into understandable and testable modules.
  6. Caching. All computer science is an exercise in caching.
  7. Optimize what matters: in a CPU- or memory-bound program, only a tiny part of the code determines the performance.
  8. Use C for I/O-bound programs, including networking code, and for very little else.
  9. Never get married to a language, a framework, a library, or a tool. Don’t be a <tool name> programmer; instead, use what is appropriate.
  10. Optimizing the algorithm matters more than micro-optimizing some inner loop.

If I were to list 10 specific algorithms as examples everyone should be familiar with, I’d probably go with these:

  1. Binary search
  2. Quicksort
  3. Backtracking
  4. Hash table
  5. Linear congruential generator and Mersenne Twister
  6. Linear least squares
  7. Karatsuba algorithm
  8. Divide and conquer for Matrix multiplication
  9. Dijkstra’s algorithm
  10. Knuth–Morris–Pratt algorithm

Memorizing them is pointless, but understanding the ideas is very useful.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s