java/08-dynamicprogramming/Catalan Source

Viewing java/08-dynamicprogramming/Catalan by daveagp@gmail.com. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.

Property Value

Description
html markup
shown to student

The <a href="http://en.wikipedia.org/wiki/Catalan_number">Catalan numbers</a>
are a fascinating sequence of integers that enumerate binary trees,
triangulations, valid parenthesizations, and other ubiquituous combinatorial
families. Their recursive definition is
<ul>
<li> $C_0 = 1$</li>
<li>for $\displaystyle k > 0, C_k = \sum_{i=0}^{k-1} (C_i \times C_{k-i-1})$</li>
</li>
</ul>
It is straightforward to write this as a recursive static method,
provided as <tt>recursiveCat()</tt> for your reference below,
but it is too slow. Write a static method <tt>dynamicCat(n)</tt>
that computes the nth Catalan number using dynamic programming.
Hint: you will need nested loops.
Remark: the code below is not optimal since it
re-computes the dynamic programming table over and over, but this is
not a big deal for this exercise. There are also closed formulas
for Catalan numbers.

Epilogue
html markup
shown when solved

remove
Public permissions remove
Remarks
Comments, history, license, etc.

remove
Engine
Choices
json list of string, bool pairs
e.g. [["good", true], ["bad", false]]

Correct answer
Template / Reference solution

// this is just for reference. it is too slow for large n
public static long recursiveCat(int n) {
if (n==0)
return 1;
long result = 0;
for (int i=0; i<n; i++)
result += recursiveCat(i)*recursiveCat(n-i-1);
return result;
}

public static long dynamicCat(int n) {
// intialize an array with indices from 0 to n
long[] dp = \[new long[n+1]]\;
// set the base case manually
\[dp[0] = 1]\;

// compute the rest of the sequence
for (int k\[=1; k<=n; k++]\) {
\[
dp[k] = 0; // not necessary, but for clarity
for (int i=0; i<k; i++)
dp[k] += dp[i]*dp[k-i-1];
]\
}
return dp[n];
}

public static void main(String[] args) {
for (int i=0; i<=35; i++) {
StdOut.println("The "+i+"th Catalan number is "+dynamicCat(i));
}
}

Template / Reference solution

Java test suite
See manual

test("dynamicCat", 0);
test("dynamicCat", 1);
test("dynamicCat", 2);
test("dynamicCat", 3);
test("dynamicCat", 4);
testMain();

C++ test suite
json list of stdin/args tests
e.g. [{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]
to just run once with no input use [{}]

C++ test suite
See manual

Forbidden substrings
json list of strings
e.g. ["for","while"]

remove
Solution visibility remove
Java imports
json list of importables
e.g. ["java.util.*"]

remove
Override Java classname
else defaults to
websheet name
remove
Dependent on other websheets?
json list of websheet names in this folder
e.g. ["DataStructure"]

remove
Is example?
i.e., just a demo
remove
Add compiler flag(s)
json list of flags
e.g. ["-Wno-unused-variable"]

remove
Remove default compiler flag(s)
json list of flags
see default_cppflags
e.g. ["-Wno-write-strings"]

remove

Property	Value
Description html markup shown to student	The <a href="http://en.wikipedia.org/wiki/Catalan_number">Catalan numbers</a> are a fascinating sequence of integers that enumerate binary trees, triangulations, valid parenthesizations, and other ubiquituous combinatorial families. Their recursive definition is <ul> <li> $C_0 = 1$</li> <li>for $\displaystyle k > 0, C_k = \sum_{i=0}^{k-1} (C_i \times C_{k-i-1})$</li> </li> </ul> It is straightforward to write this as a recursive static method, provided as <tt>recursiveCat()</tt> for your reference below, but it is too slow. Write a static method <tt>dynamicCat(n)</tt> that computes the <i>n</i>th Catalan number using dynamic programming. <p><i>Hint</i>: you will need nested loops.</p> <p><i>Remark</i>: the code below is not optimal since it re-computes the dynamic programming table over and over, but this is not a big deal for this exercise. There are also closed formulas for Catalan numbers.</p>
Epilogue html markup shown when solved	remove
Public permissions	remove
Remarks Comments, history, license, etc.	remove
Engine
Choices json list of string, bool pairs e.g. `[["good", true], ["bad", false]]`
Correct answer
Template / Reference solution	// this is just for reference. it is too slow for large n public static long recursiveCat(int n) { if (n==0) return 1; long result = 0; for (int i=0; i<n; i++) result += recursiveCat(i)recursiveCat(n-i-1); return result; } public static long dynamicCat(int n) { // intialize an array with indices from 0 to n long[] dp = \[new long[n+1]]\; // set the base case manually \[dp[0] = 1]\; // compute the rest of the sequence for (int k\[=1; k<=n; k++]\) { \[ dp[k] = 0; // not necessary, but for clarity for (int i=0; i<k; i++) dp[k] += dp[i]dp[k-i-1]; ]\ } return dp[n]; } public static void main(String[] args) { for (int i=0; i<=35; i++) { StdOut.println("The "+i+"th Catalan number is "+dynamicCat(i)); } }
Template / Reference solution
Java test suite See manual	test("dynamicCat", 0); test("dynamicCat", 1); test("dynamicCat", 2); test("dynamicCat", 3); test("dynamicCat", 4); testMain();
C++ test suite json list of stdin/args tests e.g. `[{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]` to just run once with no input use `[{}]`
C++ test suite See manual
Forbidden substrings json list of strings e.g. `["for","while"]`	remove
Solution visibility	remove
Java imports json list of importables e.g. `["java.util.*"]`	remove
Override Java classname else defaults to websheet name	remove
Dependent on other websheets? json list of websheet names in this folder e.g. `["DataStructure"]`	remove
Is example? i.e., just a demo	remove
Add compiler flag(s) json list of flags e.g. `["-Wno-unused-variable"]`	remove
Remove default compiler flag(s) json list of flags see default_cppflags e.g. `["-Wno-write-strings"]`	remove

Optional properties:

Note: problems are open-source by default (see 'Public permissions'). Assumed license for open problems is Creative Commons 4.0 Attribution-ShareAlike unless specified in 'Remarks'.