Monday, December 28, 2015

Binary Search Tree

Deletion Explained:
https://www.youtube.com/watch?v=gcULXE7ViZw

Complete Series
http://www.youtube.com/playlist?list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P

Thursday, June 25, 2015

Data Structures and their applications

http://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html

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