Assignment 1
AIM:
Write a program in Java to sort data using Quick Sort.
SOURCE CODE:
import [Link];
public class QuickSort {
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
[Link]("Enter number of elements: ");
int n = [Link]();
int[] arr = new int[n];
[Link]("Enter " + n + " elements: ");
for (int i = 0; i < n; i++) arr[i] = [Link]();
[Link]("Original array: ");
for (int x : arr) [Link](x + " ");
quickSort(arr, 0, n - 1);
[Link]("\nSorted array: ");
for (int x : arr) [Link](x + " ");
[Link]();
}
}
Assignment 2
AIM:
Write a program in Java to implement a Doubly Linked List with insertion of a node in the middle.
SOURCE CODE:
public class DoublyLinkedList {
static class Node {
int data;
Node next, prev;
Node(int d) { data = d; }
}
static Node insertMiddle(Node head, int data) {
Node newNode = new Node(data);
if (head == null) return newNode;
Node slow = head, fast = head;
while ([Link] != null && [Link] != null) {
slow = [Link];
fast = [Link];
}
[Link] = [Link];
[Link] = slow;
if ([Link] != null) [Link] = newNode;
[Link] = newNode;
return head;
}
static void display(Node head) {
while (head != null) {
[Link]([Link] + " ");
head = [Link];
}
[Link]();
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
Node head = null, tail = null;
for (int val : arr) {
Node n = new Node(val);
if (head == null) { head = tail = n; }
else { [Link] = n; [Link] = tail; tail = n; }
}
[Link]("Before: "); display(head);
head = insertMiddle(head, 99);
[Link]("After: "); display(head);
}
}
Assignment 3
AIM:
Write a program in Java to create a heap with n elements and perform Heap Sort.
SOURCE CODE:
public class HeapSort {
static void heapify(int[] arr, int n, int i) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
heapify(arr, n, largest);
}
}
static void heapSort(int[] arr) {
int n = [Link];
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
heapify(arr, i, 0);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
[Link]("Original: ");
for (int x : arr) [Link](x + " ");
heapSort(arr);
[Link]("\nSorted: ");
for (int x : arr) [Link](x + " ");
[Link]();
}
}
Assignment 4
AIM:
Implement Kruskal's Algorithm to find the Minimum Spanning Tree (MST) in a graph with 5 nodes.
SOURCE CODE:
import [Link];
import [Link];
public class Kruskal {
static int[] parent = new int[5];
static int find(int i) {
return parent[i] == -1 ? i : find(parent[i]);
}
public static void main(String[] args) {
int[][] edges = {{0,1,2},{0,3,6},{1,2,3},{1,3,8},{1,4,5},{2,4,7},{3,4,9}};
[Link](edges, [Link](e -> e[2]));
[Link](parent, -1);
int total = 0, cnt = 0;
[Link]("MST Edges:");
for (int[] e : edges) {
if (cnt == 4) break;
int x = find(e[0]), y = find(e[1]);
if (x != y) {
[Link](e[0] + " - " + e[1] + " : " + e[2]);
parent[x] = y;
total += e[2];
cnt++;
}
}
[Link]("Total weight: " + total);
}
}
Assignment 5
AIM:
Implement Prim's Algorithm to find the Minimum Spanning Tree (MST) in a graph with 5 nodes.
SOURCE CODE:
public class Prims {
static final int V = 5;
static int minKey(int[] key, boolean[] mst) {
int min = Integer.MAX_VALUE, idx = -1;
for (int i = 0; i < V; i++)
if (!mst[i] && key[i] < min) { min = key[i]; idx = i; }
return idx;
}
public static void main(String[] args) {
int[][] g = {{0,2,0,6,0},{2,0,3,8,5},{0,3,0,0,7},{6,8,0,0,9},{0,5,7,9,0}};
int[] parent = new int[V], key = new int[V];
boolean[] mst = new boolean[V];
[Link](key, Integer.MAX_VALUE);
key[0] = 0; parent[0] = -1;
for (int cnt = 0; cnt < V - 1; cnt++) {
int u = minKey(key, mst);
mst[u] = true;
for (int v = 0; v < V; v++)
if (g[u][v] != 0 && !mst[v] && g[u][v] < key[v]) {
parent[v] = u; key[v] = g[u][v];
}
}
int total = 0;
[Link]("MST Edges:");
for (int i = 1; i < V; i++) {
[Link](parent[i] + " - " + i + " : " + g[i][parent[i]]);
total += g[i][parent[i]];
}
[Link]("Total weight: " + total);
}
}