Exercise1-13 <---> Exercise1-15

Exercise 1.14

Draw the tree illustrating the process generated by the count-change procedure of section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

Ru: Нарисуйте дерево, иллюстрирующее процесс, который порождается процедурой count-change из раздела 1.2.2 при размене 11 центов. Каковы порядки роста памяти и числа шагов, используемых этим процессом при увеличении суммы, которую требуется разменять?

Solution:

To determine the order of growth of space we look at the longest path in the tree generated by the process count-change. Let
$$n = \textrm{amount}$$
$$k = \textrm{kind of coins}$$
$$v_i = \textrm{denomination of the coins of kind } i \in \{1,\ldots,k\}$$
$$T(n,k) = \textrm{number of steps}$$
The root of the tree is $(n,k)$. The two vertexes that join this node are $(n,k-1)$ and $(n-v_k,k)$. We want to decrease $n$ as slow as possible, for when $n=0$ the path ends. To do this, we first follow the edges $(n,k),\,(n,k-1),\,\ldots,\,(n,1)$ because $\min\{v_i:i\in\{1,\ldots,k\}\}=v_1$. The length of this first piece of the path is $k-1$. Now we follow the edges $(n-v_1,1),\,(n-2v_1,1),\,\ldots,\,(0,1)$. This part of the path has length $\frac{n}{v_1}$, so the total length of the longest path is $k-1+\frac{n}{v_1}$ which is $\Theta(n)$.

The attached countingcoins.pdf shows a rough proof (attempt anyway) that the order of growth of time (number of function calls is THETA(n^c)) where c is the number of types of coins.

Exercise1-13 <---> Exercise1-15

Comments
:) :)) :( ;) :\ |) X-( B) Markup

Exercise1-14 (last edited 2008-10-23 11:17:24 by JumboPhut)