The js-algorithms's discuss from make-github-pseudonymous-again

js-equation

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 )

explore other implementations of binomial heaps

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
implementation only supporting push pop and merge

implement linked list merge sort

Karp-Luby sampling

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

Boyer-Moore

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

fork js-bst

max-sat algorithms

implement algorithms 0.5, 0.63 and 0.75.

HWANG LIN ALGORITHM AND HUFFMAN SORTING

make the comparison operator an argument in sorting, selection and partitioning methods

js-logic

see

implement tail recursive quicksort

Least-squares approximation

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.

implement radix tree

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

p-flat -- q-flat intersect

fork js-binomial-heap

point location in R^n

js-poset

Migrate minima function.

js-epsilon

5-list-coloring of planar graphs

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:

Color u with the color in L(u) and color v with the color in L(v).
Base case: |T| = |C| = 3, color o in C - {u,v} with one of the colors in L(o) - L(u) - L(v).
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'.
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.

//           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