Algorithm for Catalan Number (DP)

archie94 · archie94 · commit 18472dbdf4f4 · 2016-05-30T00:15:26.000+05:30
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -72,7 +72,8 @@
       "sliding_window": "Sliding Window",
       "integer_partition": "Integer Partition",
       "ugly_numbers": "Ugly Numbers",
-      "pascal_triangle": "Pascal's Trangle"
+      "pascal_triangle": "Pascal's Trangle",
+      "catalan_number": "Catalan Number"
     }
   },
   "greedy": {
diff --git a/algorithm/dp/catalan_number/catalan_number/code.js b/algorithm/dp/catalan_number/catalan_number/code.js
@@ -0,0 +1,21 @@
+A[0] = 1;
+tracer._notify ( 0, A[0] )._wait();
+tracer._denotify ( 0 );
+A[1] = 1;
+tracer._notify ( 1, A[1] )._wait();
+tracer._denotify ( 1 );
+
+for (var i = 2; i <= N; i++) {
+	for (var j = 0; j < i; j++) {
+		A[i] += A[j] * A[i-j-1];
+		tracer._select( j )._wait();
+		tracer._select( i - j -1 )._wait();
+		tracer._notify( i, A[i])._wait();
+		tracer._deselect( j );
+		tracer._deselect( i - j - 1 );
+		tracer._denotify( i );
+	}
+}
+
+logger._print ( ' The ' + N + 'th Catalan Number is ' + A[N] );
+tracer._select( N )._wait();
diff --git a/algorithm/dp/catalan_number/catalan_number/data.js b/algorithm/dp/catalan_number/catalan_number/data.js
@@ -0,0 +1,8 @@
+var N = 10;
+var A = new Array ( N+1 );
+for (var i = N; i >= 0; i--) {
+	A[i] = 0;
+}
+
+var tracer = new Array1DTracer( ' Catalan Numbers ')._setData( A );
+var logger = new LogTracer();
diff --git a/algorithm/dp/catalan_number/desc.json b/algorithm/dp/catalan_number/desc.json
@@ -0,0 +1,19 @@
+{
+  "Catalan Number": " Pascal's triangle is a triangular array of the binomial coefficients.",
+  "Applications": [
+    "The number of ways to stack coins on a bottom row that consists of n consecutive coins in a plane, such that no coins are allowed to be put on the two sides of the bottom coins and every additional coin must be above two other coins, is the nth Catalan number",
+    "The number of ways to group a string of n pairs of parentheses, such that each open parenthesis has a matching closed parenthesis, is the nth Catalan number",
+    "The number of ways to cut an n+2-sided convex polygon in a plane into triangles by connecting vertices with straight, non-intersecting lines is the nth Catalan number. This is the application in which Euler was interested."
+  ],
+  "Complexity": {
+    "time": " O(N<sup>2</sup>)",
+    "space": "O(N)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Catalan_number'>Wikipedia</a>",
+    "<a href='http://oldweb.sbc.edu/sites/default/files/Honors/XiaotongJiang.July20_0.pdf'>Sweet Briar College"
+  ],
+  "files": {
+    "catalan_number": "Catalan Number"
+  }
+}
