2
$\begingroup$

So for my homework, I was supposed to design an algorithm which was divide-and-conquer that fulfilled the task of finding the two smallest numbers in an array of size n.

I recognize that my version is a bit cheap in that regard, in that it uses reference variables and only does work on the size 1 cases of the recursion. Is this still technically considered divide-and-conquer? Or is it practically too close to a linear search. If it is divide-and-conquer, how could you express the recurrence relation when the work is being done only on the "leaves" of the recursion. 

   find_mins(int A[], int& min, int& sec_min, int l, int r){
    int pivot = (l+r)/2;

    if(l==r){
      if(A[l] < min){
        sec_min = min;
        min = A[l];
        return;
      }
      else if(A[l] < sec_min && A[l] > min){
        sec_min = A[l];
        return;
      }
      return;
    }

    find_mins(A,min,sec_min,1,pivot);
    find_mins(A,min,sec_min,pivot+1,r);


}

"Pseudocode"

FUNCTION(Array, min1, min2, left, right)
  Find pivot
  if(size of subproblem is 1)
    calculate mins
  function(Array,min1,min2,1, pivot)
  function(array,min1,min2,pivot+1,right)

Keep in mind, the code really isn't all that relevant, I just am curious if the structure fits divide-and-conquer description. My concern is that because work is only being done on the case where the size is 1, that it's more of a "linear search" than anything else.

Improve this question
$\endgroup$
6
  • $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. While most folks could probably puzzle out what the code is doing, I'd expect well-thought-out pseudocode to be substantially more concise. Also, not everyone here is proficient with C or C++. $\endgroup$
    – D.W. ♦
    Sep 30, 2015 at 1:18
  • $\begingroup$ @D.W. Edited the question. The code can't really get much more concise without losing all content altogether $\endgroup$
    – Robert Whitmer
    Sep 30, 2015 at 1:36
  • $\begingroup$ Your algorithm isn't very well defined and is incorrect on some inputs. Suppose you set min to be too small from the start, so that A[l] < min is never true - in that case you will just get min back instead of the smallest element in array. Also, what if all numbers in array are the same, or if there are two same numbers, which also happen to be the minimum? As for your original question: D&C is more like a height of an angel, it doesn't really have a rigorous definition, it's more of a folklore. I could recognize the intention in your code, others would do too, I guess. $\endgroup$
    – wvxvw
    Sep 30, 2015 at 10:01
  • $\begingroup$ My code originally had a line mentioning that the precondition was that min and sec_min were loaded with INT_MAX but I must've deleted that when D.W. asked me to remove the source code. Whether the code works (it does) is not the part I'm looking for here, however. $\endgroup$
    – Robert Whitmer
    Sep 30, 2015 at 12:56
  • 1
    $\begingroup$ My point is that the code accomplishes the task for the general case. It works correctly to the extent that the question had asked of me. I wasn't looking for advice regarding the code itself, rather whether or not the general algorithm would be considered D&C. I appreciate you trying to correct some of the subtleties; however, it simply isn't important in this context. $\endgroup$
    – Robert Whitmer
    Sep 30, 2015 at 19:36

1 Answer 1

Reset to default
2
$\begingroup$

TL;DR

Divide and concur doesn't have any rigorous definition. So any argument you make for or against will be just an emotional argument. The situation is made worse by the fact that the task accomplished by this algorithm doesn't need D&C. So, the answer is "probably".

Long version

One scenario where it would make sense to use D&C in finding the minimum is a distributed system (eg. Hadoop), where the size of input may require from you that you do computation in chunks. The algorithm as you designed it is not suitable for this task because it would have to communicate the best result found so far to all parts of the program handling the computation of each chunk. The version I've written below eliminates this problem by computing local minima for given sublists and then calculating the minima of the previously computed minima and so on. This feels (remember emotional argument?) more like D&C. Besides, it makes the algorithm more language-agnostic and eliminates the corner-case errors.

  1. Empty lists have no minimum.
  2. Lists with only one element have only one minimum (not two).
  3. If a list happens to have more than one minimum element, then the second minimum will be equal to first minimum.
  4. Solution doesn't require guessing the minimum before running the algorithm.

The code is set in Prolog. I believe it is better than conventional pseudo-Pascal in that it allows to avoid "uninteresting" parts of the algorithm.

two_mins([], _, _) :- !, fail.  /* Empty list has no minimum */
two_mins([Min1], Min1, _) :- !. /* There is only one element */
two_mins([Min1, Min2], Min1, Min2) :- Min1 < Min2, !.
two_mins([Min1, Min2], Min2, Min1) :- !.
two_mins(List, Min1, Min2) :-
    length(List, N),
    LenA is N div 2,
    length(A, LenA),
    append(A, B, List),
    two_mins(A, Min1A, Min2A),
    two_mins(B, Min1B, Min2B),
    Min1 is min(Min1A, Min1B),
    /* In case A or B had only one element, we will get
       rid of non-instantiated solutions. */
    include(ground, [Min2A, Min2B], Ground),
    min_list([max(Min1A, Min1B) | Ground], Min2).
Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't understand how this answers the question. To remind you, the question is: "Is this algorithm considered divide-and-conquer?" Showing some different code or algorithm is interesting, but I don't see how it answers the question that was asked. $\endgroup$
    – D.W. ♦
    Sep 30, 2015 at 23:20
  • $\begingroup$ @D.W. the purpose is twofold: 1) the algorithm in question is incorrect. 2) D&C algorithms are expected to do work on parts of the input increasing in size at each iteration. This algorithm takes OP's idea, but eliminates the problematic part (the one which OP complained about): it doesn't do work at leafs only, it does it incrementally on larger sub-lists. So, this is an answer in the sense that it offers a small change to the original idea to make it more like OP wanted. While, still, I don't believe the original question is answerable in general. $\endgroup$
    – wvxvw
    Oct 1, 2015 at 7:03
  • $\begingroup$ OK, got it. Thanks. It would probably be helpful to add all of that explanation to the answer. (I'm still not sure whether it is answering the question, though....) $\endgroup$
    – D.W. ♦
    Oct 1, 2015 at 7:05
  • $\begingroup$ @D.W. I added a different explanation to the answer. $\endgroup$
    – wvxvw
    Oct 1, 2015 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.