· 6 years ago · Nov 28, 2019, 01:56 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:
495Q - -
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
1178
1179public Edge(int source, int destination, int weight) {
1180this.source = source;
1181this.destination = destination;
1182this.weight = weight;
1183}
1184}
1185static class Graph {
1186int vertices;
1187ArrayList<Edge> allEdges = new ArrayList<>();
1188Graph(int vertices) {
1189this.vertices = vertices;
1190}
1191public void addEgde(int source, int destination, int weight) {
1192Edge edge = new Edge(source, destination, weight);
1193allEdges.add(edge);
1194}
1195public void kruskalMST(){
1196PriorityQueue<Edge> pq = new PriorityQueue<>(allEdges.size(), Comparator.comparingInt(o -> o.weight));
1197for(int i = 0; i <allEdges.size() ; i++) {
1198pq.add(allEdges.get(i));
1199}
1200int [] parent = new int[vertices];
1201makeSet(parent);
1202ArrayList<Edge> mst = new ArrayList<>();
1203int index = 0;
1204while(index<vertices-1){
1205Edge edge = pq.remove();
1206int x_set = find(parent, edge.source);
1207int y_set = find(parent, edge.destination);
1208if(x_set==y_set){
1209}else {
1210mst.add(edge);
1211index++;
1212union(parent,x_set,y_set);
1213}
1214}
1215System.out.println("Minimum Spanning Tree: ");
1216printGraph(mst);
1217}
1218public void makeSet(int [] parent){
1219for (int i = 0; i <vertices ; i++) {
1220parent[i] = i;
1221}
1222}
1223public int find(int [] parent, int vertex){
1224
1225if(parent[vertex]!=vertex)
1226return find(parent, parent[vertex]);;.
1227return vertex;
1228}
1229public void union(int [] parent, int x, int y){
1230int x_set_parent = find(parent, x);
1231int y_set_parent = find(parent, y);
1232parent[y_set_parent] = x_set_parent;
1233}
1234public void printGraph(ArrayList<Edge> edgeList){
1235for (int i = 0; i <edgeList.size() ; i++) {
1236Edge edge = edgeList.get(i);
1237System.out.println("Edge-" + i + " source: " + edge.source + " destination: " + edge.destination +
1238 " weight: " + edge.weight);
1239}
1240}
1241}
1242public static void main(String[] args) {
1243int vertices = 6;
1244Graph graph = new Graph(vertices);
1245graph.addEgde(0, 1, 4);
1246graph.addEgde(0, 2, 3);
1247graph.addEgde(1, 2, 1);
1248graph.addEgde(1, 3, 2);
1249graph.addEgde(2, 3, 4);
1250graph.addEgde(3, 4, 2);
1251graph.addEgde(4, 5, 6);
1252}
1253}
1254Output:
1255Minimum Spanning Tree:
1256Edge-0 source: 1 destination: 2 weight: 1
1257Edge-1 source: 1 destination: 3 weight: 2
1258Edge-2 source: 3 destination: 4 weight: 2
1259Edge-3 source: 0 destination: 2 weight: 3
1260Edge-4 source: 4 destination: 5 weight: 6
1261
1262
1263
1264
1265
1266
1267
126812.Write a java program to implement Floyd’s algorithm for the all pairs shortest path problem.
1269
1270
1271Program:
1272
1273 package kits;
1274
1275 import java.util.Scanner;
1276 public class FloydWarshall
1277 {
1278 private int distancematrix[][];
1279 private int numberofvertices;
1280 public static final int INFINITY = 999;
1281
1282 public FloydWarshall(int numberofvertices)
1283 {
1284 distancematrix = new int[numberofvertices + 1][numberofvertices + 1];
1285 this.numberofvertices = numberofvertices;
1286 }
1287
1288 public void floydwarshall(int adjacencymatrix[][])
1289 {
1290 for (int source = 1; source <= numberofvertices; source++)
1291 {
1292 for (int destination = 1; destination <= numberofvertices; destination++)
1293 {
1294 distancematrix[source][destination] = adjacencymatrix[source][destination];
1295 }
1296 }
1297
1298 for (int intermediate = 1; intermediate <= numberofvertices; intermediate++)
1299 {
1300 for (int source = 1; source <= numberofvertices; source++)
1301 {
1302 for (int destination = 1; destination <= numberofvertices; destination++)
1303 {
1304 if (distancematrix[source][intermediate] + distancematrix[intermediate][destination]
1305 <distancematrix[source][destination])
1306 distancematrix[source][destination] = distancematrix[source][intermediate]
1307 + distancematrix[intermediate][destination];
1308 }
1309 }
1310 }
1311
1312for (int source = 1; source <= numberofvertices; source++)
1313 System.out.print("\t" + source);
1314
1315 System.out.println();
1316for (int source = 1; source <= numberofvertices; source++)
1317 {
1318 System.out.print(source + "\t");
1319 for (int destination = 1; destination <= numberofvertices; destination++)
1320 {
1321 System.out.print(distancematrix[source][destination] + "\t");
1322 }
1323 System.out.println();
1324 }
1325 }
1326
1327 public static void main(String... arg)
1328 {
1329 int adjacency_matrix[][];
1330 int numberofvertices;
1331
1332 Scanner scan = new Scanner(System.in);
1333 System.out.println("Enter the number of vertices");
1334 numberofvertices = scan.nextInt();
1335
1336 adjacency_matrix = new int[numberofvertices + 1][numberofvertices + 1];
1337 System.out.println("Enter the Weighted Matrix for the graph");
1338 for (int source = 1; source <= numberofvertices; source++)
1339 {
1340 for (int destination = 1; destination <= numberofvertices; destination++)
1341 {
1342 adjacency_matrix[source][destination] = scan.nextInt();
1343 if (source == destination)
1344 {
1345 adjacency_matrix[source][destination] = 0;
1346 continue;
1347 }
1348 if (adjacency_matrix[source][destination] == 0)
1349 {
1350 adjacency_matrix[source][destination] = INFINITY;
1351 }
1352 }
1353 }
1354
1355System.out.println("The Transitive Closure of the Graph");
1356 FloydWarshall floydwarshall = new FloydWarshall)(numberofvertices);
1357floydwarshall.floydwarshall(adjacency_matrix);
1358 scan.close();
1359 }
1360 }
1361
1362Output:Enter the number of vertices
13634
1364Enter the weighted matrix for the graph
13650 0 3 0
13662 0 0 0
13670 7 0 1
13686 0 0 0
1369The Transitive closure of the graph
13700 10 3 4
13712 0 5 6
13727 7 0 1
13736 16 9 0
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
138513. Write a java program to implement Dynamic Programming algorithm for the 0/1 Knapsack problem
1386
1387Program:
1388
1389package kits;
1390 public class Knapsack_DP
1391 {
1392 static int max(int a, int b)
1393 {
1394 return (a > b)? a : b;
1395 }
1396 static int knapSack(int W, int wt[], int val[], int n)
1397 {
1398 int i, w;
1399 int [][]K = new int[n+1][W+1];
1400
1401 // Build table K[][] in bottom up manner
1402 for (i = 0; i <= n; i++)
1403 {
1404 for (w = 0; w <= W; w++)
1405 {
1406 if (i==0 || w==0)
1407 K[i][w] = 0;
1408 else if (wt[i-1] <= w)
1409 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
1410 else
1411 K[i][w] = K[i-1][w];
1412 }
1413 }
1414
1415 return K[n][W];
1416 }
1417
1418 public static void main(String args[])
1419 {
1420 Scanner sc = new Scanner(System.in);
1421 System.out.println("Enter the number of items: ");
1422 int n = sc.nextInt();
1423 System.out.println("Enter the items weights: ");
1424 int []wt = new int[n];
1425 for(int i=0; i<n; i++)
1426 wt[i] = sc.nextInt();
1427
1428 System.out.println("Enter the items values: ");
1429 int []val = new int[n];
1430 for(int i=0; i<n; i++)
1431 val[i] = sc.nextInt();
1432
1433 System.out.println("Enter the maximum capacity: ");
1434 int W = sc.nextInt();
1435
1436 System.out.println("The maximum value that can be put in a knapsack of capacity W is: " + knapSack(W, wt, val, n));
1437 sc.close();
1438 }
1439 }
1440
1441
1442Output:
1443Enter the number of items 4
1444Enter the item weights
14453
14462
14474
14481
1449Enter the item values
1450100
145120
145260
145340
1454Enter the maximum capacity 5
1455The maximum value that can be put in a knapsack of capacity is:140
1456
1457
1458
1459
1460
1461
1462
146314.Write a java program to implement Dynamic Programming algorithm for the Optimal Binary Search Tree Problem.
1464
1465
1466Program:
1467
1468
1469package kits;
1470 import java.io.*;
1471 import java.util.*;
1472 class Optimal
1473 {
1474 public int p[];
1475 public int q[];
1476 public int a[];
1477 public int w[][];
1478 public int c[][];
1479 public int r[][];
1480 public int n;
1481 int front,rear,queue[];
1482 public Optimal(int SIZE)
1483 {
1484 p=new int[SIZE];
1485 q= new int[SIZE];
1486 a=new int[SIZE];
1487 w=new int[SIZE][SIZE];
1488 c=new int[SIZE][SIZE];
1489 r=new int[SIZE][SIZE];
1490 queue=new int[SIZE];
1491 front=rear=-1;
1492 }
1493
1494 /* 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 */
1495
1496
1497 public int Min_Value(int i, int j)
1498 {
1499 int m,k=0;
1500 int minimum = 32000;
1501 for (m=r[i][j-1] ; m<=r[i+1][j] ; m++)
1502 {
1503 if ((c[i][m-1]+c[m][j]) < minimum)
1504 {
1505 minimum = c[i][m-1] + c[m][j];
1506 k = m;
1507 }
1508 }
1509 return k;
1510 }
1511
1512
1513 /* This function builds the table from all the given probabilities It basically computes C,r,W values */
1514
1515
1516 public void OBST()
1517 {
1518 int i, j, k, l, m;
1519 for (i=0 ; i<n ; i++)
1520 {
1521 // Initialize
1522 w[i][i] = q[i];
1523 r[i][i] = c[i][i] = 0;
1524 // Optimal trees with one node
1525 w[i][i+1] = q[i] + q[i+1] + p[i+1];
1526 r[i][i+1] = i+1;
1527 c[i][i+1] = q[i] + q[i+1] + p[i+1];
1528 }
1529 w[n][n] = q[n];
1530 r[n][n] = c[n][n] = 0;
1531 // Find optimal trees with m nodes
1532 for (m=2 ; m<=n ; m++)
1533 {
1534 for (i=0 ; i<=n-m ; i++)
1535 {
1536 j = i+m;
1537 w[i][j] = w[i][j-1] + p[j] + q[j];
1538 k = Min_Value(i,j);
1539 c[i][j] = w[i][j] + c[i][k-1] + c[k][j];
1540 r[i][j] = k;
1541 }
1542 }
1543 }
1544
1545
1546 /*This function builds the tree from the tables made by the OBST function */
1547
1548
1549 public void build_tree()
1550 {
1551 int i, j, k;
1552 System.out.print("The Optimal Binary Search Tree For The Given Nodes Is ....\n");
1553 System.out.print("\n The Root of this OBST is :: "+r[0][n]);
1554 System.out.print("\n The Cost Of this OBST is :: "+c[0][n]);
1555 System.out.print("\n\n\tNODE\tLEFT CHILD\tRIGHT CHILD");
1556 System.out.println("\n -------------------------------------------------------");
1557 queue[++rear] = 0;
1558 queue[++rear] = n;
1559 while(front != rear)
1560 {
1561 i = queue[++front];
1562 j = queue[++front];
1563 k = r[i][j];
1564 System.out.print("\n "+k);
1565 if (r[i][k-1] != 0)
1566 {
1567 System.out.print(" "+r[i][k-1]);
1568 queue[++rear] = i;
1569 queue[++rear] = k-1;
1570 }
1571 else
1572 System.out.print(" -");
1573 if(r[k][j] != 0)
1574 {
1575 System.out.print(" "+r[k][j]);
1576 queue[++rear] = k;
1577 queue[++rear] = j;
1578 }
1579 else
1580 System.out.print(" -");
1581 }
1582 System.out.println("\n");
1583 }
1584 }
1585 /* This is the main function */
1586 class OBSTDemo
1587 {
1588 public static void main (String[] args )throws IOException,NullPointerException
1589 {
1590 Optimal obj=new Optimal(10);
1591 int i;
1592 System.out.print("\n Optimal Binary Search Tree \n");
1593 System.out.print("\n Enter the number of nodes ");
1594 obj.n=getInt();
1595 System.out.print("\n Enter the data as ....\n");
1596 for (i=1;i<=obj.n;i++)
1597 {
1598 System.out.print("\n a["+i+"]");
1599 obj.a[i]=getInt();
1600 }
1601 for (i=1 ; i<=obj.n ; i++)
1602 {
1603 System.out.println("p["+i+"]");
1604 obj.p[i]=getInt();
1605 }
1606 for (i=0 ; i<=obj.n ; i++)
1607 {
1608 System.out.print("q["+i+"]");
1609 obj.q[i]=getInt();
1610 }
1611 obj.OBST();
1612 obj.build_tree();
1613 }
1614 public static String getString() throws IOException
1615 {
1616 InputStreamReader input = new InputStreamReader(System.in);
1617 BufferedReader b = new BufferedReader(input);
1618 String str = b.readLine();//reading the string from console
1619 return str;
1620 }
1621
1622 public static char getChar() throws IOException
1623 {
1624 String str = getString();
1625 return str.charAt(0);//reading first char of console string
1626 }
1627 public static int getInt() throws IOException
1628 {
1629 String str = getString();
1630 return Integer.parseInt(str);//converting console string to numeric value
1631 }
1632 }
1633
1634Output:
1635
1636Enter no of identifiers 4
1637Enter identifiers
1638Do
1639If
1640Int while
1641Enter success probability for identifier
16423
16433
16441
16451
1646Enter failure probabilities for identifiers
16472
16483
16491
16501
16511
1652Tree is processed
1653If
1654Do
1655Int
1656while