Design Patterns

Design patterns are common practices which are used to solve problems which are similar in nature. More »

Algorithms and Data Structures

Data structures are basic building blocks of any computer program. Algorithms are used to solve any real life program programatically. More »

Java programming language

Java is one of the most popular and advanced programming language which is used to create many enterprise level solutions. More »

Fun Stuff

Kool and fun side of technology. More »

Other stuff

Random posts More »

 

InOrder, PreOrder and PostOrder traversal

I had discussed Breadth first and Depth First traversal algorithms sometime back.

There are 3 important traversing algorithms for tress. http://en.wikipedia.org/wiki/Tree_traversal

InOrder
-Travel Left, Travel Root, Travel Right.

PreOrder
-Root, Left, Right

PostOrder
-Left, Right, Root

Here is recursive implemenation
public void inOrder(Node root)
{
if(root.left!=null)
inOrder(root.left);
System.out.println(root.number);
if(root.right!=null)
inOrder(root.right);
}


public void preOrder(Node root)
{

System.out.println(root.number);
if(root.left!=null)
preOrder(root.left);
if(root.right!=null)
preOrder(root.right);
}

public void postOrder(Node root)
{
if(root.left!=null)
postOrder(root.left);
if(root.right!=null)
postOrder(root.right);
System.out.println(root.number);
}

Basketball Probability Puzzle

Problem: You have two options

1: One successful shot at the hoop
2: 2 of 3 successful shots at the hoop

Let P be the probability of making a successful hit, for what value of P will you choose option 2 over 1.

Solution:

If P is probability for option 1

Option 2, we can have 2 cases of success, one all 3 shots are successful – P*P*P

or 2 Hits and 1 Miss (HHM, HMH, MHH) 3 cases, each with probability of P*P*(1-P) i.e. 1-P for one miss. as there are 3 cases, total probability is 3*P*P*(1-p). Combining both result for option 2, P*P*P + 3*P*P*(1-P).

To prefer option 2,

P*P*P + 3*P*P*(1-P)>P
P*P+3P(1-P)>1

Can be solved to quadratic equation

-2P^2+3P-1>0
or
(2P-1)(P-1)>0

P>1 not possible so
P>1/2 or .5

Choose option 2 when probability of hitting hoop is more than 0.5

Monty Hall problem

Monty Hall problem is an interesting problem that plays with probability.

Problem: There are three doors, say A, B and C. Behind one of the doors there is a prize and two are empty. You have to make a choice and try to win the prize. You choose a door say A, now host opens the door C, which is empty. The question is, should you switch the doors?

Solution: According to one solution proposed, Switching doors will increase probability of winning. This is the explanation behind that

Initially all 3 doors has probability of 1/3 of winning. So when we choose door A, we had probability of winning – 1/3. Now Doors B & C have collective probability of winning as 2/3. So when we know C is empty, probability of prize behind B is 2/3(?).

Frankly the argument does not look very strong, for me the new probability should be 1/2 for each door.

Read more here- http://en.wikipedia.org/wiki/Monty_Hall_problem

Graph Data Structure

Graph is distant relative of Tree. Infact it is complexer than tree, as in tree, a node usually have link with nodes one level up or down and does not conatin any cycles, whereas graph does not have any such restrictions. Graph data structure is more useful in case of something like traveling salesman problem, or to represent computer network, i.e. a structure where we have nodes and relationship between them.

graph

In the above graph structure, we have 4 nodes or Vertices and 6 Edges (connectors). A graph is usually represented as G=(V,E).

Please note that the graph given above is directed, that is we can see link is from 1->2 and not 2->1. In undirected graph, the arrows showing direction of connection will not be there and connection can be considered both ways.

Adjacency Matrix

The above graph can be shown as

[1] [2] [3] [4]
[1]   0    1     0    1
[2] 0 0 1 1
[3] 1 0 0 0
[4] 0 0 1 0

if the same graph was undirected
[1] [2] [3] [4]
[1] 0 1 1 1
[2] 1 0 1 1
[3] 1 1 0 1
[4] 1 1 1 0

Always Aij=Aji in undirected

Adjacency List Representation

Node1->[Node2, Node4]
Node2->[Node3, Node4]
Node3->[Node1]
Node4->[Node3]

Other useful information for Graphs

Degree: Number of edges being attached to current vertex
In-Degree: Number of edges coming into the vertex in case of directed graph
Out-Degree: Number of edges going out from the vertex in case of directed graph

Weighted Graphs:

This is important in case we are trying to solve problems like traveling salesman. For example, if we look at above graph, we can see there are 2 ways to reach Vertex 3 from Vertex 1, that is, 1->4 or 1->2->4. Say these vertices represent cities, and edge weight represent distance in this case.

1->2= weight 20
2->4= 30
1->4= 60

So we can choose 1->2->4 over 1->4 as it will be shorter distance.

Depth First Search

In last post I talked about Breadth First Search. An alternative to that, is Depth First Search, used in cases we want to check upto a depth level first rather than breadth.

So let’s look back at the last example

BSD

This time we would like to parse something like

1. Check Root- 10

2. Check till depth level for one node- 18,7

3. Repeat for other nodes 22,15 and then 5, 12

A straight forward way is to modify the Breadth First Search algorithm to use Stack instead of Queue.

1. Push Root Node R to Stack S
2. Pop s node from S
3 a . If s.val is required value, return Success
3 b. Else Push all Neighbor/ child nodes to stack
4. If Stack is not empty, Repeat from 2
5. If Stack is empty, we have traversed all the nodes and not found the required node. Return failure.

Breadth First Search

Breadth First search is an effective search mechanism for Graphs and Tree Data structure. As the name suggest, this technique makes sure that all the nodes at same level/ breadth are checked before moving to deeper levels.

BSD

The above structure is hybrid of tree and graph (Still a tree as there are no cycles). Let us what it means to do a breadth first search here.

We will start with root node i.e. 10.

Move to level 2 and check nodes 18, 22, 5.

Check the next level- 7, 15, 12 and so on.

Here is algorithm to implement Breadth first search

1. Add root node R to queue- Q

2. Fetch next node N from Q

3 a. If the N.val is required val, return success

3 b. Else Find all Child/ Neighbour nodes which are not traversed already and add to Queue

4. If there are more nodes in Q, Repeat from 2.

5. If Q is empty, we know we have traversed all nodes, return failure as node not found

Read more here- http://en.wikipedia.org/wiki/Breadth-first_search

http://en.wikipedia.org/wiki/Breadth-first_search

Understanding Permutation and Combination -2

Combinations:

In last post I talked about calculating permutation. Combinaitons differ from permutation in that ordering does not matter in case of combinations. For example we were concerned about first digit, second digit etc, whereas in combination it will not matter. For example we need to pull 4 balls out of 10, order does not matter. To make it easy, let us say 2 balls are to be choosen out of 4

So we can choose

1,2
1,3
1,4
2,3
2,4
3,4

Total 6

Whereas when we were talking about permutation, we were concerned about order as well. So 1,2 was different from 2,1

1,2
1,3
1,4
2,1
2,3
2,4
3,1
3,2
3,4
4,1
4,2
4,3
Total 12, same as 4P2 or 4!/(4-2)!

So the difference between permutation and combination is that we have removed ordering info in case of combinations. In how many ways we can order 2 numbers, exactly 2 (1,2 or 2,1). In how many ways we can order 3 objects- 6 (1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,1,2; 3,2,1) or 3!. Similarly we can prove n objects can be ordered n! times.

So a formula for combinations would be nPr/r!

nCr= nPr/n! or n!/(n-r)!r!

Using it for 4 balls out of 10
10!/4!6! = 210

Understanding Permutation and Combination -1

If I go back to my previous post of finding traveling salesman problem, and I need to know how many options are available to visit all the cities, understanding of permutations and combinations can help me.

Permutation:
In how many ways we can choose and arrange options. For example, you have to create N digit number as a code, say 4 digit number.

You can choose the number in 10^4 ways. This is how-

First digit- 10 options (0 to 9 – say 0 is allowed)
Second digit- 10 options
and so on.

So at the end we have
10*10*10*10 options or 10^4

or to generalize

n*n*n*n.. r times i.e. n^r

The above case is for permutation where repetition is allowed. There can be a case where repetition is not allowed, e.g. instead of choosing numbers randomly, we are picking random balls from a sack. So if you have picked ball number 7 once, it will not be available for reuse.

First digit- 10 options
Second digit- 9 options (first digit option not available for reuse).
Third- 8
Fourth- 7

Total Options 10*9*8*7

generalize

n*(n-1)*(n-2).. (n-r)

nPr = n!/(n-r)!

Solving the Traveling salesman problem

Traveling salesman problem is a classic NP hard problem.

Problem Statement: A salesman has to visit N number of cities, say A, B, C and D. He is starting from A, and need to visit all other cities in a way that he has to cover shortest distance.

Solution: Ideal solution will be to figure out all the permutations of traveling N cities, and then choose the one where distance traveled is smallest.

Finding all Permutations is definitely a trouble. 10! will take us into million permutations and moving ahead further adds to trouble.

One solution can be to pick random city from every city and move ahead. A little betterment will be to move to next nearest city instead of random city.

1. Start from city 0
2. Look for the nearest city, not visited already
3. Go to the nearest city, mark it visited
4. If not all city visited, go to 2

Here is a piece of code

public static int travel()
{
currcity=0;
path[index++]=0;

int[][] tempdistance=distance.clone();
printarr(tempdistance);
citiesLeft=removeArr(citiesLeft, currcity);

while(citiesLeft.length>0)
{
int nextcity=findNearest(currcity, tempdistance);
path[index++]=nextcity;
currcity=nextcity;
citiesLeft=removeArr(citiesLeft, currcity);
printarr(tempdistance);
}
//Final path
for(int i=0;i<path.length;i++) System.out.print(path[i]+">");
return -1;
}

Here is the complete code

public class TravelingSalesman {

static int distance[][]={
//AA=0; AB=1; AC=2; AD=3
{0,6,2,1},
{2,0,2,3},
{1,2,0,1},
{6,10,2,0}
};

static int path[]=new int[4];
static int currcity=0;
static int index=0;
static int totalcity=0;
static int[] citiesLeft={0,1,2,3};

public static void main(String sp[])
{
totalcity=distance[0].length;
System.out.println(travel());
}

public static int travel()
{
/*
* 1. Start from city 0
* 2. Look for the nearest city, not visited already
* 3. Go to the nearest city, mark it visited
* 4. If not all city visited, go to 2
*/

currcity=0;
path[index++]=0;

int[][] tempdistance=distance.clone();
printarr(tempdistance);
citiesLeft=removeArr(citiesLeft, currcity);

while(citiesLeft.length>0)
{
int nextcity=findNearest(currcity, tempdistance);
path[index++]=nextcity;
currcity=nextcity;
citiesLeft=removeArr(citiesLeft, currcity);
printarr(tempdistance);
}
//Final path
for(int i=0;i<path.length;i++) System.out.print(path[i]+”>”);
return -1;
}

public static int[] removeArr(int[] arr, int num)
{
int[] citiesLeft=new int[arr.length-1];
if(citiesLeft.length==0)
return citiesLeft;
int j=0;
for(int i=0;i<arr.length;i++)
{
if(arr[i]!=num)
citiesLeft[j++]=arr[i];
}
return citiesLeft;
}

public static boolean availableInCitiesLeft(int check)
{
for(int i=0;i<citiesLeft.length;i++)
{
if(citiesLeft[i]==check)
return true;
}
return false;
}

public static int findNearest(int curr, int arr[][])
{
int nearest=0;
int nearestval=0;
for (int i=0;i<arr[0].length;i++) { if(availableInCitiesLeft(i)) if(arr[curr][i]>0)
if(nearestval<=0 || arr[curr][i]<nearestval)
{
nearestval=arr[curr][i];
nearest=i;

}
}
return nearest;
}

public static void printarr(int arr[][])
{
for(int i=0;i<arr[0].length;i++){
for(int j=0;j<arr[0].length;j++){
System.out.print(arr[i][j]+”,”);
}
System.out.println(“”);
}
System.out.println(“—————————-”);

}

}

Jmeter- Record and Play test cases

In my last post I talked about record part of test case in Jmeter.

Next step is to run the test cases, this is relevant even if you have created test cases manually. The first thing we need to add for any test plan is Thread Group.

Right Click on Test plan->Add-> Threads -> Thread Group

You can create test cases manually or record within Jmeter. A basic tool for providing the result data is Summary Report

Thread Group->Add-> Listener->Summary Report

There are additional reporting tools which can be used like Response Time Graph, Graph result etc.

By default the test will execute only once, but this is configurable in Thread Group properties.

Jmeter2

You can see I have set users, rampup and loop as 5.

Number of threads or user will simulate number of users hitting the application simultaneously.

Rampup period will give time it takes for the peak load. For example you have set number of user as 1000, and ramp up period as 100 seconds, Jmeter will start with 1 (or more) user at second one and will increase load gradually. At 100th second, load will get raised to 1000 users.

Loop 1 means that all users will hit the application URL only once. a higher value, say 10 means each user hits the application 10 times. so 1000 users with loop of 10 means a total of 10000 hits on URL.

Once the test completes, we can see results in Summary report or other graphs