Shuffling

Shuffling is a very interesting programming problem, Almost everybody can come up with a good algorithm using a simple rand() function, but it gets a little tricky when one has to perform a in place shuffle (i.e. w/o using any extra memory).

Knuth's Algorithm described in the Art of Computer programming, Vol 2 (which is based on Fisher Yates algorithm) is regarded as one the best known algorithm for the problem.

The description on wikipedia is a little clearer and goes like this:
1. Let A1 := 1, A2 := 2 and so on up to AN := N, and let n := N.
2. Pick a random number k between 1 and n inclusive.
3. If k ≠ n, swap the values of Ak and An.
4. Decrease n by one.
5. Repeat from step 2 until n is less than 2.

  public static void shuffle (int[] array) 
    {        
        Random rng = new Random();   // i.e., java.util.Random.
       
       // The number of items left to shuffle (loop invariant).
        int n = array.length;                
        
        while (n > 1) 
        {
            int k = rng.nextInt(n);  // 0 <= k < n.
            n--;      // n is now the last pertinent index;
            // swap array[n] with array[k] (does nothing if k == n).
            int temp = array[n];                 
            array[n] = array[k];
            array[k] = temp;
        }
    }

Alternately, instead of going n to 1 we can do a forward pass like here:

int N = array.length; 
for (int i = 0; i < N; i++) 
{ 
   int r = i + (int) (Math.random() * (N-i)); 
   int t = array[r]; 
   array[r] = array[i]; 
   array[i] = t; 
} 

An alternative method is we can assign each element of the set to be shuffled a random number and the set is then sorted according to these numbers. This may be faster in practice, despite having worse asymptotic time complexity (O(n log n) vs. O(n)).

Like the Fisher-Yates shuffle, this method will also produce unbiased results if correctly implemented, and may be more tolerant of certain kinds of bias in the random numbers. However, care must be taken to ensure that the assigned random numbers are never duplicated, since sorting algorithms in general won't order elements randomly in case of a tie.

Wikipedia also defines a interesting algorithm very similar to the Knuth's algorithm called the Sattolo algorithm for generating uniformly distributed cyclic permutations. The only difference between the 2 algorithms is that in Sattolo's algorithm in step 2, the random number k is chosen from the range between 1 and n−1 (rather than between 1 and n) inclusive.

To turn the Java example above into an example of Sattolo's algorithm, simply replace rng.nextInt(n) with rng.nextInt(n-1) in the code. This simple change modifies the algorithm so that the resulting permutation always consists of a single cycle.

Reference:
1. TAOCP Vol 2 Section 3.4.5 by Donald Knuth
2. http://en.wikipedia.org/wiki/Knuth_shuffle

Finding a loop in a singly linked list

There are three "decent" solutions for it

1. Pass through the list, use a hashtable to store the addresses of the visited nodes, if 2 nodes hash to same key, there's a loop.

function boolean hasLoop(Node startNode){
  HashSet nodesSeen = new HashSet();
  Node currentNode = startNode;
  do {
    if (nodesSeen.contains(currentNode)) return true;
    nodesSeen.add(currentNode);
  } while (currentNode = currentNode.next());
  return false;
}

2. Floyd's Cycle-Finding Algorithm

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

Alternately, in C

p=q=head;
do{
p=p->next->next;
q=q->next;
}while p!=q or p!=null;
if p==q
loop exists
else
no loop

To find the smallest index where the cycle starts:

// To find the smallest index where the cycle starts
// P is set from last algorithm
int index=0;
q=0;
while p!=q{
     p=p->next;
     q=q->next;
     index ++;
}
return index;

To find cycle length

// P & Q  is set from last algorithm
int len=0;
while p!=q{
     p=p->next;     
     len ++;
}
return len;

See reasoning for len, index functions at wiki


3. Brent' Algorithm

power=len=1;
q=head;
p=head->next;

while p!=q {
 if (power==len){
  p=q;
  power*=2 , len=0;
 }
 p=p->next; len++;
 if(p==NULL) return (no cycle);
}
return (cycle), len;

For finding Index

i=index=0;
p=q=head;
while(i++<len)
 p=p->next;

while p!=q {
  q=q->next;
  p=p->next;
  index++;
}
return index;

Reference:
http://ostermiller.org/find_loop_singly_linked_list.html
wiki

Delete a node in single linked list

The solution to this is to copy the data from the next node into this node and delete the next node!. Ofcourse this wont work if the node to be deleted is the last node. Mark it as dummy in that case. If you have a Circular linked list, then this might be all the more interesting.

Two problems for the day

Robotic Arm movement: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=37

Binary Search: http://codekata.pragprog.com/2007/01/kata_two_karate.html

To be updated...

Optimizing Loops

A few ways to optimize loops

Iterating through loops has the following structure in many cases:

for(int k=0; k<someVar.length(); k++)

Check it out, you execute the k=0 command, then you execute the comparison as well as the length method as many times as you have n variables to loop through. Finally you increment k n+1 times. This all leads to a lot of executions. To make it go faster:

int length = someVar.length();
for(int k=0; k<length; k++)

Taking the method call to length() out will increase the loop's speed slightly. However, you're still calling length from the variable table n times. So try it this way instead:

int length = someVar.length();
for(int k=length; k>0; --k)

This will iterate backwards. What that means, is that now you won't be pulling up 2 variables in the comparison. You'll only compare one variable to 0. Although, it isn't necessarily that much more beneficial to call length outside of the loop statement now since your call to length is only executed once.

Virtual Destructors

If an object (with a non-virtual destructor) is destroyed explicitly by applying the delete operator to a base-class pointer to the object, the base-class destructor function (matching the pointer type) is called on the object.

There is a simple solution to this problem: declare a virtual base-class destructor. This makes all derived-class destructors virtual even though they don't have the same name as the base-class destructor. Now, if the object in the hierarchy is destroyed explicitly by applying the delete operator to a base-class pointer to a derived-class object, the destructor for the appropriate class is called.

Virtual constructor: Constructors cannot be virtual. Declaring a constructor as a virtual function is a syntax error.

To be completed .. (Example)

References
WikiAnswers