CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member Join Date
May 2014
Posts
1

Pascals triangle looks as follows:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
The first entry in a row is 1 and the last entry is 1 (except for the first row which contains only 1), and every other entry in Pascals triangle is equal to the sum of the two entries: the entry that is in the previous row and the same column, and the entry that is in the previous row and previous column.

(a) Give a recursive definition for the entry C[i, j] at row i and column j of Pascals triangle. Make sure that you distinguish the base case(s).

(b) Give a recursive algorithm to compute C[i, j], i > j > 1. Illustrate by drawing a diagram (tree) the steps that your algorithm performs to compute C[6, 4]. Does your algorithm perform overlapping computations?

(c) Use dynamic programming to design an O(n2) time algorithm that computes the first n rows in Pascals triangle. Does the dynamic programming algorithm performs better than the recursive
algorithm? Explain.  Reply With Quote  Reply With Quote Originally Posted by BlueBir86 Pascal’s triangle looks as follows:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
The first entry in a row is 1 and the last entry is 1 (except for the first row which contains only 1), and every other entry in Pascal’s triangle is equal to the sum of the two entries: the entry that is in the previous row and the same column, and the entry that is in the previous row and previous column.

(a) Give a recursive definition for the entry C[i, j] at row i and column j of Pascal’s triangle. Make sure that you distinguish the base case(s).

(b) Give a recursive algorithm to compute C[i, j], i > j > 1. Illustrate by drawing a diagram (tree) the steps that your algorithm performs to compute C[6, 4].
You could start from wiki to solve (a) and (b)  Reply With Quote

4. Banned Join Date
Aug 2013
Posts
55 Originally Posted by BlueBir86 (c) Use dynamic programming to design an O(n2) time algorithm that computes the first n rows in Pascal’s triangle. Does the dynamic programming algorithm performs better than the recursive
algorithm? Explain.
Being presented with the question it strikes me that,

recursion + memoization == dynamic programming

Remember you read it here first Last edited by zizz; May 2nd, 2014 at 04:29 PM.  Reply With Quote

algorithm, algorithm complexity, greedy  Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•