🧠 Algorithms

Core Philosophy: Algorithms are the recipes for efficient computation. A Programmer doesn’t just memorize them but understands the underlying paradigms to choose the right tool for the specific constraints of the system.

---

🌪️ Sorting

Sorting is the foundation for many other optimizations (like binary search).

• Quick Sort: A divide-and-conquer approach. Excellent average-case performance O(n log n).
• Merge Sort: Stable and guarantees O(n log n) even in worst-case. Preferred for linked lists and when stability matters.
• Heap Sort: O(n log n) and performs sorting in-place, making it memory efficient.

Quick Sort

Code Examples (C#)

using System;

class Program
{
    static void Main()
    {
        int[] numbers = { 10, 7, 8, 9, 1, 5 };

        Console.WriteLine("Before sorting:");
        PrintArray(numbers);

        QuickSort(numbers, 0, numbers.Length - 1);

        Console.WriteLine("\nAfter sorting:");
        PrintArray(numbers);
    }

    static void QuickSort(int[] array, int low, int high)
    {
        if (low < high)
        {
            int pivotIndex = Partition(array, low, high);

            QuickSort(array, low, pivotIndex - 1);
            QuickSort(array, pivotIndex + 1, high);
        }
    }

    static int Partition(int[] array, int low, int high)
    {
        int pivot = array[high];
        int i = low - 1;

        for (int j = low; j < high; j++)
        {
            if (array[j] <= pivot)
            {
                i++;
                Swap(array, i, j);
            }
        }

        Swap(array, i + 1, high);
        return i + 1;
    }

    static void Swap(int[] array, int i, int j)
    {
        (array[i], array[j]) = (array[j], array[i]);
    }

    static void PrintArray(int[] array)
    {
        Console.WriteLine(string.Join(", ", array));
    }
}

Merge Sort

Code Examples (C#)

using System;

public class MergeSortExample
{
    public static void Main()
    {
        int[] numbers = { 38, 27, 43, 3, 9, 82, 10 };

        Console.WriteLine("Original Array:");
        PrintArray(numbers);

        MergeSort(numbers, 0, numbers.Length - 1);

        Console.WriteLine("\nSorted Array:");
        PrintArray(numbers);
    }

    public static void MergeSort(int[] array, int left, int right)
    {
        if (left >= right)
            return;

        int middle = left + (right - left) / 2;

        MergeSort(array, left, middle);
        MergeSort(array, middle + 1, right);

        Merge(array, left, middle, right);
    }

    private static void Merge(int[] array, int left, int middle, int right)
    {
        int leftSize = middle - left + 1;
        int rightSize = right - middle;

        int[] leftArray = new int[leftSize];
        int[] rightArray = new int[rightSize];

        Array.Copy(array, left, leftArray, 0, leftSize);
        Array.Copy(array, middle + 1, rightArray, 0, rightSize);

        int i = 0, j = 0, k = left;

        while (i < leftSize && j < rightSize)
        {
            if (leftArray[i] <= rightArray[j])
            {
                array[k++] = leftArray[i++];
            }
            else
            {
                array[k++] = rightArray[j++];
            }
        }

        while (i < leftSize)
        {
            array[k++] = leftArray[i++];
        }

        while (j < rightSize)
        {
            array[k++] = rightArray[j++];
        }
    }

    private static void PrintArray(int[] array)
    {
        Console.WriteLine(string.Join(", ", array));
    }
}

Heap Sort

Code Examples (C#)

using System;

public class HeapSort
{
    public static void Sort(int[] array)
    {
        int n = array.Length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--)
        {
            Heapify(array, n, i);
        }

        // Extract elements one by one from heap
        for (int i = n - 1; i > 0; i--)
        {
            // Move current root to end
            Swap(array, 0, i);

            // Call heapify on the reduced heap
            Heapify(array, i, 0);
        }
    }

    private static void Heapify(int[] array, int heapSize, int root)
    {
        int largest = root;
        int left = 2 * root + 1;
        int right = 2 * root + 2;

        // Check left child
        if (left < heapSize && array[left] > array[largest])
        {
            largest = left;
        }

        // Check right child
        if (right < heapSize && array[right] > array[largest])
        {
            largest = right;
        }

        // If root is not largest, swap and continue heapifying
        if (largest != root)
        {
            Swap(array, root, largest);
            Heapify(array, heapSize, largest);
        }
    }

    private static void Swap(int[] array, int i, int j)
    {
        (array[i], array[j]) = (array[j], array[i]);
    }

    public static void Main()
    {
        int[] numbers = { 12, 11, 13, 5, 6, 7 };

        Console.WriteLine("Original Array:");
        Console.WriteLine(string.Join(", ", numbers));

        Sort(numbers);

        Console.WriteLine("Sorted Array:");
        Console.WriteLine(string.Join(", ", numbers));
    }
}

---

🔍 Searching

Finding data efficiently is the most common task in software engineering.

• Binary Search: The gold standard for sorted data (O(log n)).
• Breadth-First Search (BFS): Explores neighbors first. Ideal for finding the shortest path in unweighted graphs.
• Depth-First Search (DFS): Explores branches deeply. Ideal for exhaustive searches and topological sorting.

Binary Search

Code Examples (C#)

using System;

public class BinarySearchExample
{
    public static int BinarySearch(int[] array, int target)
    {
        int left = 0;
        int right = array.Length - 1;

        while (left <= right)
        {
            int middle = left + (right - left) / 2;

            if (array[middle] == target)
            {
                return middle; // Target found
            }

            if (array[middle] < target)
            {
                left = middle + 1;
            }
            else
            {
                right = middle - 1;
            }
        }

        return -1; // Target not found
    }

    public static void Main()
    {
        int[] numbers = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
        int target = 23;

        int index = BinarySearch(numbers, target);

        if (index != -1)
        {
            Console.WriteLine($"Found {target} at index {index}");
        }
        else
        {
            Console.WriteLine($"{target} was not found");
        }
    }
}

Breadth-First Search (BFS)

Code Examples (C#)

using System;
using System.Collections.Generic;

public class Graph
{
    private readonly Dictionary<string, List<string>> _adjacencyList = new();

    public void AddEdge(string source, string destination)
    {
        if (!_adjacencyList.ContainsKey(source))
            _adjacencyList[source] = new List<string>();

        if (!_adjacencyList.ContainsKey(destination))
            _adjacencyList[destination] = new List<string>();

        _adjacencyList[source].Add(destination);
        _adjacencyList[destination].Add(source); // Remove for directed graph
    }

    public void BreadthFirstSearch(string startNode)
    {
        var visited = new HashSet<string>();
        var queue = new Queue<string>();

        visited.Add(startNode);
        queue.Enqueue(startNode);

        while (queue.Count > 0)
        {
            string current = queue.Dequeue();
            Console.Write($"{current} ");

            foreach (var neighbour in _adjacencyList[current])
            {
                if (!visited.Contains(neighbour))
                {
                    visited.Add(neighbour);
                    queue.Enqueue(neighbour);
                }
            }
        }
    }
}

public class Program
{
    public static void Main()
    {
        var graph = new Graph();

        graph.AddEdge("A", "B");
        graph.AddEdge("A", "C");
        graph.AddEdge("B", "D");
        graph.AddEdge("B", "E");
        graph.AddEdge("C", "F");

        Console.WriteLine("BFS Traversal:");
        graph.BreadthFirstSearch("A");
    }
}

Depth-First Search (DFS)

Code Examples (C#)

using System;
using System.Collections.Generic;

public class Graph
{
    private readonly Dictionary<int, List<int>> _adjacencyList;

    public Graph()
    {
        _adjacencyList = new Dictionary<int, List<int>>();
    }

    public void AddEdge(int source, int destination)
    {
        if (!_adjacencyList.ContainsKey(source))
            _adjacencyList[source] = new List<int>();

        if (!_adjacencyList.ContainsKey(destination))
            _adjacencyList[destination] = new List<int>();

        _adjacencyList[source].Add(destination);
    }

    public void DFS(int startVertex)
    {
        var visited = new HashSet<int>();
        DFSRecursive(startVertex, visited);
    }

    private void DFSRecursive(int vertex, HashSet<int> visited)
    {
        visited.Add(vertex);

        Console.WriteLine(vertex);

        foreach (var neighbour in _adjacencyList[vertex])
        {
            if (!visited.Contains(neighbour))
            {
                DFSRecursive(neighbour, visited);
            }
        }
    }
}

class Program
{
    static void Main()
    {
        Graph graph = new Graph();

        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(1, 4);
        graph.AddEdge(2, 5);

        Console.WriteLine("DFS traversal starting from vertex 0:");
        graph.DFS(0);
    }
}

---

💰 Greedy Algorithms

Greedy algorithms make the locally optimal choice at each step, hoping to find a global optimum.

• Concept: They are fast and simple but don’t always yield the best solution.
• Use Cases:
  • Dijkstra’s Algorithm: Finding the shortest path in a weighted graph.
  • Huffman Coding: Data compression.
  • Fractional Knapsack: When items can be broken into smaller pieces.

Dijkstra’s Algorithm

Code Examples (C#)

using System;
using System.Collections.Generic;

public class DijkstraExample
{
    public static Dictionary<int, int> Dijkstra(
        Dictionary<int, List<(int Neighbor, int Weight)>> graph,
        int startNode)
    {
        var distances = new Dictionary<int, int>();
        var priorityQueue = new PriorityQueue<int, int>();

        // Initialize distances
        foreach (var node in graph.Keys)
        {
            distances[node] = int.MaxValue;
        }

        distances[startNode] = 0;
        priorityQueue.Enqueue(startNode, 0);

        while (priorityQueue.Count > 0)
        {
            priorityQueue.TryDequeue(out int currentNode, out int currentDistance);

            // Skip stale entries
            if (currentDistance > distances[currentNode])
                continue;

            foreach (var (neighbor, weight) in graph[currentNode])
            {
                int newDistance = distances[currentNode] + weight;

                if (newDistance < distances[neighbor])
                {
                    distances[neighbor] = newDistance;
                    priorityQueue.Enqueue(neighbor, newDistance);
                }
            }
        }

        return distances;
    }

    public static void Main()
    {
        var graph = new Dictionary<int, List<(int Neighbor, int Weight)>>()
        {
            { 0, new() { (1, 4), (2, 1) } },
            { 1, new() { (3, 1) } },
            { 2, new() { (1, 2), (3, 5) } },
            { 3, new() { } }
        };

        int startNode = 0;

        var distances = Dijkstra(graph, startNode);

        Console.WriteLine($"Shortest distances from node {startNode}:");

        foreach (var kvp in distances)
        {
            Console.WriteLine($"Node {kvp.Key}: {kvp.Value}");
        }
    }
}

Huffman Coding

Code Examples (C#)

// Huffman Node
public class HuffmanNode
{
    public char? Character { get; set; }
    public int Frequency { get; set; }

    public HuffmanNode Left { get; set; }
    public HuffmanNode Right { get; set; }

    public bool IsLeaf => Left == null && Right == null;
}

// Huffman Coding Class
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class HuffmanCoding
{
    public HuffmanNode BuildTree(string text)
    {
        var frequencies = text
            .GroupBy(c => c)
            .ToDictionary(g => g.Key, g => g.Count());

        var nodes = frequencies
            .Select(f => new HuffmanNode
            {
                Character = f.Key,
                Frequency = f.Value
            })
            .ToList();

        while (nodes.Count > 1)
        {
            var left = nodes.OrderBy(n => n.Frequency).First();
            nodes.Remove(left);

            var right = nodes.OrderBy(n => n.Frequency).First();
            nodes.Remove(right);

            var parent = new HuffmanNode
            {
                Character = null,
                Frequency = left.Frequency + right.Frequency,
                Left = left,
                Right = right
            };

            nodes.Add(parent);
        }

        return nodes.First();
    }

    public Dictionary<char, string> GenerateCodes(HuffmanNode root)
    {
        var codes = new Dictionary<char, string>();
        GenerateCodesRecursive(root, "", codes);
        return codes;
    }

    private void GenerateCodesRecursive(
        HuffmanNode node,
        string code,
        Dictionary<char, string> codes)
    {
        if (node == null)
            return;

        if (node.IsLeaf && node.Character.HasValue)
        {
            codes[node.Character.Value] = code;
            return;
        }

        GenerateCodesRecursive(node.Left, code + "0", codes);
        GenerateCodesRecursive(node.Right, code + "1", codes);
    }

    public string Encode(string text, Dictionary<char, string> codes)
    {
        var sb = new StringBuilder();

        foreach (char c in text)
        {
            sb.Append(codes[c]);
        }

        return sb.ToString();
    }

    public string Decode(string encodedText, HuffmanNode root)
    {
        var result = new StringBuilder();
        var current = root;

        foreach (char bit in encodedText)
        {
            current = bit == '0'
                ? current.Left
                : current.Right;

            if (current.IsLeaf)
            {
                result.Append(current.Character);
                current = root;
            }
        }

        return result.ToString();
    }
}

// Example Usage
class Program
{
    static void Main()
    {
        string text = "HELLO HUFFMAN";

        var huffman = new HuffmanCoding();

        HuffmanNode root = huffman.BuildTree(text);

        Dictionary<char, string> codes =
            huffman.GenerateCodes(root);

        Console.WriteLine("Huffman Codes:");

        foreach (var code in codes.OrderBy(c => c.Key))
        {
            Console.WriteLine($"{code.Key} : {code.Value}");
        }

        string encoded = huffman.Encode(text, codes);

        Console.WriteLine($"\nOriginal: {text}");
        Console.WriteLine($"Encoded : {encoded}");

        string decoded = huffman.Decode(encoded, root);

        Console.WriteLine($"Decoded : {decoded}");
    }
}

Fractional Knapsack

Code Examples (C#)

using System;
using System.Collections.Generic;
using System.Linq;

public class Item
{
    public double Value { get; set; }
    public double Weight { get; set; }

    public double Ratio => Value / Weight;
}

public class FractionalKnapsack
{
    public static double GetMaximumValue(List<Item> items, double capacity)
    {
        // Sort by value-to-weight ratio descending
        var sortedItems = items
            .OrderByDescending(i => i.Ratio)
            .ToList();

        double totalValue = 0.0;
        double remainingCapacity = capacity;

        foreach (var item in sortedItems)
        {
            if (remainingCapacity == 0)
                break;

            if (item.Weight <= remainingCapacity)
            {
                // Take the whole item
                totalValue += item.Value;
                remainingCapacity -= item.Weight;

                Console.WriteLine(
                    $"Take 100% of item (Value={item.Value}, Weight={item.Weight})");
            }
            else
            {
                // Take only a fraction
                double fraction = remainingCapacity / item.Weight;

                totalValue += item.Value * fraction;

                Console.WriteLine(
                    $"Take {fraction:P2} of item (Value={item.Value}, Weight={item.Weight})");

                remainingCapacity = 0;
            }
        }

        return totalValue;
    }

    public static void Main()
    {
        var items = new List<Item>
        {
            new Item { Value = 60, Weight = 10 },
            new Item { Value = 100, Weight = 20 },
            new Item { Value = 120, Weight = 30 }
        };

        double capacity = 50;

        double maxValue = GetMaximumValue(items, capacity);

        Console.WriteLine($"\nMaximum value: {maxValue}");
    }
}

---

🧩 Dynamic Programming (DP)

DP is used to solve complex problems by breaking them down into simpler subproblems. It is the way to handle recursion by avoiding redundant calculations.

Key Strategies:

1. Memoization (Top-Down): Cache the results of expensive function calls and return the cached result when the same inputs occur again.
2. Tabulation (Bottom-Up): Solve the smallest subproblems first and store their results in a table (usually an array or matrix).

Classic Problems:

• 0/1 Knapsack: Making optimal choices with limited capacity.
• Longest Common Subsequence: Used in diff tools and bioinformatics.
• Fibonacci/Path Finding: The entry point for understanding state transitions.

---

⚖️ Trade-offs & Decisions

Strategy	When to Use	Trade-off
Greedy	When a “good enough” or local optimum is sufficient.	Might miss the global optimal solution.
Dynamic Programming	When subproblems overlap (e.g., calculating the same thing twice).	Higher memory usage (Space Complexity).
Recursion vs. Iteration	When the problem is naturally recursive (Trees).	Risk of StackOverflow in languages without Tail Call Optimization.

💡 Note: Before implementing a complex DP solution, ask: “Is the dataset small enough that a simpler O(n^2) approach is more maintainable?” Often, code readability and maintenance cost are more important than shaving off a few milliseconds if n is consistently small.

---

🔗 Related Links

• [Big-O Complexity]
• [Data Structures]
• [Design Patterns]