Skip to main content

1 - Algorithm Basics

An algorithm is a step-by-step procedure for solving a problem or accomplishing a task. In computer science, algorithms are the foundation of problem-solving and are essential for efficient software development.

What is an Algorithm?​

Think of an algorithm as a recipe. Just as a recipe provides detailed instructions to prepare a dish, an algorithm provides a sequence of well-defined steps to solve a problem. For example, a recipe for making a sandwich might include steps like:

  1. Take two slices of bread
  2. Spread butter on one side of each slice
  3. Add cheese, lettuce, and tomato
  4. Put the slices together

Similarly, an algorithm to find the maximum value in a list might include:

/// <summary>
/// Finds the maximum value in an array of integers.
/// </summary>
/// <param name="numbers">The array of integers to search.</param>
/// <returns>The maximum value found in the array.</returns>
/// <exception cref="ArgumentException">Thrown when the array is empty.</exception>
public int FindMax(int[] numbers)
{
    // Validate input to prevent errors
    if (numbers == null || numbers.Length == 0)
    {
        throw new ArgumentException("Array cannot be null or empty", nameof(numbers));
    }
    
    // Start by assuming the first element is the maximum
    int max = numbers[0];
    
    // Check each element in the array
    for (int i = 1; i < numbers.Length; i++)
    {
        // If we find a larger element, update our maximum
        // This is the core of the algorithm - a simple comparison
        if (numbers[i] > max)
        {
            max = numbers[i];
        }
    }
    
    // Return the maximum value found
    return max;
}

What Makes a Good Algorithm?​

A good algorithm should have the following characteristics:

  1. Correctness: It should solve the problem it was designed to solve.

    • Example: An algorithm to sort numbers should correctly arrange them in order.

  2. Efficiency: It should use computational resources (time and memory) efficiently.

    • Example: Finding an element in a sorted array using binary search (O(log n)) is more efficient than linear search (O(n)).

  3. Simplicity: It should be easy to understand and implement.

    • Example: A straightforward solution that's easy to code and debug is often preferable to a complex one.

  4. Generality: It should work for all possible inputs within its domain.

    • Example: A sorting algorithm should work for any valid array, not just specific cases.

  5. Optimality: It should be the best possible solution for the given constraints.

    • Example: Using the most appropriate data structure for the problem at hand.

Algorithm Design Techniques​

When designing algorithms, several approaches can be used:

Brute Force​

The brute force approach involves trying all possible solutions until finding the correct one.

Example: Finding all pairs in an array that sum to a target value.

/// <summary>
/// Finds all pairs of numbers in an array that sum to a target value.
/// Uses a brute force approach by checking every possible pair.
/// </summary>
/// <param name="numbers">The array of integers to search.</param>
/// <param name="targetSum">The target sum to find.</param>
/// <returns>A list of tuples containing pairs that sum to the target.</returns>
public List<(int, int)> FindPairs(int[] numbers, int targetSum)
{
    // Initialize a list to store the pairs we find
    List<(int, int)> result = new List<(int, int)>();
    
    // Check every possible pair using nested loops
    // This is what makes it a "brute force" approach
    for (int i = 0; i < numbers.Length; i++)
    {
        // Start j at i+1 to avoid duplicate pairs and self-pairing
        for (int j = i + 1; j < numbers.Length; j++)
        {
            // Check if this pair sums to our target
            if (numbers[i] + numbers[j] == targetSum)
            {
                // If it does, add the pair to our result list
                result.Add((numbers[i], numbers[j]));
            }
        }
    }
    
    // Return all the pairs we found
    return result;
    
    // Note: This algorithm has O(n²) time complexity because of the nested loops
    // For large arrays, a more efficient approach using a hash set would be O(n)
}

Divide and Conquer​

This technique breaks a problem into smaller subproblems, solves them, and combines their solutions.

Example: Merge Sort algorithm for sorting an array.

/// <summary>
/// Sorts an array using the Merge Sort algorithm, a classic divide and conquer approach.
/// </summary>
/// <param name="array">The array to sort.</param>
/// <returns>A new sorted array.</returns>
public int[] MergeSort(int[] array)
{
    // Base case: arrays with 0 or 1 elements are already sorted
    // This is where the recursion stops
    if (array.Length <= 1)
        return array;
    
    // DIVIDE step: Split the array into two halves
    int middle = array.Length / 2;
    
    // Create left and right subarrays
    // Using LINQ for clarity, though Array.Copy would be more efficient
    int[] left = array.Take(middle).ToArray();
    int[] right = array.Skip(middle).ToArray();
    
    // CONQUER step: Sort each half recursively
    // This is where the divide and conquer happens - we break the problem down
    // into smaller instances of the same problem
    left = MergeSort(left);
    right = MergeSort(right);
    
    // COMBINE step: Merge the sorted halves
    // This is where we combine the solutions to the subproblems
    return Merge(left, right);
}

/// <summary>
/// Helper method to merge two sorted arrays into a single sorted array.
/// </summary>
/// <param name="left">First sorted array.</param>
/// <param name="right">Second sorted array.</param>
/// <returns>A merged sorted array.</returns>
private int[] Merge(int[] left, int[] right)
{
    // Create a result array to hold the merged elements
    int[] result = new int[left.Length + right.Length];
    int leftIndex = 0, rightIndex = 0, resultIndex = 0;
    
    // Compare elements from both arrays and take the smaller one
    // This ensures the result array is sorted
    while (leftIndex < left.Length && rightIndex < right.Length)
    {
        if (left[leftIndex] <= right[rightIndex])
            result[resultIndex++] = left[leftIndex++];
        else
            result[resultIndex++] = right[rightIndex++];
    }
    
    // Copy any remaining elements from the left array
    // If the left array has elements left, they're all greater than
    // what we've already added to the result
    while (leftIndex < left.Length)
        result[resultIndex++] = left[leftIndex++];
    
    // Copy any remaining elements from the right array
    while (rightIndex < right.Length)
        result[resultIndex++] = right[rightIndex++];
    
    return result;
    
    // Note: Merge Sort has O(n log n) time complexity, making it much more
    // efficient than simple sorting algorithms like Bubble Sort for large arrays
}

Dynamic Programming​

This approach breaks a problem into overlapping subproblems and solves each subproblem only once, storing the results for future use.

Example: Computing Fibonacci numbers efficiently.

/// <summary>
/// Calculates the nth Fibonacci number using dynamic programming.
/// This approach stores previously calculated values to avoid redundant calculations.
/// </summary>
/// <param name="n">The position in the Fibonacci sequence (0-based).</param>
/// <returns>The nth Fibonacci number.</returns>
/// <exception cref="ArgumentException">Thrown when n is negative.</exception>
public int Fibonacci(int n)
{
    // Validate input
    if (n < 0)
        throw new ArgumentException("Input must be non-negative", nameof(n));
    
    // Base cases: F(0) = 0, F(1) = 1
    if (n <= 1)
        return n;
    
    // Create an array to store Fibonacci numbers
    // This is the key to dynamic programming - we store solutions to subproblems
    int[] fib = new int[n + 1];
    fib[0] = 0;
    fib[1] = 1;
    
    // Fill the array by building up from smaller values
    // This is the bottom-up approach to dynamic programming
    for (int i = 2; i <= n; i++)
    {
        // Each number is the sum of the two previous numbers
        // We're reusing previously calculated values instead of recalculating them
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    
    // Return the nth Fibonacci number
    return fib[n];
    
    // Note: This has O(n) time complexity, much better than the O(2^n) 
    // recursive approach without memoization
}

Greedy Algorithms​

Greedy algorithms make locally optimal choices at each step with the hope of finding a global optimum.

Example: Making change with the fewest coins possible.

/// <summary>
/// Makes change for a given amount using the minimum number of coins.
/// Uses a greedy approach by always taking the largest possible coin.
/// </summary>
/// <param name="amount">The amount to make change for.</param>
/// <param name="denominations">Available coin denominations.</param>
/// <returns>A list of coins that sum to the given amount.</returns>
/// <remarks>
/// Note: This greedy approach works for standard US coin denominations [25, 10, 5, 1]
/// but may not produce the optimal solution for all coin systems.
/// </remarks>
public List<int> MakeChange(int amount, int[] denominations)
{
    // Sort denominations in descending order (largest first)
    // This is the key to the greedy approach - we always take the largest coin possible
    Array.Sort(denominations);
    Array.Reverse(denominations);
    
    List<int> result = new List<int>();
    int remainingAmount = amount;
    
    // For each denomination, take as many coins as possible
    foreach (int coin in denominations)
    {
        // While we can still use this coin denomination
        while (remainingAmount >= coin)
        {
            // Add the coin to our result
            result.Add(coin);
            // Reduce the remaining amount
            remainingAmount -= coin;
        }
    }
    
    return result;
    
    // Example: For amount = 63 with US coins [25, 10, 5, 1]
    // We'd use 2 quarters (25¢), 1 dime (10¢), and 3 pennies (1¢)
    // Result: [25, 25, 10, 1, 1, 1] (6 coins total)
}

Backtracking​

Backtracking builds a solution incrementally and abandons a path when it's determined that it cannot lead to a valid solution.

Example: Solving a Sudoku puzzle.

/// <summary>
/// Solves a Sudoku puzzle using backtracking.
/// </summary>
/// <param name="board">A 9x9 Sudoku board where 0 represents empty cells.</param>
/// <returns>True if the puzzle is solvable, false otherwise.</returns>
public bool SolveSudoku(int[,] board)
{
    // Find an empty cell
    int row = -1, col = -1;
    bool isEmpty = false;
    
    // Scan the board to find an empty cell
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (board[i, j] == 0)
            {
                row = i;
                col = j;
                isEmpty = true;
                break;
            }
        }
        if (isEmpty)
            break;
    }
    
    // If no empty cell is found, the puzzle is solved
    if (!isEmpty)
        return true;
    
    // Try placing digits 1-9 in the empty cell
    for (int num = 1; num <= 9; num++)
    {
        // Check if it's safe to place the number
        if (IsSafe(board, row, col, num))
        {
            // Place the number
            board[row, col] = num;
            
            // Recursively try to solve the rest of the puzzle
            if (SolveSudoku(board))
                return true;
            
            // If placing the number doesn't lead to a solution, backtrack
            // This is the key to backtracking - we undo our choice and try another option
            board[row, col] = 0;
        }
    }
    
    // No solution found with the current configuration
    return false;
}

/// <summary>
/// Checks if it's safe to place a number at a specific position in the Sudoku board.
/// </summary>
/// <param name="board">The Sudoku board.</param>
/// <param name="row">The row index.</param>
/// <param name="col">The column index.</param>
/// <param name="num">The number to check.</param>
/// <returns>True if it's safe to place the number, false otherwise.</returns>
private bool IsSafe(int[,] board, int row, int col, int num)
{
    // Check row - the number must not appear in the same row
    for (int j = 0; j < 9; j++)
        if (board[row, j] == num)
            return false;
    
    // Check column - the number must not appear in the same column
    for (int i = 0; i < 9; i++)
        if (board[i, col] == num)
            return false;
    
    // Check 3x3 box - the number must not appear in the same 3x3 box
    // Calculate the top-left corner of the 3x3 box containing the cell
    int boxRow = row - row % 3;
    int boxCol = col - col % 3;
    
    // Check all cells in the 3x3 box
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (board[boxRow + i, boxCol + j] == num)
                return false;
    
    // If the number doesn't violate any Sudoku rules, it's safe to place
    return true;
}

Why Study Algorithms?​

Understanding algorithms is crucial for several reasons:

  1. Problem-Solving Skills: Algorithms teach you how to approach and solve complex problems systematically.

  2. Efficiency: Knowing different algorithms allows you to choose the most efficient solution for a given problem.

  3. Optimization: You can improve existing solutions by applying algorithmic principles.

  4. Technical Interviews: Algorithm knowledge is frequently tested in programming job interviews.

  5. Foundation for Advanced Topics: Many advanced computer science topics build upon algorithmic concepts.

In the following sections, we'll explore these techniques in more detail and learn how to analyze algorithm efficiency using Big O notation.