Practical Exercises - Advanced Algorithms

1. Randomized Quick Sort

Implement and visualize the randomized quicksort algorithm that reports the number of comparisons made during sorting.

Randomized Quick Sort Visualization

Array Size:

Click Generate Random Array to start

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

class RandomizedQuickSort {
private:
    int comparisons;
    std::random_device rd;
    std::mt19937 gen;
    
public:
    RandomizedQuickSort() : comparisons(0), gen(rd()) {}
    
    int quickSort(std::vector<int>& arr, int low, int high) {
        comparisons = 0;
        quickSortHelper(arr, low, high);
        return comparisons;
    }
    
private:
    void quickSortHelper(std::vector<int>& arr, int low, int high) {
        if (low < high) {
            int pivot = randomizedPartition(arr, low, high);
            quickSortHelper(arr, low, pivot - 1);
            quickSortHelper(arr, pivot + 1, high);
        }
    }
    
    int randomizedPartition(std::vector<int>& arr, int low, int high) {
        // Randomly select pivot
        std::uniform_int_distribution<int> dis(low, high);
        int randomIndex = dis(gen);
        std::swap(arr[randomIndex], arr[high]);
        
        return partition(arr, low, high);
    }
    
    int partition(std::vector<int>& arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        
        for (int j = low; j <= high - 1; j++) {
            comparisons++; // Count comparison
            if (arr[j] <= pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);
        return i + 1;
    }
};

2. Randomized Select

Find the k-th smallest element in an array using randomized selection algorithm.

Randomized Select Visualization

Array Size:

Find k-th element:

Click Generate Array to start

#include <iostream>
#include <vector>
#include <random>

class RandomizedSelect {
private:
    std::random_device rd;
    std::mt19937 gen;
    
public:
    RandomizedSelect() : gen(rd()) {}
    
    int select(std::vector<int>& arr, int k) {
        return selectHelper(arr, 0, arr.size() - 1, k - 1);
    }
    
private:
    int selectHelper(std::vector<int>& arr, int low, int high, int k) {
        if (low == high) return arr[low];
        
        int pivot = randomizedPartition(arr, low, high);
        
        if (k == pivot) {
            return arr[pivot];
        } else if (k < pivot) {
            return selectHelper(arr, low, pivot - 1, k);
        } else {
            return selectHelper(arr, pivot + 1, high, k);
        }
    }
    
    int randomizedPartition(std::vector<int>& arr, int low, int high) {
        std::uniform_int_distribution<int> dis(low, high);
        int randomIndex = dis(gen);
        std::swap(arr[randomIndex], arr[high]);
        
        return partition(arr, low, high);
    }
    
    int partition(std::vector<int>& arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        
        for (int j = low; j <= high - 1; j++) {
            if (arr[j] <= pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);
        return i + 1;
    }
};

3. Kruskal's MST Algorithm

Find minimum spanning tree using Kruskal's algorithm with Union-Find data structure.

Kruskal's Algorithm Visualization

Click Generate Graph to start

#include <iostream>
#include <vector>
#include <algorithm>

struct Edge {
    int src, dest, weight;
    
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

class UnionFind {
private:
    std::vector<int> parent, rank;
    
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }
    
    bool unionSets(int x, int y) {
        int px = find(x), py = find(y);
        
        if (px == py) return false; // Already in same set
        
        // Union by rank
        if (rank[px] < rank[py]) {
            parent[px] = py;
        } else if (rank[px] > rank[py]) {
            parent[py] = px;
        } else {
            parent[py] = px;
            rank[px]++;
        }
        return true;
    }
};

class KruskalMST {
public:
    std::vector<Edge> findMST(std::vector<Edge>& edges, int vertices) {
        std::vector<Edge> mst;
        std::sort(edges.begin(), edges.end());
        
        UnionFind uf(vertices);
        
        for (const Edge& edge : edges) {
            if (uf.unionSets(edge.src, edge.dest)) {
                mst.push_back(edge);
                if (mst.size() == vertices - 1) break;
            }
        }
        
        return mst;
    }
    
    int getMSTWeight(const std::vector<Edge>& mst) {
        int totalWeight = 0;
        for (const Edge& edge : mst) {
            totalWeight += edge.weight;
        }
        return totalWeight;
    }
};

4. Bellman Ford Algorithm

Find shortest paths from a source to all vertices, handling negative edge weights.

Bellman Ford Visualization

Source Vertex:

Click Generate Graph to start

#include <iostream>
#include <vector>
#include <climits>

struct BellmanEdge {
    int src, dest, weight;
    BellmanEdge(int s, int d, int w) : src(s), dest(d), weight(w) {}
};

class BellmanFord {
public:
    std::pair<std::vector<int>, bool> shortestPaths(
        const std::vector<BellmanEdge>& edges, int vertices, int source) {
        
        std::vector<int> distance(vertices, INT_MAX);
        distance[source] = 0;
        
        // Relax edges V-1 times
        for (int i = 0; i < vertices - 1; i++) {
            for (const BellmanEdge& edge : edges) {
                if (distance[edge.src] != INT_MAX && 
                    distance[edge.src] + edge.weight < distance[edge.dest]) {
                    distance[edge.dest] = distance[edge.src] + edge.weight;
                }
            }
        }
        
        // Check for negative cycles
        for (const BellmanEdge& edge : edges) {
            if (distance[edge.src] != INT_MAX && 
                distance[edge.src] + edge.weight < distance[edge.dest]) {
                return {distance, false}; // Negative cycle detected
            }
        }
        
        return {distance, true}; // No negative cycle
    }
    
    void printPaths(const std::vector<int>& distance, int source) {
        std::cout << "Shortest distances from vertex " << source << ":n";
        for (int i = 0; i < distance.size(); i++) {
            std::cout << "To vertex " << i << ": ";
            if (distance[i] == INT_MAX) {
                std::cout << "INF";
            } else {
                std::cout << distance[i];
            }
            std::cout << "n";
        }
    }
};

5. B-Tree Implementation

Implement a B-Tree data structure with insertion and search operations.

B-Tree Visualization

Value to Insert:

Search Value:

B-Tree (Order 3) will be displayed here

Enter values to insert into B-Tree

#include <iostream>
#include <vector>
#include <algorithm>

class BTreeNode {
public:
    std::vector<int> keys;
    std::vector<BTreeNode*> children;
    bool isLeaf;
    int degree; // Minimum degree
    
    BTreeNode(int deg, bool leaf) : degree(deg), isLeaf(leaf) {}
    
    void insertNonFull(int key) {
        int i = keys.size() - 1;
        
        if (isLeaf) {
            keys.push_back(0);
            while (i >= 0 && keys[i] > key) {
                keys[i + 1] = keys[i];
                i--;
            }
            keys[i + 1] = key;
        } else {
            while (i >= 0 && keys[i] > key) {
                i--;
            }
            i++;
            
            if (children[i]->keys.size() == 2 * degree - 1) {
                splitChild(i, children[i]);
                if (keys[i] < key) {
                    i++;
                }
            }
            children[i]->insertNonFull(key);
        }
    }
    
    void splitChild(int index, BTreeNode* fullChild) {
        int degree = fullChild->degree;
        BTreeNode* newChild = new BTreeNode(degree, fullChild->isLeaf);
        
        // Move half of the keys to new child
        for (int j = 0; j < degree - 1; j++) {
            newChild->keys.push_back(fullChild->keys[j + degree]);
        }
        
        if (!fullChild->isLeaf) {
            for (int j = 0; j < degree; j++) {
                newChild->children.push_back(fullChild->children[j + degree]);
            }
        }
        
        // Move the middle key up
        keys.insert(keys.begin() + index, fullChild->keys[degree - 1]);
        children.insert(children.begin() + index + 1, newChild);
        
        // Reduce the full child's size
        fullChild->keys.resize(degree - 1);
        if (!fullChild->isLeaf) {
            fullChild->children.resize(degree);
        }
    }
    
    bool search(int key) {
        int i = 0;
        while (i < keys.size() && key > keys[i]) {
            i++;
        }
        
        if (i < keys.size() && key == keys[i]) {
            return true;
        }
        
        if (isLeaf) {
            return false;
        }
        
        return children[i]->search(key);
    }
    
    void traverse() {
        int i;
        for (i = 0; i < keys.size(); i++) {
            if (!isLeaf) {
                children[i]->traverse();
            }
            std::cout << " " << keys[i];
        }
        
        if (!isLeaf) {
            children[i]->traverse();
        }
    }
};

class BTree {
private:
    BTreeNode* root;
    int degree;
    
public:
    BTree(int deg) : degree(deg), root(nullptr) {}
    
    void insert(int key) {
        if (root == nullptr) {
            root = new BTreeNode(degree, true);
            root->keys.push_back(key);
        } else {
            if (root->keys.size() == 2 * degree - 1) {
                BTreeNode* newRoot = new BTreeNode(degree, false);
                newRoot->children.push_back(root);
                newRoot->splitChild(0, root);
                
                int i = 0;
                if (newRoot->keys[0] < key) {
                    i++;
                }
                newRoot->children[i]->insertNonFull(key);
                root = newRoot;
            } else {
                root->insertNonFull(key);
            }
        }
    }
    
    bool search(int key) {
        return (root == nullptr) ? false : root->search(key);
    }
    
    void traverse() {
        if (root != nullptr) {
            root->traverse();
        }
    }
};

6. Binary Search Tree

Implement a binary search tree supporting insert and search operations.

BST Visualization

Insert Value:

Search Value:

Insert values to build the BST

#include <iostream>
#include <memory>

struct TreeNode {
    int data;
    std::unique_ptr<TreeNode> left;
    std::unique_ptr<TreeNode> right;
    
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class BinarySearchTree {
private:
    std::unique_ptr<TreeNode> root;
    
public:
    BinarySearchTree() : root(nullptr) {}
    
    void insert(int value) {
        root = insertHelper(std::move(root), value);
    }
    
    bool search(int value) {
        return searchHelper(root.get(), value);
    }
    
    void inorderTraversal() {
        std::cout << "Inorder: ";
        inorderHelper(root.get());
        std::cout << std::endl;
    }
    
    void preorderTraversal() {
        std::cout << "Preorder: ";
        preorderHelper(root.get());
        std::cout << std::endl;
    }
    
    void postorderTraversal() {
        std::cout << "Postorder: ";
        postorderHelper(root.get());
        std::cout << std::endl;
    }
    
private:
    std::unique_ptr<TreeNode> insertHelper(std::unique_ptr<TreeNode> node, int value) {
        if (!node) {
            return std::make_unique<TreeNode>(value);
        }
        
        if (value < node->data) {
            node->left = insertHelper(std::move(node->left), value);
        } else if (value > node->data) {
            node->right = insertHelper(std::move(node->right), value);
        }
        
        return node;
    }
    
    bool searchHelper(TreeNode* node, int value) {
        if (!node) {
            return false;
        }
        
        if (value == node->data) {
            return true;
        } else if (value < node->data) {
            return searchHelper(node->left.get(), value);
        } else {
            return searchHelper(node->right.get(), value);
        }
    }
    
    void inorderHelper(TreeNode* node) {
        if (node) {
            inorderHelper(node->left.get());
            std::cout << node->data << " ";
            inorderHelper(node->right.get());
        }
    }
    
    void preorderHelper(TreeNode* node) {
        if (node) {
            std::cout << node->data << " ";
            preorderHelper(node->left.get());
            preorderHelper(node->right.get());
        }
    }
    
    void postorderHelper(TreeNode* node) {
        if (node) {
            postorderHelper(node->left.get());
            postorderHelper(node->right.get());
            std::cout << node->data << " ";
        }
    }
};

7. KMP String Matching

Search for a pattern in a given text using the KMP (Knuth-Morris-Pratt) algorithm.

KMP Algorithm Visualization

Text:

Pattern:

Enter text and pattern to start KMP search

#include <iostream>
#include <vector>
#include <string>

class KMPAlgorithm {
public:
    std::vector<int> computeLPS(const std::string& pattern) {
        int m = pattern.length();
        std::vector<int> lps(m, 0);
        int len = 0;
        int i = 1;
        
        while (i < m) {
            if (pattern[i] == pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        return lps;
    }
    
    std::vector<int> search(const std::string& text, const std::string& pattern) {
        int n = text.length();
        int m = pattern.length();
        
        std::vector<int> matches;
        std::vector<int> lps = computeLPS(pattern);
        
        int i = 0; // index for text
        int j = 0; // index for pattern
        
        while (i < n) {
            if (pattern[j] == text[i]) {
                i++;
                j++;
            }
            
            if (j == m) {
                matches.push_back(i - j);
                j = lps[j - 1];
            } else if (i < n && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        return matches;
    }
    
    void displayLPS(const std::string& pattern) {
        std::vector<int> lps = computeLPS(pattern);
        
        std::cout << "Pattern: " << pattern << std::endl;
        std::cout << "LPS:     ";
        for (int val : lps) {
            std::cout << val << " ";
        }
        std::cout << std::endl;
    }
};

8. Suffix Tree Implementation

Implement a suffix tree data structure for efficient string processing.

Suffix Tree Visualization

Input String:

Search Suffix:

Enter a string to build its suffix tree

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>

class SuffixTreeNode {
public:
    std::unordered_map<char, SuffixTreeNode*> children;
    int start;
    int* end;
    int suffixIndex;
    
    SuffixTreeNode(int start, int* end) 
        : start(start), end(end), suffixIndex(-1) {}
};

class SuffixTree {
private:
    std::string text;
    SuffixTreeNode* root;
    int* globalEnd;
    
public:
    SuffixTree(const std::string& str) : text(str + "$") {
        globalEnd = new int(-1);
        root = new SuffixTreeNode(-1, globalEnd);
        buildSuffixTree();
    }
    
    void buildSuffixTree() {
        int n = text.length();
        
        for (int i = 0; i < n; i++) {
            insertSuffix(i);
        }
    }
    
    void insertSuffix(int suffixIndex) {
        SuffixTreeNode* current = root;
        
        for (int i = suffixIndex; i < text.length(); i++) {
            char c = text[i];
            
            if (current->children.find(c) == current->children.end()) {
                // Create new leaf node
                int* leafEnd = new int(text.length() - 1);
                current->children[c] = new SuffixTreeNode(i, leafEnd);
                current->children[c]->suffixIndex = suffixIndex;
                return;
            }
            
            current = current->children[c];
            
            // Check if we need to split an edge
            int edgeLength = *(current->end) - current->start + 1;
            int j = 0;
            
            while (j < edgeLength && i + j < text.length() && 
                   text[current->start + j] == text[i + j]) {
                j++;
            }
            
            if (j == edgeLength) {
                i += j - 1;
                continue;
            }
            
            // Split the edge
            int* splitEnd = new int(current->start + j - 1);
            SuffixTreeNode* splitNode = new SuffixTreeNode(current->start, splitEnd);
            
            current->start += j;
            splitNode->children[text[current->start]] = current;
            
            if (i + j < text.length()) {
                int* newLeafEnd = new int(text.length() - 1);
                splitNode->children[text[i + j]] = 
                    new SuffixTreeNode(i + j, newLeafEnd);
                splitNode->children[text[i + j]]->suffixIndex = suffixIndex;
            }
            
            return;
        }
    }
    
    bool search(const std::string& pattern) {
        SuffixTreeNode* current = root;
        int i = 0;
        
        while (i < pattern.length()) {
            char c = pattern[i];
            
            if (current->children.find(c) == current->children.end()) {
                return false;
            }
            
            current = current->children[c];
            int edgeLength = *(current->end) - current->start + 1;
            int j = 0;
            
            while (j < edgeLength && i < pattern.length() && 
                   text[current->start + j] == pattern[i]) {
                i++;
                j++;
            }
            
            if (j < edgeLength && i < pattern.length()) {
                return false;
            }
        }
        
        return true;
    }
    
    void displaySuffixes() {
        std::cout << "All suffixes of '" << text.substr(0, text.length()-1) << "':n";
        for (int i = 0; i < text.length() - 1; i++) {
            std::cout << i << ": " << text.substr(i, text.length()-1-i) << std::endl;
        }
    }
};