Why every other playoff system sucks

Many times we’ve seen a underdog team defeating a top-ranked team in the 1st round of a major tournament. Most people rejoice (except the fans of the losing team) since everybody loves a fairy tale  victory, The organizer’s are happy since it creates a lot of buzz and everybody’s happy that the sports is still not dead since anything can happen.

Let’s take a deeper look. Team A wins 63 games out of 80 games in the regular season plays Team B which won around 40 games. Team A loses the match and bows out of the tournament. Everybody is surprised for a moment, Team B probably loses in the next round since they again play a better team and are already happy with the results they have in hand [there was a reason it only won 40 games out of 80].

The above is a common format used across many competitions in the world (NBA, Cricket Tournaments, NCAA Tournament, Champions league). But, I think such upsets does more harm to the game than benefits it. Since the team who was definitely one of the better teams in the tournament is out due to having a bad day or couple of major players being out/suspended for the game.

Some organizers e.g. the NBA, try to avoid the above scenario by either keeping N (=3,5,7) no. of matches or sometimes  giving the top ranked team a home advantage or sometimes both. Playing multiple matches definitely lowers the odds of the better team losing, however, this usually leads to some boring matches in the initial part of the tournament.

Here comes the format used by the Australian Football league, which looks like this:

Clearly, this system has numerous advantages than the knockout system usually followed. To quote Wikipedia “Under this finals system, the final eight teams are broken up into four groups of two. Each group of two earns one extra benefit over the teams beneath it. These benefits are home ground finals and the double-chance, whereby a first-week loss will not eliminate the team from the finals.”

I think atleast some tournaments should explore this format like the NCAA basketball tournament and the Cricket world cup which have the worst structure since there is only a single match between the teams and there’s no clear home-court advantage.

References:

http://en.wikipedia.org/wiki/AFL_finals_system

Largest Element in the Stack

Problem: Given a stack you have to insert a stream of numbers in it and you have to keep track of the highest element at any point in the stack

In general, the solution will require traversing through the entire stack hence taking O(n) time. However, given the option of using another data-structure this can be done using minimal extra memory using another "Stack" !.

The basic idea is when pushing an element in the original, check if the the "highest_elem_stack" is empty or if its top element is less than or equal to the element being pushed, if yes push this element on both stacks.

While popping check if the popped element is equal to the top element of the "highest_elem_stack". If yes pop both stacks.

The highest element in the original stack would always be equal to the top element in the "highest_elem_stack"

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.