tag:blogger.com,1999:blog-336308386934546555.post4157958050799348852..comments2020-03-29T03:25:05.180+08:00Comments on C for Coding: Coin Tosses, Binomials and Dynamic ProgrammingWilliam Shieldshttp://www.blogger.com/profile/18356811199950883367noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-336308386934546555.post-69609108673375709522010-08-24T02:58:43.609+08:002010-08-24T02:58:43.609+08:00I have only ever seen the terminology Divide and C...I have only ever seen the terminology Divide and Conquer applied to problems where the problem space is divided in half (or smaller) for the subproblems, and then combined - for example, Mergesort, where the input sequence is divided in half until there is one element, and then doing the ordered merge between subproblems. Such problems usually yield a runtime with a logarithmic component, since repeatedly dividing a problem of size n in half can only be done log(n) times before you have a subproblem of size 1.<br /><br />Dynamic programming is where a problem can be solved by solving some combination of subproblems. However, the subproblems usually only add one layer to the onion, as it were - problem n requires that problem n-1 to be solved, which requires n-2 to be solved, etc. Their runtime tends to be o(total number of subproblems) * o(# subproblems examined at each step).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-336308386934546555.post-64700582429111815012010-08-20T10:39:13.550+08:002010-08-20T10:39:13.550+08:00There's no need to use pascal's triangle t...There's no need to use pascal's triangle to compute choose(n, k).<br />Just use these two facts:<br /> choose(n - k, 0) = 1<br /> choose(n, k) = choose(n - 1, k - 1) * n / k<br /><br />The code looks like this:<br />result <- 1<br />for i in 1.. k<br /> result <- result * n - k + i<br /> result <- result / i<br /><br />The division is always exact, even in integer arithmetic.Anonymousnoreply@blogger.com