· 6 years ago · Nov 18, 2019, 03:28 AM
11. Write a java program to implement Quick sort algorithm for sorting a list of integers in ascending order
2
3Program:
4
5package pp;
6public class MyQuickSort {
7private int array[];
8private int length;
9public void sort(int[] inputArr) {
10
11if (inputArr == null || inputArr.length == 0) {
12return;
13 }
14 this.array = inputArr;
15length = inputArr.length;
16quickSort(0, length - 1);
17 }
18
19private void quickSort(int lowerIndex, int higherIndex) {
20int i = lowerIndex;
21int j = higherIndex;
22 // calculate pivot number, I am taking pivot as middle index number
23int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
24 // Divide into two arrays
25while (i <= j) {
26
27while (array[i] < pivot) {
28i++;
29 }
30while (array[j] > pivot) {
31j--;
32 }
33if (i <= j) {
34exchangeNumbers(i, j);
35i++;
36j--;
37 }
38 }
39 // call quickSort() method recursively
40if (lowerIndex < j)
41quickSort(lowerIndex, j);
42if (i < higherIndex)
43quickSort(i, higherIndex);
44 }
45
46private void exchangeNumbers(int i, int j) {
47int temp = array[i];
48array[i] = array[j];
49array[j] = temp;
50 }
51
52 public static void main(String[] args) {
53 // TODO Auto-generated method stub
54int n,i;
55 MyQuickSort sorter = new MyQuickSort();
56Scanner scr=new Scanner(System.in);
57System.out.println("Enter number of elemrnts into array");
58n=scr.nextInt();
59int input[]=new int[n];
60for(i=0;i<n;i++)
61input[i] =scr.nextInt();
62sorter.sort(input);
63for(i=0;i<n;i++){
64System.out.print(input[i]);
65System.out.print(" ");
66
67 }
68
69}
70}
71
72Output:
73Enter the number of elements into array:4
745
756
762
778
782 5 6 8
79
802. Write a java program to implement Merge sort algorithm for sorting a list of integers in ascending order.
81
82
83Program:
84
85package kits;
86
87public class MyMergeSort {
88 private int[] array;
89 private int[] tempMergArr;
90 private int length;
91
92 public static void main(String a[]){
93
94 int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
95 MyMergeSort mms = new MyMergeSort();
96 mms.sort(inputArr);
97 for(int i:inputArr){
98 System.out.print(i);
99 System.out.print(" ");
100 }
101 }
102
103 public void sort(int inputArr[]) {
104 this.array = inputArr;
105 this.length = inputArr.length;
106 this.tempMergArr = new int[length];
107 doMergeSort(0, length - 1);
108 }
109
110 private void doMergeSort(int lowerIndex, int higherIndex) {
111
112 if (lowerIndex < higherIndex) {
113 int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
114 // Below step sorts the left side of the array
115 doMergeSort(lowerIndex, middle);
116 // Below step sorts the right side of the array
117 doMergeSort(middle + 1, higherIndex);
118 // Now merge both sides
119 mergeParts(lowerIndex, middle, higherIndex);
120 }
121 }
122
123 private void mergeParts(int lowerIndex, int middle, int higherIndex) {
124
125 for (int i = lowerIndex; i <= higherIndex; i++) {
126 tempMergArr[i] = array[i];
127 }
128 int i = lowerIndex;
129 int j = middle + 1;
130 int k = lowerIndex;
131 while (i <= middle && j <= higherIndex) {
132 if (tempMergArr[i] <= tempMergArr[j]) {
133 array[k] = tempMergArr[i];
134 i++;
135 } else {
136 array[k] = tempMergArr[j];
137 j++;
138 }
139 k++;
140 }
141 while (i <= middle) {
142 array[k] = tempMergArr[i];
143 k++;
144 i++;
145 }
146
147 }
148
149
150}
151
152Output: 4,11,23,28,43,45,65,77,89,98
153
154
155
156
157
158
1593. Write a java program to implement the dfs algorithm for a graph.
160
161Program:
162
163package kits;
164import java.util.ArrayList;
165import java.util.List;
166import java.util.Stack;
167public class DepthFirstSearchExampleNeighbourList {
168 static class Node
169 {
170 int data;
171 boolean visited;
172 List<Node> neighbours;
173
174 Node(int data)
175 {
176 this.data=data;
177 this.neighbours=new ArrayList<>();
178
179 }
180 public void addneighbours(Node neighbourNode)
181 {
182 this.neighbours.add(neighbourNode);
183 }
184 public List<Node> getNeighbours() {
185 return neighbours;
186 }
187 public void setNeighbours(List<Node> neighbours) {
188 this.neighbours = neighbours;
189 }
190 }
191
192 // Recursive DFS
193 public void dfs(Node node)
194 {
195 System.out.print(node.data + " ");
196 List<Node> neighbours=node.getNeighbours();
197 node.visited=true;
198 for (int i = 0; i < neighbours.size(); i++) {
199 Node n=neighbours.get(i);
200 if(n!=null && !n.visited)
201 {
202 dfs(n);
203 }
204 }
205 }
206
207 // Iterative DFS using stack
208 public void dfsUsingStack(Node node)
209 {
210 Stack<Node> stack=new Stack<Node>();
211 stack.add(node);
212 node.visited=true;
213 while (!stack.isEmpty())
214 {
215 Node element=stack.pop();
216 System.out.print(element.data + " ");
217
218 List<Node> neighbours=element.getNeighbours();
219 for (int i = 0; i < neighbours.size(); i++) {
220 Node n=neighbours.get(i);
221 if(n!=null && !n.visited)
222 {
223 stack.add(n);
224 n.visited=true;
225
226 }
227 }
228 }
229 }
230
231 public static void main(String arg[])
232 {
233
234 Node node40 =new Node(40);
235 Node node10 =new Node(10);
236 Node node20 =new Node(20);
237 Node node30 =new Node(30);
238 Node node60 =new Node(60);
239 Node node50 =new Node(50);
240 Node node70 =new Node(70);
241
242 node40.addneighbours(node10);
243 node40.addneighbours(node20);
244 node10.addneighbours(node30);
245 node20.addneighbours(node10);
246 node20.addneighbours(node30);
247 node20.addneighbours(node60);
248 node20.addneighbours(node50);
249 node30.addneighbours(node60);
250 node60.addneighbours(node70);
251 node50.addneighbours(node70);
252
253 DepthFirstSearchExampleNeighbourList dfsExample = new
254 DepthFirstSearchExampleNeighbourList();
255
256 System.out.println("The DFS traversal of the graph using stack ");
257 dfsExample.dfsUsingStack(node40);
258 System.out.println();
259
260 // Resetting the visited flag for nodes
261 node40.visited=false;
262 node10.visited=false;
263 node20.visited=false;
264 node30.visited=false;
265 node60.visited=false;
266 node50.visited=false;
267 node70.visited=false;
268 System.out.println("The DFS traversal of the graph using recursion ");
269 dfsExample.dfs(node40);
270 }
271}
272
273Output:
274The DFS traversal of the graph using stack
275 40 20 50 70 60 30 10
276The DFS traversal of the graph using recursion
27740 10 30 60 70 20 50
2784. Write a java program to implement the bfs algorithm for a graph.
279
280Program:
281
282package kits;
283import java.util.ArrayList;
284import java.util.LinkedList;
285import java.util.List;
286import java.util.Queue;
287public class BreadthFirstSearchExampleNeighbourList {
288 private Queue<Node> queue;
289static ArrayList<Node> nodes=new ArrayList<Node>();
290static class Node
291{
292 int data;
293 boolean visited;
294 List<Node> neighbours;
295
296 Node(int data)
297 {
298 this.data=data;
299 this.neighbours=new ArrayList<>();
300
301 }
302 public void addneighbours(Node neighbourNode)
303 {
304 this.neighbours.add(neighbourNode);
305 }
306 public List<Node> getNeighbours() {
307 return neighbours;
308 }
309 public void setNeighbours(List<Node> neighbours) {
310 this.neighbours = neighbours;
311 }
312}
313
314public BreadthFirstSearchExampleNeighbourList()
315{
316 queue = new LinkedList<Node>();
317}
318
319public void bfs(Node node)
320{
321 queue.add(node);
322 node.visited=true;
323 while (!queue.isEmpty())
324 {
325
326 Node element=queue.remove();
327 System.out.print(element.data + "t");
328 List<Node> neighbours=element.getNeighbours();
329 for (int i = 0; i < neighbours.size(); i++) {
330 Node n=neighbours.get(i);
331 if(n!=null && !n.visited)
332 {
333 queue.add(n);
334 n.visited=true;
335
336 }
337 }
338
339 }
340}
341
342public static void main(String arg[])
343{
344
345 Node node40 =new Node(40);
346 Node node10 =new Node(10);
347 Node node20 =new Node(20);
348 Node node30 =new Node(30);
349 Node node60 =new Node(60);
350 Node node50 =new Node(50);
351 Node node70 =new Node(70);
352
353 node40.addneighbours(node10);
354 node40.addneighbours(node20);
355 node10.addneighbours(node30);
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381 node20.addneighbours(node10);
382 node20.addneighbours(node30);
383 node20.addneighbours(node60);
384 node20.addneighbours(node50);
385 node30.addneighbours(node60);
386 node60.addneighbours(node70);
387 node50.addneighbours(node70);
388 System.out.println("The BFS traversal of the graph is ");
389 BreadthFirstSearchExampleNeighbourList bfsExample = new BreadthFirstSearchExampleNeighbourList();
390 bfsExample.bfs(node40);
391
392}
393
394
395
396}
397
398Output:
399The BFS traversal of the graph is 40 10 20 30 60 50 70
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
4225. Write a java programs to implement backtracking algorithm for the N-queens problem.
423
424Program:
425
426package kits;
427
428public class NQueens2DArray {
429 public static void main(String[] args) {
430 placeQueens(4); // Lets take example of 4*4
431 }
432 private static void placeQueens(int gridSize){
433 //If Grid is 1*1 or 2*2 or 3*3 then solution is not possible as,
434 //In 1*1 or 2*2 grid, Queen placed in 1st row at any position will attack queen placed at all the positions in row 2.
435 //In 3*3 grid, Queen placed in 1st row and 2nd row for all combinations position will attack queen placed at all the positions in row 3.
436 if(gridSize<4){
437 System.out.println("No Solution available");
438 }else{
439 int[][] board = new int[gridSize][gridSize];
440 placeAllQueens(board, 0);
441 printBoard(board); } }
442 private static boolean placeAllQueens(int board[][], int row){
443 if(row>=board.length){
444 return true;
445 }
446 boolean isAllQueensPlaced = false;
447 for (int j = 0; j < board.length; j++) {
448 if(isSafe(board, row, j)){
449 board[row][j] = 1;
450 isAllQueensPlaced = placeAllQueens(board, row+1);
451 }
452 if(isAllQueensPlaced){
453 break;
454 }else{
455 board[row][j] = 0;
456 }
457 }
458 return isAllQueensPlaced; }
459 private static boolean isSafe(int board[][], int row, int col){
460 //Check Left Upper Diagonal
461 for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {
462 if(board[i][j] == 1){
463 return false;
464 }
465 }
466 //Check Right Upper Diagonal
467 for (int i = row-1, j = col+1; i >= 0 && j < board.length; i--, j++) {
468 if(board[i][j] == 1){
469 return false;
470 }
471 }
472 //Check in same Column
473 for (int i = row-1; i >= 0; i--) {
474 if(board[i][col] == 1){
475 return false;
476 }
477 }
478 return true;
479 }
480 private static void printBoard(int[][] board){
481 for (int row = 0; row < board.length; row++) {
482 for (int col = 0; col < board.length; col++) {
483 if(board[row][col] == 1){
484 System.out.print("Q ");
485 }else{
486 System.out.print("_ ");
487 } }
488 System.out.println();
489 }
490 System.out.println("");
491 }
492}
493
494Output:
495- Q - -
496- - - Q
497Q - - -
498- - Q -
4996. Write a java program to implement the backtracking algorithm for the sum of subsets problem.
500
501Program:
502
503package kits;
504public class SubSetSum {
505 public static void main(String[] args) {
506 int[] input = { 2, 3, 4, 5 };
507 int targetSum = 7;
508 SubSetSum subSetSum = new SubSetSum();
509 subSetSum.findSubSets(input, targetSum);
510 }
511 private int[] set;
512 private int[] selectedElements;
513 private int targetSum;
514 private int numOfElements;
515
516 public void findSubSets(int[] set, int targetSum) {
517 this.set = set;
518 this.numOfElements = set.length;
519 this.targetSum = targetSum;
520 selectedElements = new int[numOfElements];
521 quicksort(set, 0, numOfElements-1);
522 int sumOfAllElements = 0;
523 for(int element : set){
524 sumOfAllElements += element;
525 }
526 findSubSets(0, 0, sumOfAllElements);
527 }
528
529 private void findSubSets(int sumTillNow, int index, int sumOfRemaining) {
530 selectedElements[index] = 1; // selecting element at index : 'index'
531 if (targetSum == set[index] + sumTillNow) {
532 print();
533 }
534
535 // (sum + set[index] + set[index+1] <= targetSum) : this condition
536 // ensures selecting
537 // the next element is useful and the total sum by including next
538 // element will not exceed the target sum.
539 if ((index + 1 < numOfElements) && (sumTillNow + set[index] + set[index + 1] <= targetSum)) {
540 findSubSets(sumTillNow + set[index], index + 1, sumOfRemaining - set[index]);
541 }
542
543 // now exploring the other path: not Selecting the element at index:
544 // 'index'
545 selectedElements[index] = 0;
546
547 // (sum + set[index+1] <= targetSum) : this condition ensures selecting
548 // the next element is useful and the total sum by including next
549 // element will not exceed the target sum.
550
551 // (sum + sumOfRemaining - set[index] >= targetSum) ensures the total
552 // sum of all the elements by excluding the current element may achieve
553 // the target sum, if in case the resultant sum is less than the target
554 // sum then exploring this path is of no use
555if ((index + 1 < numOfElements) && (sumTillNow + set[index + 1] <= targetSum)
556 && (sumTillNow + sumOfRemaining - set[index] >= targetSum)) {
557 findSubSets(sumTillNow, index + 1, sumOfRemaining - set[index]);
558 }
559 }
560
561 private void print() {
562 for (int i = 0; i < numOfElements; i++) {
563 if (selectedElements[i] == 1) {
564 System.out.print(set[i]+" ");
565 }
566 }
567 System.out.println();
568 }
569
570 private void quicksort(int[] arr, int start, int end) {
571 if (start < end) {
572 swap(arr, (start + (end - start) / 2), end);
573 int pIndex = partition(arr, start, end);
574 quicksort(arr, start, pIndex - 1);
575 quicksort(arr, pIndex + 1, end);
576 }
577 }
578
579 private int partition(int[] arr, int start, int end) {
580 int pIndex = start, pivot = arr[end];
581 for (int i = start; i < end; i++) {
582 if (arr[i] < pivot) {
583 swap(arr,pIndex,i);
584 pIndex++;
585 }
586 }
587 swap(arr,pIndex,end);
588 return pIndex;
589 }
590
591 private void swap(int[] arr, int index1, int index2) {
592 int temp = arr[index1];
593 arr[index1] = arr[index2];
594 arr[index2] = temp;
595 }
596 }
597
598
599Output:
6002 5
6013 4
602
603
604
605
606
607
608
609
610
611
612
613
614
615
6167. Write a java program to implement the backtracking algorithm for the Hamiltonian Circuits problem.
617
618
619Program:
620
621package kits;
622 import java.util.HashMap;
623 import java.util.Map;
624 public class HamiltonianCycle {
625 int verticesNum;
626 char[] vertices;
627 char[] path;
628 int size;
629 Map<Character,Integer> vertexIndexMap = new HashMap<>();
630 public HamiltonianCycle(int verticesNum) {
631 this.verticesNum = verticesNum;
632 vertices = new char[verticesNum];
633 path = new char[verticesNum];
634 }
635
636 public void addVertex(char v) {
637 vertexIndexMap.put(v, size);
638 vertices[size++] = v;
639 }
640
641 private boolean isValidNodeInPath(int [][] graph, int indexOfNewVerex ,int pos) {
642 char lastVertexInPath = path[pos-1];
643 int indexOfLastVertexInPath = vertexIndexMap.get(lastVertexInPath);
644 // check if the new vertex is adjacent to the previously added vertex in the path]
645 if(graph[indexOfNewVerex][indexOfLastVertexInPath] == 0){
646 return false;
647 }
648 // check if the new vertex has not already been added in the path
649 for(int i = 0; i < pos; i++){
650 if(vertices[indexOfNewVerex] == path[i]){
651 return false;
652 } }
653 return true;
654 }
655
656 private boolean validateHamiltonianCycleUtil(int [][] graph, int pos){
657 // base condition
658 if(pos == verticesNum){
659 char lastVertexInPath = path[pos-1];
660 int indexOfVertexlastInPath = vertexIndexMap.get(lastVertexInPath);
661 if(graph[0][indexOfVertexlastInPath] == 1){
662 return true;
663 }
664 else {
665 return false;
666 }
667 }
668 // here we try to add v in the path at position pos
669 // we start from 1 as 0th vertex from the array vertices is already in the path as source node
670 for(int i = 1; i < verticesNum; i++){
671 if(isValidNodeInPath(graph,i,pos)){
672 path[pos] = vertices[i];// include new node in the path
673 if(validateHamiltonianCycleUtil(graph, pos+1)){
674 return true;
675 }
676 path[pos] = '$';// reset the position and try to put another node at this position.
677 }
678 }
679 // no valid vertex found to be added in the path, and all nodes still not covered ,return false
680 return false;
681 }
682
683 public boolean isHamiltonianCycle(int[][] graph) {
684 for (int i = 0; i < verticesNum; i++) {
685 path[i] = '$';
686 }
687 path[0] = vertices[0]; // vertices[0] is included as a source node of
688 // the cycle
689 if (validateHamiltonianCycleUtil(graph, 1)) {
690
691 System.out.println("Path exists::");
692 for(int i = 0 ; i < verticesNum; i++){
693 System.out.print(path[i]+" ");
694 }
695 System.out.print(path[0]);
696 return true;
697 }
698 System.out.println("No path exists!!");
699 return false;
700 }
701
702 public static void main(String[] args) {
703HamiltonianCycle hamiltonianCycle = new HamiltonianCycle(5);
704 hamiltonianCycle.addVertex('a');
705 hamiltonianCycle.addVertex('b');
706 hamiltonianCycle.addVertex('c');
707 hamiltonianCycle.addVertex('d');
708 hamiltonianCycle.addVertex('e');
709 /* Let us create the following graph
710 (a)--(b)--(c)
711 | / \ |
712 | / \ |
713 | / \ |
714 (d)-------(e) */
715 int graph[][] = {
716 {0, 1, 0, 1, 0},
717 {1, 0, 1, 1, 1},
718 {0, 1, 0, 0, 1},
719 {1, 1, 0, 0, 1},
720 {0, 1, 1, 1, 0},
721 };
722 hamiltonianCycle.isHamiltonianCycle(graph);
723 }
724}
725
726
727Output:
728Solution Exists: Following is one Hamiltonian cycle
7290 1 2 4 3 0
7308. Write a java program to implement greedy algorithm for job sequencing with deadlines.
731
732Program:
733
734package kits;
735//PROGRAM:
736import java.util.*;
737class job
738{
739int p; //.............for profit of a job
740int d; //.............for deadline of a job
741int v; //.............for checking if that job has been selected
742/*************default constructor**************/
743job()
744{
745p=0;
746d=0;
747v=0;
748}
749job(int x,int y,int z) // parameterised constructor
750{
751p=x;
752d=y;
753v=z;
754}
755}
756class js
757{
758static int n;
759static int out(job jb[],int x)
760{
761for(int i=0;i<n;++i)
762if(jb[i].p==x)
763return i;
764return 0;
765}
766public static void main(String args[])
767{
768Scanner scr=new Scanner(System.in);
769System.out.println("Enter the number of jobs");
770n=scr.nextInt();
771int max=0; // this is to find the maximum deadline
772job jb[]=new job[n];
773/***********************Accepting job from user*************************/
774for(int i=0;i<n;++i)
775{
776System.out.println("Enter profit and deadline(p d)");
777int p=scr.nextInt();
778int d=scr.nextInt();
779if(max<d)
780max=d; // assign maximum value of deadline to "max" variable
781jb[i]=new job(p,d,0); //zero as third parameter to mark that initially it is unvisited
782}
783//accepted jobs from user
784
785/*************************Sorting in increasing orser of deadlines*************************/
786for(int i=0;i<=n-2;++i)
787{
788for(int j=i;j<=n-1;++j)
789{
790if(jb[i].d>jb[j].d)
791{
792job temp=jb[i];
793jb[i]=jb[j];
794jb[j]=temp;
795}
796}
797}
798//sorting process ends
799
800/******************************Displaying the jobs to the user***********************/
801System.out.println("The jobs are as follows ");
802for(int i=0;i<n;++i)
803System.out.println("Job "+i+" Profit = "+jb[i].p+" Deadline = "+jb[i].d);
804//jobs displayed to the user
805
806int count;
807int hold[]=new int[max];
808for(int i=0;i<max;++i)
809hold[i]=0;
810/*****************************Process of job sequencing begins*************************/
811for(int i=0;i<n;++i)
812{
813count=0;
814for(int j=0;j<n;++j)
815{
816
817if(count<jb[j].d && jb[j].v==0 && count<max && jb[j].p>hold[count])
818{
819int ch=0;
820
821if(hold[count]!=0)
822 {
823ch=out(jb,hold[count]);
824jb[ch].v=0;
825}
826
827hold[count]=jb[j].p;
828jb[j].v=1;
829 ++count;
830
831} // end of if
832
833} //end of inner for
834}// end of outer for
835/******************************job sequencing process ends******************************/
836
837/******************************calculating max profit**********************************/
838int profit=0;
839for(int i=0;i<max;++i)
840profit+=hold[i];
841System.out.println("The maximum profit is "+profit);
842
843}//end main method
844}//end class
845
846
847
848
849Output:
850Enter the number of jobs 4
851Enter profit and deadline 70 2
852Enter profit and dealine 12 1
853Enter profit and deadline 18 2
854Enter profit and deadline 35 1
855The jobs are as follows
856Job0 Profit-12 deadline=1
857Job1 Profit-35 deadline=1
858Job2 Profit-38 deadline=2
859Job3 Profit-70 deadline=2
860Maximum Profit is 105
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
8829. Write a java program to implement Dijkstra’s algorithm for the Single source shortest path problem.
883
884Program:
885
886package kits;
887
888 import java.util.*;
889 public class dikj {
890 public int distance[] = new int[10];
891 public int cost[][] = new int[10][10];
892
893 public void calc(int n,int s)
894 {
895 int flag[] = new int[n+1];
896 int i,minpos=1,k,c,minimum;
897
898 for(i=1;i<=n;i++)
899 {
900 flag[i]=0;
901 this.distance[i]=this.cost[s][i];
902 }
903 c=2;
904 while(c<=n)
905 {
906 minimum=99;
907 for(k=1;k<=n;k++)
908 {
909 if(this.distance[k]<minimum && flag[k]!=1)
910 {
911 minimum=this.distance[i];
912 minpos=k;
913 }
914 }
915 flag[minpos]=1;
916 c++;
917 for(k=1;k<=n;k++)
918 {
919 if(this.distance[minpos]+this.cost[minpos][k] < this.distance[k] && flag[k]!=1 )
920 this.distance[k]=this.distance[minpos]+this.cost[minpos][k];
921 }
922 }
923
924 }
925
926 public static void main(String args[])
927 {
928 int nodes,source,i,j;
929 Scanner in = new Scanner(System.in);
930 System.out.println("Enter the Number of Nodes \n");
931 nodes = in.nextInt();
932 dikj d = new dikj();
933 System.out.println("Enter the Cost Matrix Weights: \n");
934 for(i=1;i<=nodes;i++)
935 for(j=1;j<=nodes;j++)
936 {
937 d.cost[i][j]=in.nextInt();
938 if(d.cost[i][j]==0)
939 d.cost[i][j]=999;
940 }
941 System.out.println("Enter the Source Vertex :\n");
942 source=in.nextInt();
943
944 d.calc(nodes,source);
945 System.out.println("The Shortest Path from Source \t"+source+"\t to all other vertices are : \n");
946 for(i=1;i<=nodes;i++)
947 if(i!=source)
948 System.out.println("source :"+source+"\t destination :"+i+"\t MinCost is :"+d.distance[i]+"\t");
949
950
951 }
952 }
953
954
955
956
957
958Output:
959Enter the number of nodes 7
960Enter the cost matrix weights
9610 10 0 25 0 30 0
9620 0 20 0 0 0 0
9630 0 0 0 5 0 0
9640 0 0 0 12 0 20
9650 0 0 0 0 0 7
9660 0 0 0 0 0 35
967Enter the source vector:4
968The Shortest path from source4 to all other vertices are:
969Source:4 Destination: 1 mincost is:999
970Source:4 Destination: 2 mincost is:999
971Source:4 Destination: 3 mincost is:999
972Source:4 Destination: 5 mincost is:12
973Source:4 Destination: 6 mincost is:999
974Source:4 Destination: 7 mincost is:19
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
99710.Write a java program that implements Prim’s algorithm to generate minimum cost spanning tree.
998
999
1000Program:
1001
1002package kits;
1003
1004 import java.util.InputMismatchException;
1005 import java.util.Scanner;
1006
1007 public class prims
1008 {
1009 private boolean unsettled[];
1010 private boolean settled[];
1011 private int numberofvertices;
1012 private int adjacencyMatrix[][];
1013 private int key[];
1014 public static final int INFINITE = 999;
1015 private int parent[];
1016
1017 public prims(int numberofvertices)
1018 {
1019 this.numberofvertices = numberofvertices;
1020 unsettled = new boolean[numberofvertices + 1];
1021 settled = new boolean[numberofvertices + 1];
1022 adjacencyMatrix = new int[numberofvertices + 1][numberofvertices + 1];
1023 key = new int[numberofvertices + 1];
1024 parent = new int[numberofvertices + 1];
1025 }
1026
1027 public int getUnsettledCount(boolean unsettled[])
1028 {
1029 int count = 0;
1030 for (int index = 0; index < unsettled.length; index++)
1031 {
1032 if (unsettled[index])
1033 {
1034 count++;
1035 }
1036 }
1037 return count;
1038 }
1039
1040 public void primsAlgorithm(int adjacencyMatrix[][])
1041 {
1042 int evaluationVertex;
1043 for (int source = 1; source <= numberofvertices; source++)
1044 {
1045for (int destination = 1; destination <= numberofvertices; destination++)
1046 {
1047 this.adjacencyMatrix[source][destination] = adjacencyMatrix[source][destination];
1048 }
1049 }
1050
1051 for (int index = 1; index <= numberofvertices; index++)
1052 {
1053 key[index] = INFINITE;
1054 }
1055 key[1] = 0;
1056 unsettled[1] = true;
1057 parent[1] = 1;
1058
1059 while (getUnsettledCount(unsettled) != 0)
1060 {
1061evaluationVertex = getMimumKeyVertexFromUnsettled(unsettled);
1062 unsettled[evaluationVertex] = false;
1063 settled[evaluationVertex] = true;
1064 evaluateNeighbours(evaluationVertex);
1065 }
1066 }
1067
1068private int getMimumKeyVertexFromUnsettled(boolean[] unsettled2)
1069 {
1070 int min = Integer.MAX_VALUE;
1071 int node = 0;
1072 for (int vertex = 1; vertex <= numberofvertices; vertex++)
1073 {
1074 if (unsettled[vertex] == true && key[vertex] < min)
1075 {
1076 node = vertex;
1077 min = key[vertex];
1078 }
1079 }
1080 return node;
1081 }
1082
1083 public void evaluateNeighbours(int evaluationVertex)
1084 {
1085
1086for (int destinationvertex = 1; destinationvertex <= numberofvertices; destinationvertex++)
1087 {
1088 if (settled[destinationvertex] == false)
1089 {
1090 if (adjacencyMatrix[evaluationVertex][destinationvertex] != INFINITE)
1091 {
1092 if (adjacencyMatrix[evaluationVertex][destinationvertex] < key[destinationvertex])
1093 {
1094 key[destinationvertex] = adjacencyMatrix[evaluationVertex][destinationvertex];
1095 parent[destinationvertex] = evaluationVertex;
1096 }
1097 unsettled[destinationvertex] = true;
1098 }
1099 }
1100 }
1101 }
1102
1103 public void printMST()
1104 {
1105 System.out.println("SOURCE : DESTINATION = WEIGHT");
1106 for (int vertex = 2; vertex <= numberofvertices; vertex++)
1107 {
1108 System.out.println(parent[vertex] + "\t:\t" + vertex +"\t=\t"+ adjacencyMatrix[parent[vertex]][vertex]);
1109 }
1110 }
1111
1112 public static void main(String... arg)
1113 {
1114 int adjacency_matrix[][];
1115 int number_of_vertices;
1116 Scanner scan = new Scanner(System.in);
1117
1118 try
1119 {
1120 System.out.println("Enter the number of vertices");
1121 number_of_vertices = scan.nextInt();
1122adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
1123
1124 System.out.println("Enter the Weighted Matrix for the graph");
1125 for (int i = 1; i <= number_of_vertices; i++)
1126 {
1127 for (int j = 1; j <= number_of_vertices; j++)
1128 {
1129 adjacency_matrix[i][j] = scan.nextInt();
1130 if (i == j)
1131 {
1132 adjacency_matrix[i][j] = 0;
1133 continue;
1134 }
1135 if (adjacency_matrix[i][j] == 0)
1136 {
1137 adjacency_matrix[i][j] = INFINITE;
1138 }
1139 }
1140 }
1141
1142 prims prim = new prims(number_of_vertices);
1143 prim.primsAlgorithm(adjacency_matrix);
1144 prim.printMST();
1145
1146 } catch (InputMismatchException inputMismatch)
1147 {
1148 System.out.println("Wrong Input Format");
1149 }
1150 scan.close(); } }
1151Output:
1152Enter the number of nodes:4
1153Enter the cost matrix weights:
11540 3 0 7
11553 0 4 2
11560 4 0 5
11577 2 5 0
1158Enter no from vertex1 to vertex1-mincost:999
1159Enter no from vertex1 to vertex2-mincost:3
1160Enter no from vertex2 to vertex4-mincost:2
1161Enter no from vertex2 to vertex3-mincost:4
1162
1163
1164
1165
116611. Write a java program that implements Kruskal’s algorithm to generate minimum cost spanning tree.
1167
1168Program:
1169import java.util.ArrayList;
1170import java.util.Comparator;
1171import java.util.PriorityQueue;
1172public class KrushkalMST {
1173static class Edge {
1174int source;
1175int destination;
1176int weight;
1177
1178public Edge(int source, int destination, int weight) {
1179this.source = source;
1180this.destination = destination;
1181this.weight = weight;
1182}
1183}
1184static class Graph {
1185int vertices;
1186ArrayList<Edge> allEdges = new ArrayList<>();
1187Graph(int vertices) {
1188this.vertices = vertices;
1189}
1190public void addEgde(int source, int destination, int weight) {
1191Edge edge = new Edge(source, destination, weight);
1192allEdges.add(edge);
1193}
1194public void kruskalMST(){
1195PriorityQueue<Edge> pq = new PriorityQueue<>(allEdges.size(), Comparator.comparingInt(o -> o.weight));
1196for(int i = 0; i <allEdges.size() ; i++) {
1197pq.add(allEdges.get(i));
1198}
1199int [] parent = new int[vertices];
1200makeSet(parent);
1201ArrayList<Edge> mst = new ArrayList<>();
1202int index = 0;
1203while(index<vertices-1){
1204Edge edge = pq.remove();
1205int x_set = find(parent, edge.source);
1206int y_set = find(parent, edge.destination);
1207if(x_set==y_set){
1208}else {
1209mst.add(edge);
1210index++;
1211union(parent,x_set,y_set);
1212}
1213}
1214System.out.println("Minimum Spanning Tree: ");
1215printGraph(mst);
1216}
1217public void makeSet(int [] parent){
1218for (int i = 0; i <vertices ; i++) {
1219parent[i] = i;
1220}
1221}
1222public int find(int [] parent, int vertex){
1223
1224if(parent[vertex]!=vertex)
1225return find(parent, parent[vertex]);;.
1226return vertex;
1227}
1228public void union(int [] parent, int x, int y){
1229int x_set_parent = find(parent, x);
1230int y_set_parent = find(parent, y);
1231parent[y_set_parent] = x_set_parent;
1232}
1233public void printGraph(ArrayList<Edge> edgeList){
1234for (int i = 0; i <edgeList.size() ; i++) {
1235Edge edge = edgeList.get(i);
1236System.out.println("Edge-" + i + " source: " + edge.source + " destination: " + edge.destination +
1237 " weight: " + edge.weight);
1238}
1239}
1240}
1241public static void main(String[] args) {
1242int vertices = 6;
1243Graph graph = new Graph(vertices);
1244graph.addEgde(0, 1, 4);
1245graph.addEgde(0, 2, 3);
1246graph.addEgde(1, 2, 1);
1247graph.addEgde(1, 3, 2);
1248graph.addEgde(2, 3, 4);
1249graph.addEgde(3, 4, 2);
1250graph.addEgde(4, 5, 6);
1251}
1252}
1253Output:
1254Minimum Spanning Tree:
1255Edge-0 source: 1 destination: 2 weight: 1
1256Edge-1 source: 1 destination: 3 weight: 2
1257Edge-2 source: 3 destination: 4 weight: 2
1258Edge-3 source: 0 destination: 2 weight: 3
1259Edge-4 source: 4 destination: 5 weight: 6
1260
1261
1262
1263
1264
1265
126612.Write a java program to implement Floyd’s algorithm for the all pairs shortest path problem.
1267
1268
1269Program:
1270
1271 package kits;
1272
1273 import java.util.Scanner;
1274 public class FloydWarshall
1275 {
1276 private int distancematrix[][];
1277 private int numberofvertices;
1278 public static final int INFINITY = 999;
1279
1280 public FloydWarshall(int numberofvertices)
1281 {
1282 distancematrix = new int[numberofvertices + 1][numberofvertices + 1];
1283 this.numberofvertices = numberofvertices;
1284 }
1285
1286 public void floydwarshall(int adjacencymatrix[][])
1287 {
1288 for (int source = 1; source <= numberofvertices; source++)
1289 {
1290 for (int destination = 1; destination <= numberofvertices; destination++)
1291 {
1292 distancematrix[source][destination] = adjacencymatrix[source][destination];
1293 }
1294 }
1295
1296 for (int intermediate = 1; intermediate <= numberofvertices; intermediate++)
1297 {
1298 for (int source = 1; source <= numberofvertices; source++)
1299 {
1300 for (int destination = 1; destination <= numberofvertices; destination++)
1301 {
1302 if (distancematrix[source][intermediate] + distancematrix[intermediate][destination]
1303 <distancematrix[source][destination])
1304 distancematrix[source][destination] = distancematrix[source][intermediate]
1305 + distancematrix[intermediate][destination];
1306 }
1307 }
1308 }
1309
1310for (int source = 1; source <= numberofvertices; source++)
1311 System.out.print("\t" + source);
1312
1313 System.out.println();
1314for (int source = 1; source <= numberofvertices; source++)
1315 {
1316 System.out.print(source + "\t");
1317 for (int destination = 1; destination <= numberofvertices; destination++)
1318 {
1319 System.out.print(distancematrix[source][destination] + "\t");
1320 }
1321 System.out.println();
1322 }
1323 }
1324
1325 public static void main(String... arg)
1326 {
1327 int adjacency_matrix[][];
1328 int numberofvertices;
1329
1330 Scanner scan = new Scanner(System.in);
1331 System.out.println("Enter the number of vertices");
1332 numberofvertices = scan.nextInt();
1333
1334 adjacency_matrix = new int[numberofvertices + 1][numberofvertices + 1];
1335 System.out.println("Enter the Weighted Matrix for the graph");
1336 for (int source = 1; source <= numberofvertices; source++)
1337 {
1338 for (int destination = 1; destination <= numberofvertices; destination++)
1339 {
1340 adjacency_matrix[source][destination] = scan.nextInt();
1341 if (source == destination)
1342 {
1343 adjacency_matrix[source][destination] = 0;
1344 continue;
1345 }
1346 if (adjacency_matrix[source][destination] == 0)
1347 {
1348 adjacency_matrix[source][destination] = INFINITY;
1349 }
1350 }
1351 }
1352
1353System.out.println("The Transitive Closure of the Graph");
1354 FloydWarshall floydwarshall = new FloydWarshall)(numberofvertices);
1355floydwarshall.floydwarshall(adjacency_matrix);
1356 scan.close();
1357 }
1358 }
1359
1360Output:Enter the number of vertices
13614
1362Enter the weighted matrix for the graph
13630 0 3 0
13642 0 0 0
13650 7 0 1
13666 0 0 0
1367The Transitive closure of the graph
13680 10 3 4
13692 0 5 6
13707 7 0 1
13716 16 9 0
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
138313. Write a java program to implement Dynamic Programming algorithm for the 0/1 Knapsack problem
1384
1385Program:
1386
1387package kits;
1388 public class Knapsack_DP
1389 {
1390 static int max(int a, int b)
1391 {
1392 return (a > b)? a : b;
1393 }
1394 static int knapSack(int W, int wt[], int val[], int n)
1395 {
1396 int i, w;
1397 int [][]K = new int[n+1][W+1];
1398
1399 // Build table K[][] in bottom up manner
1400 for (i = 0; i <= n; i++)
1401 {
1402 for (w = 0; w <= W; w++)
1403 {
1404 if (i==0 || w==0)
1405 K[i][w] = 0;
1406 else if (wt[i-1] <= w)
1407 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
1408 else
1409 K[i][w] = K[i-1][w];
1410 }
1411 }
1412
1413 return K[n][W];
1414 }
1415
1416 public static void main(String args[])
1417 {
1418 Scanner sc = new Scanner(System.in);
1419 System.out.println("Enter the number of items: ");
1420 int n = sc.nextInt();
1421 System.out.println("Enter the items weights: ");
1422 int []wt = new int[n];
1423 for(int i=0; i<n; i++)
1424 wt[i] = sc.nextInt();
1425
1426 System.out.println("Enter the items values: ");
1427 int []val = new int[n];
1428 for(int i=0; i<n; i++)
1429 val[i] = sc.nextInt();
1430
1431 System.out.println("Enter the maximum capacity: ");
1432 int W = sc.nextInt();
1433
1434 System.out.println("The maximum value that can be put in a knapsack of capacity W is: " + knapSack(W, wt, val, n));
1435 sc.close();
1436 }
1437 }
1438
1439
1440Output:
1441Enter the number of items 4
1442Enter the item weights
14433
14442
14454
14461
1447Enter the item values
1448100
144920
145060
145140
1452Enter the maximum capacity 5
1453The maximum value that can be put in a knapsack of capacity is:140
1454
1455
1456
1457
1458
1459
1460
146114.Write a java program to implement Dynamic Programming algorithm for the Optimal Binary Search Tree Problem.
1462
1463
1464Program:
1465
1466
1467package kits;
1468 import java.io.*;
1469 import java.util.*;
1470 class Optimal
1471 {
1472 public int p[];
1473 public int q[];
1474 public int a[];
1475 public int w[][];
1476 public int c[][];
1477 public int r[][];
1478 public int n;
1479 int front,rear,queue[];
1480 public Optimal(int SIZE)
1481 {
1482 p=new int[SIZE];
1483 q= new int[SIZE];
1484 a=new int[SIZE];
1485 w=new int[SIZE][SIZE];
1486 c=new int[SIZE][SIZE];
1487 r=new int[SIZE][SIZE];
1488 queue=new int[SIZE];
1489 front=rear=-1;
1490 }
1491
1492 /* This function returns a value in the range r[i][j-1] to r[i+1][j] SO that the cost c[i][k-1] + c[k][j] is minimum */
1493
1494
1495 public int Min_Value(int i, int j)
1496 {
1497 int m,k=0;
1498 int minimum = 32000;
1499 for (m=r[i][j-1] ; m<=r[i+1][j] ; m++)
1500 {
1501 if ((c[i][m-1]+c[m][j]) < minimum)
1502 {
1503 minimum = c[i][m-1] + c[m][j];
1504 k = m;
1505 }
1506 }
1507 return k;
1508 }
1509
1510
1511 /* This function builds the table from all the given probabilities It basically computes C,r,W values */
1512
1513
1514 public void OBST()
1515 {
1516 int i, j, k, l, m;
1517 for (i=0 ; i<n ; i++)
1518 {
1519 // Initialize
1520 w[i][i] = q[i];
1521 r[i][i] = c[i][i] = 0;
1522 // Optimal trees with one node
1523 w[i][i+1] = q[i] + q[i+1] + p[i+1];
1524 r[i][i+1] = i+1;
1525 c[i][i+1] = q[i] + q[i+1] + p[i+1];
1526 }
1527 w[n][n] = q[n];
1528 r[n][n] = c[n][n] = 0;
1529 // Find optimal trees with m nodes
1530 for (m=2 ; m<=n ; m++)
1531 {
1532 for (i=0 ; i<=n-m ; i++)
1533 {
1534 j = i+m;
1535 w[i][j] = w[i][j-1] + p[j] + q[j];
1536 k = Min_Value(i,j);
1537 c[i][j] = w[i][j] + c[i][k-1] + c[k][j];
1538 r[i][j] = k;
1539 }
1540 }
1541 }
1542
1543
1544 /*This function builds the tree from the tables made by the OBST function */
1545
1546
1547 public void build_tree()
1548 {
1549 int i, j, k;
1550 System.out.print("The Optimal Binary Search Tree For The Given Nodes Is ....\n");
1551 System.out.print("\n The Root of this OBST is :: "+r[0][n]);
1552 System.out.print("\n The Cost Of this OBST is :: "+c[0][n]);
1553 System.out.print("\n\n\tNODE\tLEFT CHILD\tRIGHT CHILD");
1554 System.out.println("\n -------------------------------------------------------");
1555 queue[++rear] = 0;
1556 queue[++rear] = n;
1557 while(front != rear)
1558 {
1559 i = queue[++front];
1560 j = queue[++front];
1561 k = r[i][j];
1562 System.out.print("\n "+k);
1563 if (r[i][k-1] != 0)
1564 {
1565 System.out.print(" "+r[i][k-1]);
1566 queue[++rear] = i;
1567 queue[++rear] = k-1;
1568 }
1569 else
1570 System.out.print(" -");
1571 if(r[k][j] != 0)
1572 {
1573 System.out.print(" "+r[k][j]);
1574 queue[++rear] = k;
1575 queue[++rear] = j;
1576 }
1577 else
1578 System.out.print(" -");
1579 }
1580 System.out.println("\n");
1581 }
1582 }
1583 /* This is the main function */
1584 class OBSTDemo
1585 {
1586 public static void main (String[] args )throws IOException,NullPointerException
1587 {
1588 Optimal obj=new Optimal(10);
1589 int i;
1590 System.out.print("\n Optimal Binary Search Tree \n");
1591 System.out.print("\n Enter the number of nodes ");
1592 obj.n=getInt();
1593 System.out.print("\n Enter the data as ....\n");
1594 for (i=1;i<=obj.n;i++)
1595 {
1596 System.out.print("\n a["+i+"]");
1597 obj.a[i]=getInt();
1598 }
1599 for (i=1 ; i<=obj.n ; i++)
1600 {
1601 System.out.println("p["+i+"]");
1602 obj.p[i]=getInt();
1603 }
1604 for (i=0 ; i<=obj.n ; i++)
1605 {
1606 System.out.print("q["+i+"]");
1607 obj.q[i]=getInt();
1608 }
1609 obj.OBST();
1610 obj.build_tree();
1611 }
1612 public static String getString() throws IOException
1613 {
1614 InputStreamReader input = new InputStreamReader(System.in);
1615 BufferedReader b = new BufferedReader(input);
1616 String str = b.readLine();//reading the string from console
1617 return str;
1618 }
1619
1620 public static char getChar() throws IOException
1621 {
1622 String str = getString();
1623 return str.charAt(0);//reading first char of console string
1624 }
1625 public static int getInt() throws IOException
1626 {
1627 String str = getString();
1628 return Integer.parseInt(str);//converting console string to numeric value
1629 }
1630 }
1631
1632Output:
1633
1634Enter no of identifiers 4
1635Enter identifiers
1636Do
1637If
1638Int while
1639Enter success probability for identifier
16403
16413
16421
16431
1644Enter failure probabilities for identifiers
16452
16463
16471
16481
16491
1650Tree is processed
1651If
1652Do
1653Int
1654while