https://en.wikipedia.org/wiki/Variation_of_parameters

https://en.wikipedia.org/wiki/Principal_component_analysis

See "A Separator Theorem for Planar Graphs" by Lipton and Tarjan.

Linear time measure approximation of a set union given oracles for uniform sampling on the multiset union and membership testing on the insertion-order labeled set union.

measure: |S| e.g. volume, cardinality, ...

set union: U_i S_i

uniform sampling on the multiset union: Sample (y, k) from U_i { (x, i) : x in S_i } uniformly at random.

membership testing on the union-order labeled set union: Test whether (y, k) belongs to U_i { (x, i) : x in S_i, x not in S_j for j < i }. Can be implemented as testing whether y belongs to { x in S_k : x not in S_j for j < k } in general.

References

• 1983 Karp, Luby Monte-Carlo algorithms for enumeration and reliability problems
• 1989 Karp, Luby, Madras Monte-Carlo approximation algorithms for enumeration problems

• https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
• https://en.wikipedia.org/wiki/Dancing_Links
• https://arxiv.org/abs/cs/0011047
• https://github.com/blynn/dlx

See Small-dimensional linear programming and convex hulls made easy by Raimund Seidel.

Reference

@Article{thomassen1994every,
title={Every planar graph is 5-choosable},
author={Thomassen, Carsten},
journal={Journal of Combinatorial Theory Series B},
volume={62},
number={1},
pages={180--181},
year={1994},
publisher={Academic Press, Inc. Orlando, FL, USA}
}

Algorithm

Input:
A triangulation T with outer boundary cycle C,
two adjacent vertices on C named u and v
and color assignment L for T such that
L(u) = {1},
L(v) = {2},
|L(o)| >= 3 for o in C - {u, v}, and
|L(i)| >= 5 for i in T - C.

Output: A proper coloring of T.

Steps:

1. Color u with the color in L(u) and color v with the color in L(v).

2. Base case: |T| = |C| = 3, color o in C - {u,v} with one of the colors in L(o) - L(u) - L(v).

3. If there is a chord (s,t) of C then split C along this chord into two
   smaller cycles, given two strictly smaller triangulations A and B.
   Let A be the triangulation that contains (u,v).
   Recursively color B with L.
   This gives a color assigment to s and t of 1' and 2' respectively. Let L'(s) = 1'
   and L'(t) = 2' and L'(x) = L(x) for all other vertices in B.
   Recursively color B with L'.

4. There is no chord. Let t != v be the other vertex of C that is adjacent to u.
   Let L'(t) = L(t) - L(u). L'(t) contains at least 2 colors {x,y}.
   For all vertices f adjacent to t that are in T - C let L'(f) = L(f) - {x,y}.
   For all other vertices x of T let L'(x) = L(x).
   Recursively color T - {t} with L'.
   Let s != u (could be v) be the other adjacent vertex of t on C and x be its
   assigned color without loss of generality. Extend the coloring of T - {t} to a coloring of T
   by coloring t with y.

See https://blog.burntsushi.net/ripgrep/#literal-optimizations.

//           o A                         r = W + µ a, µ in R
//           | 
//           | b                         X = W + µ a, for some µ
//           |                               __
//      a    |                           b = AX = A - X
// r - - - - o - - - o W
//           X                           a . b = 0

related

• #25

http://en.wikipedia.org/wiki/Partition_refinement

see http://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto

implement algorithms 0.5, 0.63 and 0.75.

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm

add the update, delete, decreasekey and increasekey operations

As seen on Wikipedia.

see https://en.wikipedia.org/wiki/Radix_tree

see

• http://programmers.stackexchange.com/a/266635/83434
• https://github.com/mcsoto/LogicJS

https://en.wikipedia.org/wiki/Earley_parser

see http://stackoverflow.com/questions/6531543/efficient-implementation-of-binary-heaps

see http://en.wikipedia.org/wiki/Pairing_heap

see :

• http://en.wikipedia.org/wiki/Flat_%28geometry%29
• https://en.wikipedia.org/wiki/Projection_%28linear_algebra%29#Orthogonal_projections

dependencies :

• #23

related :

• #24

create documentation repository for heap interfaces

see

• http://en.wikipedia.org/wiki/Computer_algebra_system
• http://stackoverflow.com/questions/24311801/symbolic-differentiation-algorithm

start with

• js-algebra-ast
• js-algebra-parse
• js-algebra-stringify
• js-algebra-differentiation

Migrate minima function.

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

min_b Ab - y
b = A^+ y
where A^+ is the pseudoinverse of A

See Introduction to algorithms by TH Cormen, CE Leiserson, RL Rivest, C Stein.

1. use a backreference to keep track of nodes instead of swapping childrens
   • faster because we only need to swap values and backreferences
   • additional memory used
2. implementation only supporting push pop and merge

move issues

• #10
• #12
• #13
• #14
• #15
• #16
• #17
• #18
• #19
• #20
• #22

implement

• Gauss-Jordan Algorithm ( https://en.wikipedia.org/wiki/Gaussian_elimination )
• Bareiss Algorithm ( http://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf )

see also

• http://math.stackexchange.com/questions/663391/bareiss-algorithm

related

• #25

http://www.luschny.de/math/factorial/conclusions.html