Re: general algorithm + ackermann question

jason.s.turner@xxxxxxxxx writes:

On Jan 29, 9:55 pm, Ben Bacarisse <ben.use...@xxxxxxxxx> wrote:
jason.s.tur...@xxxxxxxxx writes:
Hi, I am working on an assignment and I'm a bit confused and stuck.

I am to write an Ackermann function using recursion which was no
problem and dynamic version as well. The dynamic version is giving me
crap.

You'll need to define the term "dynamic" since I am not sure what it
means.
<snip>
Thanks for the reply. Dynamic programming is a method of solving
problems exhibiting the properties of overlapping subproblems and
optimal substructure (described below) that takes much less time than
naive methods. (Wiki def)

Well I know that definition. I think the part that will help you is
memoization.

My interpretation of the def, along with
the comparison of the recursive and dynamic Fibonacci algorithms is
that, the dynamic approach is more iterative, and it stores the value
of the of the value of the function (at that point) at each iteration
into a variable, then it finally returns the variable.

Be careful about the term dynamic -- it is too general. The term
"dynamic programming" is very much more specific and does not refer to
programming in the modern sense. The term pre-dates most programming
languages!

The techniques of dynamic programming can be used in recursive or
iterative programs alike.

So the value
of the variable that is going to be returned, is based on the values
of the previous iteration.


***I think

I'm taking this course online and my professor seems like a nice guy,
but I think he's very busy and hasn't had the time to reply to my
email. My book appears to be useless so far.

You have not said what you need to do. If the assignment is to
implement the Ackermann function -- do it recursively. If you have to
be efficient, look at memoization. If you have to do it iteratively,
think about simulating the stack in an array. You can then plug in
memoization into that solution if you like.

--
Ben.
.

Relevant Pages

  • Re: recursion vs iteration (was Re: reduce()--what is it good for?)
    ... >> Recursive memoization can be better than iteration when the ... I don't think of that as removing the recursion, ... about the relation between memoization and dynamic programming. ... > gross redundancy) and the other linear. ...
    (comp.lang.python)
  • Re: newbie question: recursion algorithm and iterative algorithm
    ... >> Prolog doesn't have iteration. ... > That depends a bit on how you define iteration. ... I'm taking the view of the novice programmer who asks "Can recursion ... > In fact, in programming language semantics, one usually treats iteration ...
    (comp.lang.prolog)
  • Re: go to statment in matlab
    ... if lasterror == 'Opps0' ... sprintf('Zero encountered at iteration %d\n', ... Programming is what happens while you're busy making other plans. ...
    (comp.soft-sys.matlab)
  • Re: recursion vs iteration
    ... David> iterative linear version to be faster than ... David> the memoized recursive one (also linear due to the memoization). ... either recursion or iteration. ...
    (comp.lang.python)
  • Re: Does Prolog do Dynamic Programming automatically?
    ... deriving Goal from scratch but memoization doesn't help ...  The design of a clever ... I know that this goes against declarative programming in the abstract, ...
    (comp.lang.prolog)