Skip to content

Latest commit

 

History

History
94 lines (73 loc) · 3.37 KB

2 - Algorithms.md

File metadata and controls

94 lines (73 loc) · 3.37 KB
Raw

Algorithms

Types of Algorithms

Iterative

  • An algorithm that is called repeatedly but for a finite number of times, each time being a single iteration.
  • Often used to move incrementally through a dataset.

Recursive

  • An algorithm that calls itself in its definition.
  • The recursive case in a conditional statement is used to trigger the recursion.
  • The base case in a conditional statement is used to break the recursion.
  • Note that recursive algorithms can be very space inefficient as each recursive call adds a new layer to the stack.

Greedy

  • An algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
  • The general five components, taken from Wikipedia:
    • A candidate set, from which a solution is created.
    • A selection function, which chooses the best candidate to be added to the solution.
    • A feasibility function, which is used to determine if a candidate can be used to contribute to a solution.
    • An objective function, which assigns a value to a solution, or a partial solution.
    • A solution function, which will indicate when we have discovered a complete solution.

Dynamic Programming

Dynamic programming is a general method for solving a problem with optimal substructure by breaking it down into overlapping subproblems.

  • A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. Additionally, the solution to one subproblem should not affect the solution to another subproblem of the same problem.
  • A problem has overlapping subproblems when a recursive solution revisits the same problem repeatedly.

Top-Down: Memoize (store) the solutions to subproblems and solve problem recursively.

int fibonacci(int n) {
    return fibonacci(n, new int[n + 1]);
}

int fibonacci(int i, int[] memo) {
    if (i == 0 || i == 1) return i;

    if (memo[i] == 0) {
        memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
    }

    return memo[i];
}

Bottom-Up: Build up subproblems from base case up and avoid recursive overhead. Order subproblems by topologically sorting the DAG of dependencies.

int fibonacci(int n) {
    if (n == 0 || n == 1) return n;

    int[] memo = new int[n];
    memo[0] = 0;
    memo[1] = 1;
    for (int i = 2; i < n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }

    return memo[n - 1] + memo[n - 2];
}

Important Algorithms