I'd like to get a sense for the range of complexity that algorithms fall into. I think it would be interesting and helpful for those, like me, trying to better understand how algorithms are formulated and how to deconstruct them.
Can you offer a basic algorithm with explanation, an intermediate algorithm with explanation, and maybe an expert level one (with or without) an explanation?
From the Programmer Competency Matrix:
Beginner
Basic sorting, searching and data structure traversal and retrieval algorithms
Intermediate
Tree and Graph data structures, simple greedy and divide and conquer algorithms.
Advanced
graph algorithms, numerical computation algorithms, etc.
Beginner
Binary Search: Locates the position of an item in a sorted array.
AVL Tree Insertion: Insert an item in a AVL tree maintaining the subtree balancing property.
Depth-first Search, Breadth-first Search: Walk over the nodes of a Graph in DFS or BFS order.
Intermediate
Dijkstra's Algorithm: Graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree.
Longest Common Subsequence: Find the longest subsequence common to all sequences in a set of sequences (often just two).
Convex Hull (Graham Scan): Given a set of points, find the minimum subset of those points to cover with a convex polygon.
Counting Sort: Sorting algorithm of consecutive integers in O(n).
Advanced
Range Minimu Query: Given an array A[1,n] of n ordered objects (such as numbers), a Range Minimum Query (or RMQ) from i to j asks for the position of a minimum element in the sub-array A[i,j]. RMQs can be used to solve the lowest common ancestor problem.
Some more examples
Beginner: Linked list reversal, Mergesort, Sieve of Eratosthenes, Red-black tree algorithms (insertion and removal)
Intermediate: Simplex, Miller-Rabin primality test, Huffman coding, Kruskal's algorithm
Advanced: Viterbi Algorithm, Cooley–Tukey FFT, Simulated Annealing, Hindley–Milner type inference
I tried to find links that had at least some pseudocode and/or good explanation. But the thing about advanced algorithms is that they have many variations. So, you can explain the basic outline of a "genetic algorithm", but there are actually many algorithms that goes by that name. (The same for the FFT; I linked a named variant of it)
This text about numerical integration, for a gaming audience, describes two algorithms for numerical integration: a simpler, straightforward algorithm (the Euler integrator), and a more advanced one (the Runge-Kutta order 4 integrator). It may be a good for seeing "basic vs. advanced". You can use integrators for simulating physics, and the Euler integrator leads to enormous errors, so he recommends RK4 instead. But they are arguably variations of the "same" algorithm: Euler is first-order RK.
