# An example of a beginner-level Algorithm, intermediate level Algorithm and a complex/expert level Algorithm?

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.

graph algorithms, numerical computation algorithms, etc.

-
+1 (when I get votes) for the PCM. – Josh K Dec 13 '10 at 18:54
These seem to be pitched somewhat lower than the ones in other answers. – Eliot Ball Aug 30 '12 at 11:25

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

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.

-
+1 to let you post links.... – FabienAndre Dec 13 '10 at 16:50
@FabienAndre: Thanks! – vz0 Dec 13 '10 at 17:11
I agree in general, but I'd say that a counting sort is far easier than AVL tree insertion. – Viktor Dahl Sep 19 '11 at 7:00

Some more examples

Beginner: Linked list reversal, Mergesort, Sieve of Eratosthenes, Red-black tree algorithms (insertion and removal)

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.

-