algorithm-visualizer · TornjV · May 26, 2016 · May 26, 2016
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -43,10 +43,20 @@
    			"edit_distance": "Edit Distance"
    		}
    },
+   "dp": {
+    "name": "Dynamic Programming",
+    "list": {
+      "fibonacci": "Fibonacci sequence",
+      "knapsack_problem": "Knapsack problem",
+      "longest_increasing_subsequence": "Longest increasing subsequence",
+      "max_subarray": "Maximum subarray",
+      "max_sum_path": "Maximum sum path",
+      "sliding_window": "Sliding window"
+    }
+   },
   "etc": {
     "name": "Uncategorized",
     "list": {
-      "dp": "Dynamic Programming"
     }
   }
 }
diff --git a/algorithm/dp/fibonacci/basic/code.js b/algorithm/dp/fibonacci/basic/code.js
@@ -0,0 +1,7 @@
+for (var i = 2; i < index; i++) {
+    D[i] = D[i - 2] + D[i - 1];
+    tracer._select(i - 2, i - 1)._wait();
+    tracer._notify(i, D[i])._wait();
+    tracer._denotify(i);
+    tracer._deselect(i - 2, i - 1);
+}
diff --git a/algorithm/dp/fibonacci/basic/data.js b/algorithm/dp/fibonacci/basic/data.js
@@ -0,0 +1,7 @@
+var tracer = new Array1DTracer();
+var index = 15;
+var D = [1, 1];
+for (var i = 2; i < index; i++) {
+    D.push(0);
+}
+tracer._setData(D);
diff --git a/algorithm/dp/fibonacci/desc.json b/algorithm/dp/fibonacci/desc.json
@@ -0,0 +1,13 @@
+{
+  "Fivonacci": "Finding fibonacci sequence using dynamic programming.",
+  "Complexity": {
+    "time": "O(n<sup>2</sup>",
+    "space": "O(n)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Fibonacci Sequence"
+  }
+}
diff --git a/algorithm/dp/knapsack_problem/basic/code.js b/algorithm/dp/knapsack_problem/basic/code.js
@@ -0,0 +1,46 @@
+
+for ( var i = 0; i <= N; i++ ) {
+	for( var j = 0; j <= W; j++ ) {
+		if( i === 0 || j === 0 ) { 
+			/*
+			If we have no items or maximum weight we can take in collection is 0 
+			then the total weight in our collection is 0
+			*/
+			DP[i][0] = 0;
+			tracer._notify( i, j, DP[i][j])._wait();
+			tracer._denotify( i, j);
+		} else if ( wt[i-1] <= j ) { // take the current item in our collection
+
+			dataViewer1._select(i-1)._wait();
+			dataViewer2._select(i-1)._wait();
+			tracer._select( i-1, j)._wait();
+
+			var A = val[i - 1] + DP[i - 1][j - wt[i - 1]];
+			var B = DP[i - 1][j];
+			/*
+			find the maximum of these two values
+			and take which gives us a greater weight
+			 */
+			if (A > B) {
+				DP[i][j] = A;
+				tracer._notify( i, j, DP[i][j])._wait();
+			} else {
+				DP[i][j] = B;
+				tracer._notify( i, j, DP[i][j])._wait();
+			}
+
+			tracer._deselect( i-1, j);
+			tracer._denotify( i, j);
+			dataViewer2._deselect(i-1);
+			dataViewer1._deselect(i-1);
+
+		} else { // leave the current item from our collection 
+
+			DP[i][j] = DP[i - 1][j];
+			tracer._notify( i, j, DP[i][j])._wait();
+			tracer._denotify( i, j);
+		}
+	}
+}
+
+logger._print(' Best value we can achieve is ' + DP[N][W]);
diff --git a/algorithm/dp/knapsack_problem/basic/data.js b/algorithm/dp/knapsack_problem/basic/data.js
@@ -0,0 +1,17 @@
+var val = [1,4,5,7]; // The value of all available items
+var wt = [1,3,4,5];  // The weights of available items
+var W = 7;           // The maximum weight we can carry in our collection
+var N = val.length;
+var DP = new Array(N+1);
+
+for (var i = 0; i < N + 1; i++) {
+    DP[i] = new Array(W+1);
+    for (var j = 0; j < W + 1; j++) {
+        DP[i][j] = 0;
+    }
+}
+
+var tracer = new Array2DTracer()._setData(DP);
+var dataViewer1 = new Array1DTracer()._setData(val);
+var dataViewer2 = new Array1DTracer()._setData(wt);
+var logger = new LogTracer();
diff --git a/algorithm/dp/knapsack_problem/desc.json b/algorithm/dp/knapsack_problem/desc.json
@@ -0,0 +1,13 @@
+{
+  "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.",
+  "Complexity": {
+    "time": "O(n<sup>2</sup>",
+    "space": "O(n<sup>2</sup>)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Knapsack_problem'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Knapsack problem"
+  }
+}
diff --git a/algorithm/dp/longest_increasing_subsequence/basic/code.js b/algorithm/dp/longest_increasing_subsequence/basic/code.js
@@ -0,0 +1,30 @@
+// Initialize LIS values for all indexes
+for (var i = 0; i < A.length; i++) {
+    LIS[i] = 1;
+}
+
+logger._print('Calculating Longest Increasing Subsequence values in bottom up manner ');
+// Compute optimized LIS values in bottom up manner
+for (var i = 1; i < A.length; i++) {
+    tracer._select(i);
+    logger._print(' LIS[' + i + '] = ' + LIS[i]);
+    for (var j = 0; j < i; j++) {
+        tracer._notify(j)._wait();
+        tracer._denotify(j);
+        if (A[i] > A[j] && LIS[i] < LIS[j] + 1) {
+            LIS[i] = LIS[j] + 1;
+            logger._print(' LIS[' + i + '] = ' + LIS[i]);
+        }
+    }
+    tracer._deselect(i);
+}
+
+// Pick maximum of all LIS values
+logger._print('Now calculate maximum of all LIS values ');
+var max = LIS[0];
+for (var i = 1; i < A.length; i++) {
+	if (max < LIS[i]) {
+		max = LIS[i];
+	}
+}
+logger._print('Longest Increasing Subsequence = max of all LIS = ' + max);
diff --git a/algorithm/dp/longest_increasing_subsequence/basic/data.js b/algorithm/dp/longest_increasing_subsequence/basic/data.js
@@ -0,0 +1,5 @@
+var tracer = new Array1DTracer();
+var logger = new LogTracer();
+var A = Array1D.random(10, 0, 10);
+var LIS = new Array(A.length);
+tracer._setData(A);
diff --git a/algorithm/dp/longest_increasing_subsequence/desc.json b/algorithm/dp/longest_increasing_subsequence/desc.json
@@ -0,0 +1,13 @@
+{
+  "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",
+  "Complexity": {
+    "time": "O(n(log n))",
+    "space": "O(n)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Longest_increasing_subsequence'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Longest increasing subsequence"
+  }
+}
diff --git a/algorithm/dp/max_subarray/basic/code.js b/algorithm/dp/max_subarray/basic/code.js
@@ -0,0 +1,30 @@
+var maxSubarraySum = (function maxSubarray(array) {
+    var maxSoFar = 0,
+        maxEndingHere = 0;
+
+    logger._print('Initializing maxSoFar = 0 & maxEndingHere = 0');
+
+    for (var i = 0; i < array.length; i++) {
+        tracer._select(i);
+        logger._print(maxEndingHere + ' + ' + array[i]);
+        maxEndingHere += array[i];
+        logger._print('=> ' + maxEndingHere);
+
+        if (maxEndingHere < 0) {
+            logger._print('maxEndingHere is negative, set to 0');
+            maxEndingHere = 0;
+        }
+
+        if (maxSoFar < maxEndingHere) {
+            logger._print('maxSoFar < maxEndingHere, setting maxSoFar to maxEndingHere (' + maxEndingHere + ')');
+            maxSoFar = maxEndingHere;
+        }
+
+        tracer._wait();
+        tracer._deselect(i);
+    }
+
+    return maxSoFar;
+})(D);
+
+logger._print('Maximum Subarray\'s Sum is: ' + maxSubarraySum);
diff --git a/algorithm/dp/max_subarray/basic/data.js b/algorithm/dp/max_subarray/basic/data.js
@@ -0,0 +1,4 @@
+var tracer = new Array1DTracer();
+var logger = new LogTracer();
+var D = [-2, -3, 4, -1, -2, 1, 5, -3];
+tracer._setData(D);
diff --git a/algorithm/dp/max_subarray/desc.json b/algorithm/dp/max_subarray/desc.json
@@ -0,0 +1,13 @@
+{
+  "Maximum subarray": "Find the sum of the maximum Subarray in the given Array",
+  "Complexity": {
+    "time": "O(n)",
+    "space": "O(n)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Maximum_subarray_problem'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Maximum subarray"
+  }
+}
diff --git a/algorithm/dp/max_sum_path/basic/code.js b/algorithm/dp/max_sum_path/basic/code.js
@@ -0,0 +1,29 @@
+var N = DP.length;
+var M = DP[0].length;
+function update(i, j, value) {
+    DP[i][j] = value;
+    dataViewer._select(i, j)._wait();
+    tracer._notify(i, j, DP[i][j])._wait();
+    tracer._denotify(i, j);
+    dataViewer._deselect(i, j);
+}
+for (var i = 0; i < N; i++) {
+    for (var j = 0; j < M; j++) {
+        if (i == 0 && j == 0) {
+            update(i, j, D[i][j]);
+        } else if (i == 0) {
+            tracer._select(i, j - 1);
+            update(i, j, DP[i][j - 1] + D[i][j]);
+            tracer._deselect(i, j - 1);
+        } else if (j == 0) {
+            tracer._select(i - 1, j);
+            update(i, j, DP[i - 1][j] + D[i][j]);
+            tracer._deselect(i - 1, j);
+        } else {
+            tracer._select(i, j - 1)._select(i - 1, j);
+            update(i, j, Math.max(DP[i][j - 1], DP[i - 1][j]) + D[i][j]);
+            tracer._deselect(i, j - 1)._deselect(i - 1, j);
+        }
+    }
+}
+logger._print('max = ' + DP[N - 1][M - 1]);
diff --git a/algorithm/dp/max_sum_path/basic/data.js b/algorithm/dp/max_sum_path/basic/data.js
@@ -0,0 +1,12 @@
+var D = Array2D.random(5, 5, 1, 5);
+var dataViewer = new Array2DTracer()._setData(D);
+var tracer = new Array2DTracer();
+var logger = new LogTracer();
+var DP = [];
+for (var i = 0; i < D.length; i++) {
+    DP.push([]);
+    for (var j = 0; j < D[i].length; j++) {
+        DP[i].push(Infinity);
+    }
+}
+tracer._setData(DP);
diff --git a/algorithm/dp/max_sum_path/desc.json b/algorithm/dp/max_sum_path/desc.json
@@ -0,0 +1,13 @@
+{
+  "Maximum 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",
+  "Complexity": {
+    "time": "O(n)",
+    "space": "O(n)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Maximum sum path"
+  }
+}
diff --git a/algorithm/dp/sliding_window/basic/code.js b/algorithm/dp/sliding_window/basic/code.js
@@ -0,0 +1,13 @@
+var sum = D[0] + D[1] + D[2];
+var max = sum;
+tracer._select(0, 2);
+logger._print('sum = ' + sum)._wait();
+for (var i = 3; i < D.length; i++) {
+    sum += D[i] - D[i - 3];
+    if (max < sum) max = sum;
+    tracer._deselect(i - 3);
+    tracer._select(i);
+    logger._print('sum = ' + sum)._wait();
+}
+tracer._deselect(D.length - 3, D.length - 1);
+logger._print('max = ' + max);
diff --git a/algorithm/dp/sliding_window/basic/data.js b/algorithm/dp/sliding_window/basic/data.js
@@ -0,0 +1,5 @@
+var tracer = new Array1DTracer();
+var logger = new LogTracer();
+tracer.attach(logger);
+var D = Array1D.random(20, -5, 5);
+tracer._setData(D);
diff --git a/algorithm/dp/sliding_window/desc.json b/algorithm/dp/sliding_window/desc.json
@@ -0,0 +1,13 @@
+{
+  "Sliding window": "Finding the largest sum of three contiguous number",
+  "Complexity": {
+    "time": "O(n)",
+    "space": "O(n)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Sliding windows"
+  }
+}