Re: Programming techniques

Path	csiph.com!au2pb.net!feeder.erje.net!1.eu.feeder.erje.net!newsfeed.fsmpi.rwth-aachen.de!newsfeed.straub-nv.de!eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail
From	Kaz Kylheku <kaz@kylheku.com>
Newsgroups	comp.programming
Subject	Re: Programming techniques
Date	Tue, 4 Aug 2015 23:52:56 +0000 (UTC)
Organization	Aioe.org NNTP Server
Lines	25
Message-ID	<20150804163519.69@kylheku.com> (permalink)
References	<ad9aaa3d-2daa-41e0-a619-66e9ad07def7@googlegroups.com> <mprah3$9j4$1@dont-email.me>
NNTP-Posting-Host	OGJi3KNpFOhM58UHZwXj0w.user.speranza.aioe.org
X-Complaints-To	abuse@aioe.org
User-Agent	slrn/pre1.0.0-18 (Linux)
X-Notice	Filtered by postfilter v. 0.8.2
Xref	csiph.com comp.programming:5579

Show key headers only | View raw

On 2015-08-04, Charles Richmond <numerist@aquaporin4.com> wrote:
> "Chad" <cdalten@gmail.com> wrote in message 
> news:ad9aaa3d-2daa-41e0-a619-66e9ad07def7@googlegroups.com...
>>Recently on Project Euler I got introduced to the idea of Dynamic 
>>Programming to solve some of the difficult >problems.  This is the first 
>>time I heard of the programming technique. This is primary because I'm a 
>>self >taught programmer. The only other programming techniques I'm aware of 
>>are backtracking and the brute force >approach.  With that, what are some 
>>other programming techniques?
>
> Backtracking uses dynamic programming in a way... because in backtracking, 
> one must keep data indicating what paths have already been tried so one will 
> *not* take those paths again.

Paths have already been tried only if the tree being searched has
common subtrees (i.e. is a DAG).  If there are no common subtrees,
then the problem has no overlapping subcases, and so isn't a candidate
for dynamic programming (memoization).

Even in the absence of overlapping subcases, backtracking must avoid going
down the prior paths, to keep trying new avenues and eventually terminate. That
requires mainintaing state, for instance in the stack being used for recursion,
which holds activation frames that maintain suspended procedures.
Each suspended procedure knows what statement to execute next
when its child procedure returns.

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Programming techniques Chad <cdalten@gmail.com> - 2015-08-04 12:36 -0700
  Re: Programming techniques Julio Di Egidio <julio@diegidio.name> - 2015-08-04 12:57 -0700
  Re: Programming techniques "Charles Richmond" <numerist@aquaporin4.com> - 2015-08-04 16:25 -0500
    Re: Programming techniques Chad <cdalten@gmail.com> - 2015-08-04 14:51 -0700
    Re: Programming techniques Kaz Kylheku <kaz@kylheku.com> - 2015-08-04 23:52 +0000

csiph-web