Algorithm

• Used in grep

Algorithm for searching for a short pattern in a long text.

• Change with the next one if out of order.
• Time Complexity: \( O(N^2) \)
• Good for mostly sorted array.

• Find the smallest element within the undetermined next part and let it be the first one within the part.
• Time Complexity: \(O(N^2)\)
• Consistently slow.

• Insert the next element into the correct position within the sorted previous part.
• Time Complexity: \(O(N^{2})\)
• Usually fast, but slow when the array is in reverse order, to the exact point of the selection sort.
• Exceptional when few elements added to a sorted array.

• Sort the array digit by digit from the least significant digit.
• Uses an array of array that stores the elements in an outer array that matches its digit and append it in the end of the inner array, later to be read from the start.
• Time Complexity: \(O(kN)\) where \(k\) is the largest number of digits.
• Not in-place

• Recursively perform merge sort on half of the input and merge those two halves.
• Time Complexity: \(O(N\log N)\)
• Not in-place Sort, in which the elements are temporarily stored outside of the array.

• Determine a pivot (the last element, in this case) and gather the largers and the smallers, and then perform quick sort on those recursively.
• During the pivoting stage, two pointer are used one-pointer 1-for the end of the smallers, and the other-pointer 2-for the next element to swap position.
• March the pointer 2 until it finds an element smaller than the pivot and swap it with the next element of the pointer 1, march the pointer 1 by 1, again start marching the pointer 2 until it reaches the end (in this case, the pivot).
  • When set the last element to be the pivot the pivot swapped with the first larger element as the last step.
• Time Complexity: \(O(N\log N)\) on average, \(O(N^2)\) in the worst case, but use of some technique prevents the worst case scenario.
  • Pivot can be chosen to be the leftmost element or middle element, in simple implementation.
  • The most common method that eliminates the problem is to use the median of the first, last, middle elements.
• Not stable, the order of same valued element is not preserved.

• Find the largest element within the undetermined previous part and let it be the last one within the part.
• But unlike the selection sort it uses heap, a binary tree in which each node has two or less child nodes, to find the maximum element.
  • The binary tree can be encoded in an array, in this case, the original array is the heap.
    • Set the root node to be at the index 1. Child nodes have the index of 2i and 2i + 1 of the parent index i.
  • First one need to make the heap into a max-heap, in which all the nodes are larger than or equal to all of their childs.
    • Starting from the nodes that has the depth of just 1 smaller than the leaf nodes, find the largest node among the node and its two children, and swaps with the child node if it's larger. Repeat this until we reach the root node.
    • Note that after a node have swapped, the change needs to be propagated to the children of the swapped child node.
  • After max-heap has been achieved than the first element is the largest one, so swaps it with the last element of the unsorted part, and make max-heap again without the just determined element.
    • This reconstruction of max-heap is simple because it only moves one element at each depth.
• Time Complexity: \(O(N\log N)\)
• Not stable

• Hoare's Selection Algorithm

Find the \( k \)th smallest element in a list.

Probablistically count the number of distinct elements.

Hash each element and find the maximum runs of zeros. If run is longer than there are more distinct elements.

1. Start with a set of elements and few score variables that store the length of longest run.
2. Calculate hash of an element
3. Select one of the scores, and store the length of run of zeros if it is larger than the score.
4. Repeat until exhausted
5. Take the harmonic mean of the scores
6. Larger the mean, larger the number of distinct elements.

We can run this algorithm in parallel, and select the larger score (at each position of score vector).

UNIX spell checker that showed recommendations for typos.

Devised by Soviet scientist, Vladimir Levenshtein in 1965.

def lev(a: str, b: str) -> int:
    if len(a) == 0:
        return len(b)
    if len(b) == 0:
        return len(a)
    if head(a) == head(b): # head(a) = a[0]
        return lev(tail(a), tail(b)) # tail(a) = a[1:]
    return 1 + min(
        lev(tail(a), b),      # case of insertion
        lev(a, tail(b)),      # case of deletion
        lev(tail(a), tail(b)) # case of substitution
    )

• Robert Wagner and Micheal Fischer
• Used dynamic programming upon the Levenshtein distance algorithm.

Given \(n\) points on the domain, it is possible to find degree \(n-2\) polynomial \(p(x)\), such that at every given points \(f(x_i)-p(x_i)\) is distinct, sign alternating, with same error \(h\), using matrix equation,

1. We find the point with the largest error, and substitute it to the closest point with the same sign of error.
2. Repeat this multiple times and we get the minimax approximation.

Produce the minimax approximation of a function in an iterative way.

1. One-point exchange method, but exchange all the points for the points where the errors are at the local maxima.
2. Repeat this until every points of extremum errors is equal-magnitude and sign-alternating.

1. Introduce slack variables for every inequality. Initially the slack variables are basic (loose), and the variables are non-basic (tight).
2. Find a variable to loosen. One of the rules to find it is the Dantzig's pivot rule, which takes a variable with largest non-negative coefficient in the object function.
3. Find a basic variable with largest non-positive constant over coefficient ratio, and tighten it.
4. Rewrite the equations for the basic variables.
5. Repeat step 2 through 4, until every variable in the object function has non-positive coefficient.
6. Set the slack variables to zero, to obtain the maximum.

From a linear program, we can induce dual linear program by expressing the bound of the object function in terms of scalar \(y_i\) multiple of linear inequalities, while flipping the objective of the problem, maximum to minimum and vice versa.

corresponds to

It is solving a linear program with integer variables.

New Maze Generating Algorithm (Origin Shift) - YouTube