# Category Archives: Algorithms

## Worst case upper bounds is wrong metric to compare algorithms

Sudhish Rema's blog on Technology

Prof. Robert Sedgewick Princeton University talks about pit falls of using worst case BigO to compare algorithms

## Interval Partitioning Problem

The interval partitioning problem is described as follows:*Given a set {1, 2, …, n} of n requests, where i ^{th} request starts at time s(i) and finishes at time f(i), find the minimum number of resources needed to schedule all requests so that no two requests are assigned to the same resource at the same time. Two requests i and j can conflict in one of two ways:*

- s(i) <= s(j) and f(i) > s(j)
- s(j) <= s(i) and f(j) > s(i)

**Example:** Given 3 requests with s(1) = 1, f(1) = 3, s(2) = 2, f(2) = 4, s(3) = 3, f(3) = 5, at least 2 resources are needed to satisfy all requests. A valid assignment of requests to resources is {1, 3} and {2}.

View original post 390 more words

## Fast Path Finding (part II)

Harder, Better, Faster, Stronger

Last week we had a first look at a simple path finding algorithm with application to games. This week, let us have a look a the relative performance of the implementations considered: C# with a naïve implementation that scans the whole map multiple times; a C# implementation that uses lists to maintain and visit only the border of the solved region (affording massive speed-ups, one hopes); and C++ versions of these two variants, plus a C++ variant that uses set (as bitmaps) to maintain the border list.

In any quantitative study, the first thing to do is to collect data. The best way is to automate the collection, by, for example, adding a function that puts the player in all legal positions on the map, compute all the shortest paths, and measures how long it takes. One may also consider disabling the *on-demand* power policy as the CPU may jump…

View original post 551 more words

## Merge Sort

**C++ Code To Illustrate Merge-Sort In A Single Array:**

#include<iostream.h>

void merge(int A[],int p, int q, int r)

{

int i,j,k;

int x = q-p+1;

int y = r-q;

int B[20];

int C[20];

B[x] = 10000;

C[y] = 10000;

for (i=0;i<x;i++) B[i] = A[p+i];

for (i=0;i<y;i++) C[i] = A[q+i+1];

i=0;j=0;

for (k=p;k<=r;k++)

{

if (B[i]<=C[j]) A[k] = B[i++];

else A[k] = C[j++];

}

}

void mergesort(int A[], int p,int r)

{

int q;

if (p<r)

{

q = (p+r)/2;

mergesort(A,p,q);

mergesort(A,q+1,r);

merge(A,p,q,r);

}

}

void main()

{

int A[20],n;

cout << “Enter Length Of Array \n” ;

cin >> n;

cout << “Enter Array \n”;

int i;

for (i=0;i<n;i++) cin >> A[i];

mergesort(A,0,n-1);

cout << “Sorted Array \n” ;

for (i=0;i<n;i++) cout << A[i] << ” “;

}

## Heapsort

**Java Code To Illustrate Heapsort:**

package heapsort;

import edu.princeton.cs.introcs.*;

public class Heapsort

{

public static int heapsize;

public static int Parent(int i)

{

return i/2;

}

public static int Left(int i)

{

return 2*i+1;

}

public static int Right(int i)

{

return 2*i+2;

}

public static void MaxHeapify(int A[], int i)

{

int l = Left(i);

int r = Right(i);

int greatest,temp;

if (l<heapsize && A[l]>=A[i]) greatest = l;

else greatest = i;

if (r<heapsize && A[r]>=A[greatest]) greatest = r;

if (greatest!=i)

{

temp = A[greatest];

A[greatest] = A[i];

A[i] = temp;

MaxHeapify(A,greatest);

}

}

public static void BuildHeap(int A[], int n)

{

int i;

for (i=(n/2)-1;i>=0;i–) MaxHeapify(A,i);

}

public static void heapsort(int A[])

{

BuildHeap(A,heapsize);

int i,temp;

for (i=A.length-1;i>=1;i–)

{

temp = A[0];

A[0] = A[i];

A[i] = temp;

heapsize–;

BuildHeap(A,heapsize);

}

}

public static void displayheap(int A[])

{

int height = (int)((Math.log10(A.length)) / (Math.log10(2)));

int spaces =…

View original post 82 more words

## Quick: How Does Quicksort Work?

Every now and then, we need to remember how some complex algorithm works. For some, code works well. Or puzzles. Others prefer an explanation with examples. A third group likes to see what is going on.

The AlgoViz.org portal contains visualizations of all kinds of algorithms for the visually inclined.

## Algorithms: Why are they useful?

This is such a hilarious question I just had to take a crack at it.

First, let’s get one thing out of the way: even single-line procedures are technically algorithms. Hence,

1 | Jeffrey. Love me. |

is an algorithm, provided by Maude to The Dude. Admittedly, however, those are not very interesting algorithms (though they can be plenty useful), so let’s focus on more elaborate ones.

Take, for example, lovemaking. You have an algorithm for that.

It has bifurcations.

1 2 3 4 | If He moans Then Move to Next Step. |

It has loops.

1 2 3 4 5 6 | Repeat Forwards. Delay 0.1s Backwards. Delay 0.2s Until (something magical happens) or (you're exhausted). |

It has subroutines.

1 2 3 4 | Do That Thing That Always Sends Him To The Moon. Do Cuddle. |

It relies heavily on random number generators.

1 2 3… |

View original post 169 more words

## QuickSort

**Java Code To Illustrate QuickSort:**

package quicksort;

import edu.princeton.cs.introcs.*;

public class QuickSort

{

public static void display(int a[])

{

for (int k=0;k<a.length;k++) System.out.print(a[k] + ” “);

System.out.println();

}

public static int Partition(int A[], int p, int r)

{

int pivot = A[r];

int i = p-1;

int temp;

for (int j=p;j<r;j++)

{

if (A[j]<=pivot)

{

i++;

temp = A[i];

A[i] = A[j];

A[j] = temp;

}

}

temp = A[r];

A[r] = A[i+1];

A[i+1] = temp;

return i+1;

}

public static int HoarePartition(int A[], int p, int r)

{

int i = p;

int j = r;

int x = A[p];

int temp;

while (i<j)

{

while(A[j]>=x && j>p) –j;

while(A[i]<=x && i<r) ++i;

if(i<j)

{

temp = A[i];

A[i] = A[j];

A[j] = temp;

}

}

temp = A[p];

A[p] = A[j];

A[j] = temp;

return j;

}

public static void quicksort(int A[],int p, int r)

{

if…

View original post 55 more words