Algo rithms

Understanding the Mechanics

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
                swap(&arr[j], &arr[j+1]);
}

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        swap(&arr[min_idx], &arr[i]);
    }
}

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void countingSort(int array[], int size) {
  int output[10];
  int count[10];
  int max = array[0];
  for (int i = 1; i < size; i++) {
    if (array[i] > max)
      max = array[i];
  }
  for (int i = 0; i <= max; ++i) count[i] = 0;
  for (int i = 0; i < size; i++) count[array[i]]++;
  for (int i = 1; i <= max; i++) count[i] += count[i - 1];
  for (int i = size - 1; i >= 0; i--) {
    output[count[array[i]] - 1] = array[i];
    count[array[i]]--;
  }
}

void bogoSort(int* arr, int n) {
    while (!isSorted(arr, n))
        shuffle(arr, n);
}

The Power of Structure

Linear Search (O(n)): The simplest method. You look at every item one by one until you find what you need. It works on any list, sorted or not, but is inefficient for large datasets.

Binary Search (O(log n)): This algorithm fundamentally relies on the data being sorted. By checking the middle element, it can instantly discard half of the remaining possibilities. If you are looking for a name in a phone book of 1,000,000 people, Linear Search might take 1,000,000 steps. Binary Search takes at most 20 steps (log₂ 1,000,000 ≈ 20).

Hash Table (O(1)): The fastest search method. It uses a hash function to map keys to values directly, allowing for average constant-time lookups, unlike scanning an array.

Ancient & Elegant

The Principle: The Greatest Common Divisor (GCD) of two numbers doesn't change if you replace the larger number with the difference (or modulo). GCD(A, B) = GCD(B, A % B).

Visualization: Using the "subtraction" method involves cutting rectangles. If you have a rectangle of 48x18, you can cut off two 18x18 squares, leaving a 12x18 rectangle. Then cut 12x12, leaving 12x6. Finally two 6x6 fit perfectly. Square size 6 is the GCD.

Connectivity & Cycles

Union-Find (or Disjoint-Set Union / DSU) keeps track of elements partitioned into disjoint sets. It's incredibly fast (nearly constant time `O(α(n))`) for two operations:
1. Union: Merge two sets.
2. Find: Determine which set an element belongs to.

It is widely used in network connectivity, image processing, and Kruskal's Algorithm for Minimum Spanning Trees.

Self-Referential Logic

Concept: Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. It consists of a Base Case (when to stop) and a Recursive Step (breaking the problem down).

The Call Stack: Computers handle function calls using a "Stack". When fact(3) calls fact(2), it doesn't finish immediately; it pauses and adds a new "frame" to memory. Only when the base case is reached do the frames "pop" off, passing values back up the chain. If you forget the base case, you get the infinite loop known as a Stack Overflow.

Constraint Satisfaction

Concept: Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time.

In Action: In the N-Queens problem, the algorithm places a Queen in the first available column of the current row. It then moves to the next row. If it finds it cannot place a Queen anywhere in the new row without being attacked, it realizes the previous placement was a mistake. It "backtracks" (returns) to the previous row, moves that Queen to a new spot, and tries again.

Exploring Graphs

BFS (Breadth-First Search): Uses a Queue (FIFO). It radiates out from the starting node level by level. Guaranteed to find the shortest path (fewest edges) in an unweighted graph.

DFS (Depth-First Search): Uses a Stack (LIFO). It plunges deep into one path before backtracking. It doesn't find the shortest path but is useful for exploring all connected components.

Dijkstra's Algorithm: Uses a Priority Queue based on path cost. It excels in Weighted Graphs (where edges have different lengths/costs). It always finds the absolute lowest-cost path.

A* Search (A-Star): A smart search that uses a Heuristic (Euclidean distance here). It prioritizes nodes physically closer to the target, often finding the path much faster.

Deep Dive: Why it works

1. Variable Length Codes: In ASCII, every character is 8 bits (e.g., 'a' is 01100001). Huffman uses variable lengths. Frequent characters like 'e' or 's' might get just 2 or 3 bits, while rare ones get longer codes.

2. The Prefix Property: Notice that no code is a prefix of another. If 'a' = 0, then 'b' cannot be 01, because the decoder wouldn't know if "01" is "a" followed by "1" or just "b". By ensuring this property (via the tree structure), we don't need separators between codes.

3. Greedy Strategy: The algorithm is "greedy" because at each step, it makes the locally optimal choice: it merges the two smallest probability nodes. This simple local rule guarantees a globally optimal tree for the entire message.

Greedy vs. Dynamic Programming

The Greedy Flaw: A greedy strategy picks the item with the highest value-to-weight ratio first. In the example above, it picks the 6kg/$90 item. This fills the bag so much (6/10kg) that it cannot fit the next best items (5kg/$70). It ends up with $100 total.

The DP Solution: Dynamic Programming breaks the problem down. It effectively asks: "For a capacity of X kg, is it better to take this item or leave it?" It checks every combination mathematically. It realizes that skipping the high-ratio 6kg item allows us to take two 5kg items, resulting in $140 total.

Combinatorial Explosion

The Problem: Given a list of cities, find the shortest route that visits each city exactly once and returns to the origin city.

Why it's Hard: There is no known fast algorithm for this. We must use Brute Force (checking every permutation). For 5 cities, there are only (5-1)! / 2 = 12 unique routes. But for 20 cities, there are 60 quadrillion routes. This is an NP-Hard problem.

Greedy vs. Optimal

For canonical coin systems (like US Dollars: 1, 5, 10, 25), a Greedy algorithm (always taking the largest coin possible) is guaranteed to produce the optimal solution (fewest coins). However, for arbitrary systems (e.g., coins 1, 3, 4), Greedy fails. To make 6, Greedy would choose 4+1+1 (3 coins), while the optimal is 3+3 (2 coins).

Trading Space for Time

Naive recursion for Fibonacci is O(2ⁿ) because it recalculates the same values over and over (e.g., calculating Fib(5) requires Fib(3) multiple times). This is known as Overlapping Subproblems. Memoization stores these results in a table (cache) the first time they are computed. This reduces the time complexity to O(n) at the cost of O(n) memory space.