Skip to content

Commit 6600ac6

Browse files
author
duaraghav8@gmail
committed
Merge remote-tracking branch 'upstream/gh-pages'
2 parents eee4d77 + e706dc7 commit 6600ac6

24 files changed

Lines changed: 388 additions & 199 deletions

File tree

‎algorithm/category.json‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -31,9 +31,10 @@
3131
"selection": "Selection Sort",
3232
"bubble": "Bubble Sort",
3333
"quick": "Quicksort",
34-
"merge": "Mergesort",
35-
"heap" : "Heap Sort",
36-
"radix" : "Radix Sort"
34+
"merge": "Merge Sort",
35+
"heap" : "Heapsort",
36+
"radix": "Radix Sort",
37+
"shell": "Shellsort"
3738
}
3839
},
3940
"string": {
@@ -45,8 +46,7 @@
4546
"etc": {
4647
"name": "Uncategorized",
4748
"list": {
48-
"dp": "Dynamic Programming",
49-
"scratch_paper": "<i class='fa fa-code'></i> Scratch Paper"
49+
"dp": "Dynamic Programming"
5050
}
5151
}
5252
}

‎algorithm/etc/dp/desc.json‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@
1212
"sliding_window": "Finding the largest sum of three contiguous number",
1313
"max_sum_path": "Finding the maximum sum in a path from (0, 0) to (N-1, M-1) when can only move to right or down",
1414
"longest_increasing_subsequence": "Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order",
15-
"max_subarray": "Find the sum of the maximum Subarray in the given Array"
15+
"max_subarray": "Find the sum of the maximum Subarray in the given Array",
16+
"knapsack_problem": "Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible."
1617
}
1718
}

‎algorithm/etc/dp/knapsack_problem/code.js‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
2+
for ( var i = 0; i <= N; i++ ) {
3+
for( var j = 0; j <= W; j++ ) {
4+
if( i === 0 || j === 0 ) {
5+
/*
6+
If we have no items or maximum weight we can take in collection is 0
7+
then the total weight in our collection is 0
8+
*/
9+
DP[i][0] = 0;
10+
tracer._notify( i, j, DP[i][j])._wait();
11+
tracer._denotify( i, j);
12+
} else if ( wt[i-1] <= j ) { // take the current item in our collection
13+
14+
dataViewer1._select(i-1)._wait();
15+
dataViewer2._select(i-1)._wait();
16+
tracer._select( i-1, j)._wait();
17+
18+
var A = val[i - 1] + DP[i - 1][j - wt[i - 1]];
19+
var B = DP[i - 1][j];
20+
/*
21+
find the maximum of these two values
22+
and take which gives us a greater weight
23+
*/
24+
if (A > B) {
25+
DP[i][j] = A;
26+
tracer._notify( i, j, DP[i][j])._wait();
27+
} else {
28+
DP[i][j] = B;
29+
tracer._notify( i, j, DP[i][j])._wait();
30+
}
31+
32+
tracer._deselect( i-1, j);
33+
tracer._denotify( i, j);
34+
dataViewer2._deselect(i-1);
35+
dataViewer1._deselect(i-1);
36+
37+
} else { // leave the current item from our collection
38+
39+
DP[i][j] = DP[i - 1][j];
40+
tracer._notify( i, j, DP[i][j])._wait();
41+
tracer._denotify( i, j);
42+
}
43+
}
44+
}
45+
46+
logger._print(' Best value we can achieve is ' + DP[N][W]);

‎algorithm/etc/dp/knapsack_problem/data.js‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
var val = [1,4,5,7]; // The value of all available items
2+
var wt = [1,3,4,5]; // The weights of available items
3+
var W = 7; // The maximum weight we can carry in our collection
4+
var N = val.length;
5+
var DP = new Array(N+1);
6+
7+
for (var i = 0; i < N + 1; i++) {
8+
DP[i] = new Array(W+1);
9+
for (var j = 0; j < W + 1; j++) {
10+
DP[i][j] = 0;
11+
}
12+
}
13+
14+
var tracer = new Array2DTracer()._setData(DP);
15+
var dataViewer1 = new Array1DTracer()._setData(val);
16+
var dataViewer2 = new Array1DTracer()._setData(wt);
17+
var logger = new LogTracer();

‎algorithm/graph_search/bridges/naive/code.js‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -13,8 +13,8 @@ function DFSExplore (graph, source) {
1313
//logger._print (node);
1414

1515
/*
16-
if (prev !== undefined && graph [node] [prev]) { tracer._visit (node, prev)._wait (200); console.log ('tracer ' + prev + ', ' + node); }
17-
else { tracer._visit (node)._wait (200); console.log ('tracer ' + node); }
16+
if (prev !== undefined && graph [node] [prev]) { tracer._visit (node, prev)._wait (); console.log ('tracer ' + prev + ', ' + node); }
17+
else { tracer._visit (node)._wait (); console.log ('tracer ' + node); }
1818
*/
1919

2020
for (i = 0; i < graph.length; i++) {
@@ -35,8 +35,8 @@ function findBridges (graph) {
3535
for (var j = 0; j < graph.length; j++) {
3636
if (graph [i] [j]) { //check if an edge exists
3737
logger._print ('Deleting edge ' + i + '->' + j + ' and calling DFSExplore ()');
38-
tracer._visit (j, i)._wait (200);
39-
tracer._leave (j, i)._wait (200);
38+
tracer._visit (j, i)._wait ();
39+
tracer._leave (j, i)._wait ();
4040

4141
tempGraph = JSON.parse (JSON.stringify (graph));
4242
tempGraph [i] [j] = 0;
@@ -63,4 +63,4 @@ logger._print ('The bridges are: ');
6363
for (var i in bridges) {
6464
logger._print (bridges [i] [0] + ' to ' + bridges [i] [1]);
6565
}
66-
logger._print ('NOTE: A bridge is both ways, i.e., from A to B and from B to A, because this is an Undirected Graph');
66+
logger._print ('NOTE: A bridge is both ways, i.e., from A to B and from B to A, because this is an Undirected Graph');

‎algorithm/graph_search/dfs/exploration/code.js‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -11,8 +11,8 @@ function DFSExplore (graph, source) {
1111
visited [node] = true;
1212
logger._print (node);
1313

14-
if (prev !== undefined && graph [node] [prev]) { tracer._visit (node, prev)._wait (200); console.log ('tracer ' + prev + ', ' + node); }
15-
else { tracer._visit (node)._wait (200); console.log ('tracer ' + node); }
14+
if (prev !== undefined && graph [node] [prev]) { tracer._visit (node, prev)._wait (); console.log ('tracer ' + prev + ', ' + node); }
15+
else { tracer._visit (node)._wait (); console.log ('tracer ' + node); }
1616

1717
for (i = 0; i < graph.length; i++) {
1818
if (graph [node] [i]) {
@@ -32,4 +32,4 @@ if (G.length === Object.keys (visited).length) {
3232
}
3333
else {
3434
logger._print ('The Graph is NOT CONNECTED');
35-
}
35+
}

algorithm/etc/scratch_paper/scratch_paper/code.js renamed to algorithm/scratch_paper/code.js

File renamed without changes.

algorithm/etc/scratch_paper/scratch_paper/data.js renamed to algorithm/scratch_paper/data.js

File renamed without changes.

algorithm/etc/scratch_paper/desc.json renamed to algorithm/scratch_paper/desc.json

File renamed without changes.

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

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
logger._print('Original array = [' + D.join(', ') + ']');
2+
var N = D.length;
3+
4+
for (var gap = N; gap = parseInt(gap / 2);) {
5+
logger._print('');
6+
logger._print('Gap of ' + gap);
7+
for (var i = gap; i < N; i++) {
8+
tracer._select(i)._select(i - gap)._wait();
9+
var k = D[i];
10+
logger._print('Holding: ' + k)
11+
for (var j = i; j >= gap && k < D[j - gap]; j -= gap) {
12+
logger._print(k + ' < ' + D[j - gap]);
13+
D[j] = D[j - gap];
14+
tracer._notify(j, D[j])._wait();
15+
tracer._denotify(j);
16+
}
17+
var old = D[j];
18+
D[j] = k;
19+
if (old != k) {
20+
tracer._notify(j,D[j])._wait();
21+
tracer._denotify(j);
22+
logger._print('Swapped ' + D[j] + ' with ' + old);
23+
}
24+
25+
tracer._deselect(i)._deselect(i - gap);
26+
}
27+
}
28+
tracer._clear();
29+
logger._print('')
30+
logger._print('Sorted array = [' + D.join(', ') + ']');

0 commit comments

Comments
 (0)