Pascal Triangle Problem - Please help
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Pascal Triangle Problem - Please help

  1. #1
    Join Date
    May 2014
    Posts
    1

    Pascal Triangle Problem - Please help

    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.

  2. #2
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,265

    Re: Pascal Triangle Problem - Please help

    and your question is?
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  3. #3
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    17,276

    Re: Pascal Triangle Problem - Please help

    Quote Originally Posted by BlueBir86 View Post
    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)
    Victor Nijegorodov

  4. #4
    Join Date
    Aug 2013
    Posts
    55

    Re: Pascal Triangle Problem - Please help

    Quote Originally Posted by BlueBir86 View Post
    (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.

Tags for this Thread

Posting Permissions

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


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center