1

I am trying to create an algorithm using the divide-and-conquer approach but using an iterative algorithm (that is, no recursion).

I am confused as to how to approach the loops.

I need to break up my problems into smaller sub problems, until I hit a base case. I assume this is still true, but then I am not sure how I can (without recursion) use the smaller subproblems to solve the much bigger problem.

For example, I am trying to come up with an algorithm that will find the closest pair of points (in one-dimensional space - though I intend to generalize this on my own to higher dimensions). If I had a function closest_pair(L) where L is a list of integer co-ordinates in ℝ, how could I come up with a divide and conquer ITERATIVE algorithm that can solve this problem?

(Without loss of generality I am using Python)

Improve this question
4
  • Is there a particular reason why you won't (can't?) use recursion? Commented Nov 23, 2016 at 17:27
  • I have to design an iterative algorithm for an assignment given in class. I do know the solution to this recursively (using D&C) and I am confident I can translate this to iterative code and take advantage of the fact that the D&C approach is in O(nlogn) time as opposed to O(n^2). Commented Nov 23, 2016 at 17:28
  • 1
    That's what I feared. Especially in the context of a class assignment, you won't get help here before showing what you already tried in term of codes, even though I understand you question is more about general programming rather than a language in particular. Alas, you will have to code at some point and this will affect concrete answers... Though it seems someone did reply! You seem to be in luck! Commented Nov 23, 2016 at 17:33
  • 1
    Well I am not looking for a solution to this particular problem. I am looking for a general "how to approach iterative D&C algorithms". An example is one that is more specific to what I am learning (but not what I am trying to solve). Commented Nov 23, 2016 at 17:36

1 Answer 1

Reset to default
4

The cheap way to turn any recursive algorithm into an iterative algorithm is to take the recursive function, put it in a loop, and use your own stack. This eliminates the function call overhead and from saving any unneeded data on the stack. However, this is not usually the "best" approach ("best" depends on the problem and context.)

They way you've worded your problem, it sounds like the idea is to break the list into sublists, find the closest pair in each, and then take the closest pair out of those two results. To do this iteratively, I think a better way to approach this than the generic way mentioned above is to start the other way around: look at lists of size 3 (there are three pairs to look at) and work your way up from there. Note that lists of size 2 are trivial.

Lastly, if your coordinates are integers, they are in Z (a much smaller subset of R).

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Yeah you're correct. I meant Z. :-). I had thought about the Stack idea, but because I am trying to analyze this algorithm and prove it's correctness I want to avoid this idea. If I understand what you mean, are you suggesting a bottom-up approach?
@TimelordViktorious Yes; from an algorithmic perspective you can a different ordering too but I find the iterative versions make more sense bottom-up (and that will tend to have better cache performance, since you spend more time working on elements that are near each other in memory)
To do this, I should just do a linear-scan through a list L and look at partitions of 3 elements at a time (or 2) until I hit the end of the list. Is that correct in the way I am tihnking to do this?
@TimelordViktorious That's the first pass. Remember that a D&C will first divide into sublists (the smallest of which will be 2, which are trivial, and then 3) and find the nearest pair in each of those lists. Then you have to conquer by comparing the larger lists and taking the nearest pair out of those lists, and on up the division chain. The bottom-up iterative method's divide step is implicit.
Ahh right. I see what's happening. On the first pass I would take partitions L1, L2, ..., Ln of size 2 or 3. Then on the second pass I take (L1+L2), (L3+L4), ... , (Ln-1 + Ln) as my partitions of size (5-6), and so on, using what I know abut the "previous step".
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.