Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #5568 > unrolled thread

Programming techniques

Back to article view | Back to comp.programming

Contents

  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

#5568 — Programming techniques

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?

[toc] | [next] | [standalone]

#5569

On Tuesday, August 4, 2015 at 8:37:03 PM UTC+1, Chad wrote:

> 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?

<http://www.amazon.co.uk/dp/0201756080>

<https://en.wikipedia.org/wiki/Algorithm#Classification>

Julio

[toc] | [prev] | [next] | [standalone]

#5575

"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.

-- 

numerist at aquaporin4 dot com

[toc] | [prev] | [next] | [standalone]

#5576

But it's my understanding that dynamic programming almost always has a better runtime performance than backtracking.

[toc] | [prev] | [next] | [standalone]

#5579

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web