ME-DATA STRUCTURE LAB PGMS

LOCKING AND SYNCHRONIZATION MECHANISMS

QUEUE

import java.util.LinkedList;

import java.util.concurrent.locks.Lock;

import java.util.concurrent.locks.ReentrantLock;

class GenQueue<E> {

private LinkedList<E> list = new LinkedList();

Lock  lock = new ReentrantLock();

public synchronized void enqueue(E item) {

lock.lock();

list.addLast(item);

lock.unlock();

}

public synchronized E dequeue() {

lock.lock();

E e = list.poll();

lock.unlock();

return e;

}

public boolean hasItems() {

return !list.isEmpty();

}

public int size() {

return list.size();

}}

class Employee {

public String lastName;

public String firstName;

public Employee() {

}

public Employee(String last, String first) {

this.lastName = last;

this.firstName = first;

}

public String toString() {

return firstName + " " + lastName;

}}

public class QueueTest {

public static void main(String[] args) {

GenQueue empList;

empList = new GenQueue();

empList.enqueue(new Employee("Mani", "R"));

empList.enqueue(new Employee("Nasa", "S"));

empList.enqueue(new Employee("Rajesh", "R"));

System.out.println("The employees' names are:");

while (empList.hasItems()) {

Employee emp = (Employee) empList.dequeue();

System.out.println(emp.firstName + " "

+ emp.lastName);

}}}

OUT PUT

O:\>java QueueTest

The employees' names are:

R Mani           

S Nasa

R Rajesh

RECURSIVE BACKTRACKING

N-Queens

import java.util.*;

public class EightQueens {

private int[] perm;

private boolean[] used;

private int numsols;

public static void main(String[] args) {

EightQueens obj = new EightQueens(5);

obj.solveIt();

obj.printNumSols();

}

public EightQueens(int n) {

perm = new int[n];

used = new boolean[n];

numsols = 0;

for (int i=0; i<n; i++) {

perm[i] = -1;

used[i] = false;

}}

public void solveIt() {

solveItRec(0);

}

public void solveItRec(int location) {

int i;

if (location == perm.length) {

printSol();

numsols++;

}

for (i=0; i<perm.length; i++) {

if (used[i] == false) {

if (!conflict(location, i)) {

perm[location] = i;

used[i] = true;

solveItRec(location+1);

used[i] = false;

}}}}

private boolean conflict(int location, int row) {

int i;

for (i=0; i<location; i++)

if (Math.abs(location - i) == Math.abs(perm[i] - row))

return true;

return false;

}

public void printSol() {

int i,j;

System.out.println("Here is a solution:\n");

for (i=0; i<perm.length; i++) {

for (j=0; j<perm.length; j++) {

if (perm[j] == i)

System.out.print("Q ");

else

System.out.print("_ ");

}

System.out.println("\n");

}}

public void printNumSols() {

System.out.println("There were "+numsols+" solutions.");}}

Out put

O:\>javac  EightQueens.java

O:\>java EightQueens

Here is a solution:

Q _ _ _ _

_ _ _ Q _

_ Q _ _ _

_ _ _ _ Q

_ _ Q _ _

Here is a solution:

Q _ _ _ _

_ _ Q _ _

_ _ _ _ Q

_ Q _ _ _

_ _ _ Q _

Here is a solution:

_ _ Q _ _

Q _ _ _ _

_ _ _ Q _

_ Q _ _ _

_ _ _ _ Q

Here is a solution:

_ _ _ Q _

Q _ _ _ _

_ _ Q _ _

_ _ _ _ Q

_ Q _ _ _

Here is a solution:

_ Q _ _ _

_ _ _ Q _

Q _ _ _ _

_ _ Q _ _

_ _ _ _ Q

Here is a solution:

_ _ _ _ Q

_ _ Q _ _

Q _ _ _ _

_ _ _ Q _

_ Q _ _ _

Here is a solution:

_ Q _ _ _

_ _ _ _ Q

_ _ Q _ _

Q _ _ _ _

_ _ _ Q _

Here is a solution:

_ _ _ _ Q

_ Q _ _ _

_ _ _ Q _

Q _ _ _ _

_ _ Q _ _

Here is a solution:

_ _ _ Q _

_ Q _ _ _

_ _ _ _ Q

_ _ Q _ _

Q _ _ _ _

Here is a solution:

_ _ Q _ _

_ _ _ _ Q

_ Q _ _ _

_ _ _ Q _

Q _ _ _ _

SUDOKU

public class sudoku {

public static void main(String[] args) {

int[][] matrix = parseProblem(args);

writeMatrix(matrix);

if (solve(0,0,matrix))    // solves in place

writeMatrix(matrix);

else

System.out.println("NONE");

}

static boolean solve(int i, int j, int[][] cells) {

if (i == 9) {

i = 0;

if (++j == 9)

return true;

}

if (cells[i][j] != 0)  // skip filled cells

return solve(i+1,j,cells);

for (int val = 1; val <= 9; ++val) {

if (legal(i,j,val,cells)) {

cells[i][j] = val;

if (solve(i+1,j,cells))

return true;

}

}

cells[i][j] = 0; // reset on backtrack

return false;

}

static boolean legal(int i, int j, int val, int[][] cells) {

for (int k = 0; k < 9; ++k)  // row

if (val == cells[k][j])

return false;

for (int k = 0; k < 9; ++k) // col

if (val == cells[i][k])

return false;

int boxRowOffset = (i / 3)*3;

int boxColOffset = (j / 3)*3;

for (int k = 0; k < 3; ++k) // box

for (int m = 0; m < 3; ++m)

if (val == cells[boxRowOffset+k][boxColOffset+m])

return false;

return true; // no violations, so it's legal

}

static int[][] parseProblem(String[] args) {

int[][] problem = new int[9][9]; // default 0 vals

for (int n = 0; n < args.length; ++n) {

int i = Integer.parseInt(args[n].substring(0,1));

int j = Integer.parseInt(args[n].substring(1,2));

int val = Integer.parseInt(args[n].substring(2,3));

problem[i][j] = val;

}

return problem;

}

static void writeMatrix(int[][] solution) {

for (int i = 0; i < 9; ++i) {

if (i % 3 == 0)

System.out.println(" -----------------------");

for (int j = 0; j < 9; ++j) {

if (j % 3 == 0) System.out.print("| ");

System.out.print(solution[i][j] == 0

? " "

: Integer.toString(solution[i][j]));

System.out.print(' ');

}

System.out.println("|");

}

System.out.println(" -----------------------");

}

}

OUTPUT:

O:\>javac Sudoku.java

O:\>java Sudoku

-----------------------

|       |       |       |

|       |       |       |

|       |       |       |

-----------------------

|       |       |       |

|       |       |       |

|       |       |       |

-----------------------

|       |       |       |

|       |       |       |

|       |       |       |

-----------------------

-----------------------

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

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

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

-----------------------

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

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

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

-----------------------

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

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

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

-----------------------

NETWORK FLOW PROGRAMING

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

import java.util.Set;

public class NetworkFlowProb

{

private int[] parent;

private Queue<Integer> queue;

private int numberOfVertices;

private boolean[] visited;

private Set<Pair> cutSet;

private ArrayList<Integer> reachable;

private ArrayList<Integer> unreachable;

public NetworkFlowProb (int numberOfVertices)

{

this.numberOfVertices = numberOfVertices;

this.queue = new LinkedList<Integer>();

parent = new int[numberOfVertices + 1];

visited = new boolean[numberOfVertices + 1];

cutSet = new HashSet<Pair>();

reachable = new ArrayList<Integer>();

unreachable = new ArrayList<Integer>();

}

public boolean bfs (int source, int goal, int graph[][])

{

boolean pathFound = false;

int destination, element;

for (int vertex = 1; vertex <= numberOfVertices; vertex++)

{

parent[vertex] = -1;

visited[vertex] = false;

}

queue.add(source);

parent[source] = -1;

visited[source] = true;

while (!queue.isEmpty())

{

element = queue.remove();

destination = 1;

while (destination <= numberOfVertices)

{

if (graph[element][destination] > 0 &&  !visited[destination])

{

parent[destination] = element;

queue.add(destination);

visited[destination] = true;

}

destination++;

}}

if (visited[goal])

{

pathFound = true;

}

return pathFound;

}

public int  networkFlow (int graph[][], int source, int destination)

{

int u, v;

int maxFlow = 0;

int pathFlow;

int[][] residualGraph = new int[numberOfVertices + 1][numberOfVertices + 1];

for (int sourceVertex = 1; sourceVertex <= numberOfVertices; sourceVertex++)

{

for (int destinationVertex = 1; destinationVertex <= numberOfVertices; destinationVertex++)

{

residualGraph[sourceVertex][destinationVertex] = graph[sourceVertex][destinationVertex];

}

}

/*max flow*/

while (bfs(source, destination, residualGraph))

{

pathFlow = Integer.MAX_VALUE;

for (v = destination; v != source; v = parent[v])

{

u = parent[v];

pathFlow = Math.min(pathFlow, residualGraph[u][v]);

}

for (v = destination; v != source; v = parent[v])

{

u = parent[v];

residualGraph[u][v] -= pathFlow;

residualGraph[v][u] += pathFlow;

}

maxFlow += pathFlow;

}

/*calculate the cut set*/

for (int vertex = 1; vertex <= numberOfVertices; vertex++)

{

if (bfs(source, vertex, residualGraph))

{

reachable.add(vertex);

}

else

{

unreachable.add(vertex);

}}

for (int i = 0; i < reachable.size(); i++)

{

for (int j = 0; j < unreachable.size(); j++)

{

if (graph[reachable.get(i)][unreachable.get(j)] > 0)

{

cutSet.add (new Pair(reachable.get(i), unreachable.get(j)));

}}}

return maxFlow;

}

public void printCutSet ()

{

Iterator<Pair> iterator = cutSet.iterator();

while (iterator.hasNext())

{

Pair pair = iterator.next();

System.out.println(pair.source + "-" + pair.destination);

}}

public static void main (String...arg)

{

int[][] graph;

int numberOfNodes;

int source;

int sink;

int maxFlow;

Scanner scanner = new Scanner(System.in);

System.out.println("Enter the number of nodes");

numberOfNodes = scanner.nextInt();

graph = new int[numberOfNodes + 1][numberOfNodes + 1];

System.out.println("Enter the graph matrix");

for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++)

{

for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++)

{

graph[sourceVertex][destinationVertex] = scanner.nextInt();

}}

System.out.println("Enter the source of the graph");

source= scanner.nextInt();

System.out.println("Enter the sink of the graph");

sink = scanner.nextInt();

NetworkFlowProb networkFlowProb = new NetworkFlowProb(numberOfNodes);

maxFlow = networkFlowProb.networkFlow(graph, source, sink);

System.out.println("The Max flow in the graph is " + maxFlow);

System.out.println("The Minimum Cut Set in the Graph is ");

networkFlowProb.printCutSet();

scanner.close();

}}

class Pair

{

public int source;

public int destination;

public Pair(int source, int destination)

{

this.source = source;

this.destination = destination;

}

public Pair()

{

}}

OUT PUT

O:\>java NetworkFlowProb

Enter the number of nodes

3

Enter the graph matrix

3

4

5

4

1

1

2

3

4

Enter the source of the graph

3

Enter the sink of the graph

2

The Max flow in the graph is 5

The Minimum Cut Set in the Graph is

3-1

3-2

LINEAR PROGRAMMING

import java.util.Scanner;

class LinearSearch

{

public static void main(String args[])

{

int c, n, search, array[];

Scanner in = new Scanner(System.in);

System.out.println("Enter number of elements");

n = in.nextInt();

array = new int[n];

System.out.println("Enter " + n + " integers");

for (c = 0; c < n; c++)

array[c] = in.nextInt();

System.out.println("Enter value to find");

search = in.nextInt();

for (c = 0; c < n; c++)

{

if (array[c] == search)    

{

System.out.println(search + " is present at location " + (c + 1) + ".");

break;

}

}

if (c == n) 

System.out.println(search + " is not present in array.");

}

}

O:\>javac LinearSearch.java

O:\>java LinearSearch

Enter number of elements

5

Enter 5 integers

5

6

7

8

9

Enter value to find

7

7 is present at location 3.

RAMDAMISED ALGORITHM

QUICK SORT

public class sort

{

public static void main(String a[]){

int i;

int array[] = {12,9,4,99,120,1,3,10,13};

System.out.println("      \n Quick Sort\n\n");

System.out.println("Values Before the sort:\n");

for(i = 0; i < array.length; i++)

System.out.print( array[i]+"  ");

System.out.println();

quick_srt(array,0,array.length-1);

System.out.print("Values after the sort:\n");

for(i = 0; i <array.length; i++)

System.out.print(array[i]+"  ");

System.out.println();

System.out.println("PAUSE");

}

public static void quick_srt(int array[],int low, int n){

int lo = low;

int hi = n;

if (lo >= n) {

return;

}

int mid = array[(lo + hi) / 2];

while (lo < hi) {

while (lo<hi && array[lo] < mid) {

lo++;

}

while (lo<hi && array[hi] > mid) {

hi--;

}

if (lo < hi) {

int T = array[lo];

array[lo] = array[hi];

array[hi] = T;

}

}

if (hi < lo) {

int T = hi;

hi = lo;

lo = T;

}

quick_srt(array, low, lo);

quick_srt(array, lo == low ? lo+1 : lo, n);

}}

Out put

O:\>javac sort.java

O:\>java sort

Quick Sort

Values Before the sort:

12  9  4  99  120  1  3  10  13

Values after the sort:

1  3  4  9  10  12  13  99  120

HILL CLIMBING

TRAVELING SALES PERSON PROBLEM

import java.util.*;

public class TravelingSalesPerson

{

public double[][] fillDistanceMatrix(int size, int seed)

{

double[][] distances=new double[size][size];

Random random=new Random(seed);

for(int i=0; i<size; i++)

for(int j=i+1; j<size; j++)

{

distances[i][j]=random.nextDouble();

distances[j][i]=distances[i][j];

}

return distances;

}

public double swap(int[] tour, int tourIndexA,

int tourIndexB, double[][] distances)

{

return 0;

}

public double getBestTour(int[] tour,

double[][] distances, int restarts,

int seed)

{

//must use random to create new randomly ordered tours

Random random=new Random(seed);

for(int i=0; i<restarts; i++)

{

randomizeTour(tour, random);

//put code here

}

return 0;

}

public void randomizeTour(int[] tour, Random random)

{

for(int i=0; i<tour.length; i++)

tour[i]=i;

//randomize the tour from here

}

public static void main(String[] argv)

{

int[] sizes={10, 20, 30, 40};

int[] seeds={1, 2, 3, 4};

int[] restarts={20, 20, 20, 20};

TravelingSalesPerson sales=new TravelingSalesPerson();

for(int i=0; i<sizes.length; i++)

{

double[][] distances=sales.fillDistanceMatrix(sizes[i], seeds[i]);

int[] tour=new int[sizes[i]];

double cost=sales.getBestTour(tour, distances, restarts[i], seeds[i]);

System.out.println("The following tour costs "+cost);

for(int j=0; j<tour.length; j++)

System.out.print(tour[j]+" ");

System.out.println();

}}}

OUTPUT

O:\>javac  TravelingSalesPerson.java

O:\>java TravelingSalesPerson

The following tour costs 0.0

0 1 2 3 4 5 6 7 8 9

The following tour costs 0.0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

The following tour costs 0.0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

The following tour costs 0.0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

30 31 32 33 34 35 36 37 38 39

KNAPSACK

import java.util.*;

import java.io.*;

 import java.lang.*;

 public class Knapsack01

{

static int n=5, W;

static obj st[];

public static BufferedReader br =new BufferedReader(new InputStreamReader(System.in));

static class obj

{

 int weight; int profit;

}

 public static void main(String args[]) throws IOException

{

int i=0;

System.out.println("Knap Sack Problem\n------------------\n");

 System.out.print("Enter total number of objects: ");

n = Integer.parseInt( br.readLine() );

System.out.print("Enter the maximum weight sack can take: ");

W = Integer.parseInt( br.readLine() );

st = new obj[n+1];

st[0] = new obj();

st[0].weight = st[0].profit = 0;

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

 {

st[i] = new obj();

System.out.print("For Object "+(i)+" :-\n\tWeight: ");

st[i].weight = Integer.parseInt(br.readLine());

System.out.print("\tProfit: ");

st[i].profit = Integer.parseInt(br.readLine());

}

System.out.print("\nOptimal Solution is : { ");

simple_fill();

}

static void simple_fill()

{

int [][]s = new int[n+1][W+1];

 for (int w = 0; w<= W; w++)

s[0][w] = 0;

for(int i=0; i<=n; i++)

s[i][0]=0;

for(int i=1; i<=n; i++)

 for (int w = 0; w<= W; w++)

if (st[i].weight <= w)

{

if (st[i].profit + s[i-1][w-st[i].weight] > s[i-1][w])

 s[i][w] = st[i].profit + s[i-1][w- st[i].weight];

else s[i][w] = s[i-1][w];

}

else s[i][w] = s[i-1][w];

 int i = n;

int k = W;

int prof = 0;

while((i>0)&&(k>0))

{

if (s[i][k] != s[i-1][k])

 {

System.out.print(i+":("+st[i].weight+", Rs."+st[i].profit+"), ");

 k = k - st[i].weight;

 prof += st[i].profit;

 }

 i--;

 }

 System.out.print(" }\nIt will yield a profit of Rs."+ prof);

 } }

OUTPUT:

javac knapsack.java

java knapsack

 Knap Sack Problem

 Enter total number of objects: 3

Enter the maximum weight sack can take: 100

For Object 1 :- Weight: 50 Profit: 100

For Object 2 :- Weight: 100 Profit: 500

For Object 3 :- Weight: 25 Profit: 100

Optimal Solution is : { 2:(100, Rs.500), } It will yield a profit of Rs.500