Category Archives: Algorithms

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(“—————————-”);

}

}

Reverse a Link List

private static Node reverseList(Node head){
Node temp=null;
Node temp2=null;
//Initial state- set temp pointer at head->next
if(head.next!=null)temp=head.next;
//Set head.next null as this will eventually become last node
head.next=null;
while(temp!=null)
{
//Temporary pointer 2 to be placeholder of temp.next
temp2=temp.next;
temp.next=head;
head=temp;
temp=temp2;
}
return head;
}

Find Unique Rank for a String

Problem Statement: For each String we need to assign a unique rank.

B will Have higher rank than A
Z Will have higher rank than B
Z will have higher rank than AA
KAMAL will be higher than AMIT (K>A)
KAWAL will be higher than KAMAL (W>A)
and so on

Solution: Assign a numeric value to each character in string and then add them in a way to create a rank.
Value assigned to characters (A is lowest)
A=0.01, b=0.02.. and so on

Algorithm:

1. Loop The characters in string
1a. Assign Face weight to current character (A= 0.01, B= 0.02 etc)
1b. Assign Position Weight to current character (first char is multiple of 0.01, second of 0.0001 and so on)
1c. update totalweight by adding character weight calculated in 1a and 1b
2. Return totalweight

Code:
public static double getRank(String str)
{
str=str.toUpperCase();
char arr[]=str.toCharArray();
double rank=0;
double multiplier= 0.01;
for(int i=0;iAlgorithm Complexity:
Though if you look closely it might give impression of O(N) complexity, where N is characters in destination string. But as if are dealing with controlled input and string can be of average length 6-10 characters, we can easily confirm the algo to be of constant complexity.

Maximum Subarray Problem- N log N solution

For algorithm and explanation, read here.

Code implementation


public class MaxSumTest
{
/**
* Main method
* @param s
*/
public static void main(String s[])
{
int[] arr=new int[10];
arr=new int[]{10, -19 , 8 , 4, -5, 2, -1, 3, 8,-9};

int arrlength=arr.length/2;
int[] arr1=createarr(0,arrlength,arr);
int[] arr2=createarr(arrlength, arr.length,arr);
int sum=maxsum(arr1,arr2);
System.out.println(sum);
}

/**
* To find out maximum sum subarray, following divide and conquer technique is used
* 1. Divide the array in 2 equal parts, now there are 3 possibilities.
* a. Max sum subarray crosses the mid of original array, i.e. a part of solution is in left array and other in right. Finding this is simple as we just need to move backword on left subarray to find the maximum sum, and then move fwd on right array to find max, and finally add the two
* b. The other possibility is that max subarray is completely on left array. This means left subarray becomes main array and we discard right array. We will repeat the steps from 1.
* c. The last possibility is that max subarray is completely on right array. This means right subarray becomes main array and we discard left array. We will repeat the steps from 1.
*/
public static int maxsum(int[] arr1, int[] arr2)
{
int sum1=0;
int maxsum1=0;
int sum2=0;
int maxsum2=0;
int maxsum=0;

//1.a. Find maximum sum crossing the the mid of original array.
for(int i=arr1.length-1;i>=0;i–)
{
sum1=sum1+arr1[i];
if(maxsum1y)
if(x>z)
return x;
else
return z;
else
if(y>z)
return y;
else
return z;
}

/**
* Create a subarray from start to end
* @param start
* @param end
* @param arr
* @return
*/
public static int[] createarr(int start, int end, int[] arr)
{
int[] myarr=new int[end-start];
for(int i=start,j=0;i
Finish.

Revisiting Max Subarray Problem

Sometime back I discussed and solved a problem to find out a subarray from an array which has the maximum sum- here.

I solved the problem using brute force, that is, all the sub arrays were actually created and maximum sum subarray was found. That solution was created in order of N^2 complexity.

Let’s see how can we improve on our solution using divide and conquer approach.

Array: {-1,2,4,60,1,3,-2,-6,7,-9}

If we divide the original array into two half arrays from mid of the array. one of the following must be true

1. Max Subarray is part of first half {-1,2,4,60,1}

2. Max Sub array is part of second half {3,2,-6,7,-9}

3. Max Subarray passes through the mid of array

Array with maximum sum and passes through mid can be easily figured out in order of N. In this we will simply keep moving left and right from the mid until we hit maximum sum array, so first subarray would be 2+4+60+1+3=70

To solve 1 and 2 we will recursively use the approach with the 2 sub arrays (Repeatedly divide the array and find max having mid of the array).

The problem set is getting reduced to half with every iteration, so Log N iterations will be there in total. At max N elements are added (compared to be -ve), in each iteration, hence the total complexity of the algorithm is (N log N), so we are able to reduce the complexity from N^2 to (N log N) with the help of divide and conquer approach.

Merge Sort: Divide and Conquer Approach

Merge sort is classic example of divide and conquer algorithm approach.

Divide and Conquer Algorithm Design approach: The idea is simple, as the term suggest, we try to divide the original problem into multiple smaller problems. These small problems are solved and the solutions then are merged into one final solution.

The concept is used in merge sorting. Input to any sorting algorithm is a random list (array). For sake of this example let’s take a random array of numbers as input.

Divide Phase: Divide the main array into smaller arrays upto a level that it can sorted easily.

Conquer: Merge these entire sorted arrays into the final solution array.

Example – Lets say we have an array

Original: 99, 23, 45, 12, 67, 28, 09, 98, 44, 84

Divide Phase

Arr1: 99, 23, 45, 12, 67                | Arr2:   28, 09, 98, 44, 84

99, 23, 45                    | 12, 67        |28, 09, 98              | 44, 84

99, 23        | 45           |12    | 67     |28, 09        | 98      |44     | 84

99   | 23   | 45           |12    | 67       |28    | 09   | 98      |44     | 84

Merge Phase

23, 99      | 45           |12, 67            |09, 28   | 98           | 44, 84

23, 45, 99                  | 12, 67          | 09, 28, 98              |   44, 84

12, 23, 45, 67, 99                            | 09, 28, 44, 84, 98

09, 12, 23, 28, 44, 45, 67, 84, 98, 99

Complexity Analysis

The Divide phase of merge sort will need log N operations as in every step we are reducing length of array by half.

Merge step will again have log N merges and in each merge step we will have maximum N comparison, so the overall complexity will (N log N)

Quick Sort: Algorithm and Complexity

After talking about Insertion sort and Heap sort, another important sorting algorithm is quick sort. It is pretty simple algorithm, and will be easy to understand using an example. Lets say we have this random array which we are trying to sort

9, 5, 7, 1, 2, 4, 3, 8, 6

Most critical step of quick sort is to select a pivot element from the array. There are multiple approaches to select the pivot like- first element, last element, mid element, random element, mean, median etc. For sake of simplicity, lets say we randomly select the pivot as 5 for first iteration. Once pivot is selected, the array is divided into 2 arrays, one with elements smaller than pivot and other greater

Iteration 1:

A1: 1, 2, 4, 3

P: 5

A2: 9, 7, 8, 6

In next iteration, one of the arrays (A1) is chosen and again a pivot (say 3) is selected. The same exercise is repeated of breaking down the array into 2 sub arrays unless we get an array of size 1. After that the arrays are merged recursively in same order as they were created, ending up into final sorted array.

Average & Best Case: If we take above case where we kept on dividing the problem array into half (N/2 then N/4, N/8 and so on), and hence halfing number of comparison in every next step. we are looking at a complexity of N Log N.

Worst Case: In worst case, lets say we select highest element every time. So instead of having half the elements in an array, we have N-1 elements in next step. So in this case we end up N*N (N Square) complexity

Heapsort: Algorithm and Complexity

Heap sort is one of the most important and interesting algorithms. The implementation is base of many other sophisticated algorithms. We will focus on basics of heap sorting here. Infact, if you understand what a heap data structure is, heap sort is just application of some known simple operations on the heap.

Let’s relook at our heap

heapsort

This is a max heap so let’s try to create an array in reverse sorted order (a min heap is good for sorted in lowest to highest format and vice versa).  Before moving forward, revisit the heap data structure and understand Insert and Delete operations, after that heap sort algorithm is a cake walk.

We know that max heap has a property that element at the top is highest. Using this property, we can create an algorithm like

  1. Create max heap from the random array
  2. Remove top element from heap and add to reverse sorted array
  3. Heapify (restore heap property) the remaining heap elements
  4. Repeat Step 2 till the heap is empty

Step 1 is nothing but inserting all elements of an array to heap. One Insert Key operation takes Log N operations so N elements will take N Log N

Step 2 is order of 1 as we are just removing the top element and adding to our array

Step 3 is nothing but Delete Node operation in heap, i.e.  take last leaf node and add as root, then compare with its child nodes and swap with largest. Repeat the process till heap property is maintained, i.e. child is greater than parent.  This is Log N operations for one heapify.

Step 4 is combination of 2 & 3, N times. Step 2 is constant order and hence can be ignored. This means we have N Step 3 order or N Log N.

Combining Step 1 and 4, we figure out order of heap sort complexity is of  N Log N order.

Related: http://kamalmeet.com/2013/05/heap-data-structure/

http://kamalmeet.com/2011/07/insertion-sorting/

Heap Data Structure

Understanding of Heap data structure is very important as it is part of many other data structures like priority queue and algorithms like priority queues, Dijkstra’s.

Let’s understand Heap data structure first. Heap is a simple tree based data structure with a unique property that root node is always larger or smaller than its children.

heapsort

In the current heap we can see parent element is always higher than child nodes, hence it is called max heap. Similarly in case the parent is smaller than children, it will be min heap. Also the heap shown above is binary heap as each parent node has only two child nodes.

Let’s talk about efficiency of the heap data structure in terms of Inserting and deleting the nodes.

Insert a Key: To insert a new node, new element is added to next possible leaf node. It is then compared to its parent node and moved up if larger.

1. Insert node at next leaf

2. While element is less than parent

Swap child and parent

 

Insert operation in a heap data structure is order of log N, where N is number of nodes available.

Delete Node: Deletion always occur at the root node. Last leaf node is moved to root and then moved down till it is greater than children.

1. Node =root

2. While node <any child

Swap node and largest child

Delete operation in a heap data structure is order of log N, where N is number of nodes available.

Banker’s algo for deadlock avoidance

What is deadlock?

From wikipedia- A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the “chicken or the egg“. The concept of a Catch-22 is similar.

So what is a deadlock in terms of operating system job scheduling. It is same, there are multiple jobs which are trying to gain control of resources and end up in a situation where each process is waiting for some resiurce which is being held by another process.

How to avoid such situations? Banker’s algoirthm is the answer. As the name suggest, the algorithm uses intellegence shown by a banker in order to maintain safe amount of cash in the bank, so that bank never runs into a situation where it has no money to fulfill its customer needs.

A very simple example will be, say the bank has 60K amount. There are 3 customers A, B and C. A needs 30K for its project, B needs 25K, and C needs 40K. Now we know that bank can fulfill need of all three customers, but not at once. So ideally the bank will fulfill one customer’s need at a time, wait for the customer to return the money (we will ignore interest for simplicity, and we will assume money will be returned by cistomer as soon as project is finished though in real workd cstomer might need some time), and then move on to next. Which is not effective use of money as customers will need to wait while others finish. In practical world, not all the money will be needed for projects in one go, so the bank can ask customers how much amount they will need at what stage, and at what time they can return the money, and try to organize the finances in a way that all customers can finish there projects in best possible time. The same kind of logic is used by job-scheduler of on operating system to make sure all jobs gets finished in best possible time, avoiding deadlock.

Lets say customers provide this data to bank

Customer A: Need 10K at start

Customer B: Need 10K at start

Customer C: Need 10K at start

The bank sees it can afford to give this money to all the customers as it will still have enough money to fulfill needs of all the customers.

In stage 2, all customers again come up with a demand of 10K. Now the bank sees if it will allocate all the money, it will run out of money with none of the projects being successfully completed, hence no point of recovery. So it must deny some of the customer. Safest bet will be to refuse the amount to C and tell it to wait till bank has enoght fund. Allocate the money to A and B, as it will still have enough money to give to these customer to finish the project.

So C is put on hold and A and B moves on with the project. Now say A comes up with demand of 10K, which bank will fulfill and A will be able to finish project successfully and return 30K. Now bank can provide money to C, as it knows it will have sufficient funds for other customers.

The same intellegence is used by an OS to make sure the system never runs out of resources.