b.stefanuk.ca

Appearance

Greedy Algorithms & Invariants ​

A greedy algorithm is one in which you solve sub-problems of a larger problem, selecting locally optimum solutions at each step, never changing the decision made at each step. Greedy algorithms don't always provide optimal solutions, but sometimes they do.

Working with Greedy Algorithms
  • Consider greedy algorithms when you're solving an optimization problem where there's a natural set of choices to select from
  • It's easier to conceptiualize greedy algorithms recursively first, then implement hem using iteration for higher performance.
  • Greedy algorithms that don't provide an optimum solution are still typically valuable for their insights, and can serve as a heuristic when finding the best solution.
  • The correct greedy algorithm is not always obvious

An invariant is a condition or fact that holds true during the entire execution of a program.

Working with Invariants
  • Usually, the invariant is a subset of the input space, e.g., a subarray.
  • Identifying the correct invariant is difficult. The best strategy is to work on small examples to hypothesize the invariant.

Relevant problems ​

2 Sum ​

The traditional way to solve this problem is to use a hash map. See Hash Tables - Relevant problems.

With the invariant approach, the array must first be sorted. The solution uses a two pointer approach starting at the first and last index, and uses the following invariant: the sum of the lowest and highest values---at indices $i$ and $n-1$, respectively---tell us which pointer we need to move to move towards the solution. Namely, if the sum of $i$ and $n-1$ is greater than the target $t$, then we need a smaller sum. This can only be realized if we move the right-most pointer to $n-2$. Conversely, if the sum is smaller than $t$, we need a larger sum, necessitating that we increment $i$. Solution => $O(n)$ time with $O(1)$ space.

3 Sum ​

The solution to this problem is an extension to the 2 Sum solution and uses the same invariant. First, sort the array => $O(n \log n)$. Then for each element $i$ in the array, conduct the 2 Sum solution, using the dummy target $t - A[i]$. Solution => $O(n^2)$.

The Gasup Problem ​

Cities (1D) have a certain number of gallons, identify cities from which a loop is possible. (Documented solution unclear)

Starting at any $i$, do two complete passes through the ring. At each $i$, until you reach a cycle, add to a result vector the current gas when starting from each of the already visited stations, and add a new item for the current station. Fill up at each station before adding. If at any point the value for you drop below 0, on any of the entries, remove the associated starting point from the list of candidates.