From David Morgan-Mar’s Esoteric Algorithms page: Intelligent Design Sort Introduction Intelligent design sort is a sorting algorithm based on the theory of intelligent design. Algorithm Description The probability of the original input list being in the exact order it’s in is 1/(n!). There is such a small likelihood of this that it’s clearly absurd to … Read more
Let me try to clarify the cycle detection algorithm that is provided at Wikipedia – Tortoise_and_hare in my own words. How it works Let’s have a tortoise and a hare (name of the pointers) pointing to the beginning of the list with a cycle, as in the diagram above. Let’s hypothesize that if we move … Read more
(I’m assuming that this is just some kind of thought exercise, or even a trick homework/interview question, but I suppose I could imagine some bizarre scenario where you’re not allowed any heap space for some reason [some really bad custom memory manager? some bizarre runtime/OS issues?] while you still have access to the stack…) Breadth-first … Read more
Finite Projective Geometries The axioms of projective (plane) geometry are slightly different than the Euclidean geometry: Every two points have exactly one line that passes through them (this is the same). Every two lines meet in exactly one point (this is a bit different from Euclid). Now, add “finite” into the soup and you have … Read more
DFS: list nodes_to_visit = {root}; while( nodes_to_visit isn’t empty ) { currentnode = nodes_to_visit.take_first(); nodes_to_visit.prepend( currentnode.children ); //do something } BFS: list nodes_to_visit = {root}; while( nodes_to_visit isn’t empty ) { currentnode = nodes_to_visit.take_first(); nodes_to_visit.append( currentnode.children ); //do something } The symmetry of the two is quite cool. Update: As pointed out, take_first() removes and … Read more
These two terms differentiate between two different ways of walking a tree. It is probably easiest just to exhibit the difference. Consider the tree: A / \ B C / / \ D E F A depth first traversal would visit the nodes in this order A, B, D, C, E, F Notice that you … Read more
First let’s understand what big O, big Theta and big Omega are. They are all sets of functions. Big O is giving upper asymptotic bound, while big Omega is giving a lower bound. Big Theta gives both. Everything that is Ө(f(n)) is also O(f(n)), but not the other way around. T(n) is said to be … Read more
Divide and Conquer Divide and Conquer works by dividing the problem into sub-problems, conquer each sub-problem recursively and combine these solutions. Dynamic Programming Dynamic Programming is a technique for solving problems with overlapping subproblems. Each sub-problem is solved only once and the result of each sub-problem is stored in a table ( generally implemented as … Read more
Summary Type BST (*) Heap Insert average log(n) 1 Insert worst log(n) log(n) or n (***) Find any worst log(n) n Find max worst 1 (**) 1 Create worst n log(n) n Delete worst log(n) log(n) All average times on this table are the same as their worst times except for Insert. *: everywhere in … Read more
Well, here’s a simple implementation of an MSD radix sort for DNA. It’s written in D because that’s the language that I use most and therefore am least likely to make silly mistakes in, but it could easily be translated to some other language. It’s in-place but requires 2 * seq.length passes through the array. … Read more