X Tutup
Skip to content

Commit 9a115fa

Browse files
TornjVTornjV
committed
Change dynamic programming to category
1 parent 3d34b06 commit 9a115fa

File tree

19 files changed

+294
-1
lines changed

19 files changed

+294
-1
lines changed

‎algorithm/category.json‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -43,10 +43,20 @@
4343
"edit_distance": "Edit Distance"
4444
}
4545
},
46+
"dp": {
47+
"name": "Dynamic Programming",
48+
"list": {
49+
"fibonacci": "Fibonacci sequence",
50+
"knapsack_problem": "Knapsack problem",
51+
"longest_increasing_subsequence": "Longest increasing subsequence",
52+
"max_subarray": "Maximum subarray",
53+
"max_sum_path": "Maximum sum path",
54+
"sliding_window": "Sliding window"
55+
}
56+
},
4657
"etc": {
4758
"name": "Uncategorized",
4859
"list": {
49-
"dp": "Dynamic Programming"
5060
}
5161
}
5262
}

‎algorithm/dp/fibonacci/basic/code.js‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
for (var i = 2; i < index; i++) {
2+
D[i] = D[i - 2] + D[i - 1];
3+
tracer._select(i - 2, i - 1)._wait();
4+
tracer._notify(i, D[i])._wait();
5+
tracer._denotify(i);
6+
tracer._deselect(i - 2, i - 1);
7+
}

‎algorithm/dp/fibonacci/basic/data.js‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
var tracer = new Array1DTracer();
2+
var index = 15;
3+
var D = [1, 1];
4+
for (var i = 2; i < index; i++) {
5+
D.push(0);
6+
}
7+
tracer._setData(D);

‎algorithm/dp/fibonacci/desc.json‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"Fivonacci": "Finding fibonacci sequence using dynamic programming.",
3+
"Complexity": {
4+
"time": "O(n<sup>2</sup>",
5+
"space": "O(n)"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Fibonacci Sequence"
12+
}
13+
}

‎algorithm/dp/knapsack_problem/basic/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/dp/knapsack_problem/basic/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/dp/knapsack_problem/desc.json‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"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.",
3+
"Complexity": {
4+
"time": "O(n<sup>2</sup>",
5+
"space": "O(n<sup>2</sup>)"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Knapsack_problem'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Knapsack problem"
12+
}
13+
}

‎algorithm/dp/longest_increasing_subsequence/basic/code.js‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
// Initialize LIS values for all indexes
2+
for (var i = 0; i < A.length; i++) {
3+
LIS[i] = 1;
4+
}
5+
6+
logger._print('Calculating Longest Increasing Subsequence values in bottom up manner ');
7+
// Compute optimized LIS values in bottom up manner
8+
for (var i = 1; i < A.length; i++) {
9+
tracer._select(i);
10+
logger._print(' LIS[' + i + '] = ' + LIS[i]);
11+
for (var j = 0; j < i; j++) {
12+
tracer._notify(j)._wait();
13+
tracer._denotify(j);
14+
if (A[i] > A[j] && LIS[i] < LIS[j] + 1) {
15+
LIS[i] = LIS[j] + 1;
16+
logger._print(' LIS[' + i + '] = ' + LIS[i]);
17+
}
18+
}
19+
tracer._deselect(i);
20+
}
21+
22+
// Pick maximum of all LIS values
23+
logger._print('Now calculate maximum of all LIS values ');
24+
var max = LIS[0];
25+
for (var i = 1; i < A.length; i++) {
26+
if (max < LIS[i]) {
27+
max = LIS[i];
28+
}
29+
}
30+
logger._print('Longest Increasing Subsequence = max of all LIS = ' + max);

‎algorithm/dp/longest_increasing_subsequence/basic/data.js‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
var tracer = new Array1DTracer();
2+
var logger = new LogTracer();
3+
var A = Array1D.random(10, 0, 10);
4+
var LIS = new Array(A.length);
5+
tracer._setData(A);

‎algorithm/dp/longest_increasing_subsequence/desc.json‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"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",
3+
"Complexity": {
4+
"time": "O(n(log n))",
5+
"space": "O(n)"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Longest_increasing_subsequence'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic": "Longest increasing subsequence"
12+
}
13+
}

0 commit comments

Comments
 (0)
X Tutup