Help for part B
Word Pro - lab6.lwp 1/2 to calculate the number of combinations of "n choose k,"i.c, the number of ways to choose k objects fromn objects. For example, when calculating the number of unique 5-card hands from a standard 52-card deck (c.g., C(52, 5)) we need to calculate 52!5! 47! 2,598,960. Implement the function C(n, k) using formula (2) above and your recursive factorial function. Completed your factorial and binomial coefficient functions, raise your hand and demonstrate your code. Part B: One problem with using formula (2) in most languages is that n! grows very fast and overflows the integer representation before you can do the division to bring the value hack to a value that can be represented. (NOTE: Python does not suffer from this problem, but lets pretend that it does.) For example, when calculating C(52, 5) we need to calculate 52! 5! 47!. However, the value of 52-80,658,175,170,943,878.571,660,636,856,403,766,975,289,505.440,883,277,824,000,000,000,000 is much, much bigger than can fit into a 64-bit integer representation. Fortunately, another way to view C(52, 5) is recursively by splitting the problem into two smaller problems by focusing on: the hands containing a specific card, say the ace of clubs, and the hands that do not contain the ace of clubs. For those hands that do contain the ace of clubs, we nced to choose 4 more cards from the remaining 51 cards, i.e.. C(51, 4). For those hands that do not contain the ace of clubs, we need to choose 5 cards from the remaining 51 cards, i.e., C(5, 5). Therefore, C(52, 5)-C5,4)C51, 5). In general, (NOTE: When implementing your recursive code, be sure to use DC for the recursive calls) Cin, k)-Cin-1, k-11+C(n-1, k) for 1sks(n1), and fork- 0ork-n Implement the recursive function DC (n, k) for "divide-and-conquer". Notice the difference in run-time between calculating the binomial coefficient using C(24, 12) vs. DC(24, 12), C(26, 13) vs. DC(26, 13). and C(28, 14) vs. DC(28, 14). binomial coefficient function using equation (3). Call your Completed your binomial cocfficient function, DC, raise your hand and demonstrate your code. Part C: Much of the slowness of your "divide-and-conquer" binomial coefficient function, DC(n, k), is due to redundant calculations performed due to the recursive calls. For example, the recursive calls associated with DC(5, 3) = 10 would be: Lab 6-1 Data Structures (CS 1520) Lab 6 Name: DC(S, 3) DC(4, 2) DC(4, 3) Word Pro - lab6.lwp 1/2 to calculate the number of combinations of "n choose k,"i.c, the number of ways to choose k objects fromn objects. For example, when calculating the number of unique 5-card hands from a standard 52-card deck (c.g., C(52, 5)) we need to calculate 52!5! 47! 2,598,960. Implement the function C(n, k) using formula (2) above and your recursive factorial function. Completed your factorial and binomial coefficient functions, raise your hand and demonstrate your code. Part B: One problem with using formula (2) in most languages is that n! grows very fast and overflows the integer representation before you can do the division to bring the value hack to a value that can be represented. (NOTE: Python does not suffer from this problem, but lets pretend that it does.) For example, when calculating C(52, 5) we need to calculate 52! 5! 47!. However, the value of 52-80,658,175,170,943,878.571,660,636,856,403,766,975,289,505.440,883,277,824,000,000,000,000 is much, much bigger than can fit into a 64-bit integer representation. Fortunately, another way to view C(52, 5) is recursively by splitting the problem into two smaller problems by focusing on: the hands containing a specific card, say the ace of clubs, and the hands that do not contain the ace of clubs. For those hands that do contain the ace of clubs, we nced to choose 4 more cards from the remaining 51 cards, i.e.. C(51, 4). For those hands that do not contain the ace of clubs, we need to choose 5 cards from the remaining 51 cards, i.e., C(5, 5). Therefore, C(52, 5)-C5,4)C51, 5). In general, (NOTE: When implementing your recursive code, be sure to use DC for the recursive calls) Cin, k)-Cin-1, k-11+C(n-1, k) for 1sks(n1), and fork- 0ork-n Implement the recursive function DC (n, k) for "divide-and-conquer". Notice the difference in run-time between calculating the binomial coefficient using C(24, 12) vs. DC(24, 12), C(26, 13) vs. DC(26, 13). and C(28, 14) vs. DC(28, 14). binomial coefficient function using equation (3). Call your Completed your binomial cocfficient function, DC, raise your hand and demonstrate your code. Part C: Much of the slowness of your "divide-and-conquer" binomial coefficient function, DC(n, k), is due to redundant calculations performed due to the recursive calls. For example, the recursive calls associated with DC(5, 3) = 10 would be: Lab 6-1 Data Structures (CS 1520) Lab 6 Name: DC(S, 3) DC(4, 2) DC(4, 3)
