Results 1 to 8 of 8

Math Help - Programming Algorithm Prob

  1. #1
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1

    Programming Algorithm Prob

    QUESTION: Change DPChange to return not only the smallest number of coins, but to also return the correct combination of coins.

    DPChange (M, c, d)
    1 bestNumCoins_0 <-- 0
    2 for m <-- 1 to M
    3 *indent*bestNumCoins_m <-- infinity
    4 *indent*for i <-- 1 to d
    5 *indent**indent*if m >= c_i
    6 *indent**indent**indent*if bestNumCoins_(m-c_i) + 1 < bestNumCoins_m
    7 *indent**indent**indent**indent*bestNumCoins_M <-- bestNumCoins_(m-c_i) + 1
    8 return bestNumCoins_M

    NOTE: for line 7, shouldn't be going on a diff line but couldnt fit all in 1...

    *EDIT* Nevermind on note, looks like it all fit.

    Thanks for any help. I hate programming and it shouldn't be part of math !
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by fifthrapiers View Post
    QUESTION: Change DPChange to return not only the smallest number of coins, but to also return the correct combination of coins.

    DPChange (M, c, d)
    1 bestNumCoins_0 <-- 0
    2 for m <-- 1 to M
    3 ............bestNumCoins_m <-- infinity
    4 ............for i <-- 1 to d
    5 ........................if m >= c_i
    6 ...................................if bestNumCoins_(m-c_i) + 1 < bestNumCoins_m
    7 ...........................................bestNumCoins_M <-- bestNumCoins_(m-c_i) + 1
    8 return bestNumCoins_M

    NOTE: for line 7, shouldn't be going on a diff line but couldnt fit all in 1...

    *EDIT* Nevermind on note, looks like it all fit.

    Thanks for any help. I hate programming and it shouldn't be part of math !
    You will not get any constructive help from this starting point.

    As it is you are leaving it to the reader to work out what algorithm is
    supposed to be implemented by this pseudo-code, as well as what the
    parameters are.

    To me it looks like this is an attempt at a recursive function to find
    the minimum number of coins to make change M from a coin set c[1..d],
    but I am guessing. If I am right this is very far from being correct, and so
    modification to return the optimal change set as well as the size of that
    set is premature.

    As a first step you should include comments on what all the parameters
    are, what sort of thing bestNumCoins is (array, function ..?) and an
    algorithm description in plain language.

    Also is this the form of pseudo-code that you have been taught?

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    It's a problem copied right from a book "An Introduction to Bioinformatics Algorithms" by Neil Jones and Pavel Pevzner. Yes, this is the 'pseudocode' we have been using.

    The only additional information it gives is:

    "The algorithm with running time O(Md) calculates bestNumCoins_m for increasing values of m. This works because the best number of coins for some value m depends only on values less than m." "The DPChange algorithm provides a simple O(Md) solution...Conversely, a minor modification of the Change problem renders the problem very difficult."

    Now I have to correct it to return correct combination of coins.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by fifthrapiers View Post
    It's a problem copied right from a book "An Introduction to Bioinformatics Algorithms" by Neil Jones and Pavel Pevzner. Yes, this is the 'pseudocode' we have been using.

    The only additional information it gives is:

    "The algorithm with running time O(Md) calculates bestNumCoins_m for increasing values of m. This works because the best number of coins for some value m depends only on values less than m." "The DPChange algorithm provides a simple O(Md) solution...Conversely, a minor modification of the Change problem renders the problem very difficult."

    Now I have to correct it to return correct combination of coins.
    You will find this easier to do with the correct pseudo-code:


    DPChange (M, c, d)
    //
    // Arguments
    // ========
    // M the amount of change to be made
    // c and array containing the coin denominations (in no particular order)
    // d the number of denominations (ie the number of elements of c)
    //
    // Local Variables
    // ===========
    //
    // bestNumCoins[0..M] array containing the optimal number of coins
    // ....bestNumCoins(m) to make make change m. At end of processing
    // ....bestNumCoin(M) will contain the minimum number of coins to
    // ....make change for M
    // i index for loop over the coin denominations
    // m index for loop over amounts to make change for from 0 to M
    //
    1 bestNumCoins_0 <-- 0
    2 for m <-- 1 to M
    3 ............bestNumCoins_m <-- infinity
    4 ............for i <-- 1 to d
    //
    // this next section computes min( bestNumCoins(m), bestNumCoins(m-c(i)) + 1 )
    //
    5 ........................if m >= c_i
    6 ...................................if bestNumCoins_(m-c_i) + 1 < bestNumCoins_m
    7 ...........................................bestNumCoins_m <-- bestNumCoins_(m-c_i) + 1
    //
    // end of the section
    //
    8 return bestNumCoins_M

    I don't think that you realise how much work is involved in correcting this
    pseudo-code .

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    You will find this easier to do with the correct pseudo-code:


    DPChange (M, c, d)
    //
    // Arguments
    // ========
    // M the amount of change to be made
    // c and array containing the coin denominations (in no particular order)
    // d the number of denominations (ie the number of elements of c)
    //
    // Local Variables
    // ===========
    //
    // bestNumCoins[0..M] array containing the optimal number of coins
    // ....bestNumCoins(m) to make make change m. At end of processing
    // ....bestNumCoin(M) will contain the minimum number of coins to
    // ....make change for M
    // i index for loop over the coin denominations
    // m index for loop over amounts to make change for from 0 to M
    //
    1 bestNumCoins_0 <-- 0
    2 for m <-- 1 to M
    3 ............bestNumCoins_m <-- infinity
    4 ............for i <-- 1 to d
    //
    // this next section computes min( bestNumCoins(m), bestNumCoins(m-c(i)) + 1 )
    //
    5 ........................if m >= c_i
    6 ...................................if bestNumCoins_(m-c_i) + 1 < bestNumCoins_m
    7 ...........................................bestNumCoins_m <-- bestNumCoins_(m-c_i) + 1
    //
    // end of the section
    //
    8 return bestNumCoins_M

    I don't think that you realise how much work is involved in correcting this
    pseudo-code .

    RonL
    Now that we have corrected code we can think about solving the problem as
    set. We need to introduce a 2D array bestComb(0..M)(1..d) which for each
    change amount 0 .. M, contains the numbers of each denomination c(1) to
    c(d). This is initialsied to zeros, and as we compute bestNumCoins(m) we
    also compute bestComb(m).

    DPChange (M, c, d)
    //
    // Arguments
    // ========
    // M the amount of change to be made
    // c and array containing the coin denominations (in no particular order)
    // d the number of denominations (ie the number of elements of c)
    //
    // Local Variables
    // ===========
    //
    // bestNumCoins[0..M] array containing the optimal number of coins
    // ....bestNumCoins(m) to make make change m. At end of processing
    // ....bestNumCoin(M) will contain the minimum number of coins to
    // ....make change for M
    // bestComb[0..M][1..d] 2d array containing the coin counts for the
    //.....best combination bestComb[a][b] is the number of coins of the b-th
    //.....denomination in the best change combination for amount a.
    // i index for loop over the coin denominations
    // m index for loop over amounts to make change for from 0 to M
    //
    1 bestNumCoins[0] <-- 0
    2 bestComb<--zeros(M+1,d)
    3 for m <-- 1 to M
    4............bestNumCoins[m] <-- infinity
    5............for i <-- 1 to d
    //
    // this next section computes min( bestNumCoins[m], bestNumCoins[m-c[i]] + 1 )
    // and also sets the best combination so far
    //
    6........................if m >= c[i]
    7...................................if bestNumCoins[m-c[i]] + 1 < bestNumCoins[m]
    8...........................................bestNumCoins[m] <-- bestNumCoins[m-c[i]] + 1
    9...........................................bestComb[m]<--bestComb[m-c[i]]
    10..........................................bestComb[m][i]<--bestComb[m-c[i]][i]+1
    //
    // end of the section
    //
    11 return bestNumCoins[M], bestComb[M]

    Without a system that will run the pseudo-code I won't guarantee its
    correctness.

    RonL

    (By the way if those authors worked for me and turned their algorithm in as a
    piece of work with no further explanation, they would be seeing no salary review
    this year, and be cleaning the bogs for a month)
    Last edited by CaptainBlack; October 12th 2006 at 01:32 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    Indeed, my professor said it would be very complicated, and she didn't intend it to be this complicated but after she did it she realized it was. Wow, I didn't think it would be THAT complicated. Ugh! I am going to look through it now. I really appreciate you going through it. Thanks CaptainBlack.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    In case you were curious, the way my professor did it was by creating a 2-dimensional array, say a, so that a(sub-i, sub-j) is the number of coins of type j that are used in making change for i cents.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by fifthrapiers View Post
    In case you were curious, the way my professor did it was by creating a 2-dimensional array, say a, so that a(sub-i, sub-j) is the number of coins of type j that are used in making change for i cents.
    Which is what my bestComb array is

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: April 12th 2011, 11:13 AM
  2. UDD prob
    Posted in the Business Math Forum
    Replies: 1
    Last Post: May 10th 2009, 11:25 AM
  3. Replies: 1
    Last Post: November 17th 2008, 04:18 AM
  4. Prob Qn'
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: April 11th 2008, 12:51 AM
  5. Using phi in a Dif EQ Prob
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 6th 2007, 04:01 PM

Search Tags


/mathhelpforum @mathhelpforum