Skip to content

Commit d6bbf8a

Browse files
kopirokopiro
committed
Merge remote-tracking branch 'upstream/master' into pr-freivalds
# Conflicts: # algorithm/category.json
2 parents fe8bc41 + 263fef6 commit d6bbf8a

File tree

11 files changed

+282
-5
lines changed

11 files changed

+282
-5
lines changed

‎algorithm/category.json

+4-2
Original file line numberDiff line numberDiff line change
@@ -63,7 +63,8 @@
6363
"list": {
6464
"euclidean_algorithm": "Euclidean Algorithm",
6565
"sieve_of_eratosthenes": "Sieve of Eratosthenes",
66-
"freivalds_algorithm": "Freivalds Algorithm"
66+
"freivalds_algorithm": "Freivalds Algorithm",
67+
"miller_rabin_primality_test": "Miller-Rabin primality test"
6768
},
6869
"name": "Number Theory"
6970
},
@@ -115,7 +116,8 @@
115116
"flood_fill": "Flood Fill",
116117
"cellular_automata": "Cellular Automata",
117118
"create_maze": "Create Maze",
118-
"magic_square": "Magic Square"
119+
"magic_square": "Magic Square",
120+
"stable_matching": "Stable Matching"
119121
},
120122
"name": "Uncategorized"
121123
}

‎algorithm/etc/stable_matching/basic/code.js

+62
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
function init(rank) {
2+
var o = {};
3+
for (var k in rank) {
4+
o[k] = {
5+
key: k,
6+
stable: false,
7+
rank_keys: rank[k]
8+
};
9+
}
10+
return o;
11+
}
12+
13+
function extractUnstable(Q) {
14+
for (var k in Q) {
15+
if (Q[k].stable === false) {
16+
return Q[k];
17+
}
18+
}
19+
}
20+
21+
var A = init(ARank), B = init(BRank);
22+
var a, b;
23+
24+
while ((a = extractUnstable(A)) != null) {
25+
26+
logTracer._print('Selecting ' + a.key)._wait();
27+
28+
var bKey = a.rank_keys.shift();
29+
var b = B[bKey];
30+
31+
logTracer._print('--> Choicing ' + b.key)._wait();
32+
33+
if (b.stable === false) {
34+
35+
logTracer._print('--> ' + b.key + ' is not stable, stabilizing with ' + a.key)._wait();
36+
37+
a.stable = b;
38+
b.stable = a;
39+
40+
tracerA._select(_aKeys.indexOf(a.key))._wait();
41+
tracerB._select(_bKeys.indexOf(b.key))._wait();
42+
43+
} else {
44+
45+
var rank_a_in_b = b.rank_keys.indexOf(a.key);
46+
var rank_prev_a_in_b = b.rank_keys.indexOf(b.stable.key);
47+
if (rank_a_in_b < rank_prev_a_in_b) {
48+
49+
logTracer._print('--> ' + bKey + ' is more stable with ' + a.key + ' rather than ' + b.stable.key + ' - stabilizing again')._wait();
50+
51+
A[b.stable.key].stable = false;
52+
tracerA._deselect(_aKeys.indexOf(b.stable.key))._wait();
53+
54+
a.stable = b;
55+
b.stable = a;
56+
57+
tracerA._select(_aKeys.indexOf(a.key))._wait();
58+
tracerB._select(_bKeys.indexOf(b.key))._wait();
59+
}
60+
61+
}
62+
}

‎algorithm/etc/stable_matching/basic/data.js

+23
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
var ARank = {
2+
'Flavio' : [ 'Valentine', 'July', 'Summer', 'Violet' ],
3+
'Stephen': [ 'Summer', 'July', 'Valentine', 'Violet' ],
4+
'Albert' : [ 'July', 'Violet', 'Valentine', 'Summer' ],
5+
'Jack' : [ 'July', 'Violet', 'Valentine', 'Summer' ]
6+
};
7+
8+
var BRank = {
9+
'July': [ 'Jack', 'Stephen', 'Albert', 'Flavio' ],
10+
'Valentine': [ 'Flavio', 'Jack', 'Stephen', 'Albert' ],
11+
'Violet': [ 'Jack', 'Stephen', 'Flavio', 'Albert' ],
12+
'Summer': [ 'Stephen', 'Flavio', 'Albert', 'Jack' ],
13+
};
14+
15+
var tracerA = new Array1DTracer('A');
16+
var tracerB = new Array1DTracer('B');
17+
18+
var _aKeys = Object.keys(ARank);
19+
var _bKeys = Object.keys(BRank);
20+
tracerA._setData(_aKeys);
21+
tracerB._setData(_bKeys);
22+
23+
var logTracer = new LogTracer ( 'Console' );

‎algorithm/etc/stable_matching/desc.json

+12
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
{
2+
"Stable Matching": "In mathematics, economics, and computer science, the stable marriage problem (also stable matching problem or SMP) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set. A matching is not stable if: There is an element A of the first matched set which prefers some given element B of the second matched set over the element to which A is already matched, and also prefers A over the element to which B is already matched. In other words, a matching is stable when there does not exist any match (A, B) by which both A and B would be individually better off than they are with the element to which they are currently matched.",
3+
"Complexity": {
4+
"time": " $O(N^2)$"
5+
},
6+
"References": [
7+
"<a href='https://en.wikipedia.org/wiki/Stable_marriage_problem'>Wikipedia</a>"
8+
],
9+
"files": {
10+
"basic": "Stable Matching"
11+
}
12+
}

‎algorithm/graph_search/bfs/desc.json

+3-2
Original file line numberDiff line numberDiff line change
@@ -10,14 +10,15 @@
1010
"Construction of the failure function of the Aho-Corasick pattern matcher."
1111
],
1212
"Complexity": {
13-
"time": "worst $O(|E|)$",
13+
"time": "worst $O(|V|+|E|)$",
1414
"space": "worst $O(|V|)$"
1515
},
1616
"References": [
1717
"<a href='https://en.wikipedia.org/wiki/Breadth-first_search'>Wikipedia</a>"
1818
],
1919
"files": {
2020
"tree": "Searching a tree",
21-
"shortest_path": "Finding the shortest path"
21+
"shortest_path": "Finding the shortest path",
22+
"test_bipartiteness": "Test if graph is biparted (or 2-colorable)"
2223
}
2324
}

‎algorithm/graph_search/bfs/test_bipartiteness/code.js

+41
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
function BFSCheckBipartiteness(s) {
2+
var Q = [];
3+
4+
// Create a new matrix to set colors (0,1)
5+
var Colors = [];
6+
for (var _i = 0; _i < G.length; _i++) Colors[_i] = -1;
7+
colorsTracer._setData(Colors);
8+
9+
Colors[s] = 1;
10+
colorsTracer._notify(s, 1);
11+
12+
Q.push(s); // add start node to queue
13+
14+
while (Q.length > 0) {
15+
var node = Q.shift(); // dequeue
16+
tracer._visit(node)._wait();
17+
18+
for (var i = 0; i < G[node].length; i++) {
19+
if (G[node][i]) {
20+
21+
if (Colors[i] === -1) {
22+
23+
Colors[i] = 1 - Colors[node];
24+
colorsTracer._notify(i, 1 - Colors[node]);
25+
26+
Q.push(i);
27+
tracer._visit(i, node)._wait();
28+
29+
} else if (Colors[i] == Colors[node]) {
30+
logger._print('Graph is not biparted');
31+
return false;
32+
}
33+
}
34+
}
35+
}
36+
37+
logger._print('Graph is biparted');
38+
return true;
39+
}
40+
41+
BFSCheckBipartiteness(0);

‎algorithm/graph_search/bfs/test_bipartiteness/data.js

+14
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
var tracer = new UndirectedGraphTracer();
2+
var logger = new LogTracer();
3+
tracer.attach(logger);
4+
5+
var G =[
6+
[0, 1, 0, 1, 1],
7+
[1, 0, 1, 0, 0],
8+
[0, 1, 0, 1, 0],
9+
[1, 0, 1, 0, 0], // <-- replace latest 0 with 1 to make G not biparted
10+
[1, 0, 0, 0, 0],
11+
];
12+
tracer._setData(G, 0);
13+
14+
var colorsTracer = new Array1DTracer('Colors');

‎algorithm/graph_search/dfs/desc.json

+1-1
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@
1414
"Finding biconnectivity in graphs."
1515
],
1616
"Complexity": {
17-
"time": "worst $O(|E|)$",
17+
"time": "worst $O(|V|+|E|)$",
1818
"space": "worst $O(|V|)$"
1919
},
2020
"References": [

‎algorithm/number_theory/miller_rabin_primality_test/basic/code.js

+91
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
// Utility function to do modular exponentiation.
2+
// It returns (x^y) % p
3+
function power(x, y, p)
4+
{
5+
var res = 1;
6+
x = x % p;
7+
while (y > 0) {
8+
// If y is odd, multiply x with result
9+
if (y & 1) res = (res*x) % p;
10+
// y must be even now
11+
y = y>>1; // y = y/2
12+
x = (x*x) % p;
13+
}
14+
return res;
15+
}
16+
17+
18+
/**
19+
* Determine if N is prime using Miller-Rabin probabilistic algorithm
20+
* @param {Number} n The number
21+
* @param {Number} k An integer that determine the accuracy of the solution
22+
* @return {Boolean}
23+
*/
24+
function testProbablyPrime(n, k) {
25+
logger._print("==> Testing number " + n);
26+
27+
if (n === 1 || n === 3) {
28+
logger._print("==> Simple case, N is 1 or 3");
29+
return true;
30+
}
31+
if (n % 2 === 0) {
32+
logger._print("==> Simple case, " + n + " mod 2 = 0");
33+
return false;
34+
}
35+
36+
// Write (n - 1) as 2^s * d
37+
var d = n-1;
38+
while (d % 2 === 0) {
39+
d /= 2;
40+
}
41+
logger._print("d = " + d);
42+
43+
// Do 5 iterations if none supplied
44+
k = k || 5;
45+
var P = 100 * (1 - (1/Math.pow(4, k)));
46+
47+
WitnessLoop: do {
48+
logger._print("Remaining iterations: #" + k);
49+
50+
var a = 2 + Math.floor(Math.random() * (n - 4));
51+
logger._print("--> first test with random = " + a);
52+
53+
// Compute a^d % n
54+
var x = power(a, d, n);
55+
56+
if (x === 1 || x === n - 1) {
57+
logger._print("--> continue WitnessLoop, x = 1 or x = n-1");
58+
continue;
59+
}
60+
61+
logger._print("--> second test");
62+
63+
// Keep squaring x while one of the following doesn't
64+
// happen
65+
// (i) d does not reach n-1
66+
// (ii) (x^2) % n is not 1
67+
// (iii) (x^2) % n is not n-1
68+
var i = d;
69+
while (i != n-1) {
70+
x = (x * x) % n;
71+
i *= 2;
72+
73+
if (x == 1) {
74+
logger._print("--> exiting, " + n + " is composite");
75+
return false;
76+
}
77+
78+
if (x == n-1) {
79+
logger._print("--> continue WitnessLoop");
80+
continue WitnessLoop;
81+
}
82+
}
83+
84+
logger._print("--> exiting, " + n + " is composite 'cause (n-1) is reached");
85+
return false;
86+
87+
} while (--k);
88+
89+
logger._print("End of tests, " + n + " is probably prime with probabilty of " + P + "%");
90+
return true;
91+
}

‎algorithm/number_theory/miller_rabin_primality_test/basic/data.js

+18
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
var logger = new LogTracer();
2+
3+
var a = Math.floor(Math.random()*300); if (a % 2 === 0) a += 1;
4+
testProbablyPrime(a);
5+
logger._print("----------");
6+
7+
var a = Math.floor(Math.random()*300); if (a % 2 === 0) a += 1;
8+
testProbablyPrime(a);
9+
logger._print("----------");
10+
11+
var a = Math.floor(Math.random()*300); if (a % 2 === 0) a += 1;
12+
testProbablyPrime(a);
13+
logger._print("----------");
14+
15+
testProbablyPrime(151);
16+
logger._print("----------");
17+
18+
testProbablyPrime(199, 10);

‎algorithm/number_theory/miller_rabin_primality_test/desc.json

+13
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"Miller-Rabin primality test": "Determines whether a given number is prime",
3+
"Complexity": {
4+
"time": "$O(klog^{3}(n)))$",
5+
"probability": "$1 - (1/(4^{k}))$"
6+
},
7+
"References": [
8+
"<a href='https://www.wikiwand.com/en/Miller%E2%80%93Rabin_primality_test'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Miller Rabin primality test"
12+
}
13+
}

0 commit comments

Comments
 (0)