Untitled

GCR

import java.util.Arrays;

public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;

// Move elements of arr[0..i-1] that are greater than key
// one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 0};
System.out.println("Original array: " + Arrays.toString(arr));
insertionSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}

import java.util.Arrays;

public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no elements were swapped, the array is already sorted
if (!swapped) break;
}
}

public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Original array: " + Arrays.toString(arr));
bubbleSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}

import java.util.Arrays;

public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}

public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("Original array: " + Arrays.toString(arr));
selectionSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}

class LinearQueue<T> {
private T[] queue;
private int front, rear, size, capacity;

@SuppressWarnings("unchecked")
public LinearQueue(int capacity) {
this.capacity = capacity;
queue = (T[]) new Object[capacity]; // Creating a generic array
front = 0;
rear = -1;
size = 0;
}

public boolean isEmpty() {
return size == 0;
}

public boolean isFull() {
return size == capacity;
}

public void enqueue(T data) {
if (isFull()) {
System.out.println("Queue is full. Cannot enqueue " + data);
return;
}
rear++;
queue[rear] = data;
size++;
}

public T dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue.");
return null;
}
T removedElement = queue[front];
for (int i = 0; i < rear; i++) {
queue[i] = queue[i + 1]; // Shift elements to the left
}
rear--;
size--;
return removedElement;
}

public T peek() {
if (isEmpty()) {
System.out.println("Queue is empty. No front element.");
return null;
}
return queue[front];
}

public int getSize() {
return size;
}

public void display() {
if (isEmpty()) {
System.out.println("Queue is empty.");
return;
}
System.out.print("Queue elements: ");
for (int i = 0; i <= rear; i++) {
System.out.print(queue[i] + " ");
}
System.out.println();
}

public static void main(String[] args) {
LinearQueue<Integer> queue = new LinearQueue<>(5);

queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
queue.enqueue(50);
queue.display();

queue.dequeue();
queue.display();

System.out.println("Front element: " + queue.peek());
System.out.println("Queue size: " + queue.getSize());
}
}

class Stack {
private int size;
private int[] stack;
private int top;

public Stack(int size) {
this.size = size;
this.stack = new int[size];
this.top = -1;
}

public boolean isEmpty() {
return top == -1;
}

public boolean isFull() {
return top == size - 1;
}

public void push(int item) {
if (isFull()) {
System.out.println("Stack Overflow! Cannot push " + item);
} else {
stack[++top] = item;
System.out.println("Pushed " + item + " into the stack");
}
}

public int pop() {
if (isEmpty()) {
System.out.println("Stack Underflow! Cannot pop");
return -1;
} else {
return stack[top--];
}
}

public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty!");
return -1;
} else {
return stack[top];
}
}

public void display() {
if (isEmpty()) {
System.out.println("Stack is empty!");
} else {
System.out.print("Stack elements: ");
for (int i = 0; i <= top; i++) {
System.out.print(stack[i] + " ");
}
System.out.println();
}
}

public static void main(String[] args) {
Stack stack = new Stack(5);
stack.push(10);
stack.push(20);
stack.push(30);
stack.display();
System.out.println("Popped element: " + stack.pop());
stack.display();
System.out.println("Top element: " + stack.peek());
}
}

import java.util.ArrayList;
import java.util.List;

public class SubsetBacktracking {
public static void findSubsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) {
// Add the current subset to the result list
result.add(new ArrayList<>(current));

// Explore further elements
for (int i = index; i < nums.length; i++) {
// Include the current element
current.add(nums[i]);

// Recurse for the next element
findSubsets(nums, i + 1, current, result);

// BACKTRACK: Remove the last element before moving to the next iteration
current.remove(current.size() - 1);
}
}

public static List<List<Integer>> getAllSubsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
findSubsets(nums, 0, new ArrayList<>(), result);
return result;
}

public static void main(String[] args) {
int[] nums = {1, 2, 3}; // Change the set elements here
List<List<Integer>> subsets = getAllSubsets(nums);

System.out.println("All subsets:");
for (List<Integer> subset : subsets) {
System.out.println(subset);
}
}
}

// GPT

// Practice Questions 

// Q2

public class LibrarySearch {
    public static int binarySearch(int[] arr, int key) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == key) {
                return mid; // Book ID found
            } else if (arr[mid] < key) {
                left = mid + 1; // Search right half
            } else {
                right = mid - 1; // Search left half
            }
        }
        
        return -1; // Book ID not found
    }
}

public class Main {
    public static void main(String[] args) {
        int[] bookIDs = {1002, 1015, 1030, 1055, 1070};
        int searchID = 1055;

        int result = LibrarySearch.binarySearch(bookIDs, searchID);

        if (result != -1) {
            System.out.println("Book ID found at index " + result);
        } else {
            System.out.println("Book ID not found");
        }
    }
}

// Q3
public class FibonacciSeries {
    public static void printFibonacciSeries(int n) {
        if (n <= 0) {
            System.out.println("Invalid input. Please enter a positive integer.");
            return;
        }

        int first = 0, second = 1;

        System.out.print("Fibonacci Series up to " + n + " terms: ");
        for (int i = 0; i < n; i++) {
            System.out.print(first + " ");
            int next = first + second;
            first = second;
            second = next;
        }
        System.out.println(); // Move to new line after printing series
    }
}

public class Main {
    public static void main(String[] args) {
        int terms = 15; // Number of Fibonacci terms
        FibonacciSeries.printFibonacciSeries(terms);
    }
}

// LinearQueue
public class LinearQueue {
    private int front, rear, size;
    private int capacity;
    private int[] queue;

    public LinearQueue(int capacity) {
        this.capacity = capacity;
        queue = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    // Enqueue operation (Add ticket)
    public void enqueue(int ticket) {
        if (size == capacity) {
            System.out.println("Queue is full. Cannot add more tickets.");
            return;
        }
        rear++;
        queue[rear] = ticket;
        size++;
    }

    // Dequeue operation (Process ticket)
    public void dequeue() {
        if (size == 0) {
            System.out.println("Queue is empty. No tickets to process.");
            return;
        }
        front++;
        size--;
    }

    // Display queue state
    public void displayQueue() {
        if (size == 0) {
            System.out.println("Queue is empty.");
            return;
        }
        System.out.print("Tickets in queue: ");
        for (int i = front; i <= rear; i++) {
            System.out.print(queue[i] + " ");
        }
        System.out.println();
    }

    // Check if queue is full
    public boolean isFull() {
        return size == capacity;
    }

    // Check if queue is empty
    public boolean isEmpty() {
        return size == 0;
    }
}
public class Main {
    public static void main(String[] args) {
        LinearQueue queue = new LinearQueue(5);

        // Add ticket numbers 201, 202, 203
        queue.enqueue(201);
        queue.enqueue(202);
        queue.enqueue(203);

        // Process (remove) one ticket
        queue.dequeue();

        // Add ticket number 204
        queue.enqueue(204);

        // Display the current state of the queue
        queue.displayQueue();

        // Show whether the queue is full or empty
        System.out.println("Queue Full: " + queue.isFull() + ", Queue Empty: " + queue.isEmpty());
    }
}
// Q5
public class StudentSearch {
    public static int linearSearch(int[] arr, int key) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {
                return i; // Roll number found
            }
        }
        return -1; // Roll number not found
    }
}

public class Main {
    public static void main(String[] args) {
        int[] rollNumbers = {102, 105, 110, 115};
        int searchRoll = 110;

        int result = StudentSearch.linearSearch(rollNumbers, searchRoll);

        if (result != -1) {
            System.out.println("Roll number " + searchRoll + " is marked present.");
        } else {
            System.out.println("Roll number " + searchRoll + " is not found.");
        }
    }
}