Skip to content

Commit cd0ff24

Browse files
nem035nem035
committed
Merge remote-tracking branch 'parkjs814/gh-pages' into gh-pages
2 parents 6ef703f + ad12091 commit cd0ff24

35 files changed

Lines changed: 669 additions & 555 deletions

‎algorithm/category.json‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,8 @@
1515
"number_theory": {
1616
"name": "Number Theory",
1717
"list": {
18-
"seive_of_erathrones": "Seive of Erathrones"
18+
"seive_of_erathrones": "Seive of Erathrones",
19+
"euclidean_algorithm": "Euclidean Algorithm"
1920
}
2021
},
2122
"cryptography": {
@@ -58,7 +59,8 @@
5859
"list": {
5960
"edit_distance": "Edit Distance",
6061
"knuth_morris_pratt": "KMP Substring Search",
61-
"rabin_karp_algorithm": "Rabin-Karp Algorithm"
62+
"rabin_karp_algorithm": "Rabin-Karp Algorithm",
63+
"suffix_array": "Suffix Array (construction & usage)"
6264
}
6365
},
6466
"dp": {

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

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
logger._print("Finding the greatest common divisor of " + a[0] + " and " + a[1]);
2+
3+
logger._print("Checking if first number is at most the second number");
4+
5+
if(a[0] > a[1]) {
6+
var tmp = a[0];
7+
a[0] = a[1];
8+
a[1] = tmp;
9+
logger._print("The first number is bigger than the second number. Switching the numbers.");
10+
tracer._setData(a)._wait();
11+
}
12+
13+
while(a[0] > 0) {
14+
logger._print(a[1] + " % " + a[0] + " = " + a[1]%a[0]);
15+
logger._print("Switching a[1] with a[1]%a[0]");
16+
a[1] %= a[0];
17+
tracer._notify(1, a[1])._wait();
18+
logger._print("Now switching the two values to keep a[0] < a[1]");
19+
var tmp = a[0];
20+
a[0] = a[1];
21+
a[1] = tmp;
22+
tracer._notify(0, a[0]);
23+
tracer._notify(1, a[1])._wait();
24+
tracer._denotify(0);
25+
tracer._denotify(1);
26+
}
27+
28+
logger._print("The greatest common divisor is " + a[1]);

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

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
var tracer = new Array1DTracer('Euclidean Algorithm');
2+
var a = [];
3+
a.push(465);
4+
a.push(255)
5+
tracer._setData(a);
6+
var logger = new LogTracer();

‎algorithm/number_theory/euclidean_algorithm/desc.json‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"Euclidean Algorithm": "Finds the greatest common divisor of two positive integers. The Euclidean Algorithm uses the fact that gcd(m, n) = gcd(m, n % m).",
3+
"Complexity": {
4+
"time": "O(log(m)log(n))",
5+
"space": "O(1)"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Euclidean_algorithm'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Euclidean Algorithm"
12+
}
13+
}

‎algorithm/sorting/comb/basic/code.js‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,8 @@ do{
1515
swapped = false; // initialize swapped
1616
// a single comb over the input list
1717
for( var i=0; i+gap < N; i++ ){
18+
tracer._select(i)._select(i+gap)._wait();
19+
1820
if( D[i] > D[i+gap] ){
1921
logger._print('swap ' + D[i] + ' and ' + D[i+gap]); // log swap event
2022

@@ -27,5 +29,6 @@ do{
2729

2830
swapped = true; // Flag swapped has happened and list is not guaranteed sorted
2931
}
32+
tracer._deselect(i)._deselect(i+gap);
3033
} // End of combing
3134
} while( gap!=1 || swapped )

‎algorithm/sorting/cycle/basic/code.js‎

Lines changed: 65 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -1,57 +1,80 @@
1-
logger._print( 'original array = [' + D.join(', ') + ']' );
1+
logger._print('original array = [' + D.join(', ') + ']');
22
var N = D.length;
3-
var writes = 0;
4-
var pos;
5-
var item;
6-
var temp;
7-
for( cycleStart=0; cycleStart<=N-2; cycleStart++ ){
8-
item = D[cycleStart];
9-
pos = cycleStart;
10-
for( i=cycleStart+1; i<=N-1; i++ ){
11-
if( D[i]<item ){
12-
pos++;
13-
}
14-
}
15-
if( pos == cycleStart ){
16-
continue;
17-
}
18-
while( item == D[pos] ){
19-
pos++;
3+
var writes = 0; // number of writing performed
4+
var pos; // the index of item in the sorted array
5+
var item; // an item in the array
6+
var temp; // a temp value used for storing swapped item
7+
for (var cycleStart = 0; cycleStart <= N - 2; cycleStart++) {
8+
item = D[cycleStart];
9+
10+
// find where to put the item
11+
pos = cycleStart;
12+
tracer._select(cycleStart);
13+
14+
for (var i = cycleStart + 1; i <= N - 1; i++) {
15+
tracer._select(i)._wait()._deselect(i);
16+
if (D[i] < item) {
17+
pos++;
2018
}
21-
temp = D[pos];
22-
D[pos] = item;
23-
item = temp;
19+
}
2420

25-
logger._print( 'Rewrite '+D[pos]+' to index '+pos );
21+
// if the item is already there, this is not a circle
22+
if (pos == cycleStart) {
23+
tracer._deselect(cycleStart);
24+
continue;
25+
}
2626

27-
tracer._notify(pos, D[pos])._notify(cycleStart, D[cycleStart])._wait();
28-
tracer._denotify(pos)._denotify(pos);
27+
// otherwise put the item there or right after any duplicates
28+
while (item == D[pos]) {
29+
pos++;
30+
}
2931

32+
// write item to new index and increment writes
33+
temp = D[pos];
34+
D[pos] = item;
35+
item = temp;
3036

31-
while( pos != cycleStart ){
32-
pos = cycleStart;
33-
for( i=cycleStart+1; i<=N-1; i++ ){
34-
if( D[i]<item ){
35-
pos++;
36-
}
37-
}
37+
writes++;
3838

39-
while( item == D[pos] ){
40-
pos++;
41-
}
42-
temp = D[pos];
43-
D[pos] = item;
44-
item = temp;
39+
if (pos !== cycleStart) {
40+
logger._print('Rewrite ' + D[pos] + ' to index ' + pos + '; the next value to rewrite is ' + item);
41+
} else {
42+
logger._print('Rewrite ' + D[pos] + ' to index ' + pos);
43+
}
44+
tracer._select(pos)._wait()._deselect(pos);
45+
tracer._notify(pos, D[pos])._notify(cycleStart, D[cycleStart])._wait();
46+
tracer._denotify(pos)._denotify(cycleStart);
4547

46-
logger._print( 'Rewrite '+D[pos]+' to index '+pos );
48+
// rotate the rest of the cycle
49+
while (pos != cycleStart) {
50+
pos = cycleStart;
51+
52+
for (i = cycleStart + 1; i <= N - 1; i++) {
53+
tracer._select(i)._wait()._deselect(i);
54+
if (D[i] < item) {
55+
pos++;
56+
}
57+
}
58+
59+
while (item == D[pos]) {
60+
pos++;
61+
}
4762

48-
tracer._notify(pos, D[pos])._notify(cycleStart, D[cycleStart])._wait();
49-
tracer._denotify(pos)._denotify(pos);
63+
temp = D[pos];
64+
D[pos] = item;
65+
item = temp;
5066

51-
writes++;
67+
if (pos !== cycleStart) {
68+
logger._print('Rewrite ' + D[pos] + ' to index ' + pos + '; the next value to rewrite is ' + item);
69+
} else {
70+
logger._print('Rewrite ' + D[pos] + ' to index ' + pos);
5271
}
72+
tracer._select(pos)._wait()._deselect(pos);
73+
tracer._notify(pos, D[pos])._notify(cycleStart, D[cycleStart])._wait();
74+
tracer._denotify(pos)._denotify(cycleStart);
5375

5476
writes++;
77+
}
5578
}
5679

57-
logger._print( 'Number of writes performed is ' + writes );
80+
logger._print('Number of writes performed is ' + writes);

‎algorithm/string/suffix_array/construction_naive/code.js‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
word += '$'; //special character
2+
logger._print ('Appended \'$\' at the end of word as terminating (special) character. Beginning filling of suffixes');
3+
4+
function selectSuffix (word, i) {
5+
var c = i;
6+
7+
while (i < word.length-1) {
8+
wordTracer._select (i);
9+
i++;
10+
}
11+
wordTracer._wait ();
12+
13+
while (c < word.length-1) {
14+
wordTracer._deselect (c);
15+
c++;
16+
}
17+
wordTracer._wait ();
18+
}
19+
20+
(function createSA (sa, word) {
21+
for (var i = 0; i < word.length; i++) {
22+
sa [i] [1] = word.slice (i);
23+
24+
selectSuffix (word, i);
25+
saTracer._notify (i, 1, sa [i] [1])._wait ();
26+
saTracer._denotify (i, 1)._wait ();
27+
}
28+
}) (suffixArray, word);
29+
30+
logger._print ('Re-organizing Suffix Array in sorted order of suffixes using efficient sorting algorithm (O(N.log(N)))');
31+
suffixArray.sort (function (a, b) {
32+
logger._print ('The condition a [1] (' + a [1] + ') > b [1] (' + b [1] + ') is ' + (a [1] > b [1]));
33+
return a [1] > b [1];
34+
});
35+
36+
for (var i = 0; i < word.length; i++) {
37+
saTracer._notify (i, 0, suffixArray [i] [0]);
38+
saTracer._notify (i, 1, suffixArray [i] [1])._wait ();
39+
40+
saTracer._denotify (i, 0);
41+
saTracer._denotify (i, 1);
42+
}

‎algorithm/string/suffix_array/construction_naive/data.js‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
var word = 'virgo';
2+
var suffixArray = (function skeleton (word) {
3+
var arr = [];
4+
5+
for (var i = 1; i <= word.length+1; i++) {
6+
arr.push ([i, '-']);
7+
}
8+
9+
return arr;
10+
}) (word);
11+
12+
var saTracer = new Array2DTracer ('Suffix Array'),
13+
wordTracer = new Array1DTracer ('Given Word'),
14+
logger = new LogTracer ('Progress');
15+
16+
saTracer._setData (suffixArray);
17+
wordTracer._setData (word);

‎algorithm/string/suffix_array/desc.json‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
{
2+
"Suffix Array": "a suffix array is just a sorted array of all the suffixes of a given string. The main algorithms include (efficient & inefficient) construction of Suffix Array and how we can use it for substring search & other purposes",
3+
"Applications": [
4+
"Substring Search",
5+
"Bioinformatics",
6+
"Data Compression"
7+
],
8+
"Complexity": {
9+
"time": " O(N<sup>2</sup>.log(N)) for Naive construction",
10+
"space": "O(N<sup>2</sup>)"
11+
},
12+
"References": [
13+
"<a href='https://discuss.codechef.com/questions/21385/a-tutorial-on-suffix-arrays'>Codechef</a>"
14+
],
15+
"files": {
16+
"construction_naive": "Suffix Array inefficient construction"
17+
}
18+
}

‎js/index.js‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
'use strict';
22

33
const RSVP = require('rsvp');
4-
const appInstance = require('./app');
4+
const app = require('./app');
55
const AppConstructor = require('./app/constructor');
66
const DOM = require('./dom');
77
const Server = require('./server');
@@ -33,14 +33,14 @@ RSVP.on('error', function (reason) {
3333
$(() => {
3434

3535
// initialize the application and attach in to the instance module
36-
const app = new AppConstructor();
37-
extend(true, appInstance, app);
36+
const appConstructor = new AppConstructor();
37+
extend(true, app, appConstructor);
3838

3939
// load modules to the global scope so they can be evaled
4040
extend(true, window, modules);
4141

4242
Server.loadCategories().then((data) => {
43-
appInstance.setCategories(data);
43+
app.setCategories(data);
4444
DOM.addCategories();
4545

4646
// determine if the app is loading a pre-existing scratch-pad

0 commit comments

Comments
 (0)