2
$\begingroup$

As far as I can unserstand Dynamic programming stands simply for memoization (which is a fancy name for lazy evaluation or plain "caching"). Now, I read that there is we can reduce complexity of coin-change problem by truncating some search branches with caching.

Here is the problem, by the way

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

I prefer the Scala translation

  def countWithoutRepetitions(s: Int, dimes: List[Int]): Int = {
    if (s == 0) 1 else
       if (s < 0 || dimes.isEmpty) 0
        else dimes match {
          case d :: ds => {countWithoutRepetitions(s, ds) + countWithoutRepetitions(s-d, ds)}
        }
  }

Odersky also asks for cache-based trimming algorithm in his course (pdf for those who are not enrolled). Yet, I do not understand what do people discuss at all.

The search tree never repeats itslef. It never calls the function with the same (sum, available_coins) arguments. What are you going to cache?

Improve this question
$\endgroup$
2
  • $\begingroup$ dynamic programming / wikipedia $\endgroup$ – vzn Jun 29 '14 at 5:37
  • $\begingroup$ Memoization is not a fancy name for lazy evaluation. They are orthogonal concepts: you can have either without the other. But I do agree that the wikipedia info on this is less than clear. $\endgroup$ – babou Jun 30 '14 at 13:25
3
$\begingroup$

Work an example. I worked through the Scheme version with the input 35 (and with the denominations of the coins as 1, 5, 10, 25, 50) and I'm seeing a ton of repetition in the search tree. (cc 5 1) has already come up 3 times and I'm only about half way through.

Also, memoization actually does a little more than lazy evaluation. Lazy evaluation caches the thunk for the expression assigned to a particular dynamic instance of a variable so that the thunk gets evaluated at most once. But memoization caches all expression evaluations, so if the expression is assigned to different dynamic variable instances you'll also only get a single evaluation. This requires a bit more machinery (you have to hash the arguments of the expression, and store the argument/result pair in a hash table.) If you were to rewrite the function in a lazy functional language (like Haskell) you wouldn't automatically get memoization benefits in this case.

Improve this answer
$\endgroup$
6
  • $\begingroup$ You are right. The repetitions can be demonstrated even at (cc 4 (1,2)). You drop 1-coin in second branch and exchange (cc 2 2) there. In the first branch, you take 1+1 and then drop using ones again, left with (cc 2 2) again. When asking, I was sure that you will always have reduced problem either in sum or in denominations. $\endgroup$ – Val Jun 29 '14 at 14:03
  • $\begingroup$ I am not a Haskell user. Are you saying that, if the same expression appears in two distinct syntactic occurrences in the same environment of a Haskell program, it will be evaluated only once? $\endgroup$ – babou Jun 30 '14 at 12:41
  • $\begingroup$ @babou: I intended to say the opposite. In lazy functional evaluation if you assign an expression to a variable: x_0 = foo(bar) then foo(bar) will get evaluated at most once. But each additional assignment of the same expression to a different variable x_1 = foo(bar) may cause another evaluation. And x_0 and x_1 could be different static instances, or two different dynamic instances of the same static assignment statement. $\endgroup$ – Wandering Logic Jun 30 '14 at 12:58
  • $\begingroup$ Assignment is a bad example for my question. Let's replace it by fum(foo(bar)). the function fum evaluates foo(bar) at most once for each call, lazily, but it can evaluate it twice in two distinct calls. To avoid a second evaluation of identical actual argument foo(bar) in two distinct calls, you need memoization. Do you agree with that? On the other hand, you can have memoization even when the function fum does not evaluate its argument lazily. I am only trying to say, there is not one that does more: they do different things, orthogonally. $\endgroup$ – babou Jun 30 '14 at 13:23
  • $\begingroup$ @babou: I agree. "Two different dynamic instances of the same static assignment statement," was my long-winded way of saying "two distinct calls." The word "orthogonal," however, may be too strong. I think lazy evaluation caches a strict subset of the evaluations that memoization could cache, but incurs less runtime overhead. "Orthogonal," to me, would seem to imply that there were expression evaluations that lazy eval could cache that memoization could not cache. $\endgroup$ – Wandering Logic Jun 30 '14 at 14:00
0
$\begingroup$

Gasarch recently wrote up solutions to this problem using recurrence relations which presumably could be readily turned into dynamic programming form & his paper can be mined for further refs.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.