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

View original post

Interval Partitioning Problem

Everything Under The Sun

The interval partitioning problem is described as follows:
Given a set {1, 2, …, n} of n requests, where ith 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:

  1. s(i) <= s(j) and f(i) > s(j)
  2. 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

Euclid’s algorithm

Delete all duplicate elements from a singly linked list with O(n) time complexity and O(1) space.

Delete all duplicate elements from a singly linked list with O(n) time complexity and O(1) space..

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.

monster-small

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

The Code Vault

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] << ” “;
}

View original post

Heapsort

The Code Vault

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?

Dark Views

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.

 

View original post

Algorithms: Why are they useful?

TheJugad

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

The Code Vault

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