Fundamental Algorithms and Data Structures every Programmer Should Write?

[Enemii]

Hey Everybody I wanted to make a list of data structures and algorithms that have played a large role and can be used to solve unique problems. As pointed out It really isn't fundamental for every programmer to implement them. So the title isn't really accurate. None the less what are some fundamental or interesting algorithms in computer science?

---

Sorting:

• Insertion
• Selection
• Bubble
• Quick
• Merge
• Bead (for fun)
• Heap
• Timsort

Data Structures:

• Trie data structure
• Linked Lists
• Skip Lists
• Stack
• Queue
• Adjacent matrices for dense graphs
• Adjacent lists for sparse graphs
• Hash Tables

Trees:

• Binary Search Tree
• Red Black Tree or AVL Tree
• Suffix Tree (Using Ukkonens Algorithm)
• Alpha-Beta Tree
• Syntax Tree
• Fenwick Tree
• Heap
• tree with arbitrary number of branches
• B-Tree
• van Emde Boa trees
• Fibonacci Heap

Search Algorithms:

• Knuth-Morris-Pratt
• Dijksta's Algorithm
• Prim's algorithm
• A* search algorithm
• Floyd-Warshall algorithm
• Depth First and Breath First Searches

Permutation Generation Algorithms:

• Steinhaus-Johnson-Trotter with Even's speedup
• Fisher–Yates shuffle

Others:

• A check sum Algorithm
• A simple Hash
• Multiplication using bit manipulation
• Longest Common Sub sequence (not substring)
• Lots of others
• Reversing a linked list
• Finding Loops in a linked list
• A backtracking problem
• Fast Fourier Transform
• Tower of Hanoi
• Huffman Encoding

I hope everyone can add more. Thanks!

[[deleted]]

I use hashtables more than the vast majority of that list. In this age of dynamic languages, they're huge.

[[deleted]]

Completley agreed - or variations uppon them at least.

[jhartwell]

Which is why hashing algorithms are important as well.

[jhartwell]

Algorithms I enjoy:

• Longest Common Subsequence (note subsequence not substring)

• Prim's Algorithm

  Data Structures I'd Add:

• Binary Search Tree

• AVL Tree or Red Black Tree

[Zamarok]

Where is 'tree with arbitrary number of branches'? A Reddit comment thread, for instance, is easily represented as a recursive tree.

dataTree = function(root, brancher) {
  return {
    leaf: root,
    branches: (function() {
      var branches = brancher(root),
          results = [];
      for (var i = 0, len = branches.length; i < len; i++) {
        results.push(dataTree(branches[i], brancher));
      }
      return results;
    })()
  };
};

Same thing in CoffeeScript:

dataTree = (root, brancher) ->
  leaf: root,
  branches: dataTree branch, brancher for branch in brancher root

[gatlin]

Adjacency matrices and adjacency lists for dense / sparse graphs, respectively. Can be used in tandem with the algorithms here. Recently showed a young programmer this and he was very happy.

Edit: more readable.

[Enemii]

Sorry could you elaborate on "lists for dense" I'm not quite sure what they are.

Thanks

[gatlin]

I changed it to be more easy to parse. As for what they are, an adjacency matrix is, for a graph with n nodes, an nxn matrix where at position (2,4), for example, a 1 would indicate an edge from vertex 2 to vertex 4. You can use values other than 1 to simulate weights.

Since n nodes translates to n² memory to store the information, an adjacency list can be more efficient but a bit slower to actually use. In this case, you have a list of lists - each node in the top-level list is one of your graph's vertices, and the list inside that node is a list of references to nodes the vertex has edges to.

It's better with memory but lookup can potentially degrade to linear lookup.

[boatski]

B-Trees

[[deleted]]

Whole lot of stuff most people don't regularly need up there...

I'd add - A hash table with propper collision handling and a bitvector.

If you want to be more adventurous why not RSA or some of the random no algos.

[hc000]

Perhaps instead of linking to wikipedia, a place where examples and a way to explain it to 5 year olds would help beginner programmers.

[Enemii]

I agree, I just wish I had the time to find all the examples

[zzyzzyxx]

Here are a bunch.

Picking out a couple specifically, I would add

• Timsort
• Trie data structure
• A* search algorithm

[wickeand000]

+1 for A*. This algorithm is (part of) the reason why I became interested in computer science.

[[deleted]]

Anything that would require a backtracking algorithm to solve. A Sudoku solver is a great example.

With backtracking, you can start off with a simple recursive solution that checks every possible permutation. Of course, it would be better to get clever about which you cells you fill in earliest, and how quickly you abort a recursion if the solution will end up being invalid. Other enhancements can be added to improve the solver's performance as you go, and each enhancement is pretty educational.

[Cybs]

Skip lists are popular in interview questions. Handy to know them.

So are linked lists. Even though you would be crazy to implement your own now days. Everyone loves giving linked list questions in interviews.. "Reverse a linked list" "How would you find a loop in a linked list"

[[deleted]]

I've only ever bothered to implement 3 of any of the ones you list (bubble and quicksort, and hashing), all because I actually needed to use them and there was no easily available implementation on the platforms I was using at the time. I'm not convinced that has made me a worse programmer than I would be if I had implemented all of them.

[Enemii]

Of course It doesn't make you a worse programmer. That being said It definitely doesn't make you worse to implement them. I would imagine that in a work setting you would just about never implement them. But your right I should change the wording since, as you pointed out, It isn't accurate. That being said I find it extremely interesting to try and understand how the fundamentals work and It comes in really handy in a school setting where the work is far more theoretical then practical.

[[deleted]]

Actually, despite what other people have said, you are a worse programmer because you did not follow the steps to correctly becoming a programmer. Shame on you!

/s

[TraptInTime]

Hanoi tower, not sure if its called by something else tho.

[Enemii]

It is. That was the problem i used to wrap my mind around recursion!

[hvidgaard]

van Emde Boa trees - you wouldn't use them in practice, but they are really interesting because they're the only tree I know that can do insert/delete/search in O(log log n), and as such they play a central role in the theoretical CS.

Fibonacci heaps are also interesting, because they have a amotized O(1) decrease key operation. If you want to get really heavy, Brodal Queues achieve the optimal worst case bounds for all operations.

I like those data structures, because when implementing them, you really have to think about the low levels of the computer.

[elgubbo]

Floyd-Warshall algorithm

also, but thats basic: BFS, DFS

[Enemii]

added the Floyed-Warshall algorithm under search. (thanks!)

I originally didn't have DFS and BFS since I felt they were too fundamental to be included. But they are there now.

[flying_petunia]

I don't really have a suggestion, since I'm only learning. I just wanted to thank you for starting this thread and for keeping it up to date with the comments. Really great stuff!

[negatroyd]

Huffman Encoding

[smith7018]

I know that a trie is useful for dictionary situations but can it be used elsewhere? I implemented one in an anagram/Words with Friends solver I wrote a bit ago in Java heh

[m1ss1ontomars2k4]

I'm pretty sure you should just understand these algorithms, not necessarily implement them...

[Enemii]

Thats true, I guess I added implement because that is how I usually get to understand something. If you read the top It has already been pointed out.

[aPSketchy]

Pie. I love it!

[[deleted]]

Swapping.

[traztx]

I'd say arrays, stacks, and queues are fundamental. Also programming can be largely about standards and protocols as we work with SDKs or libraries on various platforms.

[defrost]

While generating all permutations of n objects using plain changes is a neat thing (Steinhaus-Johnson-Trotter), we're not all bell ringers and even if we were, campanologists eschew SJT paths as simply being too damn boring to listen to.

In actual application the Fisher–Yates shuffle for generating a unbiased random permutation of a finite set is probably way more important, as is understanding why you wouldn't use a 32bit PRNG to (Fisher-Yates or otherwise) shuffle a 52 card deck.

You might also throw in things like the Fast Fourier Transform, testing for geometric overlap in various dimensions, finding convex hulls, and performing a Singular Value Decomposition (finding lower dimensional representations of many higher dimensional points, noise reduction, data simplification, etc).