ALGORITHM QUICK REFERENCE GUIDE

================================
SORTING ALGORITHMS
================================

--- Bubble Sort ---
Explanation:
    A simple comparison-based sorting algorithm. It repeatedly steps
    through the list, compares adjacent elements and swaps them if they
    are in the wrong order. The pass through the list is repeated until
    no swaps are needed, which indicates that the list is sorted.
Pseudo Code:
    PROCEDURE BubbleSort(ARRAY A)
        n = LENGTH(A)
        FOR i FROM 0 TO n-2
            FOR j FROM 0 TO n-i-2
                IF A[j] > A[j+1] THEN
                    SWAP(A[j], A[j+1])
                END IF
            END FOR
        END FOR
    END PROCEDURE

--- Selection Sort ---
Explanation:
    A simple comparison-based sorting algorithm. It divides the input list
    into two parts: a sorted sublist of items built up from left to right at
    the front (left) of the list and an unsorted sublist of the remaining
    items. The algorithm repeatedly finds the minimum element from the
    unsorted part and puts it at the beginning of the sorted part.
Pseudo Code:
    PROCEDURE SelectionSort(ARRAY A)
        n = LENGTH(A)
        FOR i FROM 0 TO n-2
            min_idx = i
            FOR j FROM i+1 TO n-1
                IF A[j] < A[min_idx] THEN
                    min_idx = j
                END IF
            END FOR
            SWAP(A[i], A[min_idx])
        END FOR
    END PROCEDURE

--- Insertion Sort ---
Explanation:
    A simple sorting algorithm that builds the final sorted array (or list)
    one item at a time. It iterates through the input elements and builds
    a sorted list by inserting each element into its correct position in
    the sorted part of the array.
Pseudo Code:
    PROCEDURE InsertionSort(ARRAY A)
        n = LENGTH(A)
        FOR i FROM 1 TO n-1
            key = A[i]
            j = i - 1
            WHILE j >= 0 AND A[j] > key DO
                A[j+1] = A[j]
                j = j - 1
            END WHILE
            A[j+1] = key
        END FOR
    END PROCEDURE

--- Merge Sort ---
Explanation:
    A divide-and-conquer algorithm. It recursively divides the array into
    halves until it has single-element arrays. Then, it merges these smaller
    sorted arrays back together to produce a single sorted array.
Pseudo Code:
    PROCEDURE MergeSort(ARRAY A)
        n = LENGTH(A)
        IF n < 2 THEN
            RETURN A
        END IF
        mid = n / 2
        left_half = A[0 TO mid-1]
        right_half = A[mid TO n-1]

        sorted_left = MergeSort(left_half)
        sorted_right = MergeSort(right_half)

        RETURN Merge(sorted_left, sorted_right)

    PROCEDURE Merge(ARRAY L, ARRAY R)
        result = EMPTY_ARRAY
        i = 0, j = 0
        WHILE i < LENGTH(L) AND j < LENGTH(R) DO
            IF L[i] <= R[j] THEN
                ADD L[i] TO result
                i = i + 1
            ELSE
                ADD R[j] TO result
                j = j + 1
            END IF
        END WHILE
        WHILE i < LENGTH(L) DO
            ADD L[i] TO result
            i = i + 1
        END WHILE
        WHILE j < LENGTH(R) DO
            ADD R[j] TO result
            j = j + 1
        END WHILE
        RETURN result
    END PROCEDURE

--- Quick Sort ---
Explanation:
    A highly efficient, comparison-based sorting algorithm that uses a
    divide-and-conquer approach. It works by selecting a 'pivot' element
    from the array and partitioning the other elements into two sub-arrays,
    according to whether they are less than or greater than the pivot.
    The sub-arrays are then sorted recursively.
Pseudo Code:
    PROCEDURE QuickSort(ARRAY A, low, high)
        IF low < high THEN
            pivot_index = Partition(A, low, high)
            QuickSort(A, low, pivot_index - 1)
            QuickSort(A, pivot_index + 1, high)
        END IF
    END PROCEDURE

    PROCEDURE Partition(ARRAY A, low, high)
        pivot = A[high]
        i = low - 1
        FOR j FROM low TO high - 1
            IF A[j] <= pivot THEN
                i = i + 1
                SWAP(A[i], A[j])
            END IF
        END FOR
        SWAP(A[i+1], A[high])
        RETURN i + 1
    END PROCEDURE

--- Heap Sort ---
Explanation:
    A comparison-based sorting algorithm that uses a binary heap data structure.
    It's similar to selection sort where we find the maximum element and place
    it at the end. It builds a max-heap from the input data and then repeatedly
    extracts the maximum element from the heap and rebuilds the heap until
    the array is sorted.
Pseudo Code:
    PROCEDURE HeapSort(ARRAY A)
        n = LENGTH(A)
        FOR i FROM n/2 - 1 DOWNTO 0
            Heapify(A, n, i)
        END FOR

        FOR i FROM n-1 DOWNTO 0
            SWAP(A[0], A[i])
            Heapify(A, i, 0)
        END FOR
    END PROCEDURE

    PROCEDURE Heapify(ARRAY A, n, i)
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2

        IF left < n AND A[left] > A[largest] THEN
            largest = left
        END IF
        IF right < n AND A[right] > A[largest] THEN
            largest = right
        END IF

        IF largest != i THEN
            SWAP(A[i], A[largest])
            Heapify(A, n, largest)
        END IF
    END PROCEDURE

--- Counting Sort ---
Explanation:
    A non-comparison based sorting algorithm. It is effective when the range
    of input data is not significantly larger than the number of items to be
    sorted. It works by counting the number of occurrences of each distinct
    element in the input array. Then, it uses this count information to place
    each element into its correct sorted position.
Pseudo Code:
    PROCEDURE CountingSort(ARRAY A, max_val)
        count_array = ARRAY of size (max_val + 1) initialized to 0
        output_array = ARRAY of same size as A

        FOR i FROM 0 TO LENGTH(A)-1
            count_array[A[i]] = count_array[A[i]] + 1
        END FOR

        FOR i FROM 1 TO max_val
            count_array[i] = count_array[i] + count_array[i-1]
        END FOR

        FOR i FROM LENGTH(A)-1 DOWNTO 0
            output_array[count_array[A[i]] - 1] = A[i]
            count_array[A[i]] = count_array[A[i]] - 1
        END FOR

        FOR i FROM 0 TO LENGTH(A)-1
            A[i] = output_array[i]
        END FOR
    END PROCEDURE

--- Radix Sort ---
Explanation:
    A non-comparison based integer sorting algorithm that sorts data with
    integer keys by grouping keys by individual digits which share the same
    significant position and value. It typically uses counting sort as a
    subroutine for sorting by each digit.
Pseudo Code:
    PROCEDURE RadixSort(ARRAY A)
        max_val = MAX_ELEMENT(A)
        exp = 1
        WHILE max_val / exp > 0 DO
            CountSortByDigit(A, exp)
            exp = exp * 10
        END WHILE
    END PROCEDURE

    PROCEDURE CountSortByDigit(ARRAY A, exp)
        n = LENGTH(A)
        output_array = ARRAY of size n
        count_array = ARRAY of size 10 initialized to 0

        FOR i FROM 0 TO n-1
            digit = (A[i] / exp) MOD 10
            count_array[digit] = count_array[digit] + 1
        END FOR

        FOR i FROM 1 TO 9
            count_array[i] = count_array[i] + count_array[i-1]
        END FOR

        FOR i FROM n-1 DOWNTO 0
            digit = (A[i] / exp) MOD 10
            output_array[count_array[digit] - 1] = A[i]
            count_array[digit] = count_array[digit] - 1
        END FOR

        FOR i FROM 0 TO n-1
            A[i] = output_array[i]
        END FOR
    END PROCEDURE

--- Bucket Sort ---
Explanation:
    A distribution sort algorithm that works by distributing elements into
    a number of buckets. Each bucket is then sorted individually, either
    using a different sorting algorithm or by recursively applying the
    bucket sort algorithm. Finally, the sorted elements are gathered from
    the buckets. It is efficient for uniformly distributed data.
Pseudo Code:
    PROCEDURE BucketSort(ARRAY A)
        n = LENGTH(A)
        num_buckets = n
        buckets = ARRAY of num_buckets empty lists

        // Assume elements are in range [0, 1)
        FOR i FROM 0 TO n-1
            bucket_index = FLOOR(num_buckets * A[i])
            ADD A[i] TO buckets[bucket_index]
        END FOR

        FOR i FROM 0 TO num_buckets-1
            Sort(buckets[i]) // Use insertion sort or other stable sort
        END FOR

        index = 0
        FOR i FROM 0 TO num_buckets-1
            FOR EACH element IN buckets[i]
                A[index] = element
                index = index + 1
            END FOR
        END FOR
    END PROCEDURE

--- Shell Sort ---
Explanation:
    An in-place comparison sort. It can be seen as an optimization of
    insertion sort. Instead of sorting adjacent elements, it sorts elements
    that are far apart by a certain gap, then progressively reduces the gap
    until it becomes 1 (at which point it's essentially insertion sort).
    This allows elements to move large distances in the array more quickly.
Pseudo Code:
    PROCEDURE ShellSort(ARRAY A)
        n = LENGTH(A)
        gap = n / 2
        WHILE gap > 0 DO
            FOR i FROM gap TO n-1
                temp = A[i]
                j = i
                WHILE j >= gap AND A[j - gap] > temp DO
                    A[j] = A[j - gap]
                    j = j - gap
                END WHILE
                A[j] = temp
            END FOR
            gap = gap / 2
        END WHILE
    END PROCEDURE

--- TimSort ---
Explanation:
    A hybrid stable sorting algorithm, derived from merge sort and insertion
    sort, designed to perform well on many kinds of real-world data. It works
    by finding already sorted "runs" in the data and merging them efficiently.
    It's the default sorting algorithm in Python and Java.
Pseudo Code:
    (Conceptual, simplified as it's complex)
    PROCEDURE TimSort(ARRAY A)
        n = LENGTH(A)
        min_run = CalculateMinRun(n) // Typically between 32 and 64
        
        // Step 1: Divide array into runs and sort them using Insertion Sort
        FOR i FROM 0 TO n-1 STEP min_run
            InsertionSort(A, i, MIN(i + min_run - 1, n - 1))
        END FOR

        // Step 2: Merge runs
        size = min_run
        WHILE size < n DO
            FOR left FROM 0 TO n-1 STEP 2 * size
                mid = left + size - 1
                right = MIN(left + 2 * size - 1, n - 1)
                IF mid < right THEN // Check if there's a right run to merge
                    Merge(A, left, mid, right) // Similar to MergeSort's Merge
                END IF
            END FOR
            size = 2 * size
        END WHILE
    END PROCEDURE

    PROCEDURE Merge(ARRAY A, left, mid, right)
        // Standard merge logic from Merge Sort
        // Merges A[left...mid] and A[mid+1...right]
    END PROCEDURE

    PROCEDURE CalculateMinRun(n)
        // Algorithm to calculate optimal min_run based on n
        // For simplicity, can be a fixed value like 32 or 64
        RETURN 32
    END PROCEDURE

================================
SEARCH ALGORITHMS
================================

--- Linear Search ---
Explanation:
    The simplest search algorithm. It sequentially checks each element of
    the list until a match is found or the end of the list is reached.
Pseudo Code:
    PROCEDURE LinearSearch(ARRAY A, target)
        n = LENGTH(A)
        FOR i FROM 0 TO n-1
            IF A[i] == target THEN
                RETURN i // Target found at index i
            END IF
        END FOR
        RETURN -1 // Target not found
    END PROCEDURE

--- Binary Search ---
Explanation:
    An efficient algorithm for finding an item from a sorted list of items.
    It works by repeatedly dividing the search interval in half. If the value
    of the search key is less than the item in the middle of the interval,
    narrow the interval to the lower half. Otherwise, narrow it to the
    upper half.
Pseudo Code:
    PROCEDURE BinarySearch(ARRAY A, target)
        low = 0
        high = LENGTH(A) - 1
        WHILE low <= high DO
            mid = low + (high - low) / 2 // To prevent overflow for large low, high
            IF A[mid] == target THEN
                RETURN mid
            ELSE IF A[mid] < target THEN
                low = mid + 1
            ELSE
                high = mid - 1
            END IF
        END WHILE
        RETURN -1
    END PROCEDURE

--- Ternary Search ---
Explanation:
    A divide and conquer algorithm that can be used to find an element in
    an array or to find the maximum or minimum of a unimodal function.
    Similar to binary search, but it divides the array into three parts.
Pseudo Code:
    PROCEDURE TernarySearch(ARRAY A, target)
        low = 0
        high = LENGTH(A) - 1
        WHILE low <= high DO
            mid1 = low + (high - low) / 3
            mid2 = high - (high - low) / 3

            IF A[mid1] == target THEN
                RETURN mid1
            END IF
            IF A[mid2] == target THEN
                RETURN mid2
            END IF

            IF target < A[mid1] THEN
                high = mid1 - 1
            ELSE IF target > A[mid2] THEN
                low = mid2 + 1
            ELSE
                low = mid1 + 1
                high = mid2 - 1
            END IF
        END WHILE
        RETURN -1
    END PROCEDURE

--- Jump Search ---
Explanation:
    A search algorithm for sorted arrays. It works by checking fewer elements
    than linear search by jumping ahead by fixed steps or blocks. Once a block
    is found that might contain the element, a linear search is performed
    within that block.
Pseudo Code:
    PROCEDURE JumpSearch(ARRAY A, target)
        n = LENGTH(A)
        blockSize = FLOOR(SQRT(n))
        prev = 0
        WHILE A[MIN(blockSize, n) - 1] < target DO
            prev = blockSize
            blockSize = blockSize + FLOOR(SQRT(n))
            IF prev >= n THEN
                RETURN -1 // Target not in array
            END IF
        END WHILE

        // Linear search within the block
        WHILE A[prev] < target DO
            prev = prev + 1
            IF prev == MIN(blockSize, n) THEN
                RETURN -1 // Target not in array
            END IF
        END WHILE

        IF A[prev] == target THEN
            RETURN prev
        END IF

        RETURN -1
    END PROCEDURE

--- Exponential Search ---
Explanation:
    An algorithm for searching sorted arrays. It involves finding a range
    where the target element might reside, and then performing a binary search
    within that range. It's particularly useful for unbounded arrays or
    very large arrays where the element is likely to be near the beginning.
Pseudo Code:
    PROCEDURE ExponentialSearch(ARRAY A, target)
        n = LENGTH(A)
        IF A[0] == target THEN
            RETURN 0
        END IF

        i = 1
        WHILE i < n AND A[i] <= target DO
            i = i * 2
        END WHILE

        RETURN BinarySearch(A, target, i / 2, MIN(i, n - 1))
    END PROCEDURE

    (Note: BinarySearch here is the standard one, adjusted for sub-array)
    PROCEDURE BinarySearch(ARRAY A, target, low, high)
        WHILE low <= high DO
            mid = low + (high - low) / 2
            IF A[mid] == target THEN
                RETURN mid
            ELSE IF A[mid] < target THEN
                low = mid + 1
            ELSE
                high = mid - 1
            END IF
        END WHILE
        RETURN -1
    END PROCEDURE

--- Interpolation Search ---
Explanation:
    An improvement over binary search for uniformly distributed sorted arrays.
    It uses the value of the key and the values at the low and high ends of
    the array to determine where to search next, similar to how we would look
    up a name in a phone book.
Pseudo Code:
    PROCEDURE InterpolationSearch(ARRAY A, target)
        low = 0
        high = LENGTH(A) - 1
        WHILE low <= high AND target >= A[low] AND target <= A[high] DO
            IF low == high THEN
                IF A[low] == target THEN RETURN low
                ELSE RETURN -1
            END IF

            pos = low + (((high - low) / (A[high] - A[low])) * (target - A[low]))

            IF A[pos] == target THEN
                RETURN pos
            END IF
            IF A[pos] < target THEN
                low = pos + 1
            ELSE
                high = pos - 1
            END IF
        END WHILE
        RETURN -1
    END PROCEDURE

================================
GRAPH ALGORITHMS
================================

--- Breadth-First Search (BFS) ---
Explanation:
    An algorithm for traversing or searching tree or graph data structures.
    It starts at the tree root (or some arbitrary node of a graph, sometimes
    referred to as a 'search key') and explores all of the neighbor nodes at
    the present depth before moving on to the nodes at the next depth level.
Pseudo Code:
    PROCEDURE BFS(Graph G, start_node)
        CREATE Queue Q
        CREATE Set visited_nodes
        
        ENQUEUE(Q, start_node)
        ADD start_node TO visited_nodes

        WHILE NOT IS_EMPTY(Q) DO
            current_node = DEQUEUE(Q)
            PRINT current_node // Or process as needed

            FOR EACH neighbor OF current_node IN G.ADJACENCY_LIST[current_node] DO
                IF neighbor NOT IN visited_nodes THEN
                    ADD neighbor TO visited_nodes
                    ENQUEUE(Q, neighbor)
                END IF
            END FOR
        END WHILE
    END PROCEDURE

--- Depth-First Search (DFS) ---
Explanation:
    An algorithm for traversing or searching tree or graph data structures.
    The algorithm starts at the root (or any arbitrary node as the root in
    the case of a graph) and explores as far as possible along each branch
    before backtracking.
Pseudo Code:
    // Recursive implementation
    PROCEDURE DFS_Recursive(Graph G, current_node, visited_nodes)
        ADD current_node TO visited_nodes
        PRINT current_node // Or process as needed

        FOR EACH neighbor OF current_node IN G.ADJACENCY_LIST[current_node] DO
            IF neighbor NOT IN visited_nodes THEN
                DFS_Recursive(G, neighbor, visited_nodes)
            END IF
        END FOR
    END PROCEDURE

    // Iterative implementation
    PROCEDURE DFS_Iterative(Graph G, start_node)
        CREATE Stack S
        CREATE Set visited_nodes

        PUSH(S, start_node)
        ADD start_node TO visited_nodes

        WHILE NOT IS_EMPTY(S) DO
            current_node = POP(S)
            PRINT current_node // Or process as needed

            FOR EACH neighbor OF current_node IN G.ADJACENCY_LIST[current_node] DO
                IF neighbor NOT IN visited_nodes THEN
                    ADD neighbor TO visited_nodes
                    PUSH(S, neighbor)
                END IF
            END FOR
        END WHILE
    END PROCEDURE

--- Dijkstra’s Algorithm (Shortest Path) ---
Explanation:
    An algorithm for finding the shortest paths between nodes in a graph,
    which may represent, for example, road networks. It works for graphs
    with non-negative edge weights. It explores the graph layer by layer,
    always expanding the node with the currently shortest known distance
    from the source.
Pseudo Code:
    PROCEDURE Dijkstra(Graph G, source_node)
        distances = MAP from node to infinity
        distances[source_node] = 0
        
        priority_queue = MIN_PRIORITY_QUEUE (stores pairs of (distance, node))
        INSERT(priority_queue, (0, source_node))

        WHILE NOT IS_EMPTY(priority_queue) DO
            (current_dist, current_node) = EXTRACT_MIN(priority_queue)

            IF current_dist > distances[current_node] THEN
                CONTINUE // Already found a shorter path
            END IF

            FOR EACH neighbor_edge (current_node, neighbor, weight) IN G.ADJACENCY_LIST[current_node] DO
                new_dist = current_dist + weight
                IF new_dist < distances[neighbor] THEN
                    distances[neighbor] = new_dist
                    INSERT(priority_queue, (new_dist, neighbor))
                END IF
            END FOR
        END WHILE
        RETURN distances
    END PROCEDURE

--- Bellman-Ford Algorithm (Shortest Path) ---
Explanation:
    An algorithm that computes shortest paths from a single source vertex to
    all other vertices in a weighted digraph. It is slower than Dijkstra's
    algorithm but can handle graphs with negative edge weights. It can also
    detect negative cycles.
Pseudo Code:
    PROCEDURE BellmanFord(Graph G, source_node)
        distances = MAP from node to infinity
        predecessors = MAP from node to NULL
        distances[source_node] = 0

        // Relax edges V-1 times
        FOR i FROM 1 TO NUMBER_OF_VERTICES(G) - 1
            FOR EACH edge (u, v, weight) IN G.EDGES DO
                IF distances[u] + weight < distances[v] THEN
                    distances[v] = distances[u] + weight
                    predecessors[v] = u
                END IF
            END FOR
        END FOR

        // Check for negative cycles
        FOR EACH edge (u, v, weight) IN G.EDGES DO
            IF distances[u] + weight < distances[v] THEN
                PRINT "Graph contains negative cycle"
                RETURN ERROR
            END IF
        END FOR

        RETURN distances, predecessors
    END PROCEDURE

--- Floyd-Warshall Algorithm (All-Pairs Shortest Path) ---
Explanation:
    An algorithm for finding shortest paths in a weighted graph with positive
    or negative edge weights (but no negative cycles). It calculates the
    shortest paths between all pairs of vertices in a single run. It is a
    dynamic programming algorithm.
Pseudo Code:
    PROCEDURE FloydWarshall(Graph G)
        num_vertices = NUMBER_OF_VERTICES(G)
        dist = 2D ARRAY of size num_vertices x num_vertices

        // Initialize dist matrix
        FOR i FROM 0 TO num_vertices-1
            FOR j FROM 0 TO num_vertices-1
                IF i == j THEN
                    dist[i][j] = 0
                ELSE IF there is an edge from i to j THEN
                    dist[i][j] = WEIGHT(i, j)
                ELSE
                    dist[i][j] = INFINITY
                END IF
            END FOR
        END FOR

        FOR k FROM 0 TO num_vertices-1
            FOR i FROM 0 TO num_vertices-1
                FOR j FROM 0 TO num_vertices-1
                    IF dist[i][k] + dist[k][j] < dist[i][j] THEN
                        dist[i][j] = dist[i][k] + dist[k][j]
                    END IF
                END FOR
            END FOR
        END FOR

        // Optional: Check for negative cycles (diagonal elements will be negative)
        // FOR i FROM 0 TO num_vertices-1
        //    IF dist[i][i] < 0 THEN
        //        PRINT "Graph contains negative cycle"
        //        RETURN ERROR
        //    END IF
        // END FOR

        RETURN dist
    END PROCEDURE

--- A* Algorithm (Pathfinding) ---
Explanation:
    A popular pathfinding algorithm, widely used in artificial intelligence.
    It's an informed search algorithm, meaning it uses a heuristic function
    to guide its search towards the goal. It finds the shortest path between
    a start and a goal node in a graph.
Pseudo Code:
    PROCEDURE A_Star(Graph G, start_node, goal_node, heuristic_function H)
        open_set = MIN_PRIORITY_QUEUE (stores pairs of (f_score, node))
        INSERT(open_set, (H(start_node, goal_node), start_node)) // f_score = g_score + h_score

        g_score = MAP from node to infinity // Cost from start to current node
        g_score[start_node] = 0

        f_score = MAP from node to infinity // Estimated total cost from start to goal through current node
        f_score[start_node] = H(start_node, goal_node)

        came_from = MAP from node to node // To reconstruct path

        WHILE NOT IS_EMPTY(open_set) DO
            (current_f_score, current_node) = EXTRACT_MIN(open_set)

            IF current_node == goal_node THEN
                RETURN ReconstructPath(came_from, current_node)
            END IF

            FOR EACH neighbor_edge (current_node, neighbor, weight) IN G.ADJACENCY_LIST[current_node] DO
                tentative_g_score = g_score[current_node] + weight
                
                IF tentative_g_score < g_score[neighbor] THEN
                    came_from[neighbor] = current_node
                    g_score[neighbor] = tentative_g_score
                    f_score[neighbor] = tentative_g_score + H(neighbor, goal_node)
                    IF neighbor NOT IN open_set THEN // Check if already in priority queue (efficient update)
                        INSERT(open_set, (f_score[neighbor], neighbor))
                    END IF
                END IF
            END FOR
        END WHILE
        RETURN PATH_NOT_FOUND
    END PROCEDURE

    PROCEDURE ReconstructPath(came_from, current_node)
        total_path = LIST
        ADD current_node TO total_path
        WHILE current_node IN came_from DO
            current_node = came_from[current_node]
            PREPEND current_node TO total_path
        END WHILE
        RETURN total_path
    END PROCEDURE

--- Prim’s Algorithm (Minimum Spanning Tree) ---
Explanation:
    A greedy algorithm that finds a minimum spanning tree (MST) for a
    weighted undirected graph. It starts from an arbitrary vertex and
    grows the MST by adding the cheapest available edge that connects a
    vertex in the tree to a vertex outside the tree.
Pseudo Code:
    PROCEDURE Prim(Graph G, start_node)
        min_spanning_tree_edges = EMPTY_LIST
        visited_nodes = SET
        priority_queue = MIN_PRIORITY_QUEUE (stores triples of (weight, u, v))

        ADD start_node TO visited_nodes
        FOR EACH edge (start_node, neighbor, weight) IN G.ADJACENCY_LIST[start_node] DO
            INSERT(priority_queue, (weight, start_node, neighbor))
        END FOR

        WHILE NOT IS_EMPTY(priority_queue) AND LENGTH(visited_nodes) < NUMBER_OF_VERTICES(G) DO
            (weight, u, v) = EXTRACT_MIN(priority_queue)

            IF v NOT IN visited_nodes THEN
                ADD v TO visited_nodes
                ADD (u, v) TO min_spanning_tree_edges

                FOR EACH edge (v, neighbor, new_weight) IN G.ADJACENCY_LIST[v] DO
                    IF neighbor NOT IN visited_nodes THEN
                        INSERT(priority_queue, (new_weight, v, neighbor))
                    END IF
                END FOR
            END IF
        END WHILE
        RETURN min_spanning_tree_edges
    END PROCEDURE

--- Kruskal’s Algorithm (Minimum Spanning Tree) ---
Explanation:
    A greedy algorithm that finds a minimum spanning tree (MST) for a
    weighted undirected graph. It works by repeatedly adding the next
    cheapest edge in the graph, as long as it does not form a cycle with
    the already added edges. It typically uses a Union-Find data structure.
Pseudo Code:
    PROCEDURE Kruskal(Graph G)
        min_spanning_tree_edges = EMPTY_LIST
        edges = LIST of all edges in G, sorted by weight in ascending order
        CREATE DisjointSetUnion DSU (one set for each vertex)

        FOR EACH vertex v IN G.VERTICES DO
            MAKE_SET(DSU, v)
        END FOR

        FOR EACH edge (u, v, weight) IN edges DO
            IF FIND_SET(DSU, u) != FIND_SET(DSU, v) THEN
                ADD (u, v) TO min_spanning_tree_edges
                UNION_SETS(DSU, u, v)
            END IF
        END FOR
        RETURN min_spanning_tree_edges
    END PROCEDURE

--- Topological Sort (DAG Ordering) ---
Explanation:
    An ordering of the vertices of a directed acyclic graph (DAG) such that
    for every directed edge from vertex `u` to vertex `v`, `u` comes before
    `v` in the ordering. It's not unique for a given DAG.
Pseudo Code:
    // Kahn's Algorithm (using in-degrees)
    PROCEDURE TopologicalSort(Graph G)
        in_degrees = MAP from node to integer (count of incoming edges)
        queue = EMPTY_QUEUE
        topological_order = EMPTY_LIST
        
        // Calculate in-degrees for all nodes
        FOR EACH node u IN G.VERTICES DO
            in_degrees[u] = 0
        END FOR
        FOR EACH node u IN G.VERTICES DO
            FOR EACH neighbor v IN G.ADJACENCY_LIST[u] DO
                in_degrees[v] = in_degrees[v] + 1
            END FOR
        END FOR

        // Add nodes with in-degree 0 to the queue
        FOR EACH node u IN G.VERTICES DO
            IF in_degrees[u] == 0 THEN
                ENQUEUE(queue, u)
            END IF
        END FOR

        count = 0
        WHILE NOT IS_EMPTY(queue) DO
            u = DEQUEUE(queue)
            ADD u TO topological_order
            count = count + 1

            FOR EACH neighbor v IN G.ADJACENCY_LIST[u] DO
                in_degrees[v] = in_degrees[v] - 1
                IF in_degrees[v] == 0 THEN
                    ENQUEUE(queue, v)
                END IF
            END FOR
        END WHILE

        IF count != NUMBER_OF_VERTICES(G) THEN
            PRINT "Graph contains a cycle (not a DAG)"
            RETURN ERROR
        ELSE
            RETURN topological_order
        END IF
    END PROCEDURE

    // DFS-based algorithm (using recursion)
    PROCEDURE TopologicalSortDFS(Graph G)
        visited = SET
        recursion_stack = SET // To detect cycles
        order_stack = STACK // Stores the topological order
        
        FOR EACH vertex u IN G.VERTICES DO
            IF u NOT IN visited THEN
                DFS_Visit_Topological(G, u, visited, recursion_stack, order_stack)
            END IF
        END FOR

        RETURN order_stack (popped elements)
    END PROCEDURE

    PROCEDURE DFS_Visit_Topological(Graph G, u, visited, recursion_stack, order_stack)
        ADD u TO visited
        ADD u TO recursion_stack

        FOR EACH v IN G.ADJACENCY_LIST[u] DO
            IF v NOT IN visited THEN
                DFS_Visit_Topological(G, v, visited, recursion_stack, order_stack)
            ELSE IF v IN recursion_stack THEN
                PRINT "Graph contains a cycle (not a DAG)"
                // Handle cycle detection (e.g., throw error)
            END IF
        END FOR
        
        REMOVE u FROM recursion_stack
        PUSH(order_stack, u) // Push after all descendants are visited
    END PROCEDURE

--- Tarjan’s Algorithm (Strongly Connected Components) ---
Explanation:
    An algorithm for finding strongly connected components (SCCs) in a directed
    graph. An SCC is a maximal subgraph such that for every pair of vertices
    (u, v) in the subgraph, there is a path from u to v and a path from v to u.
    It uses Depth-First Search and maintains discovery times and low-link values.
Pseudo Code:
    PROCEDURE TarjanSCC(Graph G)
        index = 0
        stack = EMPTY_STACK
        on_stack = BOOLEAN_MAP initialized to FALSE
        disc = MAP from node to UNDEFINED // Discovery times
        low_link = MAP from node to UNDEFINED // Low-link values
        sccs = LIST of lists

        FOR EACH vertex u IN G.VERTICES DO
            IF disc[u] IS UNDEFINED THEN
                StrongConnect(G, u, index, stack, on_stack, disc, low_link, sccs)
            END IF
        END FOR
        RETURN sccs
    END PROCEDURE

    PROCEDURE StrongConnect(Graph G, u, index, stack, on_stack, disc, low_link, sccs)
        disc[u] = index
        low_link[u] = index
        index = index + 1
        PUSH(stack, u)
        on_stack[u] = TRUE

        FOR EACH v IN G.ADJACENCY_LIST[u] DO
            IF disc[v] IS UNDEFINED THEN
                StrongConnect(G, v, index, stack, on_stack, disc, low_link, sccs)
                low_link[u] = MIN(low_link[u], low_link[v])
            ELSE IF on_stack[v] THEN
                low_link[u] = MIN(low_link[u], disc[v])
            END IF
        END FOR

        IF low_link[u] == disc[u] THEN // u is root of an SCC
            current_scc = EMPTY_LIST
            LOOP
                w = POP(stack)
                on_stack[w] = FALSE
                ADD w TO current_scc
                IF w == u THEN BREAK
            END LOOP
            ADD current_scc TO sccs
        END IF
    END PROCEDURE

--- Kosaraju’s Algorithm (Strongly Connected Components) ---
Explanation:
    Another algorithm for finding strongly connected components (SCCs) in
    a directed graph. It involves two passes of Depth-First Search.
    First, perform DFS on the original graph to get finishing times.
    Second, perform DFS on the transpose (reverse) graph in decreasing
    order of finishing times.
Pseudo Code:
    PROCEDURE KosarajuSCC(Graph G)
        visited = SET
        order_stack = STACK // Stores vertices in order of finishing times
        sccs = LIST of lists

        // Step 1: DFS on G to get finishing times
        FOR EACH vertex u IN G.VERTICES DO
            IF u NOT IN visited THEN
                FillOrder(G, u, visited, order_stack)
            END IF
        END FOR

        // Step 2: Compute G_transpose (reverse all edges)
        G_transpose = Transpose(G)
        
        // Step 3: DFS on G_transpose in decreasing order of finishing times
        visited = SET // Reset visited
        WHILE NOT IS_EMPTY(order_stack) DO
            u = POP(order_stack)
            IF u NOT IN visited THEN
                current_scc = EMPTY_LIST
                DFS_Explore(G_transpose, u, visited, current_scc)
                ADD current_scc TO sccs
            END IF
        END WHILE
        RETURN sccs
    END PROCEDURE

    PROCEDURE FillOrder(Graph G, u, visited, order_stack)
        ADD u TO visited
        FOR EACH v IN G.ADJACENCY_LIST[u] DO
            IF v NOT IN visited THEN
                FillOrder(G, v, visited, order_stack)
            END IF
        END FOR
        PUSH(order_stack, u)
    END PROCEDURE

    PROCEDURE DFS_Explore(Graph G, u, visited, current_scc)
        ADD u TO visited
        ADD u TO current_scc
        FOR EACH v IN G.ADJACENCY_LIST[u] DO
            IF v NOT IN visited THEN
                DFS_Explore(G, v, visited, current_scc)
            END FOR
    END PROCEDURE

    PROCEDURE Transpose(Graph G)
        G_T = NEW Graph with same vertices as G
        FOR EACH vertex u IN G.VERTICES DO
            FOR EACH v IN G.ADJACENCY_LIST[u] DO
                ADD_EDGE(G_T, v, u) // Reverse edge
            END FOR
        END FOR
        RETURN G_T
    END PROCEDURE

--- Edmonds-Karp Algorithm (Maximum Flow) ---
Explanation:
    An implementation of the Ford-Fulkerson method for computing the maximum
    flow in a flow network. It uses Breadth-First Search (BFS) to find
    augmenting paths (paths from source to sink with available capacity)
    in the residual graph. It guarantees termination for rational capacities.
Pseudo Code:
    PROCEDURE EdmondsKarp(Graph G, source, sink)
        max_flow = 0
        residual_graph = G // Initialize residual graph with original capacities

        WHILE TRUE DO
            // Find an augmenting path using BFS in residual_graph
            (path_found, path, min_capacity) = BFS_FindPath(residual_graph, source, sink)
            
            IF NOT path_found THEN
                BREAK // No more augmenting paths
            END IF

            // Augment flow along the path
            max_flow = max_flow + min_capacity

            FOR i FROM 0 TO LENGTH(path)-2 DO
                u = path[i]
                v = path[i+1]
                // Decrease forward edge capacity
                residual_graph.CAPACITY[u][v] = residual_graph.CAPACITY[u][v] - min_capacity
                // Increase backward edge capacity (for residual graph)
                residual_graph.CAPACITY[v][u] = residual_graph.CAPACITY[v][u] + min_capacity
            END FOR
        END WHILE
        RETURN max_flow
    END PROCEDURE

    PROCEDURE BFS_FindPath(residual_graph, source, sink)
        parent = MAP from node to node // To reconstruct path
        queue = EMPTY_QUEUE
        visited = SET

        ENQUEUE(queue, source)
        ADD source TO visited
        parent[source] = NULL

        WHILE NOT IS_EMPTY(queue) DO
            u = DEQUEUE(queue)
            FOR EACH v IN residual_graph.ADJACENCY_LIST[u] DO
                IF v NOT IN visited AND residual_graph.CAPACITY[u][v] > 0 THEN
                    ADD v TO visited
                    parent[v] = u
                    ENQUEUE(queue, v)
                    IF v == sink THEN
                        // Path found, reconstruct and find min capacity
                        path = EMPTY_LIST
                        current = sink
                        min_cap = INFINITY
                        WHILE parent[current] IS NOT NULL DO
                            PREPEND current TO path
                            min_cap = MIN(min_cap, residual_graph.CAPACITY[parent[current]][current])
                            current = parent[current]
                        END WHILE
                        PREPEND source TO path
                        RETURN TRUE, path, min_cap
                    END IF
                END IF
            END FOR
        END WHILE
        RETURN FALSE, NULL, 0 // No path found
    END PROCEDURE

--- Ford-Fulkerson Algorithm (Maximum Flow) ---
Explanation:
    A method for computing the maximum flow in a flow network. It finds
    augmenting paths from the source to the sink in the residual graph and
    adds their capacities to the total flow until no more augmenting paths
    can be found. Edmonds-Karp is a specific implementation of Ford-Fulkerson.
Pseudo Code:
    PROCEDURE FordFulkerson(Graph G, source, sink)
        max_flow = 0
        residual_graph = G // Initialize residual graph with original capacities

        WHILE TRUE DO
            // Find an augmenting path in the residual graph (e.g., using DFS or BFS)
            // This example uses a generic FindAugmentingPath
            (path_found, path, min_capacity) = FindAugmentingPath(residual_graph, source, sink)
            
            IF NOT path_found THEN
                BREAK // No more augmenting paths
            END IF

            // Augment flow along the path
            max_flow = max_flow + min_capacity

            FOR i FROM 0 TO LENGTH(path)-2 DO
                u = path[i]
                v = path[i+1]
                residual_graph.CAPACITY[u][v] = residual_graph.CAPACITY[u][v] - min_capacity
                residual_graph.CAPACITY[v][u] = residual_graph.CAPACITY[v][u] + min_capacity // Backward edge
            END FOR
        END WHILE
        RETURN max_flow
    END PROCEDURE

    (Note: FindAugmentingPath can be implemented using BFS (Edmonds-Karp) or DFS.
    The pseudocode for BFS_FindPath from EdmondsKarp can be used here.)

--- Hopcroft-Karp Algorithm (Maximum Bipartite Matching) ---
Explanation:
    An algorithm that takes a bipartite graph and produces a maximum
    cardinality matching (a set of edges such that no two edges share a
    vertex and the set has the largest possible number of edges). It uses
    BFS and DFS to find augmenting paths of increasing length.
Pseudo Code:
    PROCEDURE HopcroftKarp(BipartiteGraph G)
        match = MAP from vertex to vertex (stores current matching)
        dist = MAP from vertex to integer (distance in BFS layers)
        
        matching_size = 0
        WHILE BFS_Layering(G, match, dist) IS TRUE DO
            FOR EACH u IN LEFT_PARTITION(G) DO
                IF match[u] IS NULL AND DFS_FindPath(G, u, match, dist) THEN
                    matching_size = matching_size + 1
                END IF
            END FOR
        END WHILE
        RETURN matching_size
    END PROCEDURE

    PROCEDURE BFS_Layering(G, match, dist)
        queue = EMPTY_QUEUE
        FOR EACH u IN LEFT_PARTITION(G) DO
            IF match[u] IS NULL THEN
                dist[u] = 0
                ENQUEUE(queue, u)
            ELSE
                dist[u] = INFINITY
            END IF
        END FOR
        dist[NULL_NODE] = INFINITY // Sentinel for unmatched
        
        WHILE NOT IS_EMPTY(queue) DO
            u = DEQUEUE(queue)
            IF dist[u] != INFINITY THEN
                FOR EACH v IN G.ADJACENCY_LIST[u] DO
                    IF dist[match[v]] == INFINITY THEN
                        dist[match[v]] = dist[u] + 1
                        ENQUEUE(queue, match[v])
                    END IF
                END FOR
            END IF
        END WHILE
        RETURN dist[NULL_NODE] != INFINITY
    END PROCEDURE

    PROCEDURE DFS_FindPath(G, u, match, dist)
        IF u IS NULL_NODE THEN
            RETURN TRUE
        END IF

        FOR EACH v IN G.ADJACENCY_LIST[u] DO
            IF dist[match[v]] == dist[u] + 1 THEN
                IF DFS_FindPath(G, match[v], match, dist) THEN
                    match[v] = u
                    match[u] = v
                    RETURN TRUE
                END IF
            END IF
        END FOR
        dist[u] = INFINITY // Backtrack, u cannot lead to augmenting path
        RETURN FALSE
    END PROCEDURE

--- Johnson’s Algorithm (Shortest Path for Sparse Graphs) ---
Explanation:
    An algorithm that finds the shortest paths between all pairs of vertices
    in a sparse, edge-weighted directed graph. It allows some negative edge
    weights but no negative cycles. It works by reweighting the edges using
    Bellman-Ford and then running Dijkstra from each vertex.
Pseudo Code:
    PROCEDURE Johnson(Graph G)
        // Step 1: Add a new source vertex S and edges from S to all other vertices with weight 0
        G_prime = AddSuperSource(G)

        // Step 2: Run Bellman-Ford from S
        (h_values, has_negative_cycle) = BellmanFord(G_prime, S)
        IF has_negative_cycle THEN
            PRINT "Graph contains negative cycle"
            RETURN ERROR
        END IF

        // Step 3: Reweight edges
        reweighted_graph = CreateNewGraph(G.VERTICES)
        FOR EACH edge (u, v, original_weight) IN G.EDGES DO
            new_weight = original_weight + h_values[u] - h_values[v]
            ADD_EDGE(reweighted_graph, u, v, new_weight)
        END FOR

        // Step 4: Run Dijkstra from each vertex on the reweighted graph
        all_pairs_shortest_paths = 2D ARRAY of size N x N
        FOR EACH vertex u IN G.VERTICES DO
            (d_u, _) = Dijkstra(reweighted_graph, u) // Dijkstra on reweighted graph
            FOR EACH vertex v IN G.VERTICES DO
                IF d_u[v] IS INFINITY THEN
                    all_pairs_shortest_paths[u][v] = INFINITY
                ELSE
                    all_pairs_shortest_paths[u][v] = d_u[v] - h_values[u] + h_values[v]
                END IF
            END FOR
        END FOR
        RETURN all_pairs_shortest_paths
    END PROCEDURE

    (Note: BellmanFord and Dijkstra procedures from above can be reused.)

================================
DYNAMIC PROGRAMMING (DP) ALGORITHMS
================================

--- Longest Common Subsequence (LCS) ---
Explanation:
    Finds the longest subsequence common to two sequences. A subsequence is
    a sequence that can be derived from another sequence by deleting some or
    no elements without changing the order of the remaining elements.
    It uses a 2D DP table to store the lengths of LCS for all prefixes.
Pseudo Code:
    PROCEDURE LCS(String X, String Y)
        m = LENGTH(X)
        n = LENGTH(Y)
        dp = 2D ARRAY of size (m+1) x (n+1) initialized to 0

        FOR i FROM 1 TO m
            FOR j FROM 1 TO n
                IF X[i-1] == Y[j-1] THEN // Characters match
                    dp[i][j] = 1 + dp[i-1][j-1]
                ELSE // Characters don't match
                    dp[i][j] = MAX(dp[i-1][j], dp[i][j-1])
                END IF
            END FOR
        END FOR
        RETURN dp[m][n] // Length of LCS
    END PROCEDURE

--- Longest Increasing Subsequence (LIS) ---
Explanation:
    Finds the length of the longest subsequence of a given sequence such
    that all elements of the subsequence are sorted in increasing order.
    It can be solved using dynamic programming or by maintaining an array
    of the smallest end element of all increasing subsequences of given length.
Pseudo Code:
    // O(N^2) DP approach
    PROCEDURE LIS_N_Squared(ARRAY A)
        n = LENGTH(A)
        dp = ARRAY of size n, initialized to 1 // dp[i] = LIS ending at index i

        FOR i FROM 1 TO n-1
            FOR j FROM 0 TO i-1
                IF A[i] > A[j] AND dp[i] < dp[j] + 1 THEN
                    dp[i] = dp[j] + 1
                END IF
            END FOR
        END FOR
        RETURN MAX_VALUE(dp) // Max value in dp array is the LIS length
    END PROCEDURE

    // O(N log N) approach using Patience Sorting principle
    PROCEDURE LIS_N_Log_N(ARRAY A)
        tails = EMPTY_LIST // Stores smallest end element of all increasing subsequences of length i+1
        FOR EACH num IN A DO
            IF IS_EMPTY(tails) OR num > LAST_ELEMENT(tails) THEN
                ADD num TO tails
            ELSE
                // Find smallest element in tails >= num using binary search
                // Replace that element with num
                // Example: Use lower_bound to find index
                idx = BINARY_SEARCH_FOR_INSERTION_POINT(tails, num)
                tails[idx] = num
            END IF
        END FOR
        RETURN LENGTH(tails)
    END PROCEDURE

--- Knapsack Problem (0/1 Knapsack, Fractional Knapsack) ---
Explanation:
    **0/1 Knapsack:** Given a set of items, each with a weight and a value,
    determine the number of each item to include in a collection so that
    the total weight is less than or equal to a given limit and the total
    value is as large as possible. Items cannot be broken (either take it or leave it).
    **Fractional Knapsack:** Similar to 0/1, but items can be broken into fractions.

Pseudo Code:
    // 0/1 Knapsack (Dynamic Programming)
    PROCEDURE ZeroOneKnapsack(weights, values, capacity)
        n = LENGTH(weights)
        dp = 2D ARRAY of size (n+1) x (capacity+1) initialized to 0

        FOR i FROM 1 TO n
            FOR w FROM 1 TO capacity
                IF weights[i-1] <= w THEN
                    // Max of (not including item i, including item i)
                    dp[i][w] = MAX(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])
                ELSE
                    dp[i][w] = dp[i-1][w] // Cannot include item i
                END IF
            END FOR
        END FOR
        RETURN dp[n][capacity]
    END PROCEDURE

    // Fractional Knapsack (Greedy Algorithm)
    PROCEDURE FractionalKnapsack(items, capacity)
        // items: list of (value, weight) pairs
        SORT items by (value / weight) in descending order

        total_value = 0
        current_weight = 0

        FOR EACH item IN items DO
            IF current_weight + item.weight <= capacity THEN
                total_value = total_value + item.value
                current_weight = current_weight + item.weight
            ELSE
                remaining_capacity = capacity - current_weight
                fraction = remaining_capacity / item.weight
                total_value = total_value + (item.value * fraction)
                current_weight = capacity
                BREAK // Knapsack is full
            END IF
        END FOR
        RETURN total_value
    END PROCEDURE

--- Matrix Chain Multiplication ---
Explanation:
    Finds the most efficient way to multiply a given sequence of matrices.
    The problem is not to perform the multiplications, but merely to decide
    the order in which to perform the multiplications. Matrix multiplication
    is associative, so the order can be changed.
Pseudo Code:
    PROCEDURE MatrixChainMultiplication(dimensions) // dimensions[i] is row_i, dimensions[i+1] is col_i
        n = LENGTH(dimensions) - 1 // Number of matrices
        dp = 2D ARRAY of size n x n // dp[i][j] = min scalar multiplications for A_i..A_j

        FOR length FROM 2 TO n // Length of chain
            FOR i FROM 0 TO n - length
                j = i + length - 1
                dp[i][j] = INFINITY
                FOR k FROM i TO j - 1
                    cost = dp[i][k] + dp[k+1][j] + dimensions[i] * dimensions[k+1] * dimensions[j+1]
                    IF cost < dp[i][j] THEN
                        dp[i][j] = cost
                    END IF
                END FOR
            END FOR
        END FOR
        RETURN dp[0][n-1]
    END PROCEDURE

--- Coin Change Problem ---
Explanation:
    Given a set of coin denominations and a target amount, find the minimum
    number of coins required to make that amount, or the number of ways to
    make that amount.
Pseudo Code:
    // Minimum Number of Coins
    PROCEDURE CoinChangeMinCoins(coins, amount)
        dp = ARRAY of size (amount + 1)
        dp[0] = 0
        FOR i FROM 1 TO amount
            dp[i] = INFINITY
        END FOR

        FOR i FROM 1 TO amount
            FOR EACH coin IN coins DO
                IF coin <= i THEN
                    IF dp[i - coin] != INFINITY THEN
                        dp[i] = MIN(dp[i], 1 + dp[i - coin])
                    END IF
                END IF
            END FOR
        END FOR
        IF dp[amount] == INFINITY THEN
            RETURN -1 // Cannot make the amount
        ELSE
            RETURN dp[amount]
        END IF
    END PROCEDURE

    // Number of Ways to Make Change
    PROCEDURE CoinChangeNumWays(coins, amount)
        dp = ARRAY of size (amount + 1) initialized to 0
        dp[0] = 1 // One way to make amount 0 (by using no coins)

        FOR EACH coin IN coins DO
            FOR i FROM coin TO amount
                dp[i] = dp[i] + dp[i - coin]
            END FOR
        END FOR
        RETURN dp[amount]
    END PROCEDURE

--- Subset Sum Problem ---
Explanation:
    Given a set of non-negative integers and a target sum, determine if there
    is a subset of the given set whose sum equals the target sum.
Pseudo Code:
    PROCEDURE SubsetSum(set, target_sum)
        n = LENGTH(set)
        dp = 2D BOOLEAN ARRAY of size (n+1) x (target_sum+1)

        // Initialize dp[i][0] to TRUE (empty set sums to 0)
        FOR i FROM 0 TO n
            dp[i][0] = TRUE
        END FOR
        // Initialize dp[0][j] to FALSE for j > 0 (cannot make sum > 0 with empty set)
        FOR j FROM 1 TO target_sum
            dp[0][j] = FALSE
        END FOR

        FOR i FROM 1 TO n
            FOR j FROM 1 TO target_sum
                IF j < set[i-1] THEN // Current element is too large
                    dp[i][j] = dp[i-1][j]
                ELSE // Either exclude or include current element
                    dp[i][j] = dp[i-1][j] OR dp[i-1][j - set[i-1]]
                END IF
            END FOR
        END FOR
        RETURN dp[n][target_sum]
    END PROCEDURE

--- Rod Cutting Problem ---
Explanation:
    Given a rod of length `n` and a table of prices `P_i` for rods of length
    `i`, determine the maximum revenue obtainable by cutting up the rod and
    selling the pieces.
Pseudo Code:
    PROCEDURE RodCutting(prices, n) // prices[i] is price for length i+1
        dp = ARRAY of size (n+1) initialized to 0
        
        FOR i FROM 1 TO n // Current rod length
            max_revenue_for_i = 0
            FOR j FROM 0 TO i-1 // Cut point for first piece (length j+1)
                max_revenue_for_i = MAX(max_revenue_for_i, prices[j] + dp[i - (j+1)])
            END FOR
            dp[i] = max_revenue_for_i
        END FOR
        RETURN dp[n]
    END PROCEDURE

--- Egg Dropping Problem ---
Explanation:
    Given `k` eggs and `n` floors, find the minimum number of trials in the
    worst case to determine the threshold floor `F` (the lowest floor from
    which an egg will break when dropped).
Pseudo Code:
    PROCEDURE EggDropping(k_eggs, n_floors)
        dp = 2D ARRAY of size (k_eggs + 1) x (n_floors + 1)

        // Base cases:
        // dp[i][0] = 0 (0 trials for 0 floors)
        // dp[1][j] = j (j trials for j floors with 1 egg)
        FOR j FROM 0 TO n_floors
            dp[1][j] = j
        END FOR

        FOR i FROM 2 TO k_eggs // For each egg count
            FOR j FROM 1 TO n_floors // For each floor count
                dp[i][j] = INFINITY
                // Try dropping from each floor x
                FOR x FROM 1 TO j
                    // If egg breaks, we have (i-1) eggs and (x-1) floors below
                    // If egg doesn't break, we have i eggs and (j-x) floors above
                    res = 1 + MAX(dp[i-1][x-1], dp[i][j-x])
                    dp[i][j] = MIN(dp[i][j], res)
                END FOR
            END FOR
        END FOR
        RETURN dp[k_eggs][n_floors]
    END PROCEDURE

--- Palindrome Partitioning ---
Explanation:
    Given a string, find the minimum cuts needed to partition it such that
    every substring of the partition is a palindrome.
Pseudo Code:
    PROCEDURE PalindromePartitioning(String S)
        n = LENGTH(S)
        is_palindrome = 2D BOOLEAN ARRAY of size n x n
        cuts = ARRAY of size n initialized to 0

        // Precompute all palindrome substrings
        FOR i FROM n-1 DOWNTO 0
            FOR j FROM i TO n-1
                IF S[i] == S[j] AND (j - i <= 1 OR is_palindrome[i+1][j-1]) THEN
                    is_palindrome[i][j] = TRUE
                ELSE
                    is_palindrome[i][j] = FALSE
                END IF
            END FOR
        END FOR

        // Compute minimum cuts
        FOR i FROM 0 TO n-1
            IF is_palindrome[0][i] THEN
                cuts[i] = 0 // If prefix is palindrome, 0 cuts needed
            ELSE
                cuts[i] = INFINITY
                FOR j FROM 0 TO i-1
                    IF is_palindrome[j+1][i] THEN
                        cuts[i] = MIN(cuts[i], 1 + cuts[j])
                    END IF
                END FOR
            END IF
        END FOR
        RETURN cuts[n-1]
    END PROCEDURE

--- Edit Distance (Levenshtein Distance) ---
Explanation:
    Calculates the minimum number of single-character edits (insertions,
    deletions, or substitutions) required to change one word into the other.
Pseudo Code:
    PROCEDURE EditDistance(String S1, String S2)
        m = LENGTH(S1)
        n = LENGTH(S2)
        dp = 2D ARRAY of size (m+1) x (n+1)

        // Initialize base cases
        FOR i FROM 0 TO m
            dp[i][0] = i // Cost of deleting i characters from S1 to get empty S2
        END FOR
        FOR j FROM 0 TO n
            dp[0][j] = j // Cost of inserting j characters into empty S1 to get S2
        END FOR

        FOR i FROM 1 TO m
            FOR j FROM 1 TO n
                cost_substitution = 0
                IF S1[i-1] != S2[j-1] THEN
                    cost_substitution = 1
                END IF

                dp[i][j] = MIN(
                    dp[i-1][j] + 1,           // Deletion from S1
                    dp[i][j-1] + 1,           // Insertion into S1 (deletion from S2)
                    dp[i-1][j-1] + cost_substitution // Substitution
                )
            END FOR
        END FOR
        RETURN dp[m][n]
    END PROCEDURE

--- Optimal Binary Search Tree ---
Explanation:
    Given a sorted sequence of keys and an array of frequencies for these
    keys, construct a Binary Search Tree (BST) that has the minimum cost.
    The cost is calculated as the sum of (frequency * depth) for all keys.
Pseudo Code:
    PROCEDURE OptimalBST(keys, frequencies, n)
        // keys: sorted array of keys
        // frequencies: frequencies of keys, frequencies[i] for keys[i]
        // n: number of keys

        cost = 2D ARRAY of size n x n // cost[i][j] stores cost of BST for keys[i..j]

        // Cost for single key
        FOR i FROM 0 TO n-1
            cost[i][i] = frequencies[i]
        END FOR

        // Fill table for chain lengths from 2 to n
        FOR length FROM 2 TO n
            FOR i FROM 0 TO n - length
                j = i + length - 1
                cost[i][j] = INFINITY
                sum_freq = SUM(frequencies, i, j) // Sum of frequencies from i to j

                FOR r FROM i TO j // r is the root of the current subtree
                    c = 0
                    IF r > i THEN
                        c = c + cost[i][r-1]
                    END IF
                    IF r < j THEN
                        c = c + cost[r+1][j]
                    END IF
                    
                    c = c + sum_freq
                    IF c < cost[i][j] THEN
                        cost[i][j] = c
                    END IF
                END FOR
            END FOR
        END FOR
        RETURN cost[0][n-1]
    END PROCEDURE

--- Wildcard Matching ---
Explanation:
    Given an input string `s` and a pattern `p`, implement wildcard matching
    with support for '?' (matches any single character) and '*' (matches any
    sequence of characters including the empty sequence).
Pseudo Code:
    PROCEDURE WildcardMatching(String s, String p)
        n = LENGTH(s)
        m = LENGTH(p)
        dp = 2D BOOLEAN ARRAY of size (n+1) x (m+1)

        dp[0][0] = TRUE // Empty string matches empty pattern

        // Handle patterns starting with '*'
        FOR j FROM 1 TO m
            IF p[j-1] == '*' THEN
                dp[0][j] = dp[0][j-1]
            END IF
        END FOR

        FOR i FROM 1 TO n
            FOR j FROM 1 TO m
                IF p[j-1] == s[i-1] OR p[j-1] == '?' THEN
                    dp[i][j] = dp[i-1][j-1]
                ELSE IF p[j-1] == '*' THEN
                    // '*' matches empty sequence (dp[i][j-1]) OR
                    // '*' matches one or more characters (dp[i-1][j])
                    dp[i][j] = dp[i][j-1] OR dp[i-1][j]
                ELSE
                    dp[i][j] = FALSE
                END IF
            END FOR
        END FOR
        RETURN dp[n][m]
    END PROCEDURE

--- Word Break Problem ---
Explanation:
    Given a string `s` and a dictionary of words `wordDict`, determine if `s`
    can be segmented into a space-separated sequence of one or more dictionary words.
Pseudo Code:
    PROCEDURE WordBreak(String s, Set wordDict)
        n = LENGTH(s)
        dp = BOOLEAN ARRAY of size (n+1)

        dp[0] = TRUE // Empty string can be segmented (base case)

        FOR i FROM 1 TO n
            FOR j FROM 0 TO i-1
                IF dp[j] AND SUBSTRING(s, j, i-j) IN wordDict THEN
                    dp[i] = TRUE
                    BREAK // Found a way to segment up to i
                END IF
            END FOR
        END FOR
        RETURN dp[n]
    END PROCEDURE

================================
GREEDY ALGORITHMS
================================

--- Activity Selection Problem ---
Explanation:
    Given a set of activities, each with a start and finish time, select the
    maximum number of non-overlapping activities that can be performed by
    a single person or machine.
Pseudo Code:
    PROCEDURE ActivitySelection(activities) // activities: list of (start_time, finish_time) pairs
        SORT activities by finish_time in ascending order

        selected_activities = EMPTY_LIST
        IF IS_EMPTY(activities) THEN
            RETURN selected_activities
        END IF

        ADD activities[0] TO selected_activities
        last_finish_time = activities[0].finish_time

        FOR i FROM 1 TO LENGTH(activities)-1 DO
            current_activity = activities[i]
            IF current_activity.start_time >= last_finish_time THEN
                ADD current_activity TO selected_activities
                last_finish_time = current_activity.finish_time
            END IF
        END FOR
        RETURN selected_activities
    END PROCEDURE

--- Huffman Coding (Compression) ---
Explanation:
    A greedy algorithm used for lossless data compression. It builds a binary
    tree to assign variable-length codes to input characters, with more
    frequent characters having shorter codes, resulting in optimal prefix codes.
Pseudo Code:
    PROCEDURE HuffmanCoding(frequencies) // frequencies: MAP from character to count
        CREATE MIN_PRIORITY_QUEUE pq
        FOR EACH char, freq IN frequencies DO
            INSERT(pq, NEW HuffmanNode(char, freq))
        END FOR

        WHILE LENGTH(pq) > 1 DO
            node1 = EXTRACT_MIN(pq)
            node2 = EXTRACT_MIN(pq)
            
            merged_freq = node1.frequency + node2.frequency
            merged_node = NEW HuffmanNode(NULL, merged_freq)
            merged_node.left = node1
            merged_node.right = node2
            INSERT(pq, merged_node)
        END WHILE
        
        root = EXTRACT_MIN(pq) // The single remaining node is the Huffman tree root
        
        // Generate codes (can be done with a DFS traversal)
        codes = MAP from character to string
        GenerateCodes(root, "", codes)
        RETURN codes, root
    END PROCEDURE

    PROCEDURE GenerateCodes(node, current_code, codes)
        IF node IS NULL THEN
            RETURN
        END IF
        IF node.character IS NOT NULL THEN // Leaf node
            codes[node.character] = current_code
        ELSE
            GenerateCodes(node.left, current_code + "0", codes)
            GenerateCodes(node.right, current_code + "1", codes)
        END IF
    END PROCEDURE

--- Job Scheduling Problem ---
Explanation:
    Given a set of jobs, each with a deadline and a profit, schedule a subset
    of jobs to maximize total profit, such that each job finishes by its
    deadline and only one job can be processed at a time.
Pseudo Code:
    PROCEDURE JobScheduling(jobs) // jobs: list of (job_id, deadline, profit)
        SORT jobs by profit in descending order

        max_deadline = 0
        FOR EACH job IN jobs DO
            max_deadline = MAX(max_deadline, job.deadline)
        END FOR

        result = ARRAY of size max_deadline initialized to NULL // Stores scheduled jobs
        total_profit = 0

        FOR EACH job IN jobs DO
            // Find a slot for the job, starting from its deadline backwards
            FOR i FROM job.deadline - 1 DOWNTO 0
                IF result[i] IS NULL THEN
                    result[i] = job.job_id
                    total_profit = total_profit + job.profit
                    BREAK
                END IF
            END FOR
        END FOR
        RETURN result, total_profit
    END PROCEDURE

--- Fractional Knapsack Problem ---
Explanation:
    (Revisited, see Knapsack Problem in DP)
    Given items with weights and values, maximize the total value in a knapsack
    of a given capacity. Items can be broken into fractions.
Pseudo Code:
    (See FractionalKnapsack in Knapsack Problem under DP)

--- Greedy Coloring (Graph Coloring) ---
Explanation:
    Assigns colors to vertices of a graph such that no two adjacent vertices
    have the same color, using the minimum possible number of colors. The greedy
    approach assigns the smallest available color to each vertex in some order.
Pseudo Code:
    PROCEDURE GreedyGraphColoring(Graph G)
        colors = MAP from vertex to integer (assigned color)
        
        FOR EACH vertex u IN G.VERTICES DO
            available_colors = SET of all possible colors (e.g., 1 to N)
            FOR EACH neighbor v IN G.ADJACENCY_LIST[u] DO
                IF colors[v] IS ASSIGNED THEN
                    REMOVE colors[v] FROM available_colors
                END IF
            END FOR
            
            // Assign the smallest available color
            min_color = SMALLEST_ELEMENT(available_colors)
            colors[u] = min_color
        END FOR
        RETURN colors
    END PROCEDURE

================================
DIVIDE AND CONQUER ALGORITHMS
================================

--- Merge Sort (Revisited) ---
Explanation:
    (Revisited, see Sorting Algorithms)
    A divide-and-conquer algorithm. It recursively divides the array into
    halves until it has single-element arrays. Then, it merges these smaller
    sorted arrays back together to produce a single sorted array.
Pseudo Code:
    (See MergeSort in Sorting Algorithms)

--- Quick Sort (Revisited) ---
Explanation:
    (Revisited, see Sorting Algorithms)
    A highly efficient, comparison-based sorting algorithm that uses a
    divide-and-conquer approach. It works by selecting a 'pivot' element
    from the array and partitioning the other elements into two sub-arrays,
    according to whether they are less than or greater than the pivot.
    The sub-arrays are then sorted recursively.
Pseudo Code:
    (See QuickSort in Sorting Algorithms)

--- Binary Search (Revisited) ---
Explanation:
    (Revisited, see Search Algorithms)
    An efficient algorithm for finding an item from a sorted list of items.
    It works by repeatedly dividing the search interval in half.
Pseudo Code:
    (See BinarySearch in Search Algorithms)

--- Strassen’s Matrix Multiplication ---
Explanation:
    A divide-and-conquer algorithm for matrix multiplication. It's asymptotically
    faster than the standard matrix multiplication algorithm for large matrices
    by reducing the number of recursive multiplications from 8 to 7.
Pseudo Code:
    PROCEDURE StrassenMatrixMultiply(Matrix A, Matrix B)
        n = DIMENSION(A) // Assumes square matrices of size 2^k x 2^k

        IF n == 1 THEN
            RETURN A[0][0] * B[0][0]
        END IF

        // Divide A and B into n/2 x n/2 sub-matrices
        A11, A12, A21, A22 = DIVIDE(A)
        B11, B12, B21, B22 = DIVIDE(B)

        // Compute 7 products recursively
        P1 = StrassenMatrixMultiply(A11 + A22, B11 + B22)
        P2 = StrassenMatrixMultiply(A21 + A22, B11)
        P3 = StrassenMatrixMultiply(A11, B12 - B22)
        P4 = StrassenMatrixMultiply(A22, B21 - B11)
        P5 = StrassenMatrixMultiply(A11 + A12, B22)
        P6 = StrassenMatrixMultiply(A21 - A11, B11 + B12)
        P7 = StrassenMatrixMultiply(A12 - A22, B21 + B22)

        // Combine products to get C sub-matrices
        C11 = P1 + P4 - P5 + P7
        C12 = P3 + P5
        C21 = P2 + P4
        C22 = P1 - P2 + P3 + P6

        RETURN COMBINE_MATRICES(C11, C12, C21, C22)
    END PROCEDURE

--- Karatsuba Algorithm (Fast Multiplication) ---
Explanation:
    A fast multiplication algorithm for multiplying two large numbers. It's
    a divide-and-conquer algorithm that reduces the number of single-digit
    multiplications required compared to the traditional long multiplication.
Pseudo Code:
    PROCEDURE KaratsubaMultiply(numX, numY) // numX, numY are large integers
        n = MAX(LENGTH(numX), LENGTH(numY))
        IF n < THRESHOLD THEN // Base case for small numbers, use traditional multiplication
            RETURN numX * numY
        END IF

        m = CEIL(n / 2) // Split point

        // Split numbers into two halves
        X_high, X_low = SPLIT(numX, m)
        Y_high, Y_low = SPLIT(numY, m)

        // Recursively compute three products
        Z0 = KaratsubaMultiply(X_low, Y_low)
        Z1 = KaratsubaMultiply(X_low + X_high, Y_low + Y_high)
        Z2 = KaratsubaMultiply(X_high, Y_high)

        // Combine results
        RETURN Z2 * (10^(2*m)) + (Z1 - Z2 - Z0) * (10^m) + Z0
    END PROCEDURE

--- Closest Pair of Points ---
Explanation:
    Given a set of n points in a 2D plane, find the pair of points that are
    closest to each other. It uses a divide-and-conquer approach.
Pseudo Code:
    PROCEDURE ClosestPair(Points P_x_sorted, P_y_sorted)
        n = LENGTH(P_x_sorted)
        IF n <= 3 THEN
            RETURN BruteForceClosestPair(P_x_sorted)
        END IF

        mid = n / 2
        mid_point = P_x_sorted[mid]

        // Divide points into left and right halves
        left_P_x = P_x_sorted[0 TO mid-1]
        right_P_x = P_x_sorted[mid TO n-1]
        
        left_P_y, right_P_y = SPLIT_BY_X_COORDINATE(P_y_sorted, mid_point.x)

        // Recursively find closest pairs in halves
        (d_left, pair_left) = ClosestPair(left_P_x, left_P_y)
        (d_right, pair_right) = ClosestPair(right_P_x, right_P_y)

        min_dist = MIN(d_left, d_right)
        closest_pair = IF d_left < d_right THEN pair_left ELSE pair_right

        // Consider points in the strip around the dividing line
        strip_points = EMPTY_LIST
        FOR EACH p IN P_y_sorted DO
            IF ABS(p.x - mid_point.x) < min_dist THEN
                ADD p TO strip_points
            END IF
        END FOR

        // Find closest pair in strip
        (strip_min_dist, strip_pair) = ClosestInStrip(strip_points, min_dist)

        IF strip_min_dist < min_dist THEN
            RETURN strip_min_dist, strip_pair
        ELSE
            RETURN min_dist, closest_pair
        END IF
    END PROCEDURE

    PROCEDURE ClosestInStrip(strip_points, current_min_dist)
        // Iterate through strip_points (which are y-sorted)
        // For each point, check only the next 7 points (a constant number)
        // because points further away won't be closer than current_min_dist
        min_dist_in_strip = current_min_dist
        closest_pair_in_strip = NULL

        FOR i FROM 0 TO LENGTH(strip_points)-1
            FOR j FROM i+1 TO MIN(i+7, LENGTH(strip_points)-1)
                dist = DISTANCE(strip_points[i], strip_points[j])
                IF dist < min_dist_in_strip THEN
                    min_dist_in_strip = dist
                    closest_pair_in_strip = (strip_points[i], strip_points[j])
                END IF
            END FOR
        END FOR
        RETURN min_dist_in_strip, closest_pair_in_strip
    END PROCEDURE

    PROCEDURE BruteForceClosestPair(Points P)
        // For N <= 3, compute all pairwise distances and return min
    END PROCEDURE

--- Maximum Subarray Problem (Kadane’s Algorithm, Divide and Conquer version) ---
Explanation:
    Finds the contiguous subarray within a one-dimensional array of numbers
    which has the largest sum. Kadane's algorithm is a greedy approach,
    but it can also be solved using divide and conquer.
Pseudo Code:
    // Divide and Conquer Approach
    PROCEDURE MaxSubarray(ARRAY A, low, high)
        IF low == high THEN
            RETURN A[low]
        END IF

        mid = (low + high) / 2
        
        // Max sum in left half
        max_left_sum = MaxSubarray(A, low, mid)
        
        // Max sum in right half
        max_right_sum = MaxSubarray(A, mid + 1, high)
        
        // Max sum crossing the midpoint
        max_cross_sum = MaxCrossingSubarray(A, low, mid, high)

        RETURN MAX(max_left_sum, max_right_sum, max_cross_sum)
    END PROCEDURE

    PROCEDURE MaxCrossingSubarray(ARRAY A, low, mid, high)
        left_sum = NEGATIVE_INFINITY
        current_sum = 0
        FOR i FROM mid DOWNTO low DO
            current_sum = current_sum + A[i]
            IF current_sum > left_sum THEN
                left_sum = current_sum
            END IF
        END FOR

        right_sum = NEGATIVE_INFINITY
        current_sum = 0
        FOR i FROM mid + 1 TO high DO
            current_sum = current_sum + A[i]
            IF current_sum > right_sum THEN
                right_sum = current_sum
            END IF
        END FOR

        RETURN left_sum + right_sum
    END PROCEDURE

    // Kadane's Algorithm (Greedy/DP)
    PROCEDURE Kadane(ARRAY A)
        max_so_far = A[0]
        current_max = A[0]
        
        FOR i FROM 1 TO LENGTH(A)-1 DO
            current_max = MAX(A[i], current_max + A[i])
            max_so_far = MAX(max_so_far, current_max)
        END FOR
        RETURN max_so_far
    END PROCEDURE

================================
MATHEMATICAL ALGORITHMS
================================

--- Greatest Common Divisor (GCD) (Euclidean Algorithm) ---
Explanation:
    Finds the largest positive integer that divides two or more integers
    without leaving a remainder. The Euclidean algorithm is an efficient
    method for computing GCD.
Pseudo Code:
    PROCEDURE GCD(a, b)
        WHILE b != 0 DO
            temp = b
            b = a MOD b
            a = temp
        END WHILE
        RETURN a
    END PROCEDURE

--- Least Common Multiple (LCM) ---
Explanation:
    Finds the smallest positive integer that is a multiple of two or more
    integers. It can be computed using the GCD: LCM(a, b) = (a * b) / GCD(a, b).
Pseudo Code:
    PROCEDURE LCM(a, b)
        RETURN (a * b) / GCD(a, b)
    END PROCEDURE

--- Sieve of Eratosthenes (Prime Numbers) ---
Explanation:
    An efficient algorithm for finding all prime numbers up to a specified integer.
    It works by iteratively marking as composite (i.e., not prime) the multiples
    of each prime, starting with the first prime number, 2.
Pseudo Code:
    PROCEDURE SieveOfEratosthenes(n)
        primes = BOOLEAN ARRAY of size (n+1) initialized to TRUE
        primes[0] = FALSE
        primes[1] = FALSE

        FOR p FROM 2 TO SQRT(n) DO
            IF primes[p] IS TRUE THEN // p is a prime
                FOR i FROM p*p TO n STEP p DO
                    primes[i] = FALSE // Mark multiples of p as composite
                END FOR
            END IF
        END FOR

        result = EMPTY_LIST
        FOR p FROM 2 TO n DO
            IF primes[p] IS TRUE THEN
                ADD p TO result
            END IF
        END FOR
        RETURN result
    END PROCEDURE

--- Modular Exponentiation ---
Explanation:
    An algorithm for computing the remainder when a large integer exponentiation
    (base^exponent) is divided by another integer (modulus). It's essential
    in cryptography.
Pseudo Code:
    PROCEDURE ModularExponentiation(base, exponent, modulus)
        result = 1
        base = base MOD modulus // Reduce base
        WHILE exponent > 0 DO
            IF exponent IS ODD THEN
                result = (result * base) MOD modulus
            END IF
            base = (base * base) MOD modulus
            exponent = exponent / 2 // Integer division
        END WHILE
        RETURN result
    END PROCEDURE

--- Extended Euclidean Algorithm ---
Explanation:
    An extension of the Euclidean algorithm. It computes not only the GCD(a, b)
    but also integers x and y such that ax + by = GCD(a, b). It's used to
    find modular multiplicative inverses.
Pseudo Code:
    PROCEDURE ExtendedEuclidean(a, b)
        IF a == 0 THEN
            RETURN b, 0, 1 // Returns (gcd, x, y)
        END IF
        
        (gcd, x1, y1) = ExtendedEuclidean(b MOD a, a)
        
        x = y1 - (b / a) * x1
        y = x1
        
        RETURN gcd, x, y
    END PROCEDURE

--- Fast Fourier Transform (FFT) ---
Explanation:
    An efficient algorithm to compute the discrete Fourier transform (DFT)
    and its inverse. It transforms a signal from its original domain (e.g.,
    time) to a frequency domain representation. Used in signal processing,
    multiplication of large numbers, etc.
Pseudo Code:
    (Highly complex, conceptual outline for Iterative Cooley-Tukey FFT)
    PROCEDURE FFT(A, INVERSE_FFT_FLAG) // A: array of complex numbers (coefficients)
        n = LENGTH(A)
        IF n == 1 THEN
            RETURN A
        END IF

        // Bit-reversal permutation (reorder array for iterative approach)
        A = BitReversePermutation(A)

        FOR len FROM 2 TO n STEP len * 2 DO
            omega_n = EXP(2 * PI * i / len) // Primitive nth root of unity
            IF INVERSE_FFT_FLAG THEN
                omega_n = 1 / omega_n // Inverse FFT
            END IF
            
            FOR i FROM 0 TO n-1 STEP len DO
                omega = 1
                FOR j FROM 0 TO len/2 - 1 DO
                    u = A[i + j]
                    v = A[i + j + len/2] * omega
                    A[i + j] = u + v
                    A[i + j + len/2] = u - v
                    omega = omega * omega_n
                END FOR
            END FOR
        END FOR
        
        IF INVERSE_FFT_FLAG THEN
            FOR i FROM 0 TO n-1 DO
                A[i] = A[i] / n
            END FOR
        END IF
        RETURN A
    END PROCEDURE

--- Chinese Remainder Theorem ---
Explanation:
    A theorem that provides a unique solution to a system of linear
    congruences, provided that the moduli are pairwise coprime.
Pseudo Code:
    PROCEDURE ChineseRemainderTheorem(remainders, moduli)
        // remainders: list of a_i
        // moduli: list of n_i (must be pairwise coprime)
        
        product_moduli = PRODUCT(moduli) // N = n_1 * n_2 * ... * n_k
        sum_x = 0

        FOR i FROM 0 TO LENGTH(remainders)-1 DO
            current_remainder = remainders[i]
            current_modulus = moduli[i]
            
            Ni = product_moduli / current_modulus
            
            // Find modular inverse of Ni modulo current_modulus
            // Use Extended Euclidean Algorithm: Ni * xi + current_modulus * yi = 1
            // We need xi = modular_inverse(Ni, current_modulus)
            (_, modular_inverse_Ni, _) = ExtendedEuclidean(Ni, current_modulus)
            
            // Ensure modular_inverse_Ni is positive
            modular_inverse_Ni = (modular_inverse_Ni % current_modulus + current_modulus) % current_modulus

            term = current_remainder * Ni * modular_inverse_Ni
            sum_x = sum_x + term
        END FOR
        RETURN sum_x MOD product_moduli
    END PROCEDURE

--- Fermat’s Little Theorem ---
Explanation:
    A theorem in number theory stating that if `p` is a prime number, then
    for any integer `a` not divisible by `p`, the number `a^(p-1) - 1` is an
    integer multiple of `p`. This can be written as `a^(p-1) ≡ 1 (mod p)`.
    Also, `a^p ≡ a (mod p)` for any integer `a`.
Pseudo Code:
    (No direct algorithm, rather a property used in other algorithms like primality testing, modular inverse)
    // To check if a number 'p' is likely prime using Fermat's Little Theorem:
    PROCEDURE FermatPrimalityTest(n, num_iterations)
        IF n <= 1 THEN RETURN FALSE
        IF n <= 3 THEN RETURN TRUE
        FOR i FROM 1 TO num_iterations DO
            a = RANDOM_INTEGER(2, n-2)
            IF ModularExponentiation(a, n-1, n) != 1 THEN
                RETURN FALSE // n is composite
            END IF
        END FOR
        RETURN TRUE // n is likely prime
    END PROCEDURE

--- Wilson’s Theorem ---
Explanation:
    A theorem in number theory stating that a natural number `n > 1` is a
    prime number if and only if `(n - 1)! ≡ -1 (mod n)`.
Pseudo Code:
    (No direct algorithm, rather a property)
    // To check if a number 'n' is prime using Wilson's Theorem (computationally expensive)
    PROCEDURE WilsonPrimalityTest(n)
        IF n <= 1 THEN RETURN FALSE
        IF n == 2 THEN RETURN TRUE
        factorial_n_minus_1 = 1
        FOR i FROM 1 TO n-1 DO
            factorial_n_minus_1 = (factorial_n_minus_1 * i) MOD n
        END FOR
        IF factorial_n_minus_1 == n - 1 THEN // n-1 is equivalent to -1 mod n
            RETURN TRUE
        ELSE
            RETURN FALSE
        END IF
    END PROCEDURE

--- Discrete Logarithm Problem ---
Explanation:
    Given a prime `p`, a primitive root `g` modulo `p`, and an integer `y`,
    find the integer `x` such that `g^x ≡ y (mod p)`. This `x` is the discrete
    logarithm of `y` to the base `g` modulo `p`. There's no known efficient
    polynomial-time algorithm for general instances, which forms the basis
    of many cryptographic systems.
Pseudo Code:
    (No efficient general algorithm known; brute-force is to try x from 0 to p-2)
    PROCEDURE BruteForceDiscreteLog(g, y, p)
        FOR x FROM 0 TO p-2 DO
            IF ModularExponentiation(g, x, p) == y THEN
                RETURN x
            END IF
        END FOR
        RETURN -1 // No solution found (or y is not in the group)
    END PROCEDURE

--- Miller-Rabin Primality Test ---
Explanation:
    A probabilistic primality test used to determine if a given number is prime.
    It's more efficient and reliable than Fermat's Little Theorem for primality
    testing.
Pseudo Code:
    PROCEDURE MillerRabin(n, k_iterations)
        IF n <= 1 THEN RETURN FALSE
        IF n <= 3 THEN RETURN TRUE
        IF n IS EVEN THEN RETURN FALSE

        // Write n-1 as 2^s * d, where d is odd
        d = n - 1
        s = 0
        WHILE d IS EVEN DO
            d = d / 2
            s = s + 1
        END WHILE

        FOR i FROM 1 TO k_iterations DO
            a = RANDOM_INTEGER(2, n-2) // 'witness'
            x = ModularExponentiation(a, d, n)

            IF x == 1 OR x == n-1 THEN
                CONTINUE // Potentially prime, try next witness
            END IF

            FOR r FROM 1 TO s-1 DO
                x = ModularExponentiation(x, 2, n)
                IF x == n-1 THEN
                    BREAK // Potentially prime, try next witness
                END IF
                IF x == 1 THEN
                    RETURN FALSE // Composite
                END IF
            END FOR
            IF x != n-1 THEN
                RETURN FALSE // Composite
            END IF
        END FOR
        RETURN TRUE // Likely prime
    END PROCEDURE

--- Pollard’s Rho Algorithm (Factorization) ---
Explanation:
    A specialized integer factorization algorithm, particularly effective for
    finding small factors of a composite number. It's a probabilistic algorithm.
Pseudo Code:
    PROCEDURE PollardRho(n)
        IF n IS EVEN THEN RETURN 2
        IF n == 1 THEN RETURN 1

        x = RANDOM_INTEGER(2, n-1)
        y = x
        d = 1
        
        // Define a pseudo-random function, e.g., f(x) = (x^2 + c) mod n
        c = RANDOM_INTEGER(1, n-1)

        WHILE d == 1 DO
            x = (x*x + c) MOD n
            y = (y*y + c) MOD n
            y = (y*y + c) MOD n // Move y twice as fast
            
            d = GCD(ABS(x - y), n)

            IF d == n THEN
                // Cycle detected, try different c or starting x
                // For simplicity, this implementation might return fail or re-start
                RETURN PollardRho(n) // Restart with new random values
            END IF
        END WHILE
        RETURN d
    END PROCEDURE

================================
STRING ALGORITHMS
================================

--- Knuth-Morris-Pratt (KMP) Algorithm (Pattern Matching) ---
Explanation:
    An efficient string-searching algorithm that finds occurrences of a
    "word" (pattern) within a longer "text". It avoids re-examining
    characters already matched, by pre-processing the pattern to build
    a "longest proper prefix suffix" (LPS) array.
Pseudo Code:
    PROCEDURE KMP(text, pattern)
        n = LENGTH(text)
        m = LENGTH(pattern)
        IF m == 0 THEN RETURN 0 // Empty pattern matches at index 0

        lps = ComputeLPSArray(pattern) // LPS array (prefix function)
        
        i = 0 // index for text
        j = 0 // index for pattern

        WHILE i < n DO
            IF pattern[j] == text[i] THEN
                i = i + 1
                j = j + 1
            END IF

            IF j == m THEN
                PRINT "Pattern found at index " (i - j)
                j = lps[j-1] // Shift pattern to find next occurrence
            ELSE IF i < n AND pattern[j] != text[i] THEN
                IF j != 0 THEN
                    j = lps[j-1] // Fallback using LPS array
                ELSE
                    i = i + 1 // Move to next character in text
                END IF
            END IF
        END WHILE
    END PROCEDURE

    PROCEDURE ComputeLPSArray(pattern)
        m = LENGTH(pattern)
        lps = ARRAY of size m initialized to 0
        length = 0 // Length of the previous longest prefix suffix
        i = 1

        WHILE i < m DO
            IF pattern[i] == pattern[length] THEN
                length = length + 1
                lps[i] = length
                i = i + 1
            ELSE // Mismatch
                IF length != 0 THEN
                    length = lps[length - 1]
                ELSE // length is 0
                    lps[i] = 0
                    i = i + 1
                END IF
            END IF
        END WHILE
        RETURN lps
    END PROCEDURE

--- Rabin-Karp Algorithm (Pattern Matching) ---
Explanation:
    A string-searching algorithm that uses hashing to find any one of a
    set of pattern strings in a text. It uses a rolling hash function to
    quickly compare substrings of the text with the pattern.
Pseudo Code:
    PROCEDURE RabinKarp(text, pattern, prime_modulus, base)
        n = LENGTH(text)
        m = LENGTH(pattern)
        IF m == 0 THEN RETURN 0
        IF m > n THEN RETURN -1

        pattern_hash = 0
        text_hash = 0
        h = 1 // h = base^(m-1) % prime_modulus

        FOR i FROM 0 TO m-2 DO
            h = (h * base) MOD prime_modulus
        END FOR

        // Calculate initial hashes for pattern and first text window
        FOR i FROM 0 TO m-1 DO
            pattern_hash = (pattern_hash * base + pattern[i]) MOD prime_modulus
            text_hash = (text_hash * base + text[i]) MOD prime_modulus
        END FOR

        FOR i FROM 0 TO n - m DO
            IF pattern_hash == text_hash THEN
                // Potential match, verify character by character (to handle hash collisions)
                IF SUBSTRING(text, i, m) == pattern THEN
                    PRINT "Pattern found at index " i
                END IF
            END IF

            // Roll hash for next window
            IF i < n - m THEN
                text_hash = (base * (text_hash - text[i] * h) + text[i + m]) MOD prime_modulus
                // Ensure text_hash is positive
                IF text_hash < 0 THEN
                    text_hash = text_hash + prime_modulus
                END IF
            END IF
        END FOR
    END PROCEDURE

--- Z Algorithm (Pattern Matching) ---
Explanation:
    An efficient string matching algorithm that finds all occurrences of a
    pattern `P` in a text `T`. It constructs a "Z-array" where Z[i] stores
    the length of the longest substring starting at `i` that is also a prefix
    of the string itself.
Pseudo Code:
    PROCEDURE ZAlgorithm(String S) // S = Pattern + "$" + Text
        n = LENGTH(S)
        Z = ARRAY of size n initialized to 0
        L = 0, R = 0 // [L, R] is the Z-box

        FOR i FROM 1 TO n-1 DO
            IF i > R THEN
                L = i
                R = i
                WHILE R < n AND S[R-L] == S[R] DO
                    R = R + 1
                END WHILE
                Z[i] = R - L
                R = R - 1
            ELSE
                k = i - L
                IF Z[k] < R - i + 1 THEN
                    Z[i] = Z[k]
                ELSE
                    L = i
                    WHILE R < n AND S[R-L] == S[R] DO
                        R = R + 1
                    END WHILE
                    Z[i] = R - L
                    R = R - 1
                END IF
            END IF
        END FOR
        RETURN Z
    END PROCEDURE

    // For Pattern Matching:
    // Concatenate Pattern + "$" + Text
    // Compute Z-array for this concatenated string.
    // Any Z[i] value equal to LENGTH(Pattern) indicates a match.

--- Aho-Corasick Algorithm (Pattern Matching) ---
Explanation:
    A dictionary-matching algorithm that locates elements of a finite set of
    strings (the "dictionary") within an input text. It builds a trie of the
    dictionary words and then adds "failure links" to allow fast transitions
    between failed string matches to other branches of the trie.
Pseudo Code:
    (Conceptual, building Aho-Corasick automaton is complex)
    PROCEDURE AhoCorasick(dictionary_words, text)
        // Step 1: Build Trie (Goto Function)
        root = CREATE_TRIE_NODE()
        FOR EACH word IN dictionary_words DO
            INSERT_WORD_IN_TRIE(root, word)
        END FOR

        // Step 2: Build Failure Links (BFS traversal of Trie)
        queue = EMPTY_QUEUE
        FOR EACH child C of root DO
            ENQUEUE(queue, C)
            C.failure_link = root
        END FOR

        WHILE NOT IS_EMPTY(queue) DO
            current_node = DEQUEUE(queue)
            FOR EACH child C of current_node DO
                failure = current_node.failure_link
                WHILE failure IS NOT NULL AND failure.next_node(C.char) IS NULL DO
                    failure = failure.failure_link
                END WHILE
                IF failure IS NULL THEN
                    C.failure_link = root
                ELSE
                    C.failure_link = failure.next_node(C.char)
                END IF
                // Add output links (optional, for all matches ending at this point)
                // C.output_link = If C.failure_link is a dictionary word, C.failure_link, else C.failure_link.output_link
                ENQUEUE(queue, C)
            END FOR
        END WHILE

        // Step 3: Search text
        current_state = root
        FOR EACH char IN text DO
            WHILE current_state IS NOT NULL AND current_state.next_node(char) IS NULL DO
                current_state = current_state.failure_link
            END WHILE
            IF current_state IS NULL THEN
                current_state = root
            ELSE
                current_state = current_state.next_node(char)
            END IF
            
            // Output matches found at current_state and through output links
            node_to_output = current_state
            WHILE node_to_output IS NOT NULL AND node_to_output IS_DICTIONARY_WORD THEN
                PRINT "Found word ending at current position: " node_to_output.word
                node_to_output = node_to_output.output_link // Follow output links
            END WHILE
        END FOR
    END PROCEDURE

--- Suffix Tree Construction ---
Explanation:
    A data structure that contains all suffixes of a given string as explicit
    paths from the root, compressed to represent common prefixes efficiently.
    Used for various string problems like pattern matching, longest repeated
    substring, etc.
Pseudo Code:
    (Highly complex, typically uses Ukkonen's algorithm for linear time construction)
    PROCEDURE UkkonenSuffixTreeConstruction(String S)
        // Conceptual steps:
        // Initialize an empty suffix tree with a root node.
        // For each character in the string, incrementally add all suffixes.
        // Maintain implicit and explicit suffixes.
        // Use suffix links to avoid redundant traversals.
        // Apply "extension rules" to create new nodes and edges.
        // Rules involve active point, active edge, active length.
        RETURN SuffixTree_Object
    END PROCEDURE

--- Suffix Array Construction ---
Explanation:
    A sorted array of all suffixes of a given string. It's an alternative to
    suffix trees, often more memory-efficient. Used for various string
    matching and bioinformatics problems.
Pseudo Code:
    PROCEDURE SuffixArrayConstruction(String S)
        n = LENGTH(S)
        suffixes = LIST of (suffix, index) pairs

        FOR i FROM 0 TO n-1 DO
            ADD (SUBSTRING(S, i), i) TO suffixes
        END FOR

        SORT suffixes lexicographically

        suffix_array = ARRAY of size n
        FOR i FROM 0 TO n-1 DO
            suffix_array[i] = suffixes[i].index
        END FOR
        RETURN suffix_array
    END PROCEDURE

    (Note: More efficient algorithms like DC3/Skew algorithm or Suffix Array construction using LCP array exist, typically O(N log N) or O(N).)

--- Manacher’s Algorithm (Longest Palindromic Substring) ---
Explanation:
    An algorithm that finds the longest palindromic substring in a string
    in linear time. It does this by expanding around a center, but with
    optimizations to avoid re-computations for overlapping palindromes.
Pseudo Code:
    PROCEDURE Manacher(String S)
        // Transform S to handle even-length palindromes (e.g., "aba" -> "^#a#b#a#$")
        transformed_s = TransformString(S)
        n = LENGTH(transformed_s)
        P = ARRAY of size n initialized to 0 // P[i] = radius of palindrome centered at i

        center = 0 // Center of the current longest palindrome found
        right = 0  // Right boundary of the current longest palindrome found

        max_len = 0
        max_center_idx = 0

        FOR i FROM 1 TO n-1 DO
            mirror_i = 2 * center - i // Mirror index of i relative to center

            IF i < right THEN
                P[i] = MIN(right - i, P[mirror_i])
            END IF

            // Attempt to expand palindrome centered at i
            a = i + (1 + P[i])
            b = i - (1 + P[i])
            WHILE a < n AND b >= 0 AND transformed_s[a] == transformed_s[b] DO
                P[i] = P[i] + 1
                a = a + 1
                b = b - 1
            END WHILE

            // If palindrome centered at i expands past 'right', update 'center' and 'right'
            IF i + P[i] > right THEN
                center = i
                right = i + P[i]
            END IF

            // Update max_len and max_center_idx
            IF P[i] > max_len THEN
                max_len = P[i]
                max_center_idx = i
            END IF
        END FOR
        
        // Reconstruct longest palindromic substring from max_center_idx and max_len
        // The length of the original palindrome is max_len.
        // Start index in transformed_s is (max_center_idx - max_len)
        // Start index in original S is (max_center_idx - max_len) / 2
        RETURN EXTRACT_ORIGINAL_PALINDROME(transformed_s, max_center_idx, max_len)
    END PROCEDURE

    PROCEDURE TransformString(S)
        // Example: "aba" -> "^#a#b#a#$"
        // Pad with '#' and add sentinels '^' and '$'
    END PROCEDURE

--- Trie Construction (Prefix Tree) ---
Explanation:
    A tree-like data structure that stores a dynamic set or associative array
    where keys are usually strings. Each node represents a prefix, and the
    children of a node are all characters that can follow that prefix.
    Efficient for prefix-based searches and autocomplete.
Pseudo Code:
    CLASS TrieNode
        children = MAP from character to TrieNode
        is_end_of_word = BOOLEAN (default: FALSE)
    END CLASS

    PROCEDURE TrieConstruction()
        root = NEW TrieNode()
        RETURN root
    END PROCEDURE

    PROCEDURE InsertWord(root, word)
        current = root
        FOR EACH char IN word DO
            IF char NOT IN current.children THEN
                current.children[char] = NEW TrieNode()
            END IF
            current = current.children[char]
        END FOR
        current.is_end_of_word = TRUE
    END PROCEDURE

    PROCEDURE SearchWord(root, word)
        current = root
        FOR EACH char IN word DO
            IF char NOT IN current.children THEN
                RETURN FALSE
            END IF
            current = current.children[char]
        END FOR
        RETURN current.is_end_of_word
    END PROCEDURE

    PROCEDURE SearchPrefix(root, prefix)
        current = root
        FOR EACH char IN prefix DO
            IF char NOT IN current.children THEN
                RETURN FALSE
            END IF
            current = current.children[char]
        END FOR
        RETURN TRUE
    END PROCEDURE

--- Boyer-Moore Algorithm (Pattern Matching) ---
Explanation:
    An efficient string-searching algorithm. It preprocesses the pattern
    (not the text) and uses two heuristics ("bad character rule" and
    "good suffix rule") to skip as many characters as possible in the text
    during matching, allowing it to often run in sublinear time.
Pseudo Code:
    (Conceptual, implementation details for rules are complex)
    PROCEDURE BoyerMoore(text, pattern)
        n = LENGTH(text)
        m = LENGTH(pattern)
        IF m == 0 THEN RETURN 0
        IF m > n THEN RETURN -1

        // Preprocessing:
        // 1. Bad Character Rule table (occurrence table)
        bad_char_shift = BuildBadCharTable(pattern)
        // 2. Good Suffix Rule table (borders array for shifts)
        good_suffix_shift = BuildGoodSuffixTable(pattern)
        
        s = 0 // Shift of the pattern with respect to text
        WHILE s <= (n - m) DO
            j = m - 1 // Start comparing from end of pattern
            WHILE j >= 0 AND pattern[j] == text[s + j] DO
                j = j - 1
            END WHILE

            IF j < 0 THEN
                PRINT "Pattern found at index " s
                // Shift pattern to find next occurrence
                s = s + good_suffix_shift[0] // or use good_suffix_shift[m]
            ELSE
                // Mismatch at text[s+j] and pattern[j]
                // Calculate shifts from both rules and take maximum
                shift_bad_char = MAX(1, j - bad_char_shift[text[s+j]])
                shift_good_suffix = good_suffix_shift[j+1] // Or similar logic based on border array

                s = s + MAX(shift_bad_char, shift_good_suffix)
            END IF
        END WHILE
    END PROCEDURE

--- Longest Common Substring ---
Explanation:
    Finds the longest string that is a substring of two or more strings.
    Unlike subsequence, a substring must be contiguous.
Pseudo Code:
    PROCEDURE LongestCommonSubstring(String S1, String S2)
        m = LENGTH(S1)
        n = LENGTH(S2)
        dp = 2D ARRAY of size (m+1) x (n+1) initialized to 0

        max_length = 0
        end_index_s1 = 0 // To reconstruct the substring

        FOR i FROM 1 TO m
            FOR j FROM 1 TO n
                IF S1[i-1] == S2[j-1] THEN
                    dp[i][j] = 1 + dp[i-1][j-1]
                    IF dp[i][j] > max_length THEN
                        max_length = dp[i][j]
                        end_index_s1 = i - 1
                    END IF
                ELSE
                    dp[i][j] = 0 // Mismatch breaks contiguous substring
                END IF
            END FOR
        END FOR
        
        IF max_length > 0 THEN
            RETURN SUBSTRING(S1, end_index_s1 - max_length + 1, max_length)
        ELSE
            RETURN ""
        END IF
    END PROCEDURE

--- Edit Distance Algorithm (Revisited) ---
Explanation:
    (Revisited, see Dynamic Programming)
    Calculates the minimum number of single-character edits (insertions,
    deletions, or substitutions) required to change one word into the other.
Pseudo Code:
    (See EditDistance in Dynamic Programming)

================================
NUMBER THEORY AND CRYPTOGRAPHY
================================

--- RSA Algorithm ---
Explanation:
    A public-key cryptosystem widely used for secure data transmission.
    It relies on the computational difficulty of factoring large numbers.
    It involves key generation (public and private), encryption, and decryption.
Pseudo Code:
    // Key Generation
    PROCEDURE RSA_KeyGeneration()
        1. Choose two large distinct prime numbers, p and q.
        2. Calculate n = p * q.
        3. Calculate Euler's totient function: phi(n) = (p-1) * (q-1).
        4. Choose an integer e such that 1 < e < phi(n) and GCD(e, phi(n)) = 1. (e is the public exponent)
        5. Calculate d such that d * e ≡ 1 (mod phi(n)). (d is the private exponent, modular multiplicative inverse of e mod phi(n))
        6. Public key: (e, n)
        7. Private key: (d, n)
        RETURN (public_key, private_key)
    END PROCEDURE

    // Encryption
    PROCEDURE RSA_Encrypt(message_M, public_key_E, public_key_N)
        // message_M must be an integer < public_key_N
        ciphertext_C = ModularExponentiation(message_M, public_key_E, public_key_N)
        RETURN ciphertext_C
    END PROCEDURE

    // Decryption
    PROCEDURE RSA_Decrypt(ciphertext_C, private_key_D, private_key_N)
        decrypted_M = ModularExponentiation(ciphertext_C, private_key_D, private_key_N)
        RETURN decrypted_M
    END PROCEDURE

--- Diffie-Hellman Key Exchange ---
Explanation:
    A method of securely exchanging cryptographic keys over a public channel.
    It allows two parties who have no prior knowledge of each other to jointly
    establish a shared secret key. It relies on the difficulty of the discrete
    logarithm problem.
Pseudo Code:
    PROCEDURE DiffieHellman()
        // Publicly agreed parameters (large prime p, generator g mod p)
        // These can be publicly known.
        p = LargePrimeNumber // e.g., 23
        g = GeneratorModuloP // e.g., 5 (primitive root mod p)

        // Alice's side
        Alice_private_key_a = RANDOM_INTEGER(2, p-2) // Alice's secret integer
        Alice_public_value_A = ModularExponentiation(g, Alice_private_key_a, p) // Alice sends A to Bob

        // Bob's side
        Bob_private_key_b = RANDOM_INTEGER(2, p-2) // Bob's secret integer
        Bob_public_value_B = ModularExponentiation(g, Bob_private_key_b, p) // Bob sends B to Alice

        // Alice computes shared secret
        Alice_shared_secret = ModularExponentiation(Bob_public_value_B, Alice_private_key_a, p)

        // Bob computes shared secret
        Bob_shared_secret = ModularExponentiation(Alice_public_value_A, Bob_private_key_b, p)

        // Alice_shared_secret == Bob_shared_secret now. This is their shared secret key.
        RETURN Alice_shared_secret // Or Bob_shared_secret, they are identical
    END PROCEDURE

--- Elliptic Curve Cryptography (ECC) ---
Explanation:
    A public-key cryptosystem that provides a high level of security with
    smaller key sizes compared to RSA. It relies on the mathematical properties
    of elliptic curves over finite fields, specifically the difficulty of the
    elliptic curve discrete logarithm problem.
Pseudo Code:
    (Highly complex, involves elliptic curve point arithmetic)
    // Core idea:
    // Choose an elliptic curve E, a base point G on E, and a prime field Fp. (Public parameters)
    // Alice's Private Key: a random integer `a`.
    // Alice's Public Key: `A = aG` (point multiplication, G added `a` times to itself).
    // Bob's Private Key: a random integer `b`.
    // Bob's Public Key: `B = bG`.
    // Shared Secret: `aS = a(bG) = b(aG) = abG`.

    PROCEDURE ECC_KeyGeneration(Curve E, BasePoint G)
        private_key_d = RANDOM_INTEGER(1, ORDER_OF_G)
        public_key_Q = POINT_MULTIPLY(G, private_key_d, E) // d * G
        RETURN (private_key_d, public_key_Q)
    END PROCEDURE

    PROCEDURE ECC_KeyAgreement(private_key_d_A, public_key_Q_B, Curve E)
        shared_secret_point = POINT_MULTIPLY(public_key_Q_B, private_key_d_A, E) // d_A * Q_B
        RETURN shared_secret_point.x_coordinate // Or hash of X coordinate as symmetric key
    END PROCEDURE

--- SHA Algorithms (Secure Hashing Algorithms) ---
Explanation:
    A family of cryptographic hash functions published by the National Institute
    of Standards and Technology (NIST). They produce fixed-size outputs (hash
    values) for variable-size inputs. SHA-256 and SHA-3 are commonly used for
    data integrity and digital signatures.
Pseudo Code:
    (SHA algorithms are complex, highly detailed, and involve many bitwise operations,
    message padding, compression functions. A high-level overview.)
    PROCEDURE SHA256(message)
        1. Padding: Pad message to a multiple of 512 bits.
        2. Initialize Hash Values: Set initial 8 hash values (H0 to H7) to fixed constants.
        3. Process Message in 512-bit Chunks:
            a. For each chunk, break it into 16 32-bit words (W0 to W15).
            b. Extend W0 to W15 to 64 words (W0 to W63) using a specific expansion function.
            c. Initialize 8 working variables (a to h) with current hash values.
            d. Main Loop (64 iterations):
                i. Apply specific SHA-256 compression functions (Ch, Maj, Sigma0, Sigma1).
                ii. Update working variables based on word Wt and constants Kt.
            e. Add results to hash values H0 to H7.
        4. Output Hash: Concatenate final H0 to H7.
        RETURN 256-bit_hash
    END PROCEDURE

--- MD5 (Not secure but historically important) ---
Explanation:
    A widely used cryptographic hash function that produces a 128-bit hash value.
    It's historically important but is now considered cryptographically broken
    (vulnerable to collision attacks) and is not recommended for security
    purposes.
Pseudo Code:
    (Similar complexity to SHA algorithms, but for 128-bit output)
    PROCEDURE MD5(message)
        1. Padding: Pad message.
        2. Initialize MD Buffer: Set 4 32-bit registers (A, B, C, D) to fixed constants.
        3. Process Message in 512-bit Chunks:
            a. Each chunk undergoes 4 rounds of 16 operations.
            b. Each operation involves a non-linear function (F, G, H, I), modular addition, and left rotation.
            c. Updates A, B, C, D.
        4. Output Hash: Concatenate final A, B, C, D.
        RETURN 128-bit_hash
    END PROCEDURE

--- Caesar Cipher ---
Explanation:
    One of the simplest and most widely known encryption techniques. It's a
    type of substitution cipher in which each letter in the plaintext is
    replaced by a letter some fixed number of positions down the alphabet.
Pseudo Code:
    PROCEDURE CaesarEncrypt(plaintext, shift)
        ciphertext = ""
        FOR EACH char IN plaintext DO
            IF char IS UPPERCASE_LETTER THEN
                encrypted_char = CHR(((ORD(char) - ORD('A') + shift) MOD 26) + ORD('A'))
            ELSE IF char IS LOWERCASE_LETTER THEN
                encrypted_char = CHR(((ORD(char) - ORD('a') + shift) MOD 26) + ORD('a'))
            ELSE
                encrypted_char = char // Keep non-alphabetic characters as is
            END IF
            ciphertext = ciphertext + encrypted_char
        END FOR
        RETURN ciphertext
    END PROCEDURE

    PROCEDURE CaesarDecrypt(ciphertext, shift)
        // Decryption is simply encryption with a negative shift (26 - shift)
        RETURN CaesarEncrypt(ciphertext, 26 - shift)
    END PROCEDURE

--- Vigenère Cipher ---
Explanation:
    A method of encrypting alphabetic text by using a series of different
    Caesar ciphers based on the letters of a keyword. It's a polyalphabetic
    substitution cipher, much stronger than a simple Caesar cipher.
Pseudo Code:
    PROCEDURE VigenereEncrypt(plaintext, keyword)
        ciphertext = ""
        key_index = 0
        key_length = LENGTH(keyword)
        FOR EACH char IN plaintext DO
            IF char IS ALPHABETIC THEN
                key_char_shift = ORD(TO_UPPERCASE(keyword[key_index MOD key_length])) - ORD('A')
                IF char IS UPPERCASE_LETTER THEN
                    encrypted_char = CHR(((ORD(char) - ORD('A') + key_char_shift) MOD 26) + ORD('A'))
                ELSE // LOWERCASE_LETTER
                    encrypted_char = CHR(((ORD(char) - ORD('a') + key_char_shift) MOD 26) + ORD('a'))
                END IF
                key_index = key_index + 1
            ELSE
                encrypted_char = char // Keep non-alphabetic characters as is
            END IF
            ciphertext = ciphertext + encrypted_char
        END FOR
        RETURN ciphertext
    END PROCEDURE

    PROCEDURE VigenereDecrypt(ciphertext, keyword)
        plaintext = ""
        key_index = 0
        key_length = LENGTH(keyword)
        FOR EACH char IN ciphertext DO
            IF char IS ALPHABETIC THEN
                key_char_shift = ORD(TO_UPPERCASE(keyword[key_index MOD key_length])) - ORD('A')
                IF char IS UPPERCASE_LETTER THEN
                    decrypted_char = CHR(((ORD(char) - ORD('A') - key_char_shift + 26) MOD 26) + ORD('A'))
                ELSE // LOWERCASE_LETTER
                    decrypted_char = CHR(((ORD(char) - ORD('a') - key_char_shift + 26) MOD 26) + ORD('a'))
                END IF
                key_index = key_index + 1
            ELSE
                decrypted_char = char // Keep non-alphabetic characters as is
            END IF
            plaintext = plaintext + decrypted_char
        END FOR
        RETURN plaintext
    END PROCEDURE

--- Hill Cipher ---
Explanation:
    A polygraphic substitution cipher based on linear algebra. Each letter is
    represented by a number. The plaintext is grouped into blocks of `n`
    letters, which are then multiplied by an `n x n` invertible matrix (the key)
    modulo 26 (for English alphabet).
Pseudo Code:
    (Conceptual, requires matrix operations and modular inverse of matrices)
    PROCEDURE HillEncrypt(plaintext, key_matrix)
        1. Convert plaintext to numerical vector (A=0, B=1, ... Z=25).
        2. Pad plaintext if length is not a multiple of matrix dimension `n`.
        3. Divide plaintext vector into blocks of size `n`.
        4. For each block:
            a. Multiply the plaintext block vector by the `n x n` key_matrix.
            b. Take modulo 26 for each element of the resulting vector.
            c. Convert back to letters.
        RETURN ciphertext
    END PROCEDURE

    PROCEDURE HillDecrypt(ciphertext, key_matrix)
        1. Convert ciphertext to numerical vector.
        2. Find the modular inverse of the key_matrix modulo 26. (This is the decryption key).
        3. Divide ciphertext vector into blocks of size `n`.
        4. For each block:
            a. Multiply the ciphertext block vector by the inverse_key_matrix.
            b. Take modulo 26 for each element.
            c. Convert back to letters.
        RETURN plaintext
    END PROCEDURE

================================
BACKTRACKING ALGORITHMS
================================

--- N-Queens Problem ---
Explanation:
    The problem of placing N non-attacking queens on an N×N chessboard.
    A queen can attack horizontally, vertically, and diagonally.
    Backtracking is used to explore possible placements.
Pseudo Code:
    PROCEDURE SolveNQueens(n)
        result = EMPTY_LIST_OF_BOARDS
        board = 2D ARRAY of size n x n, initialized to EMPTY
        SolveNQueensRecursive(n, 0, board, result)
        RETURN result
    END PROCEDURE

    PROCEDURE SolveNQueensRecursive(n, row, board, result)
        IF row == n THEN
            ADD COPY(board) TO result // Found a valid configuration
            RETURN
        END IF

        FOR col FROM 0 TO n-1 DO
            IF IsSafe(board, row, col, n) THEN
                board[row][col] = 'Q' // Place queen
                SolveNQueensRecursive(n, row + 1, board, result)
                board[row][col] = EMPTY // Backtrack (remove queen)
            END IF
        END FOR
    END PROCEDURE

    PROCEDURE IsSafe(board, row, col, n)
        // Check column above
        FOR i FROM 0 TO row-1 DO
            IF board[i][col] == 'Q' THEN RETURN FALSE
        END FOR
        // Check upper-left diagonal
        FOR i, j FROM row-1, col-1 DOWNTO 0, 0 DO
            IF i < 0 OR j < 0 THEN BREAK
            IF board[i][j] == 'Q' THEN RETURN FALSE
        END FOR
        // Check upper-right diagonal
        FOR i, j FROM row-1, col+1 DOWNTO 0, n-1 DO
            IF i < 0 OR j >= n THEN BREAK
            IF board[i][j] == 'Q' THEN RETURN FALSE
        END FOR
        RETURN TRUE
    END PROCEDURE

--- Sudoku Solver ---
Explanation:
    Given a partially filled 9x9 Sudoku grid, solve it by filling the empty
    cells (represented by 0 or empty) such that the rules of Sudoku are met
    (each row, column, and 3x3 subgrid contains digits 1-9 without repetition).
Pseudo Code:
    PROCEDURE SolveSudoku(board)
        FOR row FROM 0 TO 8 DO
            FOR col FROM 0 TO 8 DO
                IF board[row][col] == 0 THEN // Found an empty cell
                    FOR num FROM 1 TO 9 DO
                        IF IsValidPlacement(board, row, col, num) THEN
                            board[row][col] = num // Try placing number
                            IF SolveSudoku(board) THEN // Recurse
                                RETURN TRUE // Solution found
                            END IF
                            board[row][col] = 0 // Backtrack
                        END IF
                    END FOR
                    RETURN FALSE // No number works for this cell
                END IF
            END FOR
        END FOR
        RETURN TRUE // All cells filled, solution found
    END PROCEDURE

    PROCEDURE IsValidPlacement(board, row, col, num)
        // Check row
        FOR x FROM 0 TO 8 DO
            IF board[row][x] == num THEN RETURN FALSE
        END FOR
        // Check column
        FOR x FROM 0 TO 8 DO
            IF board[x][col] == num THEN RETURN FALSE
        END FOR
        // Check 3x3 subgrid
        start_row = row - row MOD 3
        start_col = col - col MOD 3
        FOR i FROM 0 TO 2 DO
            FOR j FROM 0 TO 2 DO
                IF board[start_row + i][start_col + j] == num THEN RETURN FALSE
            END FOR
        END FOR
        RETURN TRUE
    END PROCEDURE

--- Rat in a Maze ---
Explanation:
    Given a maze (represented as a 2D grid), find a path from a starting
    point to an ending point. The rat can only move in certain directions
    (e.g., up, down, left, right).
Pseudo Code:
    PROCEDURE SolveMaze(maze, N) // N is dimension of square maze
        solution_path = 2D ARRAY of size N x N initialized to 0
        IF FindPath(maze, 0, 0, N, solution_path) THEN
            PRINT solution_path
            RETURN TRUE
        ELSE
            PRINT "No path found"
            RETURN FALSE
        END IF
    END PROCEDURE

    PROCEDURE FindPath(maze, x, y, N, solution_path)
        IF x == N-1 AND y == N-1 AND maze[x][y] == 1 THEN // Reached destination
            solution_path[x][y] = 1
            RETURN TRUE
        END IF

        IF IsSafe(maze, x, y, N) THEN
            solution_path[x][y] = 1 // Mark current cell as part of path

            // Try moving Right
            IF FindPath(maze, x, y+1, N, solution_path) THEN RETURN TRUE
            // Try moving Down
            IF FindPath(maze, x+1, y, N, solution_path) THEN RETURN TRUE
            // (Optional: Try Up/Left depending on problem constraints)

            solution_path[x][y] = 0 // Backtrack: Unmark current cell
            RETURN FALSE
        END IF
        RETURN FALSE
    END PROCEDURE

    PROCEDURE IsSafe(maze, x, y, N)
        RETURN (x >= 0 AND x < N AND y >= 0 AND y < N AND maze[x][y] == 1)
    END PROCEDURE

--- Word Search in a Grid ---
Explanation:
    Given a 2D board of characters and a word, find if the word exists in
    the grid. The word can be constructed from letters of sequentially
    adjacent cells, where "adjacent" cells are horizontally or vertically
    neighboring.
Pseudo Code:
    PROCEDURE ExistWord(board, word)
        rows = LENGTH(board)
        cols = LENGTH(board[0])
        FOR r FROM 0 TO rows-1 DO
            FOR c FROM 0 TO cols-1 DO
                IF board[r][c] == word[0] THEN
                    IF DFS_SearchWord(board, word, r, c, 0, rows, cols) THEN
                        RETURN TRUE
                    END IF
                END IF
            END FOR
        END FOR
        RETURN FALSE
    END PROCEDURE

    PROCEDURE DFS_SearchWord(board, word, r, c, word_idx, rows, cols)
        IF word_idx == LENGTH(word) THEN
            RETURN TRUE // Word found
        END IF

        IF r < 0 OR r >= rows OR c < 0 OR c >= cols OR board[r][c] != word[word_idx] THEN
            RETURN FALSE // Out of bounds or mismatch
        END IF

        original_char = board[r][c]
        board[r][c] = '#' // Mark as visited to avoid cycles

        // Explore 4 directions
        IF DFS_SearchWord(board, word, r + 1, c, word_idx + 1, rows, cols) THEN RETURN TRUE
        IF DFS_SearchWord(board, word, r - 1, c, word_idx + 1, rows, cols) THEN RETURN TRUE
        IF DFS_SearchWord(board, word, r, c + 1, word_idx + 1, rows, cols) THEN RETURN TRUE
        IF DFS_SearchWord(board, word, r, c - 1, word_idx + 1, rows, cols) THEN RETURN TRUE

        board[r][c] = original_char // Backtrack
        RETURN FALSE
    END PROCEDURE

--- Hamiltonian Path and Cycle ---
Explanation:
    A Hamiltonian path in an undirected graph visits each vertex exactly once.
    A Hamiltonian cycle is a Hamiltonian path that is a cycle (starts and
    ends at the same vertex). Backtracking is a common approach to find them.
Pseudo Code:
    PROCEDURE HamiltonianPath(Graph G)
        num_vertices = NUMBER_OF_VERTICES(G)
        path = ARRAY of size num_vertices initialized to -1
        visited = BOOLEAN_ARRAY of size num_vertices initialized to FALSE

        FOR start_node FROM 0 TO num_vertices-1 DO
            path[0] = start_node
            visited[start_node] = TRUE
            IF FindHamiltonianPath(G, path, visited, 1, num_vertices) THEN
                PRINT "Hamiltonian Path: " path
                RETURN TRUE
            END IF
            visited[start_node] = FALSE // Backtrack for next start node
        END FOR
        RETURN FALSE
    END PROCEDURE

    PROCEDURE FindHamiltonianPath(G, path, visited, current_pos, num_vertices)
        IF current_pos == num_vertices THEN
            RETURN TRUE // Path found
        END IF

        last_vertex = path[current_pos - 1]
        FOR next_vertex FROM 0 TO num_vertices-1 DO
            IF G.HAS_EDGE(last_vertex, next_vertex) AND NOT visited[next_vertex] THEN
                path[current_pos] = next_vertex
                visited[next_vertex] = TRUE
                IF FindHamiltonianPath(G, path, visited, current_pos + 1, num_vertices) THEN
                    RETURN TRUE
                END IF
                visited[next_vertex] = FALSE // Backtrack
                path[current_pos] = -1
            END IF
        END FOR
        RETURN FALSE
    END PROCEDURE

    PROCEDURE HamiltonianCycle(Graph G)
        // Similar to HamiltonianPath, but after finding a path of length N,
        // check if there's an edge from the last vertex back to the start_node.
        // If so, it's a cycle.
    END PROCEDURE

--- Knight’s Tour ---
Explanation:
    A sequence of moves of a knight on a chessboard such that the knight
    visits every square exactly once.
Pseudo Code:
    PROCEDURE KnightTour(board_size)
        board = 2D ARRAY of size board_size x board_size initialized to -1
        
        // Possible moves for a knight
        x_moves = {2, 1, -1, -2, -2, -1, 1, 2}
        y_moves = {1, 2, 2, 1, -1, -2, -2, -1}

        // Start from (0,0) with move 0
        board[0][0] = 0
        IF SolveKnightTour(board, 0, 0, 1, board_size, x_moves, y_moves) THEN
            PRINT board
            RETURN TRUE
        ELSE
            PRINT "No tour found"
            RETURN FALSE
        END IF
    END PROCEDURE

    PROCEDURE SolveKnightTour(board, current_x, current_y, move_count, board_size, x_moves, y_moves)
        IF move_count == board_size * board_size THEN
            RETURN TRUE // All squares visited
        END IF

        FOR i FROM 0 TO 7 DO // Try all 8 possible knight moves
            next_x = current_x + x_moves[i]
            next_y = current_y + y_moves[i]

            IF IsSafeKnightMove(next_x, next_y, board_size, board) THEN
                board[next_x][next_y] = move_count
                IF SolveKnightTour(board, next_x, next_y, move_count + 1, board_size, x_moves, y_moves) THEN
                    RETURN TRUE
                END IF
                board[next_x][next_y] = -1 // Backtrack
            END IF
        END FOR
        RETURN FALSE
    END PROCEDURE

    PROCEDURE IsSafeKnightMove(x, y, board_size, board)
        RETURN (x >= 0 AND x < board_size AND y >= 0 AND y < board_size AND board[x][y] == -1)
    END PROCEDURE

--- Subset Generation ---
Explanation:
    Generate all possible subsets (the power set) of a given set.
Pseudo Code:
    // Recursive approach
    PROCEDURE GenerateSubsets_Recursive(set, current_subset, index, all_subsets)
        IF index == LENGTH(set) THEN
            ADD COPY(current_subset) TO all_subsets
            RETURN
        END IF

        // Include current element
        ADD set[index] TO current_subset
        GenerateSubsets_Recursive(set, current_subset, index + 1, all_subsets)
        REMOVE LAST_ELEMENT_FROM(current_subset) // Backtrack

        // Exclude current element
        GenerateSubsets_Recursive(set, current_subset, index + 1, all_subsets)
    END PROCEDURE

    // Iterative approach (using bit manipulation)
    PROCEDURE GenerateSubsets_Iterative(set)
        n = LENGTH(set)
        all_subsets = EMPTY_LIST_OF_LISTS
        num_subsets = 2^n // Total number of subsets

        FOR i FROM 0 TO num_subsets-1 DO // Each number from 0 to 2^n - 1 represents a subset
            current_subset = EMPTY_LIST
            FOR j FROM 0 TO n-1 DO // Check j-th bit
                IF (i >> j) AND 1 THEN // If j-th bit is set
                    ADD set[j] TO current_subset
                END IF
            END FOR
            ADD current_subset TO all_subsets
        END FOR
        RETURN all_subsets
    END PROCEDURE

--- Permutations and Combinations ---
Explanation:
    **Permutations:** Different arrangements of a set of items where the order
    matters.
    **Combinations:** Different selections of a set of items where the order
    does not matter.
Pseudo Code:
    // Permutations (Recursive Backtracking)
    PROCEDURE GeneratePermutations(array, start_index, result_list)
        IF start_index == LENGTH(array) - 1 THEN
            ADD COPY(array) TO result_list
            RETURN
        END IF

        FOR i FROM start_index TO LENGTH(array) - 1 DO
            SWAP(array[start_index], array[i])
            GeneratePermutations(array, start_index + 1, result_list)
            SWAP(array[start_index], array[i]) // Backtrack
        END FOR
    END PROCEDURE

    // Combinations (Recursive Backtracking)
    PROCEDURE GenerateCombinations(array, k, start_index, current_combination, result_list)
        IF LENGTH(current_combination) == k THEN
            ADD COPY(current_combination) TO result_list
            RETURN
        END IF

        FOR i FROM start_index TO LENGTH(array) - 1 DO
            ADD array[i] TO current_combination
            GenerateCombinations(array, k, i + 1, current_combination, result_list)
            REMOVE LAST_ELEMENT_FROM(current_combination) // Backtrack
        END FOR
    END PROCEDURE

================================
BIT MANIPULATION ALGORITHMS
================================

--- Count Set Bits (Hamming Weight) ---
Explanation:
    Counts the number of "set" bits (bits with value 1) in the binary
    representation of an integer. Also known as population count or popcount.
Pseudo Code:
    // Method 1: Iterating through bits
    PROCEDURE CountSetBits_Iterative(n)
        count = 0
        WHILE n > 0 DO
            n = n AND (n - 1) // Brian Kernighan's algorithm: removes the rightmost set bit
            count = count + 1
        END WHILE
        RETURN count
    END PROCEDURE

    // Method 2: Shifting
    PROCEDURE CountSetBits_Shifting(n)
        count = 0
        WHILE n > 0 DO
            IF (n AND 1) == 1 THEN
                count = count + 1
            END IF
            n = n >> 1 // Right shift by 1
        END WHILE
        RETURN count
    END PROCEDURE

--- Check if a Number is a Power of Two ---
Explanation:
    Determines if a given integer is a power of two (i.e., 2^k for some
    non-negative integer k).
Pseudo Code:
    PROCEDURE IsPowerOfTwo(n)
        IF n <= 0 THEN RETURN FALSE
        RETURN (n AND (n - 1)) == 0
    END PROCEDURE

--- Find the Only Non-Repeating Element ---
Explanation:
    Given an array of integers where every element appears twice except
    for one, find that single non-repeating element.
Pseudo Code:
    PROCEDURE FindSingleNonRepeating(ARRAY A)
        result = 0
        FOR EACH num IN A DO
            result = result XOR num // XORing a number with itself cancels it out
        END FOR
        RETURN result
    END PROCEDURE

    // Variation: If two non-repeating elements:
    PROCEDURE FindTwoNonRepeating(ARRAY A)
        xor_sum = 0
        FOR EACH num IN A DO
            xor_sum = xor_sum XOR num
        END FOR

        // xor_sum now holds (num1 XOR num2)
        // Find the rightmost set bit in xor_sum
        rightmost_set_bit = xor_sum AND (-xor_sum)

        num1 = 0
        num2 = 0
        FOR EACH num IN A DO
            IF (num AND rightmost_set_bit) != 0 THEN // Group numbers based on this bit
                num1 = num1 XOR num
            ELSE
                num2 = num2 XOR num
            END IF
        END FOR
        RETURN num1, num2
    END PROCEDURE

--- Swap Numbers Without Temp Variable ---
Explanation:
    Swaps the values of two variables without using a temporary variable.
    Can be done using arithmetic or XOR operations.
Pseudo Code:
    // Using XOR
    PROCEDURE SwapXOR(a, b)
        a = a XOR b
        b = a XOR b
        a = a XOR b
        RETURN a, b
    END PROCEDURE

    // Using Addition/Subtraction
    PROCEDURE SwapArithmetic(a, b)
        a = a + b
        b = a - b
        a = a - b
        RETURN a, b
    END PROCEDURE

--- Reverse Bits ---
Explanation:
    Reverses the order of bits in a given integer.
Pseudo Code:
    PROCEDURE ReverseBits(n)
        reversed_n = 0
        num_bits = 32 // Assuming 32-bit integer

        FOR i FROM 0 TO num_bits-1 DO
            IF (n AND 1) == 1 THEN // Check if last bit is set
                reversed_n = reversed_n OR (1 << (num_bits - 1 - i)) // Set corresponding bit in reversed_n
            END IF
            n = n >> 1 // Right shift n
        END FOR
        RETURN reversed_n
    END PROCEDURE

--- Gray Code Generation ---
Explanation:
    Generates Gray codes, which are binary numeral system where two successive
    values differ in only one bit (i.e., a single bit flip).
Pseudo Code:
    PROCEDURE GenerateGrayCode(n_bits)
        result = EMPTY_LIST_OF_STRINGS
        IF n_bits == 0 THEN
            ADD "0" TO result
            RETURN result
        END IF

        // Base case for 1 bit
        IF n_bits == 1 THEN
            ADD "0" TO result
            ADD "1" TO result
            RETURN result
        END IF

        // Recursively generate Gray code for n-1 bits
        prev_gray_codes = GenerateGrayCode(n_bits - 1)

        // Add 0 prefix to previous codes in forward order
        FOR EACH code IN prev_gray_codes DO
            ADD "0" + code TO result
        END FOR
        
        // Add 1 prefix to previous codes in reverse order
        FOR i FROM LENGTH(prev_gray_codes)-1 DOWNTO 0 DO
            ADD "1" + prev_gray_codes[i] TO result
        END FOR
        RETURN result
    END PROCEDURE

    // Iterative method: G(n) = n XOR (n >> 1)
    PROCEDURE BinaryToGray(n)
        RETURN n XOR (n >> 1)
    END PROCEDURE

    PROCEDURE GrayToBinary(n)
        result = n
        WHILE n > 0 DO
            n = n >> 1
            result = result XOR n
        END WHILE
        RETURN result
    END PROCEDURE

--- XOR Queries ---
Explanation:
    A class of problems where queries involve the XOR operation, often on
    ranges of an array or properties of numbers, typically solvable with
    prefix XOR sums or Trie data structures.
Pseudo Code:
    // Example: XOR sum of range [L, R]
    PROCEDURE ComputePrefixXOR(ARRAY A)
        n = LENGTH(A)
        prefix_xor = ARRAY of size n
        prefix_xor[0] = A[0]
        FOR i FROM 1 TO n-1 DO
            prefix_xor[i] = prefix_xor[i-1] XOR A[i]
        END FOR
        RETURN prefix_xor
    END PROCEDURE

    PROCEDURE QueryXORRange(prefix_xor, L, R)
        IF L == 0 THEN
            RETURN prefix_xor[R]
        ELSE
            RETURN prefix_xor[R] XOR prefix_xor[L-1]
        END IF
    END PROCEDURE

    // Example: Max XOR subarray sum (using Trie/Trie of bits)
    PROCEDURE MaxXORSubarray(ARRAY A)
        // Build a Trie of prefix XOR sums
        // For each prefix XOR sum, query the Trie for the XOR sum that maximizes current_prefix_xor XOR previous_prefix_xor
        // This is a more complex application.
    END PROCEDURE

================================
MISCELLANEOUS ALGORITHMS
================================

--- Union-Find (Disjoint Set Union) ---
Explanation:
    A data structure that stores a collection of disjoint (non-overlapping) sets.
    It provides two primary operations:
    1. Union: Merges two sets into a single set.
    2. Find: Determines which set a particular element belongs to.
    Used in Kruskal's algorithm, connected components, etc.
Pseudo Code:
    CLASS DisjointSetUnion
        parent = MAP from element to parent_element
        rank = MAP from element to integer (or size)

        PROCEDURE MAKE_SET(element)
            parent[element] = element
            rank[element] = 0 // or 1 for size
        END PROCEDURE

        PROCEDURE FIND_SET(element) // Path compression
            IF parent[element] == element THEN
                RETURN element
            END IF
            parent[element] = FIND_SET(parent[element])
            RETURN parent[element]
        END PROCEDURE

        PROCEDURE UNION_SETS(element1, element2) // Union by rank/size
            root1 = FIND_SET(element1)
            root2 = FIND_SET(element2)

            IF root1 != root2 THEN
                IF rank[root1] < rank[root2] THEN
                    SWAP(root1, root2)
                END IF
                parent[root2] = root1
                IF rank[root1] == rank[root2] THEN
                    rank[root1] = rank[root1] + 1
                END IF
                RETURN TRUE // Union successful
            END IF
            RETURN FALSE // Already in the same set
        END PROCEDURE
    END CLASS

--- Sliding Window Technique ---
Explanation:
    A technique used to optimize array or string problems. It involves
    maintaining a "window" of elements that slides over the input. The window
    can expand or shrink depending on problem constraints, often used to find
    subarrays/substrings meeting certain criteria.
Pseudo Code:
    // Example: Find max sum subarray of size k
    PROCEDURE MaxSumSubarrayK(ARRAY A, k)
        n = LENGTH(A)
        IF n < k THEN RETURN -1

        current_sum = 0
        FOR i FROM 0 TO k-1 DO // Calculate sum of first window
            current_sum = current_sum + A[i]
        END FOR
        
        max_sum = current_sum
        
        FOR i FROM k TO n-1 DO // Slide the window
            current_sum = current_sum + A[i] - A[i-k] // Add new element, remove old
            max_sum = MAX(max_sum, current_sum)
        END FOR
        RETURN max_sum
    END PROCEDURE

    // Example: Smallest subarray with sum >= S
    PROCEDURE SmallestSubarrayWithSum(ARRAY A, S)
        min_length = INFINITY
        current_sum = 0
        window_start = 0

        FOR window_end FROM 0 TO LENGTH(A)-1 DO
            current_sum = current_sum + A[window_end]
            WHILE current_sum >= S DO
                min_length = MIN(min_length, window_end - window_start + 1)
                current_sum = current_sum - A[window_start]
                window_start = window_start + 1
            END WHILE
        END FOR
        IF min_length == INFINITY THEN RETURN 0 ELSE RETURN min_length
    END PROCEDURE

--- Two Pointer Technique ---
Explanation:
    A technique that involves using two pointers to iterate through a data
    structure (like an array or linked list), often from opposite ends or
    at different speeds, to solve problems efficiently.
Pseudo Code:
    // Example: Check if a sorted array has two elements that sum to target
    PROCEDURE TwoSumSortedArray(ARRAY A, target)
        left = 0
        right = LENGTH(A) - 1
        WHILE left < right DO
            current_sum = A[left] + A[right]
            IF current_sum == target THEN
                RETURN TRUE
            ELSE IF current_sum < target THEN
                left = left + 1
            ELSE
                right = right - 1
            END IF
        END WHILE
        RETURN FALSE
    END PROCEDURE

    // Example: Reverse a string in-place
    PROCEDURE ReverseString(ARRAY chars)
        left = 0
        right = LENGTH(chars) - 1
        WHILE left < right DO
            SWAP(chars[left], chars[right])
            left = left + 1
            right = right - 1
        END WHILE
    END PROCEDURE

--- Reservoir Sampling ---
Explanation:
    A family of algorithms for randomly choosing a sample of `k` items from
    a list of `n` items, where `n` is a very large or unknown number, and
    where only one pass over the list is allowed.
Pseudo Code:
    PROCEDURE ReservoirSampling(stream, k)
        reservoir = ARRAY of size k

        // Fill reservoir with first k items
        FOR i FROM 0 TO k-1 DO
            reservoir[i] = stream.next_item()
        END FOR

        count = k
        WHILE stream.has_more_items() DO
            item = stream.next_item()
            count = count + 1
            j = RANDOM_INTEGER(1, count) // Random integer between 1 and count (inclusive)
            IF j <= k THEN
                reservoir[j-1] = item // Replace a random element in reservoir
            END IF
        END WHILE
        RETURN reservoir
    END PROCEDURE

--- Fisher-Yates Shuffle (Random Shuffle) ---
Explanation:
    An algorithm for generating a random permutation of a finite sequence.
    It works by iterating through the array from the end, and for each element,
    swapping it with a randomly chosen element from the remaining unsampled
    part of the array.
Pseudo Code:
    PROCEDURE FisherYatesShuffle(ARRAY A)
        n = LENGTH(A)
        FOR i FROM n-1 DOWNTO 1 DO
            j = RANDOM_INTEGER(0, i) // Random index from 0 to i (inclusive)
            SWAP(A[i], A[j])
        END FOR
    END PROCEDURE

--- Flood-Fill Algorithm ---
Explanation:
    An algorithm that determines the area connected to a given node in a
    multi-dimensional array. It's often used in image processing to identify
    connected regions (e.g., painting tool fills).
Pseudo Code:
    PROCEDURE FloodFill(image_array, start_x, start_y, target_color, replacement_color)
        IF target_color == replacement_color THEN RETURN
        
        rows = LENGTH(image_array)
        cols = LENGTH(image_array[0])

        IF image_array[start_x][start_y] != target_color THEN RETURN

        queue = EMPTY_QUEUE
        ENQUEUE(queue, (start_x, start_y))
        image_array[start_x][start_y] = replacement_color

        WHILE NOT IS_EMPTY(queue) DO
            (curr_x, curr_y) = DEQUEUE(queue)

            // Define neighbors (up, down, left, right)
            dx = {0, 0, 1, -1}
            dy = {1, -1, 0, 0}

            FOR i FROM 0 TO 3 DO
                new_x = curr_x + dx[i]
                new_y = curr_y + dy[i]

                IF new_x >= 0 AND new_x < rows AND new_y >= 0 AND new_y < cols AND image_array[new_x][new_y] == target_color THEN
                    image_array[new_x][new_y] = replacement_color
                    ENQUEUE(queue, (new_x, new_y))
                END IF
            END FOR
        END WHILE
    END PROCEDURE

--- Fast Inverse Square Root (Quake III) ---
Explanation:
    An ingenious algorithm developed for Quake III Arena that calculates
    an approximation of `1/sqrt(x)` very quickly, typically faster than
    using standard floating-point division and square root operations.
    It uses a magic constant and a few Newton-Raphson iterations.
Pseudo Code:
    (This is a low-level, bit-manipulation algorithm, more C-like pseudocode)
    FUNCTION Q_rsqrt(float number)
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y = number;
        i = *(long *) &y;               // evil floating point bit level hacking
        i = 0x5f3759df - (i >> 1);      // what the f***?
        y = *(float *) &i;
        y = y * (threehalfs - (x2 * y * y)); // 1st iteration of Newton-Raphson
        // y = y * (threehalfs - (x2 * y * y)); // 2nd iteration (optional)

        RETURN y;
    END FUNCTION

================================
MACHINE LEARNING AND AI-RELATED ALGORITHMS
================================

--- Gradient Descent ---
Explanation:
    An iterative optimization algorithm used to find the minimum of a function.
    In machine learning, it's widely used to minimize the cost (or loss)
    function of a model by iteratively adjusting the model's parameters in
    the direction of the steepest descent of the cost function's gradient.
Pseudo Code:
    PROCEDURE GradientDescent(initial_parameters, learning_rate, num_iterations, cost_function, gradient_function)
        parameters = initial_parameters
        FOR i FROM 1 TO num_iterations DO
            gradient = gradient_function(parameters) // Calculate gradient of cost function
            parameters = parameters - learning_rate * gradient // Update parameters
        END FOR
        RETURN parameters
    END PROCEDURE

    // Example with a single parameter 'theta' and cost J(theta)
    PROCEDURE GradientDescent_Simple(initial_theta, alpha, max_iter, data)
        theta = initial_theta
        FOR i FROM 1 TO max_iter DO
            // Calculate derivative of J(theta) w.r.t theta
            derivative_J_theta = (1/m) * SUM( (hypothesis(x_j, theta) - y_j) * x_j ) for all data points j
            theta = theta - alpha * derivative_J_theta
        END FOR
        RETURN theta
    END PROCEDURE

--- K-Means Clustering ---
Explanation:
    An unsupervised machine learning algorithm used for clustering data
    points into `k` distinct groups (clusters). It iteratively assigns data
    points to the nearest centroid and then updates the centroids based on
    the mean of the points assigned to that cluster.
Pseudo Code:
    PROCEDURE KMeans(data_points, k, max_iterations)
        // Step 1: Initialize k centroids randomly (e.g., pick k random data points)
        centroids = SELECT_RANDOM_POINTS(data_points, k)
        
        FOR iter FROM 1 TO max_iterations DO
            // Step 2: Assign each data point to the closest centroid
            clusters = LIST of k empty lists
            FOR EACH point IN data_points DO
                closest_centroid_index = FIND_CLOSEST_CENTROID(point, centroids)
                ADD point TO clusters[closest_centroid_index]
            END FOR

            // Step 3: Update centroids based on the mean of assigned points
            new_centroids = EMPTY_LIST
            FOR i FROM 0 TO k-1 DO
                IF IS_EMPTY(clusters[i]) THEN
                    // Handle empty cluster (e.g., re-initialize centroid or keep old)
                    ADD centroids[i] TO new_centroids
                ELSE
                    ADD CALCULATE_MEAN(clusters[i]) TO new_centroids
                END IF
            END FOR
            
            // Check for convergence
            IF new_centroids == centroids THEN
                BREAK // Centroids did not change significantly
            END IF
            centroids = new_centroids
        END FOR
        RETURN centroids, clusters
    END PROCEDURE

    PROCEDURE FIND_CLOSEST_CENTROID(point, centroids)
        min_dist = INFINITY
        closest_index = -1
        FOR i FROM 0 TO LENGTH(centroids)-1 DO
            dist = EUCLIDEAN_DISTANCE(point, centroids[i])
            IF dist < min_dist THEN
                min_dist = dist
                closest_index = i
            END IF
        END FOR
        RETURN closest_index
    END PROCEDURE

--- Decision Trees ---
Explanation:
    A supervised learning algorithm used for both classification and regression.
    It builds a tree-like model of decisions and their possible consequences.
    It splits data based on features to create homogeneous subsets, ultimately
    leading to leaf nodes representing predictions.
Pseudo Code:
    PROCEDURE BuildDecisionTree(data, features, target_attribute)
        IF ALL_EXAMPLES_SAME_CLASS(data, target_attribute) THEN
            RETURN NEW LEAF_NODE(CLASS_OF_EXAMPLES(data, target_attribute))
        END IF
        IF NO_MORE_FEATURES_TO_SPLIT(features) THEN
            RETURN NEW LEAF_NODE(MAJORITY_CLASS(data, target_attribute))
        END IF

        // Select the best splitting feature (e.g., using Information Gain or Gini Impurity)
        best_feature = FIND_BEST_SPLIT_FEATURE(data, features, target_attribute)
        root = NEW DECISION_NODE(best_feature)
        
        FOR EACH value OF best_feature DO
            subset = SUBSET_OF_DATA(data, best_feature, value)
            IF IS_EMPTY(subset) THEN
                ADD NEW LEAF_NODE(MAJORITY_CLASS(data, target_attribute)) AS CHILD_FOR_VALUE(root, value)
            ELSE
                remaining_features = REMOVE_FEATURE(features, best_feature)
                child_node = BuildDecisionTree(subset, remaining_features, target_attribute)
                ADD child_node AS CHILD_FOR_VALUE(root, value)
            END IF
        END FOR
        RETURN root
    END PROCEDURE

    PROCEDURE Classify(tree, instance)
        IF tree IS LEAF_NODE THEN
            RETURN tree.class
        ELSE
            feature_value = INSTANCE_FEATURE_VALUE(instance, tree.split_feature)
            child_node = tree.child_for_value[feature_value]
            RETURN Classify(child_node, instance)
        END IF
    END PROCEDURE

--- Naive Bayes ---
Explanation:
    A simple probabilistic classifier based on applying Bayes' theorem with
    strong (naive) independence assumptions between the features. It's often
    used for text classification, spam filtering, etc.
Pseudo Code:
    PROCEDURE TrainNaiveBayes(training_data)
        // For each class C (e.g., Spam/Not Spam):
        // 1. Calculate P(C): Probability of class C (e.g., count(Spam emails) / total emails)
        // 2. For each feature F (e.g., word "free"), calculate P(F|C):
        //    Probability of feature F given class C (e.g., count("free" in Spam) / count(all words in Spam))
        //    Use Laplace smoothing to avoid zero probabilities for unseen features.

        class_probabilities = CALCULATE_CLASS_PRIORS(training_data)
        feature_probabilities = CALCULATE_CONDITIONAL_PROBABILITIES(training_data)

        RETURN (class_probabilities, feature_probabilities)
    END PROCEDURE

    PROCEDURE ClassifyNaiveBayes(instance, trained_model)
        (class_probabilities, feature_probabilities) = trained_model
        
        predicted_class = NULL
        max_posterior = -INFINITY

        FOR EACH class C IN class_probabilities DO
            // Posterior = P(C) * P(F1|C) * P(F2|C) * ... * P(Fn|C)
            current_posterior = LOG(class_probabilities[C]) // Use log-probabilities to prevent underflow
            FOR EACH feature F IN instance DO
                current_posterior = current_posterior + LOG(feature_probabilities[F][C])
            END FOR

            IF current_posterior > max_posterior THEN
                max_posterior = current_posterior
                predicted_class = C
            END IF
        END FOR
        RETURN predicted_class
    END PROCEDURE

--- Support Vector Machines (SVMs) ---
Explanation:
    A supervised learning model for classification and regression tasks.
    SVMs work by finding the optimal hyperplane that best separates data
    points of different classes in a high-dimensional feature space,
    maximizing the margin between the classes.
Pseudo Code:
    (Highly complex, typically involves quadratic programming for training)
    PROCEDURE TrainSVM(training_data, labels)
        // Data: (x_i, y_i) where x_i is feature vector, y_i is class label (+1 or -1)
        // Goal: Find weight vector 'w' and bias 'b' such that y_i * (w . x_i + b) >= 1
        // And minimize ||w|| (maximize margin).

        // Transform data into higher dimension (if using kernel trick)
        // Set up and solve a Quadratic Programming problem
        //   Minimize: 1/2 * ||w||^2
        //   Subject to: y_i * (w . x_i + b) >= 1  for all i

        // Solution gives optimal 'w' and 'b' (or Lagrange multipliers for kernel SVM)
        RETURN (weight_vector_w, bias_b, support_vectors)
    END PROCEDURE

    PROCEDURE PredictSVM(instance, trained_model)
        (w, b, _) = trained_model
        // Prediction: sign(w . instance + b)
        prediction_value = DOT_PRODUCT(w, instance) + b
        IF prediction_value >= 0 THEN
            RETURN +1
        ELSE
            RETURN -1
        END IF
    END PROCEDURE

--- Backpropagation (Neural Networks) ---
Explanation:
    A widely used algorithm for training artificial neural networks. It
    calculates the gradient of the loss function with respect to the weights
    and biases of the network, allowing these parameters to be adjusted
    (e.g., using gradient descent) to minimize the loss.
Pseudo Code:
    PROCEDURE TrainNeuralNetwork(network, training_data, learning_rate, num_epochs)
        FOR epoch FROM 1 TO num_epochs DO
            FOR EACH (input_X, target_Y) IN training_data DO
                // Step 1: Forward Pass
                // Calculate activations for each layer
                outputs = ForwardPass(network, input_X)
                
                // Step 2: Calculate Loss
                loss = CalculateLoss(outputs, target_Y)

                // Step 3: Backward Pass (Backpropagation)
                // Calculate gradients of loss w.r.t. output layer's weights/biases
                delta_output_layer = CalculateOutputLayerError(outputs, target_Y)
                
                // Propagate errors backwards through hidden layers
                delta_hidden_layers = PropagateErrorBackwards(network, delta_output_layer)

                // Step 4: Update Weights and Biases (e.g., Gradient Descent)
                UpdateNetworkParameters(network, delta_output_layer, delta_hidden_layers, learning_rate)
            END FOR
        END FOR
    END PROCEDURE

    (Helper functions like ForwardPass, CalculateOutputLayerError, PropagateErrorBackwards,
    UpdateNetworkParameters involve matrix multiplications, activation functions,
    and their derivatives, which are quite detailed.)

--- Minimax Algorithm (Game Trees) ---
Explanation:
    A decision rule used in artificial intelligence for minimizing the
    possible loss for a worst-case (maximum loss) scenario. It's often
    used for two-player zero-sum games (like chess or tic-tac-toe) where
    players take turns, and the outcome is numerical.
Pseudo Code:
    PROCEDURE Minimax(node, depth, is_maximizing_player)
        IF depth == 0 OR IS_TERMINAL_NODE(node) THEN
            RETURN EVALUATE_SCORE(node)
        END IF

        IF is_maximizing_player THEN
            max_eval = -INFINITY
            FOR EACH child_node IN GENERATE_CHILDREN(node) DO
                eval = Minimax(child_node, depth - 1, FALSE)
                max_eval = MAX(max_eval, eval)
            END FOR
            RETURN max_eval
        ELSE // Minimizing player
            min_eval = +INFINITY
            FOR EACH child_node IN GENERATE_CHILDREN(node) DO
                eval = Minimax(child_node, depth - 1, TRUE)
                min_eval = MIN(min_eval, eval)
            END FOR
            RETURN min_eval
        END IF
    END PROCEDURE

    // Minimax with Alpha-Beta Pruning (optimization)
    PROCEDURE MinimaxAlphaBeta(node, depth, alpha, beta, is_maximizing_player)
        IF depth == 0 OR IS_TERMINAL_NODE(node) THEN
            RETURN EVALUATE_SCORE(node)
        END IF

        IF is_maximizing_player THEN
            max_eval = -INFINITY
            FOR EACH child_node IN GENERATE_CHILDREN(node) DO
                eval = MinimaxAlphaBeta(child_node, depth - 1, alpha, beta, FALSE)
                max_eval = MAX(max_eval, eval)
                alpha = MAX(alpha, eval)
                IF beta <= alpha THEN
                    BREAK // Beta cut-off
                END IF
            END FOR
            RETURN max_eval
        ELSE // Minimizing player
            min_eval = +INFINITY
            FOR EACH child_node IN GENERATE_CHILDREN(node) DO
                eval = MinimaxAlphaBeta(child_node, depth - 1, alpha, beta, TRUE)
                min_eval = MIN(min_eval, eval)
                beta = MIN(beta, eval)
                IF beta <= alpha THEN
                    BREAK // Alpha cut-off
                END IF
            END FOR
            RETURN min_eval
        END IF
    END PROCEDURE

================================
DATA COMPRESSION ALGORITHMS
================================

--- Run-Length Encoding ---
Explanation:
    A simple form of lossless data compression in which runs of data
    (sequences in which the same data value occurs in many consecutive data
    elements) are stored as a single data value and count, rather than as
    the original run.
Pseudo Code:
    PROCEDURE RunLengthEncode(input_string)
        IF LENGTH(input_string) == 0 THEN RETURN ""
        
        encoded_string = ""
        count = 1
        FOR i FROM 1 TO LENGTH(input_string)-1 DO
            IF input_string[i] == input_string[i-1] THEN
                count = count + 1
            ELSE
                encoded_string = encoded_string + input_string[i-1] + TO_STRING(count)
                count = 1
            END IF
        END FOR
        encoded_string = encoded_string + input_string[LENGTH(input_string)-1] + TO_STRING(count)
        RETURN encoded_string
    END PROCEDURE

    PROCEDURE RunLengthDecode(encoded_string)
        decoded_string = ""
        i = 0
        WHILE i < LENGTH(encoded_string) DO
            char = encoded_string[i]
            i = i + 1
            num_str = ""
            WHILE i < LENGTH(encoded_string) AND IS_DIGIT(encoded_string[i]) DO
                num_str = num_str + encoded_string[i]
                i = i + 1
            END WHILE
            count = TO_INTEGER(num_str)
            FOR j FROM 1 TO count DO
                decoded_string = decoded_string + char
            END FOR
        END WHILE
        RETURN decoded_string
    END PROCEDURE

--- Huffman Coding (Revisited) ---
Explanation:
    (Revisited, see Greedy Algorithms)
    A greedy algorithm used for lossless data compression. It builds a binary
    tree to assign variable-length codes to input characters, with more
    frequent characters having shorter codes, resulting in optimal prefix codes.
Pseudo Code:
    (See HuffmanCoding in Greedy Algorithms)

--- Lempel-Ziv-Welch (LZW) Compression ---
Explanation:
    A universal lossless data compression algorithm. It works by building
    a dictionary of common phrases (sequences of characters) and then encoding
    occurrences of those phrases with shorter codes. It's used in GIF images,
    TIFF, and PDF files.
Pseudo Code:
    // LZW Compression
    PROCEDURE LZW_Compress(input_string)
        dictionary = INITIALIZE_DICTIONARY_WITH_SINGLE_CHARS() // e.g., 'a':1, 'b':2, ...
        output_codes = EMPTY_LIST
        current_sequence = ""
        dict_code_counter = INITIAL_CODE_FOR_NEW_PHRASES // e.g., 257 for ASCII

        FOR EACH char IN input_string DO
            new_sequence = current_sequence + char
            IF new_sequence IN dictionary THEN
                current_sequence = new_sequence
            ELSE
                ADD dictionary[current_sequence] TO output_codes
                dictionary[new_sequence] = dict_code_counter
                dict_code_counter = dict_code_counter + 1
                current_sequence = char
            END IF
        END FOR
        ADD dictionary[current_sequence] TO output_codes // Add last sequence
        RETURN output_codes
    END PROCEDURE

    // LZW Decompression
    PROCEDURE LZW_Decompress(input_codes)
        dictionary = INITIALIZE_DICTIONARY_WITH_SINGLE_CHARS()
        decoded_string = ""
        dict_code_counter = INITIAL_CODE_FOR_NEW_PHRASES

        previous_code = input_codes[0]
        previous_entry = dictionary[previous_code]
        decoded_string = decoded_string + previous_entry

        FOR i FROM 1 TO LENGTH(input_codes)-1 DO
            current_code = input_codes[i]
            
            IF current_code IN dictionary THEN
                current_entry = dictionary[current_code]
            ELSE IF current_code == dict_code_counter THEN
                current_entry = previous_entry + previous_entry[0] // Special case: C + C[0]
            ELSE
                // Error: code not in dictionary and not the special case
                RETURN ERROR
            END IF

            decoded_string = decoded_string + current_entry
            
            // Add new entry to dictionary
            new_entry = previous_entry + current_entry[0]
            dictionary[dict_code_counter] = new_entry
            dict_code_counter = dict_code_counter + 1

            previous_code = current_code
            previous_entry = current_entry
        END FOR
        RETURN decoded_string
    END PROCEDURE

================================
PARALLEL AND DISTRIBUTED ALGORITHMS
================================

--- MapReduce ---
Explanation:
    A programming model and a framework for processing large datasets
    with a parallel, distributed algorithm on a cluster. It consists of
    two main phases:
    1. Map: Processes input data to generate key-value pairs.
    2. Reduce: Aggregates values based on keys.
Pseudo Code:
    // Map Phase (executed in parallel on chunks of input data)
    PROCEDURE Map(input_key, input_value)
        // Example: Word count
        FOR EACH word IN TOKENIZE(input_value) DO
            EMIT(word, 1) // Output (key, value) pair
        END FOR
    END PROCEDURE

    // Shuffle and Sort Phase (handled by the framework)
    // Groups all values by key and sorts them, sending to reducer.

    // Reduce Phase (executed in parallel for each unique key)
    PROCEDURE Reduce(key, list_of_values)
        // Example: Word count
        sum = 0
        FOR EACH value IN list_of_values DO
            sum = sum + value
        END FOR
        EMIT_RESULT(key, sum) // Output final result
    END PROCEDURE

--- Paxos Algorithm (Consensus) ---
Explanation:
    A family of protocols for solving consensus in a network of unreliable
    processors (or processes). It allows a set of nodes to agree on a single
    value, even if some nodes fail. It's complex and involves roles like
    Proposer, Acceptor, and Learner.
Pseudo Code:
    (Highly conceptual, very complex distributed protocol)
    // Roles:
    // Proposer: Proposes a value, tries to get it accepted.
    // Acceptor: Responds to proposals, accepts values.
    // Learner: Learns the agreed-upon value.

    // Phase 1a: Prepare (Proposer to Acceptors)
    PROCEDURE Proposer_SendPrepare(proposal_number N)
        FOR EACH acceptor IN ALL_ACCEPTORS DO
            SEND("PREPARE", N) TO acceptor
        END FOR
    END PROCEDURE

    // Phase 1b: Promise (Acceptor to Proposer)
    PROCEDURE Acceptor_ReceivePrepare(proposal_number N)
        IF N > latest_promised_proposal_number THEN
            latest_promised_proposal_number = N
            SEND("PROMISE", N, latest_accepted_proposal_number, latest_accepted_value) TO proposer
        ELSE
            SEND("NACK", N) TO proposer
        END IF
    END PROCEDURE

    // Phase 2a: Accept (Proposer to Acceptors)
    PROCEDURE Proposer_SendAccept(proposal_number N, value V)
        // Proposer selects V: if any acceptor promised a value, it picks the value
        // associated with the highest proposal number; otherwise, it picks its own value.
        FOR EACH acceptor IN ALL_ACCEPTORS DO
            SEND("ACCEPT", N, V) TO acceptor
        END FOR
    END PROCEDURE

    // Phase 2b: Accepted (Acceptor to Proposer/Learners)
    PROCEDURE Acceptor_ReceiveAccept(proposal_number N, value V)
        IF N >= latest_promised_proposal_number THEN // N must be at least the promised one
            latest_promised_proposal_number = N
            latest_accepted_proposal_number = N
            latest_accepted_value = V
            SEND("ACCEPTED", N, V) TO learners
        ELSE
            SEND("NACK", N) TO proposer
        END IF
    END PROCEDURE

    // Learners observe accepted messages from a majority of acceptors.

--- Raft Algorithm (Consensus) ---
Explanation:
    A consensus algorithm designed to be more understandable than Paxos.
    It's used to manage a replicated log, ensuring that all state machines
    in a distributed system agree on the same sequence of commands, even in
    the face of failures. It defines roles: Leader, Follower, Candidate.
Pseudo Code:
    (Highly conceptual, very complex distributed protocol)
    // Roles:
    // Leader: Handles all client requests, replicates log entries.
    // Follower: Passive, responds to requests from Leader and Candidates.
    // Candidate: Tries to become Leader.

    // State Variables (on each server):
    // currentTerm, votedFor, log[]
    // commitIndex, lastApplied
    // nextIndex[], matchIndex[] (on Leader)

    // AppendEntries RPC (Leader to Followers/Candidates)
    PROCEDURE HandleAppendEntries(term, leaderId, prevLogIndex, prevLogTerm, entries[], leaderCommit)
        IF term < currentTerm THEN RETURN {success: false, term: currentTerm}
        // ... (Log consistency checks)
        // ... (Append new entries)
        // ... (Update commitIndex)
        RETURN {success: true, term: currentTerm}
    END PROCEDURE

    // RequestVote RPC (Candidate to other servers)
    PROCEDURE HandleRequestVote(term, candidateId, lastLogIndex, lastLogTerm)
        IF term < currentTerm THEN RETURN {voteGranted: false, term: currentTerm}
        IF term > currentTerm THEN
            currentTerm = term
            votedFor = NULL
            // Convert to follower
        END IF
        IF votedFor IS NULL OR votedFor == candidateId THEN
            // ... (Log up-to-date check)
            votedFor = candidateId
            RETURN {voteGranted: true, term: currentTerm}
        END IF
        RETURN {voteGranted: false, term: currentTerm}
    END PROCEDURE

    // Leader Election (Candidate state)
    // If follower receives no communication, it becomes a candidate, increments term,
    // votes for itself, sends RequestVote RPCs, waits for votes.
    // If it gets majority votes, it becomes leader.

--- MPI (Message Passing Interface) ---
Explanation:
    A standardized and portable message-passing standard designed to allow
    programs to run in parallel on distributed memory architectures. It's
    a library specification, not an algorithm itself, but a tool for
    implementing parallel algorithms.
Pseudo Code:
    (MPI defines functions for communication, not a single algorithm)
    // Example: Parallel Sum
    PROCEDURE ParallelSum(ARRAY A)
        // Assume A is distributed across processes
        
        MPI_INIT() // Initialize MPI environment
        rank = MPI_COMM_RANK(MPI_COMM_WORLD) // Get current process rank
        size = MPI_COMM_SIZE(MPI_COMM_WORLD) // Get total number of processes

        local_array_chunk = GET_LOCAL_CHUNK(A, rank, size)
        local_sum = SUM(local_array_chunk)

        // Gather all local sums at root process (rank 0)
        IF rank == 0 THEN
            global_sums = ARRAY of size 'size'
            MPI_GATHER(&local_sum, 1, MPI_INT, &global_sums, 1, MPI_INT, 0, MPI_COMM_WORLD)
            total_sum = SUM(global_sums)
            PRINT "Total sum: " total_sum
        ELSE
            MPI_GATHER(&local_sum, 1, MPI_INT, NULL, 0, MPI_INT, 0, MPI_COMM_WORLD)
        END IF
        
        MPI_FINALIZE() // Finalize MPI environment
    END PROCEDURE