Sunday, January 22, 2012

Prim's algorithm - Greedy Approach

Wikipedia : http://en.wikipedia.org/wiki/Prim%27s_algorithm

Refer to Example Run.

Saturday, January 21, 2012

Dijkstra Algorithm - Very simple explanation

Dijkstra : http://renaud.waldura.com/doc/java/dijkstra/

Phone Number - Permutation of chars

package com.algorithms;

// @author - Lakshman
// Does not validate input.

public class PhoneNumbers {

private static final boolean debug = false;
private static final char[][] digits = {{'0'}, {'1'},
{'a', 'b', 'c'}, {'d', 'e', 'f'},
{'g', 'h', 'i'}, {'j', 'k', 'l'},
{'m', 'n', 'o'}, {'p', 'q', 'r', 's'},
{'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}
};
private int permutationsCount = 0;

private void numberDisplay() {
for (int i=0; i System.out.print("array[" + i + "] length = " + digits[i].length);
System.out.print(" :: Characters are : ");
for (int j=0; j System.out.print(digits[i][j] + " , ");
}
System.out.println();
}
System.out.println("Total number of array elements = " + digits.length);
}


// Recursively display permutations.
private void numberPerms(String number, String result) {
int digit = Integer.parseInt(number.substring(0,1));
if (debug) {
System.out.println("digit = " + digit);
System.out.println("digits[numberCh].length = " + digits[digit].length);
}

// Exit condition
if (number.length() == 1) {
for (int i=0; i permutationsCount++;
System.out.println("Permutation [" + permutationsCount + "] = " + result + digits[digit][i]);
}
return;
}

// Recursive function
for (int i=0; i String result1 = result + digits[digit][i];
numberPerms(number.substring(1), result1);
}
}

public static void main(String[] args) {
PhoneNumbers phone = new PhoneNumbers();
if (debug) {
phone.numberDisplay();
}
phone.numberPerms("246", "");
}

}

*******
Output
*******
Permutation [1] = agm
Permutation [2] = agn
Permutation [3] = ago
Permutation [4] = ahm
Permutation [5] = ahn
Permutation [6] = aho
Permutation [7] = aim
Permutation [8] = ain
Permutation [9] = aio
Permutation [10] = bgm
Permutation [11] = bgn
Permutation [12] = bgo
Permutation [13] = bhm
Permutation [14] = bhn
Permutation [15] = bho
Permutation [16] = bim
Permutation [17] = bin
Permutation [18] = bio
Permutation [19] = cgm
Permutation [20] = cgn
Permutation [21] = cgo
Permutation [22] = chm
Permutation [23] = chn
Permutation [24] = cho
Permutation [25] = cim
Permutation [26] = cin
Permutation [27] = cio

Friday, January 20, 2012

Longest Increasing Sequence

Algorithm : Two ways.
1. LCS with one array - being input array a[]; second array - sort input array b[];
So complexity = nlogn (for sort) + DP

2. Another approach
Algorithm: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
Impl: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.c

LCS - Longest Common Subsequence

Very Easy approach :
Wikipedia - http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Dynamic Programming

Problem Varieties - http://www.codeforces.com/blog/entry/325

CMU edu - http://mat.gsia.cmu.edu/classes/dynamic/node2.html#SECTION00020000000000000000

Code Chef - http://www.codechef.com/wiki/tutorial-dynamic-programming

Problem : Minimum Steps to One

Problem : Minimum Steps to One
===============================

Problem Statement: On a positive integer, you can perform any one of the following 3 steps.
1.) Subtract 1 from it. ( n = n - 1 ) ,
2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2 ) ,
3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3 ). Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1

eg: 1.)For n = 1 , output: 0 2.) For n = 4 , output: 2 ( 4 /2 = 2 /2 = 1 ) 3.) For n = 7 , output: 3 ( 7 -1 = 6 /3 = 2 /2 = 1 )

Approach / Idea: One can think of greedily choosing the step, which makes n as low as possible and conitnue the same, till it reaches 1. If you observe carefully, the greedy strategy doesn't work here. Eg: Given n = 10 , Greedy --> 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1 ( 4 steps ). But the optimal way is --> 10 -1 = 9 /3 = 3 /3 = 1 ( 3 steps ). So, we need to try out all possible steps we can make for each possible value of n we encounter and choose the minimum of these possibilities.

It all starts with recursion :). F(n) = 1 + min{ F(n-1) , F(n/2) , F(n/3) } if (n>1) , else 0 ( i.e., F(1) = 0 ) . Now that we have our recurrence equation, we can right way start coding the recursion. Wait.., does it have over-lapping subproblems ? YES. Is the optimal solution to a given input depends on the optimal solution of its subproblems ? Yes... Bingo ! its DP :) So, we just store the solutions to the subproblems we solve and use them later on, as in memoization.. or we start from bottom and move up till the given n, as in dp. As its the very first problem we are looking at here, lets see both the codes.

Memoization

[code]

int memo[n+1]; // we will initialize the elements to -1 ( -1 means, not solved it yet )

int getMinSteps ( int n )

{

if ( n == 1 ) return 0; // base case

if( memo[n] != -1 ) return memo[n]; // we have solved it already :)

int r = 1 + getMinSteps( n - 1 ); // '-1' step . 'r' will contain the optimal answer finally

if( n%2 == 0 ) r = min( r , 1 + getMinSteps( n / 2 ) ) ; // '/2' step

if( n%3 == 0 ) r = min( r , 1 + getMinSteps( n / 3 ) ) ; // '/3' step

memo[n] = r ; // save the result. If you forget this step, then its same as plain recursion.

return r;

}

[/code]

Bottom-Up DP

[code]

int getMinSteps ( int n )

{

int dp[n+1] , i;

dp[1] = 0; // trivial case

for( i = 2 ; i < = n ; i ++ )

{

dp[i] = 1 + dp[i-1];

if(i%2==0) dp[i] = min( dp[i] , 1+ dp[i/2] );

if(i%3==0) dp[i] = min( dp[i] , 1+ dp[i/3] );

}

return dp[n];

}

[/code]

Both the approaches are fine. But one should also take care of the lot of over head involved in the function calls in Memoization, which may give StackOverFlow error or TLE rarely.

Reference : http://www.codechef.com/wiki/tutorial-dynamic-programming