CODING :

import java.util.*;

public class Quicksort

public static void main(String []args)

int[]arr={5,2,8,3,1,6,4};

int n=arr.length;

long start=System.currentTimeMillis();

quicksort(arr,0,n-1);

long end=System.currentTimeMillis();

System.out.println("Sorted Array:"+Arrays.toString(arr));

System.out.println("Time taken:"+(end-start)+"milliseconds");

public 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 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++;

int temp=arr[i];

arr[i]=arr[j];

arr[j]=temp;

int temp=arr[i+1];

arr[i+1]=arr[high];

arr[high]=temp;

return i+1;

OUTPUT :

Sorted Array:[1, 2, 3, 4, 5, 6, 8]

Time taken:0milliseconds
CODING :

import java.util.*;

public class Mergesort

public static void main(String args[])

int[] arr = {5, 2, 8, 3, 1, 6, 4};

int n = arr.length;

long start = System.currentTimeMillis();

mergesort(arr, 0, n - 1);

long end = System.currentTimeMillis();

System.out.println("***********************");

System.out.println("Sorted array: " + Arrays.toString(arr));

System.out.println("Time taken: " + (end - start) + " milliseconds");

System.out.println("***********************");

public static void mergesort(int[] arr, int low, int high)

if (low < high)

int mid = (low + high) / 2;

mergesort(arr, low, mid);

mergesort(arr, mid + 1, high);

merge(arr, low, mid, high);

public static void merge(int[] arr, int low, int mid, int high)

int[] left = Arrays.copyOfRange(arr, low, mid + 1);

int[] right = Arrays.copyOfRange(arr, mid + 1, high + 1);

int i = 0, j = 0, k = low;

while (i<left.length&& j <right.length)

if (left[i] <= right[j])

arr[k] = left[i];

i++;

else

arr[k] = right[j]; // Fixed the typo here (was 'rigth')

j++;

k++;

while (i<left.length)

arr[k] = left[i];

i++;

k++;

while (j <right.length)

arr[k] = right[j];

j++;

k++;

}}}
OUTPUT :

***********************

Sorted array: [1, 2, 3, 4, 5, 6, 8]

Time taken: 0 milliseconds

***********************
CODING :

import java.util.*;

public class Knapsack

public static int knapsack(int[]v,int[]w,int c)

int n=v.length;

int[][] dp=new int[n+1][c+1];

for(int i=1;i&amp;lt;=n;i++)

for(int j=1;j&amp;lt;=c;j++)

if(w[i-1]&amp;lt;=j)

dp[i][j]=Math.max(dp[i-1][j],v[i-1]+dp[i-1][j-w[i-1]]);

else

dp[i][j]=dp[i-1][j];

return dp[n][c];

public static void main(String[] args)

int[]v={60,100,120};

int[]w={10,20,30};

int c=50;
int maxValue=knapsack(v,w,c);

System.out.println(&amp;quot;Maximum value in KnapSack:&amp;quot;+maxValue);

OUTPUT:

Maximum value in KnapSack:220

CODING :
import java.util.*;

class Graph {

int V;

List<List<Edge>> adj;

int[] dist;

boolean[] visited;

Graph(int V) {

this.V = V;

adj = new ArrayList<>(V);

for (int i = 0; i < V; i++)

adj.add(new ArrayList<>());

dist = new int[V];

visited = new boolean[V];

Arrays.fill(dist, Integer.MAX_VALUE);

void addEdge(int u, int v, int weight) {

adj.get(u).add(new Edge(v, weight));

void dijkstra(int src) {

dist[src] = 0;

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {

if (dist[a] == dist[b]) {

return a - b;

} else {

return Integer.compare(dist[a], dist[b]);

});

pq.offer(src);

while (!pq.isEmpty()) {
int u = pq.poll();

if (visited[u])

continue;

visited[u] = true;

for (Edge e : adj.get(u)) {

int v = e.v;

int weight = e.weight;

if (!visited[v] && (dist[v] == Integer.MAX_VALUE || dist[u] + weight <

dist[v])) {

dist[v] = dist[u] + weight;

pq.offer(v);

System.out.println("\nShortest paths from node " + src + ":");

for (int i = 0; i < V; i++) {

System.out.println("Node " + i + ": " + dist[i]);

System.out.println("Shortest path from node " + src + " to node 4: " +

dist[4]);

class Edge {

int v, weight;

Edge(int v, int weight) {

this.v = v;

this.weight = weight;

}
}

public class Main{

public static void main(String[] args) {

Graph g = new Graph(5);

g.addEdge(0, 1, 2);

g.addEdge(0, 2, 4);

g.addEdge(1, 2, 1);

g.addEdge(1, 3, 7);

g.addEdge(2, 4, 3);

g.addEdge(3, 4, 2);

g.dijkstra(0);

OUTPUT :

Shortest paths from node 0:

Node 0: 0

Node 1: 2

Node 2: 3

Node 3: 9

Node 4: 6

Shortest path from node 0 to node 4: 6

CODING :

class Node
{

int value;

Node left,right;

public Node(int value)

this.value=value;

left=right=null;

public class BinaryTreeTraversal

void inOrder(Node node)

if(node==null)

return;

inOrder(node.left);

System.out.print(node.value+"");

inOrder(node.right);

void preOrder(Node node)

if(node==null)

return;

preOrder(node.left);

preOrder(node.right);

System.out.print(node.value+"");

void postOrder(Node node)

{
if(node==null)

return;

postOrder(node.left);

postOrder(node.right);

System.out.print(node.value+"");

public static void main(String[] args)

BinaryTreeTraversal tree=new BinaryTreeTraversal();

Node root=new Node(1);

root.left=new Node(2);

root.right=new Node(3);

root.left.left=new Node(4);

root.left.right=new Node(5);

System.out.println("In-order traversal:");

tree.inOrder(root);

System.out.println("\n pre-order traversal:");

tree.preOrder(root);

System.out.println("\n post-order traversal:");

tree.postOrder(root);

OUTPUT :
In-order traversal:

42513

pre-order traversal:

45231

post-order traversal:

45231

CODING :
import java.io.*;

import java.util.*;

class Edge

int destination;

int weight;

public Edge(int destination, int weight)

this.destination = destination;

this.weight = weight;

public class PrimMST

public static void primMST(List<List<Edge>> graph)

int vertices = graph.size();

int[] minWeight = new int[vertices];

boolean[] inMST = new boolean[vertices];

int[] parent = new int[vertices];

Arrays.fill(minWeight, Integer.MAX_VALUE);

minWeight[0] = 0;

parent[0] = -1;

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

pq.offer(new int[]{0, 0});

while (!pq.isEmpty())

int[] nodeInfo = pq.poll();

int node = nodeInfo[0];

if (inMST[node])

continue;

inMST[node] = true;

for (Edge edge : graph.get(node))

if (!inMST[edge.destination] && edge.weight <

minWeight[edge.destination])

minWeight[edge.destination] = edge.weight;

parent[edge.destination] = node;

pq.offer(new int[]{edge.destination, minWeight[edge.destination]});

System.out.println("Edge \tWeight");

for (int i = 1; i < vertices; i++)

System.out.println(parent[i] + " -- " + i + "\t" + minWeight[i]);

public static void main(String[] args)

int vertices = 5;

List<List<Edge>> graph = new ArrayList<>();

for (int i = 0; i < vertices; i++)

graph.add(new ArrayList<>());

graph.get(0).add(new Edge(1, 2));

graph.get(0).add(new Edge(3, 6));

graph.get(1).add(new Edge(0, 2));

graph.get(1).add(new Edge(2, 3));

graph.get(1).add(new Edge(3, 8));

graph.get(1).add(new Edge(4, 5));

graph.get(2).add(new Edge(1, 3));

graph.get(2).add(new Edge(4, 7));

graph.get(3).add(new Edge(0, 6));

graph.get(3).add(new Edge(1, 8));

graph.get(4).add(new Edge(1, 5));

graph.get(4).add(new Edge(2, 7));

primMST(graph);

OUTPUT :

Edge Weight

0 -- 1 2

1 -- 2 3

0 -- 3 6

1 -- 4 5
CODING :

public class NQueens

private static boolean isSafe(int[][] board, int row, int col, int n)

for (int i = 0; i < col; i++)

if (board[row][i] == 1)

return false;

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)

if (board[i][j] == 1)

return false;

for (int i = row, j = col; i < n && j >= 0; i++, j--)

if (board[i][j] == 1)

return false;

return true;

private static boolean solveNQueens(int[][] board, int col, int n)

{

if (col >= n)

return true;

for (int i = 0; i < n; i++)

if (isSafe(board, i, col, n))

board[i][col] = 1;

if (solveNQueens(board, col + 1, n))

return true;

board[i][col] = 0;

return false;

private static void printSolution(int[][] board, int n)

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

System.out.print(board[i][j] + " ");

System.out.println();

}
}

public static void main(String[] args)

int n = 8;

int[][] board = new int[n][n];

if (solveNQueens(board, 0, n))

printSolution(board, n);

else

System.out.println("Solution does not exist.");

OUTPUT :

10000000

00000010

00001000

00000001

01000000

00010000

00000100

00100000