DSA_LAB

Using suitable Abstract Data Types (ADTs) perform the following tasks:
(i) Checking if the parentheses are well formed i.e. [ ( ) ( ) ] is well-formed, but [ ( ( ] ) ) is not.
(ii) Reverse the contents of a List using List ADT
(iii) Use dictionary ADT to count the number of occurrences of each word in an online book.

i)
import java.util.Stack;

public class WellFormedParentheses {
    public static boolean isWellFormed(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
                stack.pop();
            } else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
                stack.pop();
            } else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String exp1 = "[()()]";
        String exp2 = "[(()])";
        System.out.println("Expression 1 well-formed: " + isWellFormed(exp1));
        System.out.println("Expression 2 well-formed: " + isWellFormed(exp2));
    }
}

ii)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ReverseList {
    public static void reverseList(List<Integer> list) {
        int left = 0, right = list.size() - 1;
        while (left < right) {
            int temp = list.get(left);
            list.set(left, list.get(right));
            list.set(right, temp);
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
        System.out.println("Original List: " + list);
        reverseList(list);
        System.out.println("Reversed List: " + list);
    }
}

iii)
import java.util.HashMap;
import java.util.Map;

public class WordCount {
    public static Map<String, Integer> countWordOccurrences(String text) {
        Map<String, Integer> wordCount = new HashMap<>();
        String[] words = text.toLowerCase().replaceAll("[^a-z ]", "").split("\\s+");

        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }
        return wordCount;
    }

    public static void main(String[] args) {
        String text = "This is a sample book text. This book contains sample text.";
        Map<String, Integer> wordCount = countWordOccurrences(text);
        System.out.println("Word occurrences: " + wordCount);
    }
}

2) Hot potato game

import java.util.LinkedList;
import java.util.Queue;

public class HotPotato {
    public static String hotPotato(String[] names, int num) {
        Queue<String> queue = new LinkedList<>();

        // Add all names to the queue
        for (String name : names) {
            queue.offer(name);
        }

        // Simulation of passing the potato
        while (queue.size() > 1) {
            // Pass the potato num times
            for (int i = 0; i < num - 1; i++) {
                queue.offer(queue.poll()); // Move front player to the back
            }
            System.out.println("Eliminated: " + queue.poll()); // Remove the player at the front
        }

        return queue.peek(); // Last remaining player
    }

    public static void main(String[] args) {
        String[] players = {"Bill", "David", "Susan", "Jane", "Kent", "Brad"};
        int num = 7;

        String winner = hotPotato(players, num);
        System.out.println("Winner: " + winner);
    }
}

3. Library

import java.util.HashMap;

class Book {
    String isbn;
    String title;
    String author;
    boolean isAvailable;

    public Book(String isbn, String title, String author) {
        this.isbn = isbn;
        this.title = title;
        this.author = author;
        this.isAvailable = true; // Initially available
    }

    @Override
    public String toString() {
        return "ISBN: " + isbn + ", Title: " + title + ", Author: " + author + ", Available: " + isAvailable;
    }
}

public class LibrarySystem {
    private HashMap<String, Book> books; // Store books by ISBN
    private HashMap<String, Book> borrowedBooks; // Store borrowed books separately

    public LibrarySystem() {
        books = new HashMap<>();
        borrowedBooks = new HashMap<>();
    }

    // Add a book to the library
    public void addBook(String isbn, String title, String author) {
        books.put(isbn, new Book(isbn, title, author));
    }

    // Check if a book is available
    public boolean isBookAvailable(String isbn) {
        return books.containsKey(isbn) && books.get(isbn).isAvailable;
    }

    // Borrow a book
    public boolean borrowBook(String isbn) {
        if (isBookAvailable(isbn)) {
            Book book = books.get(isbn);
            book.isAvailable = false;
            borrowedBooks.put(isbn, book);
            return true;
        }
        return false;
    }

    // Return a book
    public boolean returnBook(String isbn) {
        if (borrowedBooks.containsKey(isbn)) {
            Book book = borrowedBooks.remove(isbn);
            book.isAvailable = true;
            books.put(isbn, book);
            return true;
        }
        return false;
    }

    // Lookup book by ISBN
    public Book getBook(String isbn) {
        return books.getOrDefault(isbn, null);
    }

    public static void main(String[] args) {
        LibrarySystem library = new LibrarySystem();

        // Adding books
        library.addBook("12345", "Data Structures", "Mark Allen");
        library.addBook("67890", "Algorithms", "Thomas Cormen");

        // Lookup book
        System.out.println("Lookup Book: " + library.getBook("12345"));

        // Check availability
        System.out.println("Is Book Available: " + library.isBookAvailable("12345"));

        // Borrow a book
        System.out.println("Borrowing Book: " + library.borrowBook("12345"));
        System.out.println("Is Book Available After Borrowing: " + library.isBookAvailable("12345"));

        // Return a book
        System.out.println("Returning Book: " + library.returnBook("12345"));
        System.out.println("Is Book Available After Return: " + library.isBookAvailable("12345"));
    }
}

4. Quick SOrt

1. Last element as pivot

import java.util.Arrays;

public class SimpleQuickSort {

    // Quick Sort using last element as pivot
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // Last element as pivot
        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;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        System.out.println("Before Sorting: " + Arrays.toString(arr));

        quickSort(arr, 0, arr.length - 1);

        System.out.println("After Sorting: " + Arrays.toString(arr));
    }
}

2. Random pivot

import java.util.Arrays;
import java.util.Random;

public class RandomPivotQuickSort {

    // Quick Sort using a random pivot
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = randomPartition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int randomPartition(int[] arr, int low, int high) {
        Random rand = new Random();
        int randomIndex = low + rand.nextInt(high - low + 1);
        swap(arr, randomIndex, high); // Swap random element with last element
        return partition(arr, low, high);
    }

    private 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;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        System.out.println("Before Sorting: " + Arrays.toString(arr));

        quickSort(arr, 0, arr.length - 1);

        System.out.println("After Sorting: " + Arrays.toString(arr));
    }
}

5. Max Flow
/******************************************************************************

                            Online Java Compiler.
                Code, Compile, Run and Debug java program online.
Write your code in this editor and press "Run" button to execute it.

*******************************************************************************/
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static final int V = 8;

    boolean bfs(int rGraph[][], int s, int t, int parent[]) {
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; ++i)
            visited[i] = false;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = true;
        parent[s] = -1;

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

            for (int v = 0; v < V; v++) {
                if (!visited[v] && rGraph[u][v] > 0) {
                    queue.add(v);
                    parent[v] = u;
                    visited[v] = true;
                }
            }
        }

        return visited[t];
    }

    int fordFulkerson(int graph[][], int s, int t) {
        int u, v;
        int rGraph[][] = new int[V][V];

        for (u = 0; u < V; u++)
            for (v = 0; v < V; v++)
                rGraph[u][v] = graph[u][v];

        int parent[] = new int[V];

        int max_flow = 0;

        while (bfs(rGraph, s, t, parent)) {
            int path_flow = Integer.MAX_VALUE;
            for (v = t; v != s; v = parent[v]) {
                u = parent[v];
                path_flow = Math.min(path_flow, rGraph[u][v]);
            }

            for (v = t; v != s; v = parent[v]) {
                u = parent[v];
                rGraph[u][v] -= path_flow;
                rGraph[v][u] += path_flow;
            }

            max_flow += path_flow;
        }

        return max_flow;
    }

    public static void main(String[] args) {
        int graph[][] = {
            {0,  13,  10,  10,   0, 0,  0,  0},
            {0,   0,  0,   0,  24, 0,  0,  0},
            {0,   5,  0,   15,  0, 0,  7,  0},
            {0,   0,  0,    0,  0, 0,  15, 0},
            {0,   0,  0,    0,  0, 1,   0, 9},
            {0,   0,  0,    0,  0, 0,   6, 13},
            {0,   0,  0,    0,  0, 0,   0, 16},
            {0,   0,  0,    0,  0, 0,   0,  0}

        };

        Main m = new Main();

        System.out.println("The maximum possible flow is " + m.fordFulkerson(graph, 0, 7));
    }
}

O/P
The maximum possible flow is 26

6. Dijikstra Algorithm

import java.util.*;

class Dijkstra {
    static class Edge {
        int dest, weight;
        Edge(int d, int w) {
            this.dest = d;
            this.weight = w;
        }
    }

    static class Node implements Comparable<Node> {
        int vertex, cost;
        Node(int v, int c) {
            this.vertex = v;
            this.cost = c;
        }

        public int compareTo(Node other) {
            return Integer.compare(this.cost, other.cost);
        }
    }

    public static int dijkstra(Map<Integer, List<Edge>> graph, int source, int target) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Map<Integer, Integer> distance = new HashMap<>();

        // Initialize distances
        for (int node : graph.keySet()) {
            distance.put(node, Integer.MAX_VALUE);
        }
        distance.put(source, 0);
        pq.add(new Node(source, 0));

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

            if (u == target) {
                return distance.get(u); // Shortest path found
            }

            for (Edge edge : graph.get(u)) {
                int v = edge.dest;
                int newDist = distance.get(u) + edge.weight;

                if (newDist < distance.get(v)) {
                    distance.put(v, newDist);
                    pq.add(new Node(v, newDist));
                }
            }
        }

        return -1; // No path found
    }

    public static void main(String[] args) {
        Map<Integer, List<Edge>> graph = new HashMap<>();

        // Defining the graph with time weights
        graph.put(0, Arrays.asList(new Edge(1, 1), new Edge(2, 5)));  // A -> B (1), A -> C (5)
        graph.put(1, Arrays.asList(new Edge(3, 20)));                 // B -> D (20)
        graph.put(2, Arrays.asList(new Edge(3, 10)));                 // C -> D (10)
        graph.put(3, new ArrayList<>());                              // D has no outgoing edges

        int minTime = dijkstra(graph, 0, 3);
        System.out.println("Minimum time to reach D: " + minTime + " minutes");
    }
}

O/P
Minimum time to reach D: 15 minutes


7. Leveinshtien ALgo

import java.util.*;

public class NameMatcher {
    // Function to calculate Levenshtein Distance
    public static int levenshteinDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else {
                    int cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1;
                    dp[i][j] = Math.min(Math.min(
                            dp[i - 1][j] + 1,     // Deletion
                            dp[i][j - 1] + 1),    // Insertion
                            dp[i - 1][j - 1] + cost); // Substitution
                }
            }
        }
        return dp[m][n];
    }

    public static String findBestMatch(String nameA, List<String> listB) {
        String bestMatch = "";
        int minDistance = Integer.MAX_VALUE;

        for (String nameB : listB) {
            if (nameB.equals(".") || nameB.trim().isEmpty()) continue;  // Ignore blank cells
            int distance = levenshteinDistance(nameA.toLowerCase(), nameB.toLowerCase());
            if (distance < minDistance) {
                minDistance = distance;
                bestMatch = nameB;
            }
        }
        return bestMatch;
    }

    public static void main(String[] args) {
        List<String> listA = Arrays.asList(
            "Accenture", "Adobe", "Akamai", "Alexandria Real Estates",
            "Biotech", "Boeing", "Catamarine", "Cadmaxx Solutions", "Cisco Systems"
        );
        List<String> listB = Arrays.asList(
            "Accent llxure", "Addobbe", ".", "Alexandira Reel Estates",
            "Biotec", "Boing", "Catamaine", "Cadmax Soltion", "Cisc Systm"
        );

        System.out.println("Matching Results:");
        for (String nameA : listA) {
            String bestMatch = findBestMatch(nameA, listB);
            System.out.println(nameA + " -> " + bestMatch);
        }
    }
}

O/P
Accenture -> Accent llxure
Adobe -> Addobbe
Akamai -> (No match)
Alexandria Real Estates -> Alexandira Reel Estates
Biotech -> Biotec
Boeing -> Boing
Catamarine -> Catamaine
Cadmaxx Solutions -> Cadmax Soltion
Cisco Systems -> Cisc Systm

8. Robin Karp

import java.util.*;

public class RabinKarpPlagiarismDetector {
    private static final int PRIME = 101; // Prime number for hashing

    // Function to compute hash for a substring
    private static long createHash(String str, int len) {
        long hash = 0;
        for (int i = 0; i < len; i++) {
            hash += str.charAt(i) * Math.pow(PRIME, i);
        }
        return hash;
    }

    // Function to recalculate hash when sliding window moves
    private static long recalculateHash(String str, int oldIndex, int newIndex, long oldHash, int patternLen) {
        long newHash = (oldHash - str.charAt(oldIndex)) / PRIME;
        newHash += str.charAt(newIndex) * Math.pow(PRIME, patternLen - 1);
        return newHash;
    }

    // Function to detect similar substrings using Rabin-Karp
    public static boolean isPlagiarized(String code1, String code2, int patternLen) {
        int len1 = code1.length(), len2 = code2.length();

        if (len1 < patternLen || len2 < patternLen) return false; // If too short, can't compare

        long hash1 = createHash(code1, patternLen);
        long hash2 = createHash(code2, patternLen);

        // Compare initial hashes
        if (hash1 == hash2 && code1.substring(0, patternLen).equals(code2.substring(0, patternLen))) {
            return true;
        }

        // Sliding window hash comparison
        for (int i = 1; i <= len2 - patternLen; i++) {
            hash2 = recalculateHash(code2, i - 1, i + patternLen - 1, hash2, patternLen);
            if (hash1 == hash2 && code1.substring(0, patternLen).equals(code2.substring(i, i + patternLen))) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        // Example Code Submissions
        String codeA = "int sum(int a, int b) { return a + b; }";
        String codeB = "int sum(int x, int y) { return x + y; }";

        int patternLength = 5; // Define substring pattern size for comparison

        boolean plagiarized = isPlagiarized(codeA, codeB, patternLength);

        if (plagiarized) {
            System.out.println("Plagiarism Detected!");
        } else {
            System.out.println("Code is unique.");
        }
    }
}