EX.NO.
:1(a) SOLVE PROBLEMS BY USING SEQUENTIAL SEARCH
AIM:
To develop a Java application to search an element in an array using sequential
search
algorithm.
ALGORITHM:
Step 1: Start the program
Step 2: Declare an array and search element as key.
Step 3: Traverse the array until the key is found.
Step 4: If the key is found, return the index position of the array element
Step 5: If the key element is not found, return -1.
Step 6: Stop the program.
PROGRAM:
LinearSearch.java
public class LinearSearch
{
static intsearch(intarr[], int n, int s)
{
for (inti = 0; i< n; i++)
{
if (arr[i] == s)
return i;
}
return -1;
}
public static void main(String[] args)
{
int[] arr = { 3, 4, 1, 7, 5 };
int n = arr.length;
int s = 4;
int index = search(arr, n, s);
if (index == -1)
System.out.println("Element is not present in the array");
else
System.out.println("Element found at index " + index);
}
}
OUTPUT:
D:\Java\CS3381>javac LinearSearch.java
D:\Java\CS3381>java LinearSearch
Element found at index 1
RESULT:
Thus, the Java application to perform sequential search was implemented and
executed successfully.
EX.NO.:1(b) SOLVE PROBLEMS BY USING BINARY SEARCH
AIM:
To develop a Java application to search an element in an array using binary
search
algorithm.
ALGORITHM:
Step 1: Start the program.
Step 2: Declare an array and search element as key.
Step 3: Compare search key with the middle element.
Step 4: If key matches with the middle element,return the mid index.
Step 5: Otherwise, if key is greater than the mid element recur for the right half.
Step 6: Otherwise (s is smaller) recur for the left half.
Step 7: Stop the program.
PROGRAM:
BinarySearch.java
class BinarySearch
{
public static intbinarySearch(intarr[], int first, int last, int key)
{
if (last>=first)
{
int mid = (first +last)/2;
if (arr[mid] == key)
{
return mid;
}
else if (arr[mid] >key)
{
return binarySearch(arr, first, mid-1, key);
}
else
{
return binarySearch(arr, mid+1, last, key);
}
}
return -1;
}
public static void main(String args[])
{
intarr[] = {10,20,30,40,50};
int key = 30;
int last=arr.length-1;
int result = binarySearch(arr,0,last,key);
if (result == -1)
System.out.println("Element is not found!");
else
System.out.println("Element is found at index: "+result);
}
}
OUTPUT:
D:\Java\CS3381>javac BinarySearch.java
D:\Java\CS3381>java BinarySearch
Element is found at index: 2
D:\Java\CS3381>
RESULT:
Thus, the Java application to perform binary search was implemented and
executed
successfully.
EX.NO.:1(c) SOLVE PROBLEMS BY USING QUADRATIC SORTING
ALGORITHMS- SELECTION SORT
AIM:
To develop a Java application to sort an array of elements in ascending order
using selection sort.
ALGORITHM:
Step 1: Start the program.
Step 2: Select the first unsorted element as the minimum.
Step 3: For each of the unsorted elements, if the element is <minimum, set
element as new minimum.
Step 4: Swap minimum with first unsorted position.
Step 5: Repeat steps 2-4 for (n-1) elements until the list is sorted.
Step 6: Print the sorted array.
Step 7: Stop the program.
PROGRAM:
SelectionSort.java
public class SelectionSort
{
public static void selectionsort(int[] arr)
{
int n=arr.length;
for(int i=0;i<n-1;i++)
{
int min=i;
for(int j=i+1;j<n;j++)
{
if(arr[j]<arr[min])
{
min=j;
}
}
int temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
public static void main(String[] args)
{
int[] arr= {15,21,6,3,19,20};
System.out.println("Elements in the array before Sorting");
for(int i:arr)
System.out.print(i+" ");
selectionsort(arr);
System.out.println("\nElements in the array after Sorting");
for(int i:arr)
System.out.print(i+" ");
}
}
OUTPUT:
D:\Java\CS3381>javac SelectionSort.java
D:\Java\CS3381>java SelectionSort
Elements in the array before Sorting
15 21 6 3 19 20
Elements in the array after Sorting
3 6 15 19 20 21
D:\Java\CS3381>
RESULT:
Thus, the Java application to sort an array of N elements using selection sort was
implemented and executed successfully.
EX.NO.:1(d) SOLVE PROBLEMS BY USING QUADRATIC SORTING
ALGORITHMS-INSERTION SORT
AIM:
To develop a Java application to sort an array of elements in ascending order
using insertion sort.
ALGORITHM:
Step 1: Start the program.
Step 2: Define an array num to store N numbers for insertion sort.
Step 3: Run an outer loop i from 1 to N to repeat the process.
Step 4: Store the number num[i] to be inserted at proper place in variable x.
Step 5: Run a while loop j inside the body of the outer loop i from i-1 to 0.
Step 6: Check if the value of x is less than value of num[j] then shift the number
num[j] towards right else break the inner loop j.
Step 7: Outside the body of inner loop j insert the value of x at num[j+1] position.
Step 8: Print the sorted array.
Step 9: Stop the program.
PROGRAM:
InsertionSort.java
public class InsertionSort
{
public static void main(String args[])
{
int num[]= {12,9,37,86,2,17,5};
int i,j,x;
System.out.println("Array before Insertion Sort");
for(i=0; i<num.length; i++)
{
System.out.print(num[i]+" ");
}
for(i=1; i<num.length; i++)
{
x=num[i];
j=i-1;
while(j>=0)
{
if(x<num[j])
{
num[j+1]=num[j];
}
else
{
break;
}
j=j-1;
}
num[j+1]=x;
}
System.out.print("\n\nArray after Insertion Sort\n");
for(i=0; i<num.length; i++)
{
System.out.print(num[i]+" ");
}
}
}
OUTPUT:
D:\Java\CS3381>javac InsertionSort.java
D:\Java\CS3381>java InsertionSort
Array before Insertion Sort
12 9 37 86 2 17 5
Array after Insertion Sort
2 5 9 12 17 37 86
D:\Java\CS3381>
RESULT:
Thus, the Java application to sort an array of N elements using insertion sort was
implemented and executed successfully.
EX.NO.: 2(a) DEVELOP STACK DATA STRUCTURES USING CLASSES AND
OBJECTS
AIM:
To develop a Java program to implement stack data structure using classes and
objects.
ALGORITHM:
Step 1: Start the program.
Step 2: Create a class named Stack and declare the instance variables st[], top,
maxsize as private.
Step3: Use constructor to allocate memory space for the array and initialize top
as -1.
Step 4: Define methods such as isFull(), isEmpty(), push(), pop() and printStack();
Step 5: Push Operation
Step 5.1: Check whetherstack has some space or stack is full.
Step 5.2: If the stack has no space then display “overflow” and exit.
Step 5.3: If the stack has space then increase top by 1 to point next empty space.
Step 5.4: Add element to the new stack location, where top is pointing.
Step 5.5: Push operation performed successfully.
Step 6: Pop operation
Step 6.1: Check whether stack has some element or stack is empty.
Step 6.2: If the stack has no element means it is empty then display “underflow”
Step 6.3: If the stack has some element, accesses the data element at which top is
pointing.
Step 6.4: Decrease the value of top by 1.
Step 6.5: Pop operation performed successfully.
Step 7: PrintStack operation
Step 7.1: Check whether stack has some element or stack is empty.
Step 7.2: If the stack has no element means it is empty then display “underflow”.
Step 7.3: If the stack has some element, traverse the array from top to bottom and
display the elements.
Step 8: Define the main() method
Step 9: Create object of Stack class.
Step 10: Display the menu and get the user choice and invoke appropriate method.
Step 11: Stop the program.
PROGRAM:
Stack.java
import java.util.Scanner;
public class Stack
{
private int maxsize, top;
private int[] st;
public Stack(int size)
{
maxsize = size;
st = new int[maxsize];
top = -1;
}
boolean isEmpty()
{
return top==-1;
}
boolean isFull()
{
return top==maxsize-1;
}
public void push(int element)
{
if(isFull())
System.out.println("Overflow");
else
st[++top] = element;
}
public int pop()
{
if(isEmpty())
{
System.out.println("UnderFlow");
return (-1);
}
return (st[top--]);
}
public void printStack()
{
System.out.println("Stack Elements:");
for (int i = top; i>=0; i--)
System.out.println(st[i]);
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter stack size");
int size=sc.nextInt();
Stack obj = new Stack(size);
while (true)
{
System.out.println("\nSTACK\n*****\n1.PUSH\n2.POP\n3.Display\n4.EXIT\n
Enter your choice");
int ch = sc.nextInt();
switch (ch)
{
case 1:
System.out.println("Enter Element");
int n = sc.nextInt();
obj.push(n);
break;
case 2:
System.out.printf("Poped element is %d", obj.pop());
break;
case 3:
obj.printStack();
break;
case 4:
System.exit(0);
default:
System.out.println("Wrong option");
}
}
}
}
OUTPUT:
D:\Java\CS3381>java Stack
Enter stack size
5
STACK
*****
1.PUSH
2.POP
4931_GRACE College of Engineering, Thoothukudi
CS3381_OOP LAB
12
3.Display
4.EXIT
Enter your choice
1
Enter Element
12
STACK
*****
1.PUSH
2.POP
3.Display
4.EXIT
Enter your choice
1
Enter Element
34
STACK
*****
1.PUSH
2.POP
3.Display
4.EXIT
Enter your choice
1
Enter Element
56
STACK
*****
1.PUSH
2.POP
3.Display
4.EXIT
Enter your choice
1
Enter Element
78
STACK
*****
1.PUSH
2.POP
3.Display
4.EXIT
Enter your choice
3
Stack Elements:
78
56
34
12
STACK
*****
1.PUSH
2.POP
3.Display
4.EXIT
Enter your choice
2
Poped element is 78
STACK
*****
1.PUSH
2.POP
3.Display
4.EXIT
Enter your choice
4
D:\Java\CS3381>
RESULT:
Thus, the Java program to implement stack data structure using classes and
objects has
developed and executed successfully.
EX.NO.: 2(b) DEVELOP QUEUE DATA STRUCTURES USING CLASSES AND
OBJECTS
AIM:
To develop a Java program to implement queue data structure using classes and
objects.
ALGORITHM:
Step 1: Start the program.
Step 2: Create a class named Queue and declare the instance variables items[],
front, rear, maxsize as private.
Step3: Use constructor to allocate memory space for the array and initialize front
as -1 and rear as -1.
Step 4: Define methods such as isFull(), isEmpty(), enQueue(), deQueue() and
display();
Step 5: Enqueue Operation
Step 5.1: Check whether queue has some space or queue is full.
Step 5.2: If the queue has no space then display “overflow” and exit.
Step 5.3: If the queue has space then increase rear by 1 to point next empty space.
Step 5.4: Add element to the new location, where rear is pointing.
Step 5.5: Enqueue operation performed successfully.
Step 6: Dequeue operation
Step 6.1: Check whether queue has some element or queue is empty.
Step 6.2: If the queue has no element means it is empty then display “underflow”
Step 6.3: If the queue has some element, accesses the data element at which front is
pointing.
Step 6.4: Increment the value of front by 1.
Step 6.5: Dequeue operation performed successfully.
Step 7: Display operation
Step 7.1: Check whether queue has some element or queue is empty.
Step 7.2: If the stack has no element means it is empty then display “underflow”.
Step 7.3: If the stack has some element, traverse the array from front to rear and
display the elements.
Step 8: Define the main() method
Step 9: Create object of Queue class.
Step 10: Display the menu and get the user choice and invoke appropriate method.
Step 11: Stop the program.
PROGRAM:
Queue.java
import java.util.Scanner;
public class Queue
{
private int items[];
private int maxsize, front, rear;
Queue(int size)
{
maxsize=size;
items = new int[size];
front = -1;
rear = -1;
}
boolean isFull()
{
if (front == 0 && rear ==maxsize-1)
{
return true;
}
return false;
}
boolean isEmpty()
{
if (front == -1)
return true;
else
return false;
}
void enQueue(int element)
{
if (isFull())
{
System.out.println("Queue is full");
}
else
{
if (front == -1)
front = 0;
rear++;
items[rear] = element;
System.out.println("Inserted " + element);
}
}
int deQueue()
{
int element;
if (isEmpty())
{
System.out.println("Queue is empty");
return (-1);
}
else
{
element = items[front];
if (front >= rear)
{
front = -1;
rear = -1;
}
else
{
front++;
}
return (element);
}
}
void display()
{
int i;
if (isEmpty())
{
System.out.println("Empty Queue");
}
else
{
System.out.println("\nFront index-> " + front);
System.out.println("Items -> ");
for (i = front; i<= rear; i++)
System.out.print(items[i] + " ");
System.out.println("\nRear index-> " + rear);
}
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter queue size");
int size=sc.nextInt();
Queue obj = new Queue(size);
while (true)
{
System.out.println("\nQUEUE\n**********\n1.ENQUEUE\n2.DEQUEUE\n3.DI
SPLAY\n4.EXIT\n**********\nEnter your choice");
int ch = sc.nextInt();
switch (ch)
{
case 1:
System.out.println("Enter Element");
int n = sc.nextInt();
obj.enQueue(n);
break;
case 2:
System.out.printf("Dequeued element is %d",
obj.deQueue());
break;
case 3:
obj.display();
break;
case 4:
System.exit(0);
default:
System.out.println("Wrong option");
}
}
}
}
OUTPUT:
D:\Java\CS3381>javac Queue.java
D:\Java\CS3381>java Queue
Enter queue size
5
QUEUE
*****
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
Enter your choice
1
Enter Element
12
Inserted 12
QUEUE
*****
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
Enter your choice
1
Enter Element
34
Inserted 34
QUEUE
*****
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
Enter your choice
1
Enter Element
56
Inserted 56
QUEUE
*****
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
Enter your choice
1
Enter Element
78
Inserted 78
QUEUE
*****
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
Enter your choice
3
Front index-> 0
Items ->
12 34 56 78
Rear index-> 3
QUEUE
*****
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
Enter your choice
2
Poped element is 12
QUEUE
*****
1.ENQUEUE
2.DEQUEUE
3.DISPLAY
4.EXIT
Enter your choice
4
D:\Java\CS3381>
RESULT:
Thus, the Java program to implement queue data structure using classes and
objects has
developed and executed successfully.
