Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

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.

share|improve this answer
    
+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
add comment

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.

share|improve this answer
1  
+1 to let you post links.... –  FabienAndre Dec 13 '10 at 16:50
    
@FabienAndre: Thanks! –  vz0 Dec 13 '10 at 17:11
3  
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.