<p>There are many general techniques and meta-theorems. Unlike software engineering, in TCS we don't want to repeat things similar to what the others did, we want to create something new or solve an unsolved problem, so it's not as easy as using lazy propagation in software development. Here I provide some examples but it's surely way far from the complete list. </p>

<ol>
<li><p>Parametrised complexity: kernelization, iterative compression, bidimentionality, ...</p></li>
<li><p>Approximation algorithms: randomised rounding, scaling, ... </p></li>
<li><p>In graph theory, based on structural hierarchies of graphs like bounded tree width graphs/excluded minor graphs/ bounded expansion graphs / nowhere dens graphs, there are different tools (like decompositions) and meta theorems (like Courcelle theorem).</p></li>
</ol>

CC BY-SA 3.0
2016-07-07T22:01:24.727Z
yikes, didn't know we had that level of control over the space of graph properties, as Courcelle's theorem
Sidharth Ghoshal
CC BY-SA 3.0
2016-07-07T22:06:40.830Z
Thanks for your answer. However, I would argue that meta-theorems or generalization of a technique isn't just mere repetition. Having a formalization of a pattern or idea would turn it into a reproducible idea that can be used in novel situations instead of reinventing it for every scenario. I believe every new idea in some way or another borrows from some old idea.
Amir Nasr
CC BY-SA 3.0
2016-07-11T21:32:07.277Z
@AmirNasr, without doubt meta-theorems are important even for creating new ideas. My point was that in theory, IMO, it's interesting to build up over those meta theorems, unlike in engineering where it's more important to use patterns.
Saeed
CC BY-SA 3.0
2016-07-06T21:30:36.440Z
2016-07-06T21:30:36.440Z
Saeed
<p>In the context of heuristic search and optimization, I suggest reviewing the article <a href="http://onlinelibrary.wiley.com/doi/10.1111/itor.12001/abstract" rel="nofollow">"<strong>The metaphore exposed</strong>"</a> by Kenneth Sörensen, where he deals with this generalization problem, that resulted in some limits that journals had to add in order to filter out proposals of algorithms that just exchange one metaphore (or lexicon) by another, without significant changes to the underlying method. There is also <a href="https://prezi.com/wat8ssdnl4hk/metaheuristics-and-metaphors/" rel="nofollow">a Prezi that he made, here</a> on this topic.</p>

CC BY-SA 3.0
2016-07-12T18:40:41.770Z
2016-07-12T18:40:41.770Z
Alfonso F R
<p>From what I've seen in the majority of algorithms publications, the focus of research is mainly towards <strong>improving</strong> the solutions to algorithmic problems in terms of efficiency or optimality in the case of approximation algorithms. My interest and hence my question is towards the <strong>generalization</strong> rather than improvement of algorithms, that is finding common ideas,techniques,optimization tricks that underlie the design or analysis process of algorithms and data structures. Examples of such patterns would be: lazy propagation in data structures, sqrt decomposition, incremental (sweep like) algorithms, smaller to larger merging (as in union by rank)...etc.</p>

<p>I am aware that these techniques would be explained when used in a specific instance of an algorithm, but the focus would still be on the algorithm rather than the design technique.</p>

<p>I appreciate if someone can provide guidance on where to look for such research and whether design techniques are valid as a research point.</p>

CC BY-SA 3.0
2016-07-06T21:35:32.207Z
I found your question a bit off topic, but I thought answers to question are maybe useful and I provided an answer. But the question is not well suited here, and you may ask such question at cs.se.
Saeed
CC BY-SA 3.0
2016-07-07T08:36:52.313Z
I'd like to second Saeed's comment -- while clearly research on algorithm engineering is useful, it doesn't quite fit the "CS theory" mind set, which aims for results that can be rigorously proven. Results such as "this concept can be applied in a variety of applications, such as (1) and (2)" that would be outcomes of research on algorithmic design patterns don't fit this scheme, and hence does not fit to the self-understanding of the community.
DCTLib
CC BY-SA 3.0
2016-07-07T22:35:55.213Z
Well, all of the examples i've mentioned in the question have their provable (maybe trivially) results. I don't see how the generalization or formalization of a technique or an algorithm be on the engineering side with the algorithm analysis/design belonging to the theory mindset. How is the reduction of a problem to another different from say observing the similarity in the structure of 2 algorithms and generalizing the idea. Just different forms of abstraction, aren't they?
Amir Nasr
CC BY-SA 3.0
2016-07-07T22:38:50.543Z
@DCTLib forgive my ignorance, is there research on algorithm engineering even out of the theory community?
Amir Nasr
<ds.algorithms><research-practice>
Is there research on algorithmic design patterns?
Amir Nasr
# Is there research on algorithmic design patterns?

(Asked by: username_0 on 2016-07-06)

From what I've seen in the majority of algorithms publications, the focus of research is mainly towards **improving** the solutions to algorithmic problems in terms of efficiency or optimality in the case of approximation algorithms. My interest and hence my question is towards the **generalization** rather than improvement of algorithms, that is finding common ideas,techniques,optimization tricks that underlie the design or analysis process of algorithms and data structures. Examples of such patterns would be: lazy propagation in data structures, sqrt decomposition, incremental (sweep like) algorithms, smaller to larger merging (as in union by rank)...etc.

I am aware that these techniques would be explained when used in a specific instance of an algorithm, but the focus would still be on the algorithm rather than the design technique.

I appreciate if someone can provide guidance on where to look for such research and whether design techniques are valid as a research point.

**Tags:** ds.algorithms, research-practice

> **Comments:**
> **username_1**: I found your question a bit off topic, but I thought answers to question are maybe useful and I provided an answer. But the question is not well suited here, and you may ask such question at cs.se.  
> **username_2**: I'd like to second username_1's comment -- while clearly research on algorithm engineering is useful, it doesn't quite fit the "CS theory" mind set, which aims for results that can be rigorously proven. Results such as "this concept can be applied in a variety of applications, such as (1) and (2)" that would be outcomes of research on algorithmic design patterns don't fit this scheme, and hence does not fit to the self-understanding of the community.  
> **username_0**: Well, all of the examples i've mentioned in the question have their provable (maybe trivially) results. I don't see how the generalization or formalization of a technique or an algorithm be on the engineering side with the algorithm analysis/design belonging to the theory mindset. How is the reduction of a problem to another different from say observing the similarity in the structure of 2 algorithms and generalizing the idea. Just different forms of abstraction, aren't they?  
> **username_0**: @username_2 forgive my ignorance, is there research on algorithm engineering even out of the theory community?  

---

## 2 answers

### Answer by username_1 on 2016-07-06. Score: 2

There are many general techniques and meta-theorems. Unlike software engineering, in TCS we don't want to repeat things similar to what the others did, we want to create something new or solve an unsolved problem, so it's not as easy as using lazy propagation in software development. Here I provide some examples but it's surely way far from the complete list.

1. Parametrised complexity: kernelization, iterative compression, bidimentionality, ...
2. Approximation algorithms: randomised rounding, scaling, ...
3. In graph theory, based on structural hierarchies of graphs like bounded tree width graphs/excluded minor graphs/ bounded expansion graphs / nowhere dens graphs, there are different tools (like decompositions) and meta theorems (like Courcelle theorem).

> **Comments:**
> **username_3**: yikes, didn't know we had that level of control over the space of graph properties, as Courcelle's theorem  
> **username_0**: Thanks for your answer. However, I would argue that meta-theorems or generalization of a technique isn't just mere repetition. Having a formalization of a pattern or idea would turn it into a reproducible idea that can be used in novel situations instead of reinventing it for every scenario. I believe every new idea in some way or another borrows from some old idea.  
> **username_1**: @AmirNasr, without doubt meta-theorems are important even for creating new ideas. My point was that in theory, IMO, it's interesting to build up over those meta theorems, unlike in engineering where it's more important to use patterns.  

---

### Answer by username_4 on 2016-07-12. Score: 0

In the context of heuristic search and optimization, I suggest reviewing the article ["**The metaphore exposed**"](http://onlinelibrary.wiley.com/doi/10.1111/itor.12001/abstract) by Kenneth Sörensen, where he deals with this generalization problem, that resulted in some limits that journals had to add in order to filter out proposals of algorithms that just exchange one metaphore (or lexicon) by another, without significant changes to the underlying method. There is also [a Prezi that he made, here](https://prezi.com/wat8ssdnl4hk/metaheuristics-and-metaphors/) on this topic.


---

