Daa1_manual.docx

HKBK COLLEGE OF ENGINEERING (Affiliated to VTU, Belgaum and Approved by AICTE) DEPARTMENT OF INFORMATION SCIENCE & ENGINEERING

NBA Accredited Programme

LABORATORY MANUAL DESIGN AND ANALYSIS OF ALGORITHM LABORATORY [As per Choice Based Credit System (CBCS) scheme] (Effective from the academic year 2015 -2016)

15CSL47

PREPARED BY Prof. Farnaz Khatoon

HKBK COLLEGE OF ENGINEERING Nagawara, Bangaluru -560 045 www.hkbkeducation.org

HKBK COLLEGE OF ENGINEERING (Affiliated to VTU, Belgaum and Approved by AICTE) DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Mission and Vision of the Institution

  

Mission To achieve academic excellence in science, engineering and technology through dedication to duty, innovation in teaching and faith in human values. To enable our students to develop into outstanding professional with high ethical standards to face the challenges of 21st century. To provide educational opportunities to the deprived and weaker section of the society to uplift their socio-economic status.

Vision To empower students through wholesome education and enable the students to develop into highly qualified and trained professionals with ethics and emerge as responsible citizen with broad outlook to build a vibrant nation. Mission and Vision of the CSE Department

 

Mission To provide excellent technical knowledge and computing skills to make the graduates globally competitive with professional ethics. To involve in research activities and be committed to lifelong learning to make positive contributions to the society.

Vision To advance the intellectual capacity of the nation and the international community by imparting knowledge to graduates who are globally recognized as innovators, entrepreneur and competent professionals.

HKBK COLLEGE OF ENGINEERING (Affiliated to VTU, Belgaum and Approved by AICTE) DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

PEO-1 PEO-2

PEO-3 PEO-4 PEO-5

Programme Educational Objectives To provide students with a strong foundation in engineering fundamentals and in the computer science and engineering to work in the global scenario. To provide sound knowledge of programming and computing techniques and good communication and interpersonal skills so that they will be capable of analyzing, designing and building innovative software systems. To equip students in the chosen field of engineering and related fields to enable him to work in multidisciplinary teams. To inculcate in students professional, personal and ethical attitude to relate engineering issues to broader social context and become responsible citizen. To provide students with an environment for life-long learning which allow them to successfully adapt to the evolving technologies throughout their professional carrier and face the global challenges. Programme Outcomes

a.

b.

c.

d.

e.

f.

g.

h. i.

Engineering Knowledge: Apply knowledge of mathematics, science, engineering fundamentals and an engineering specialization to the solution of complex engineering problems. Problem Analysis: Identify, formulate, research literature and analyze complex engineering problems reaching substantiated conclusions using first principles of mathematics, natural sciences and engineering sciences Design/ Development of Solutions: Design solutions for complex engineering problems and design system components or processes that meet specified needs with appropriate consideration for public health and safety, cultural, societal and environmental considerations. Conduct investigations of complex problems using research-based knowledge and research methods including design of experiments, analysis and interpretation of data and synthesis of information to provide valid conclusions. Modern Tool Usage: Create, select and apply appropriate techniques, resources and modern engineering and IT tools including prediction and modeling to complex engineering activities with an under- standing of the limitations. The Engineer and Society: Apply reasoning informed by contextual knowledge to assess societal, health, safety, legal and cultural issues and the consequent responsibilities relevant to professional engineering practice. Environment and Sustainability: Understand the impact of professional engineering solutions in societal and environmental contexts and demonstrate knowledge of and need for sustainable development. Ethics: Apply ethical principles and commit to professional ethics and responsibilities and norms of engineering practice. Individual and Team Work: Function effectively as an individual, and as a member or leader in diverse teams and in multi disciplinary settings.

Communication: Communicate effectively on complex engineering activities with the engineering community and with society at large, such as being able to comprehend and write effective reports and design documentation, make effective presentations and give and receive clear instructions. k. Life-long Learning: Recognize the need for and have the preparation and ability to engage in independent and life- long learning in the broadest context of technological change. Project Management and Finance: Demonstrate knowledge and understanding of l. engineering and management principles and apply these to one’s own work, as a member and leader in a team, to manage projects and in multidisciplinary environments. Programme Specific Outcomes j.

m. Problem-Solving Skills: An ability to investigate and solve a problem by analysis, interpretation of data, design and implementation through appropriate techniques,tools and skills. n. Professional Skills: An ability to apply algorithmic principles, computing skills and computer science theory in the modelling and design of computerbased systems. o.

Entrepreneurial Ability: An ability to apply design, development principles and management skills in the construction of software product of varying complexity to become an entrepreneur

15CSL47

DAA Lab-1 Manual

HKBK College of Engineering Department of Computer Sciences and Engineering Bangalore-560045 Design And analysis of Algorithms Laboratory

Course objectives: This course will enable students to  Design and implement various algorithms in JAVA  Employ various design strategies for problem solving.  Measure and compare the performance of different algorithms

List of Experiments Subject Code 15CSL47 IA Marks 20 S.No Questions- DAA-1 1. Write a Java program to print 'Hello' on screen and then print your name on a separate line 2.

Write a program to print the factorial of 4

3.

Write a Java Program to compute the area and perimenter of a circle by reading its radius as a command line argument. Write a program in Java to compute the sum of the digits of a given integer. Remember, your integer should not be less than the five digits. (e.g., if input is 23451 then sum of the digits of 23451will be 15) Write a program in Java to reverse a given number and check for palindrome and display appropriate message. a. Create a Java class called Student with the following details as variables within it. (i) USN (ii) Name (iii) Branch (iv) Phone Write a Java program to create nStudentobjects and print the USN, Name, Branch, and Phone of these objects with suitable headings. b. Write a Java program to implement the Stack using arrays. Write Push(), Pop(), and Display() methods to demonstrate its working. a. Write a Java program to read two integers a andb. Compute a/b and print, when b is not zero. Raise an exception when b is equal to zero b. Write a Java program that implements a multi-thread application that hash tree threads. First thread generates a random integer for every 1 second; second thread computes the square of the number and prints; third thread will print the value of cube

4.

5. 6.

7.

ISE @ HKBKCE

5

2016-17

15CSL47

DAA Lab-1 Manual

of the number.

8.

9. 10. 11. 12.

13.

Sort a given set of n integer elements using Quick Sort method and compute its time complexity. Run the program for varied values of n > 5000 and record the time taken to sort. Plot a graph of the time taken versus n on graph sheet. The elements can be read from a file or can be generated using the random number generator. Demonstrate using Java how the divideand-conquer method works along with its time complexity analysis: worst case, average case and best case. Implement in Java, the 0/1 Knapsack problem using (a) Dynamic Programming method (b) Greedy method. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's algorithm. Implement program in java language. Find Minimum Cost Spanning Tree of a given undirected graph using Prim's algorithm Implement program in java language. Write a Java Applet program which reads your name and address in different text fields and when a button named find is pressed the sum of the length of characters in name and address is displayed in another text field. Use appropriate colors, layout to make your applet look good. Write a Java Applet program, which provides a text area with horizontal and vertical scrollbars. Type some lines of text in the text area and use scrollbars for movements in the text area. Read a word in a text field and find whether the word is in the content of the text area or not.

Course Outcomes: After studying this course, students will be able to CO1. Design algorithms using appropriate design techniques (brute-force, greedy, dynamic programming, etc.) CO2. Implement a variety of algorithms such assorting, graph related, combinatorial, etc., in a high level language. CO3. Analyze and compare the performance of algorithms using language features. CO4. Apply and implement learned algorithm design techniques and data structures to solve realworldproblems

ISE @ HKBKCE

6

2016-17

15CSL47

DAA Lab-1 Manual

1. Write a Java program to print 'Hello' on screen and then print your name on a separate line ALGORITHM 1. Algorithm 2. { 3. write “hello” 4. write “” 5. } PROGRAM: publicclass first { publicstaticvoid main(String []args) { System.out.println("Hello"); System.out.println("DAA"); } } OUTPUT: Hello DAA 2. Write a program to print the factorial of 4 ALGORITHM: 1. Algorithm fact 2. { f:=1 for i= 1 to 4 do f=f*i write f 3. } PROGRAM : publicclass fact { public static void main(String[] args) { int f=1; for(inti=1;i<=4;i++) f=f*i; ISE @ HKBKCE

7

2016-17

15CSL47

DAA Lab-1 Manual

System.out.println("factorial of 4 is "+f);

} } OUTPUT: factorial of 4 is 24 3. Write a Java Program to compute the area and perimenter of a circle by reading its radius as a command line argument Algorithm Area(r) 1. { 2. Read r 3. Area=3.14*r*r 4. Circumference=2*3.14*r 5. Write area and circumference 6. } Program : publicclass circle{ publicstaticvoid main(String[] args) { int r= Integer.parseInt(args[0]); double area=3.14*r*r; doublecirc=2*3.14*r; System.out.println("Area of the circle is "+area); System.out.println("circumference of the circle is "+circ);

} } Output: O1 Radius=5 Area of the circle is 78.5 circumference of the circle is 31.400000000000002 ISE @ HKBKCE

8

2016-17

15CSL47

DAA Lab-1 Manual

O2 Radius=0 Area of the circle is 0.0 circumference of the circle is 0.0

4. Write a program in Java to compute the sum of the digits of a given integer. Remember, your integer should not be less than the five digits. (e.g., if input is 23451 then sum of the digits of 23451will be 15) ALGORITHM sum(n) 1. { 2. sum:=0 3. Read num 4. If num>=9999; while( num!=0 ) { rem=n%10 sum+=rem n=n/10 } else write “number should be 5digit” 5. } PROGRAM: importjava.util.Scanner; classSumdigits { public static void main(String args[])throws IOException { Scanner input=new Scanner(System.in)); int num,rem; int sum=0; System.out.println("Enter a number"); num=input.nextInt(); if(num>=999) { while(num>0) { rem=num%10; ISE @ HKBKCE

9

2016-17

15CSL47

DAA Lab-1 Manual

sum=sum+rem; num=num/10; } System.out.println("The sum of the digits"+sum); } else { System.out.println(“it should be a 5 digit number”); } } } OUTPUT: O1 Enter a number 122 Output: It should be a 5 digit number O2 Enter a number 23415 Output: The sum of the digits is:15 O3 Enter a number 234165 Output: The sum of the digits is:21 5. Write a program in Java to reverse a given number and check for palindrome and display appropriate message. ALGORITHM: 1. Start 2. Read num 3. Initialize orig with num 4. While num> 0 5. { 6. Rem= num%10 7. rev=rev*10+rem; 8. num=num/10; 9. } ISE @ HKBKCE

10

2016-17

15CSL47

DAA Lab-1 Manual

10. display the reversed number, rev 11. If (rev == orig) 12. Outout “the number is palindrome” 13. Else 14. Output “the number is not palindrome” 15. Stop PROGRAM: importjava.util.Scanner; publicclass reverse { publicstaticvoid main(String[] args) { Scanner input=newScanner(System.in); intnum,rem,orig; int rev=0; System.out.println("Enter a number"); num=input.nextInt(); orig=num; while(num>0) { rem=num%10; rev=rev*10+rem; num=num/10; } System.out.println("The reverse of the digits"+sum); if(rev==orig) System.out.println("the number is a palindrome"); else System.out.println("the number is not a palindrome"); } } OUTPUT: O1 Enter a number 123 The reverse of the digits 321 the number is not a palindrome O2 Enter a number 0 The reverse of the digits0 ISE @ HKBKCE

11

2016-17

15CSL47

DAA Lab-1 Manual

the number is a palindrome O3 Enter a number 121 The reverse of the digits121 The number is a palindrome 6. A. Create a Java class called Student with the following details as variables within it. (i) USN (ii) Name (iii) Branch (iv) Phone Write a Java program to create nStudentobjects and print the USN, Name, Branch, and Phone of these objects with suitable headings. ALGORITHM: 1. Start 2. read total number of students n 3. for i= 1 to n 4. read usn,name, branch phone number 5. for i= 1 to n 6. displayusn,name, branch phone number 7. Stop PROGRAM: importjava.io.*; importjava.util.Scanner; classStudentDetails { publicstaticvoid main(String s[]) { Scanner in = newScanner(System.in); System.out.println("enter the number of students"); int n=in.nextInt(); Student students[] = new Student[n]; for(inti = 0; i<students.length; i++) { students[i] = new Student();

ISE @ HKBKCE

12

2016-17

15CSL47

DAA Lab-1 Manual

System.out.println("enter student "+(i+1)+"details -- USN Name Branch Phno"); students[i].usn=in.next(); students[i].name=in.next(); students[i].branch=in.next(); students[i].phno=in.nextInt(); } System.out.println("USN \t Name\t Branch\t Phno"); for(inti = 0; i<students.length; i++) { System.out.println( students[i].usn +"\t "+ students[i].name +"\t" + students[i].phno); } }

students[i].branch+"\t" +

} class Student { String name; String usn; String branch; intphno; } OUTPUT: O1 Enter the number of students 2 Enter student 1 details -- USN Name Branch Phno 1 abc CSE 123456 Enter student 2details -- USN Name Branch Phno 2 xyz CSE 67890 USN 1 2

Name Branch Phno abc CSE 123456 xyz CSE 67890

O2 enter the number of students 0 ISE @ HKBKCE

13

2016-17

15CSL47

USN

ISE @ HKBKCE

DAA Lab-1 Manual

Name Branch

Phno

14

2016-17

15CSL47

DAA Lab-1 Manual

6. B. Write a Java program to implement the Stack using arrays. Write Push(), Pop(), and Display() methods to demonstrate its working. ALGORITHM 1. 2. 3. 4. 5. 6. 7. 8. 9.

Start push If top== size-1 Display “stack full” Else { Top= top+1 S[top]= item } Stop push

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

Start pop If top== -1 Display “stack empty” Else { Itemdel=S[top] top=top-1 } Stop pop

1. 2. 3. 4.

Start display For i= 0 to top do Display s[i] Stop display

1. Start main 2. Repeat until true 3. { 4. Display 1.push, 2.Pop, 3. Display, 4. Exit 5. Read choice 6. Case(choice) 7. { 8. 9. Case 1: push 10. Case 2: pop ISE @ HKBKCE

15

2016-17

15CSL47

DAA Lab-1 Manual

11. Case 3: display 12. Case 4: exit 13. } 14. } 15. Stop Main PROGRAM: importjava.io.*; importjava.util.Scanner; publicclass stack { int size=5; int top; int s[]= newint[size]; stack() { top=-1; } void push(int item) { if (top==size-1) System.out.println("Stack is full "); else s[++top]=item; } int pop() { if (top==-1) { System.out.println("Stack is Empty "); return 0; } else return s[top--]; } void display() { if (top==-1) System.out.println("Stack is Empty "); ISE @ HKBKCE

16

2016-17

15CSL47

DAA Lab-1 Manual

else { for(inti=top;i>=0;i--) System.out.println(s[i]); } } publicstaticvoid main(String[] args) { stack s1 = new stack(); while(true) { System.out.println("1.push 2.pop, 3. display, 4. Exit"); System.out.println("Enter the Choice"); Scanner in= newScanner(System.in); intch=in.nextInt(); switch(ch) { case 1: System.out.println("Enter the item"); int item=in.nextInt(); s1.push(item);break; case 2: intitemdel=s1.pop(); if(itemdel!=0) System.out.println("The item deleted is "+itemdel); break; case 3:s1.display(); break; default:System.exit(0); } } } } OUTPUT: 1.push 2.pop, 3. display, 4. Exit Enter the Choice 2 Stack is Empty 1.push 2.pop, 3. display, 4. Exit Enter the Choice 3 Stack is Empty 1.push 2.pop, 3. display, 4. Exit ISE @ HKBKCE

17

2016-17

15CSL47

DAA Lab-1 Manual

Enter the Choice 1 Enter the item 4 1.push 2.pop, 3. display, 4. Exit Enter the Choice 1 Enter the item 6 1.push 2.pop, 3. display, 4. Exit Enter the Choice 1 Enter the item 7 1.push 2.pop, 3. display, 4. Exit Enter the Choice 1 Enter the item 9 1.push 2.pop, 3. display, 4. Exit Enter the Choice 1 Enter the item 8 1.push 2.pop, 3. display, 4. Exit Enter the Choice 1 Enter the item 5 Stack is full 1.push 2.pop, 3. display, 4. Exit Enter the Choice 3 Elemensts are 8 9 7 6 4 1.push 2.pop, 3. display, 4. Exit Enter the Choice ISE @ HKBKCE

18

2016-17

15CSL47

DAA Lab-1 Manual

2 The item deleted is 8 1.push 2.pop, 3. display, 4. Exit Enter the Choice 2 The item deleted is 9 1.push 2.pop, 3. display, 4. Exit Enter the Choice 3 7 6 4 1.push 2.pop, 3. display, 4. Exit Enter the Choice 4 7. A. Write a Java program to read two integers a and b. Compute a/b and print, when b isnot zero. Raise an exception when b is equal to zero. ALGORITHM: 1. Start 2. Read number a,b 3. If b!=0 4. { 5. c=a/b 6. Display c 7. } 8. Else 9. Display exception “b is equal to zer “ 10. Stop PROGRAM: importjava.io.*; importjava.util.Scanner; class div3a { publicstaticvoid main(String s[]) { System.out.println("enter two integers a and b"); Scanner in = newScanner(System.in); ISE @ HKBKCE

19

2016-17

15CSL47

DAA Lab-1 Manual

int a=in.nextInt(); int b=in.nextInt(); try { int c; c=a/b; System.out.println("the computed value of a/b is:"+c); } catch(ArithmeticException e) { System.out.println("error:"+e); } } } OUTPUT: O1 enter two integers a and b 36 The computed value of a/b is:0 O2 Enter two integers a and b 25 5 The computed value of a/b is:5 O3 Enter two integers a and b 50 error:java.lang.ArithmeticException: / by zero 7. B. Write a Java program that implements a multi-thread application that hashtree threads. First thread generates a random integer for every 1 second; second thread computes the square of the number and prints; thirdthread will print the value of cube of the number ALGORITHM: 1. Start 2. Thread 1: generate random number num 3. Thread 2: display num*num 4. Thread 3: display num*num*num 5. Stop ISE @ HKBKCE

20

2016-17

15CSL47

DAA Lab-1 Manual

PROGRAM: importjava.util.Random; class square extends Thread { publicint x; public square(int x) { this.x = x; } publicvoid run() { System.out.println("New Thread -" +" Number generated is " + x + " square of num is: " + x * x); } } class cube extends Thread { publicint x; public cube(int x) { this.x = x; } publicvoid run() { System.out.println("New Thread - " +" Number Generated is " + x + " cube of num is: " + x * x * x); } } class A extends Thread { publicvoid run() { intnum = 0; Random r = newRandom(); try { for (inti = 0; i< 5; i++) { num = r.nextInt(100); System.out.println("Main Thread - Generated Number is " + num); Thread t1 = newsquare(num); ISE @ HKBKCE

21

2016-17

15CSL47

DAA Lab-1 Manual

t1.start(); Thread t2 = newcube(num); t2.start(); Thread.sleep(1000); System.out.println("--------------------------------------"); } } catch (Exception ex) { System.out.println(ex.getMessage()); } } } publicclass multithread { publicstaticvoid main(String[] args) { A a = newA(); a.start(); } } OUTPUT: Main Thread - Generated Number is 66 New Thread - Number Generated is 66 cube of num is: 287496 New Thread - Number generated is 66 square of num is: 4356 -------------------------------------Main Thread - Generated Number is 68 New Thread - Number generated is 68 square of num is: 4624 New Thread - Number Generated is 68 cube of num is: 314432 -------------------------------------Main Thread -Generated Number is 99 New Thread - Number generated is 99 square of num is: 9801 New Thread - Number Generated is 99 cube of num is: 970299 -------------------------------------Main Thread -Generated Number is 25 New Thread - Number generated is 25 square of num is: 625 New Thread - Number Generated is 25 cube of num is: 15625 -------------------------------------Main Thread - Generated Number is 20 New Thread - Number generated is 20 square of num is: 400 ISE @ HKBKCE

22

2016-17

15CSL47

DAA Lab-1 Manual

New Thread - Number Generated is 20 cube of num is: 8000 --------------------------------------

8. Sort a given set of n integer elements using Quick Sort method and compute its time complexity. Run the program for varied values of n > 5000 and record the time taken to sort. Plot a graph of the time taken versus n on graph sheet. The elements can be read from a file or can be generated using the random number generator. Demonstrate using Java how the divide and-conquer method works along with its time complexity analysis: worst case, average case and best case. ALGORITHM: QuickSort(a,p,q) 2. // Sorts the elements a[p],……,a[q] which reside in the global array a[1 : n] into //ascending order. 3. { 4. if( p < q) then // if there are more than one element// divide P into two sub problems 5. { 6. j=Partition (a, p,q+1); 7. QuickSort (p, j 1); 8. QuickSort (j + 1, q); 9. } 10. } Partition (a, m, p) 2. 3. 4. 5.

{ v = a[m];i=m; j=p; repeat { repeati=i+1; until a[i] >=v; repeat j = j1; 6. until a[j] <=v; 7. if i< j then exchange A[i] ↔ A[j] 8. } until ( i>= j); 9. a[m]=a[j]; a[j]=v; return j; 10. } PROGRAM: importjava.util.Scanner; publicclass MyQuickSort1 { publiclong a[]; ISE @ HKBKCE

23

2016-17

15CSL47

DAA Lab-1 Manual

publicvoid quicksort1( long [] inputArr, int low, int high) { int j; if(low < high) { j=partition1(inputArr,low,high); quicksort1(inputArr,low,j-1); quicksort1(inputArr,j+1,high); } } publicint partition1(long []a,int low, int high) { inti,j; longtemp,key; key=a[low]; i=low+1; j=high; while(i<j) { while (ikey) j--; if(i<j) { temp=a[i]; a[i]=a[j]; a[j]=temp; } } temp=a[low]; a[low]=a[j]; a[j]=temp; return j; } ISE @ HKBKCE

24

2016-17

15CSL47

DAA Lab-1 Manual

publicstaticvoid main(String args[]) { MyQuickSort1 sorter = newMyQuickSort1(); Scanner in=newScanner(System.in); System.out.println("Enter the value of n"); int n=in.nextInt(); long [] input = newlong [n]; for(inti=0;i
27

2016-17

15CSL47

DAA Lab-1 Manual

System.out.println("Enter the maximum capacity: "); int W = sc.nextInt(); k.knapSack1(W, wt, val, n); } }

OUTPUT: Enter the number of items: 4 Enter the items weights: 7345 Enter the items values: 42 12 40 25 Enter the maximum capacity: 10 The maximum value that can be put in a knapsack of capacity W is: 65 9. B.Implement in Java, the 0/1 Knapsack problem using Greedy method. ALGORITHM: GreedyKnapsack(m,n) //p[1;n] and w[1:n] contains the profits and weights respectively of the n objects ordered such that //p[i]/w[i] p[i+1] // m is the knapsack size and x[1:n] is the solution vector. { 1. for i:= 1 to n do 2. x[i]=0 // initialize x 3. u:=m; 4. for i:=1 to n do; 5. { 6. if (w[i] > U ) then break; 7. x[i]:=1.0; U=U-w[i]; 8. } 9. If(in) then x[i]:=U/w[i]; } PROGRAM: importjava.util.Scanner; publicclassGreedyKnapsack { int[] profit; ISE @ HKBKCE

28

2016-17

15CSL47

DAA Lab-1 Manual

int[] weight; int[] take = newint[100]; publicvoidunitPriceOrder() { for (inti = 0; i<profit.length; i++) { for (int j = 0; j < (profit.length - i-1); j++) { double x=profit[j] / weight[j]; double y=profit[j+1] / weight[j+1]; if (x <=y) { int temp = profit[j]; profit[j] = profit[j+1]; profit[j+1] = temp; int temp1 = weight[j]; weight[j] = weight[j+1]; weight[j+1] = temp1; } } } } publicvoid Knapsack(int m) { unitPriceOrder(); int j; for (j = 0; j <profit.length; j++) { take[j] = 0; } double total = m; for (j = 0; j <profit.length; j++) { if (weight[j] <= total) { take[j] = 1; total = total - weight[j]; } } } ISE @ HKBKCE

29

2016-17

15CSL47

DAA Lab-1 Manual

publicvoid print() { System.out.println("item" + " | " + "profit" + " | " + "weight" + " | " + "Unit Price" + " |" + " Take weight"); for (int n = 0; n <profit.length; n++) { System.out.println(n + " \t" + profit[n] + " \t" + weight[n] + " + (profit[n] / weight[n]) + "\t" + take[n]); } }

\t"

publicstaticvoid main(String args[]) { GreedyKnapsack G = newGreedyKnapsack(); System.out.println("Enter the number of items: "); Scanner sc= newScanner(System.in); int n = sc.nextInt(); System.out.println("Enter the items weights: "); G.weight = newint[n]; for(inti=0; ied[j+1].wt) { Edge t=new Edge(); t=ed[j]; ed[j]=ed[j+1]; ed[j+1]=t; } } int visited[]=new int[v+1]; // array to check whether the vertex is visited or not for(i=1;i<=v;i++) visited[i]=0; System.out.println("MINIMUM SPANNING TREE :"); for(i=1;i<=e;i++) { if(i>v) break; ISE @ HKBKCE

32

2016-17

15CSL47

DAA Lab-1 Manual

else if( visited[ed[i].v1]==0 || visited[ed[i].v2]==0) { System.out.println(ed[i].v1+ "-"+ ed[i].v2); visited[ed[i].v1]=visited[ed[i].v2]=1; mincost+=ed[i].wt; } } System.out.println("MINIMUM COST = " +mincost); } } OUTPUT : Enter no.of vertices: 4 Enter no.of edges: 5 Enter the vertices and the weight of edge 1: 121 Enter the vertices and the weight of edge 2: 132 Enter the vertices and the weight of edge 3: 141 Enter the vertices and the weight of edge 4: 233 Enter the vertices and the weight of edge 5: 342 MINIMUM SPANNING TREE : 1-2 1-4 1-3 MINIMUM COST = 4 11. Find Minimum Cost Spanning Tree of a given undirected graph using prim’s algorithm ALGORITHM: Prim(E,cost,n,t) //E is the set of edges in G.cost [1:n,1:n] is the cost //adjacency matrix of an n vertex graph such that cost[i,j] is //either a positive real number or infinity if no edge of (i,j) exists ISE @ HKBKCE

33

2016-17

15CSL47

DAA Lab-1 Manual

//a minimum spanning tree is computed and stored as a set of //edges in the array t[1:n-1,1:2] . (t[i,1],t[i,2] is an edge in the minimum cost spanning //tree .The final cost is returned. 2. { 3. Let (k,l) be an edge of minimum cost in Ei 4. mincost :=cost[k,l]; 5. t[1,1]:=k;t[1,2]:=l; 6. for i:=1 to n do

//initialize near

7. if(cost[i,l]
//Update near[].

21. if((near[k]!=0) and (cost[k,near[k]]>cost[k,j])) 22. then near[k]:=j; 23. } 24. return mincost; 25. } PROGRAM: importjava.util.Scanner; publicclassprims { publicstaticvoid main(String args[]) ISE @ HKBKCE

34

2016-17

15CSL47

DAA Lab-1 Manual

{ int f[]= newint[10]; intmin,ne,mincost; int c[][]= newint[10][10]; inta,b,i,j; ne=1; mincost=0; a=0; b=0; Scanner in= newScanner(System.in); System.out.println("enter n\n"); int n=in.nextInt(); System.out.println("enter cost adj. matrix\n"); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { c[i][j]= in.nextInt(); if(c[i][j]==0) c[i][j]=999; } for(i=1;i<=n;i++) f[i]=0; f[1]=1; while(ne\t"+ a + "--" + b + "\t Min cost "+min); mincost+=min; f[b]=1; } ISE @ HKBKCE

35

2016-17

15CSL47

DAA Lab-1 Manual

c[a][b]=c[b][a]=999; } System.out.println("\nMINCOST=\n"+ mincost); } } OUTPUT: enter n 4 enter cost adj. matrix 0121 1 0 3 999 2302 1 999 2 0 edge ->

1--2

Min cost 1

edge ->

1--4

Min cost 1

edge ->

1--3

Min cost 2

MINCOST= 4 12. Write a Java Applet program which reads your name and address in different text fields and when a button named find is pressed the sum of the length of characters in name and address is displayed in another text field. Use appropriate colors, layout to make your applet look good. ALGORITHM1. Create a java file with .java extension. 2. Create a class that extends applet class and implements action listener. 3. Write an applet code that cretaes 3 text fields and button. 4. Save and compile the program using command javac filename.java. 5. Run the code using appletviewer as appletviewer filename.java PROGRAM Import java.applet.*; Import java.awt.*; Import java.awt.event.*; ISE @ HKBKCE

36

2016-17

15CSL47

DAA Lab-1 Manual

/**/ public class nameaddr extends Applet implements ActionListener { public void init() { label1 = new Label(); label2 = new Label(); label3 = new Label(); t1 = new TextField(30); t2 = new TextField(40); t3 = new TextField(45); b1 = new Button("Total"); setBackground(new Color(0, 153, 102)); label1.setText("Name"); add(label1); add(t1); label2.setText("Address"); add(label2); add(t2); b1.addActionListener(this); add(b1); label3.setText("\nTotal length"); add(label3); add(t3); } public void actionPerformed(ActionEvent ae) { int a=t1.getText().length(); a+=t2.getText().length(); t3.setText(Integer.toString(a));} Label label1;Label label2; Label label3; TextField t1; TextField t2; TextField t3; Button b1; } OUTPUT:

ISE @ HKBKCE

37

2016-17

15CSL47

ISE @ HKBKCE

DAA Lab-1 Manual

38

2016-17

15CSL47

DAA Lab-1 Manual

13. Write a Java Applet program, which provides a text area with horizontal and vertical scrollbars. Type some lines of text in the text area and use scrollbars for movements in the text area. Read a word in a text field and find whether the word is in the content of the text area or not. ALGORITHM 1. Create a java file with .java extension. 2. Create a class that extends applet class and implements action listener. 3. Write an applet code that cretaes a textarea and text fields and button. 4. Save and compile the program using command javac filename.java. 5. Run the code using appletviewer as appletviewer filename.java PROGRAM importjava.applet.*; importjava.awt.*; importjava.awt.event.*; /*<APPLET Code="AppletWithTxtFlds" Width=500 Height=200> */ public class AppletWithTxtFlds extends Applet implements ActionListener { public void init() { Label label1 = new Label("enter multiple line text: "); taDetails = new TextArea("", 3, 40); Label label2 = new Label("enter the word to be searched: "); textField1 = new TextField(40); Label label3 = new Label("the word to be searched is: "); textField2 = new TextField(40); swapEm = new Button("find"); swapEm.addActionListener(this); add(label1); add(taDetails); add(label2); add(textField1); add(swapEm); add(label3); add(textField2); } ISE @ HKBKCE

39

2016-17

15CSL47

DAA Lab-1 Manual

public void actionPerformed(ActionEvent e) { try { String str1 = taDetails.getText(); String str2=textField1.getText(); if(str1.indexOf(str2)!=-1) { textField2.setText("found"); } else { textField2.setText("not found"); } } catch(Exception x) { System.out.println("Exception caught "); } } TextArea Details; TextField textField1, textField2; Button swapEm; } OUTPUT:

ISE @ HKBKCE

40

2016-17

15CSL47

DAA Lab-1 Manual

Word found

Word not found

ISE @ HKBKCE

41

2016-17