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
