COMP4500/7500 Advanced Algorithms & Data Structures Tutorial Exercises 6 (2014/2)∗
School of Information Technology and Electrical Engineering, University of Queensland
September 2, 2014
This material aims to familiarise you with dynamic programming algorithms. A good treatment of dynamic programming may be found in CLRS chapter 15; CLR chapter 16.
1. (Aho, Hopcroft and Ullman, Data Structures and Algorithms, Exercise 10.5)
The number of combinations of m things chosen from amongst a set of n things is denoted C (n, m), for n ≥ 0
and 0 ≤ m ≤ n. We can give a recurrence for C(n, m) as follows: C(n,0) = C(n,n) = 1
C(n,m) = C(n−1,m)+C(n−1,m−1) for0