How divide and conquer algorithms are implemented
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: How divide and conquer algorithms are implemented

  1. #1
    Join Date
    Mar 2010
    Posts
    4

    How divide and conquer algorithms are implemented

    Hi,
    I was studying recursion in c++ recently. Although I understood the simple single-recursion as calculating factorial, etc, easily, but was unable to understand double or multiple recursion as in case of binary search, merge sort, binary search tree 's insert,inorder,preorder functions. I just couldn't get how programmer thought of using recursion in first place and how they guaranteed its success. To concentrate on topic I choose only this simple example of printing elements of binary search tree in inorder:
    Code:
    void inorder(node *temp){
              if(temp!=NULL){
                   inorder(temp->left);
                   cout << temp->data << " ";
                   inorder(temp->right);
              }
    Now precisely I can't understand two things:
    1.How programmer thought in which order and what next case he should take for recursion.
    2.How he guarantees that it will always print element in correct order.

    Please help me in understanding these two issues. Thanks in advance and please forgive me if this post in wrong section( I posted here as I am a newbie in C++).

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,273

    Re: How divide and conquer algorithms are implemented

    Quote Originally Posted by sherkhan2010
    Now precisely I can't understand two things:
    1.How programmer thought in which order and what next case he should take for recursion.
    2.How he guarantees that it will always print element in correct order.
    This particular example might not be a very good one, since from what I understand the code follows from the definition, so an "obvious" answer to both your questions is: "by definition of 'in-order traversal'", but that probably is not very helpful in general.

    Perhaps you are looking for an explanation like this: suppose you wanted to print a binary tree of n levels in-order. You are allowed to use a function that can print the left subtree in-order, and a function that can print the right subtree in-order. How will you print this tree? Knowing the definition of "in-order", you might call the function to print the left subtree, then print the current element, then call the function to print the right subtree.

    But then you recognise that you can use this function for a binary tree of n levels with a binary tree of n-1 levels, as long as the current element exists so that it can be printed. Therefore, these hypothetical left and right subtree printing functions can be replaced by the very function that you are implementing, with the temp!=NULL check added.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    Join Date
    Mar 2010
    Posts
    4

    Re: How divide and conquer algorithms are implemented

    Thanks for reply laserlight!
    Really I chose too specific example. However I found your explanation quite understandable. Only this part was little bit confusing:
    Quote Originally Posted by laserlight View Post
    .
    But then you recognise that you can use this function for a binary tree of n levels with a binary tree of n-1 levels, as long as the current element exists so that it can be printed. Therefore, these hypothetical left and right subtree printing functions can be replaced by the very function that you are implementing, with the temp!=NULL check added.
    However after some time of pondering I understood it.

    However, to make my question more general:
    1. I want to know how I programmer decides that he should take divide and conquer approach in particular situation. Like, for example, you are given merge sort situation. How do you decide you should go for divide and conquer here.
    2.What care should he take so that recursion end at correct place.
    3. What care should he take so that all pieces again get together( this part is perhaps more confusing than any other one.)
    4.Is there any mathematical way to prove that all the elments in array will be covered.(or as in case of binary tree inorder traversal all the elements wil be printed.)

    I am extremely sorry if these are too many queries at a time. But I am troubled with this topic for so long. Please do help me out here.

  4. #4
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,013

    Re: How divide and conquer algorithms are implemented

    Quote Originally Posted by sherkhan2010 View Post
    1. I want to know how I programmer decides that he should take divide and conquer approach in particular situation. Like, for example, you are given merge sort situation. How do you decide you should go for divide and conquer here.
    Finding new algorithms, like solving any new problem, is not a deductive task, it's inductive. So you don't decide that you should use a recursive approach, you play around and discover that you can use recursion. This involves a lot of trial and error.
    There are generic problem solving techniques though, and reducing the problem to a smaller problem is one of them. Read the books by George Polya if you'd like to know more about this.
    2.What care should he take so that recursion end at correct place.
    3. What care should he take so that all pieces again get together( this part is perhaps more confusing than any other one.)
    4.Is there any mathematical way to prove that all the elments in array will be covered.(or as in case of binary tree inorder traversal all the elements wil be printed.)
    You can use preconditions, postconditions and invariants for such a proof.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  5. #5
    Join Date
    Mar 2010
    Posts
    4

    Smile Re: How divide and conquer algorithms are implemented

    Quote Originally Posted by D_Drmmr View Post
    Finding new algorithms, like solving any new problem, is not a deductive task, it's inductive. So you don't decide that you should use a recursive approach, you play around and discover that you can use recursion. This involves a lot of trial and error.
    There are generic problem solving techniques though, and reducing the problem to a smaller problem is one of them. Read the books by George Polya if you'd like to know more about this.

    You can use preconditions, postconditions and invariants for such a proof.
    Thanks for your kind reply D_Drmmr!
    I will surely go through Polya's books once I get access to them(hope they may be in library.)Are there any available on net?
    Also can give me any more indications on what these terms means:
    invariants
    Any online resource/link will do.
    Also thanks again for solving my query and introducing me to such great mathematician as Polya (reading on wiki about him currently..:-))
    I admit I am bit weak in mathematical topics such as combinatorials and recurrences(was scared of them in previous semesters.) If there any interesting and simple read on them then please mention those. Also what are other important mathematical subjects required to become good computer programmer.
    Thanks in advance.

  6. #6
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

    Re: How divide and conquer algorithms are implemented

    It sounds to me like you should enroll in your college's Algorithms course, they cover this sort of stuff in detail.

    Do you understand the basic principal of proof by induction? Divide-and-conquer is basically the algorithmic equivalent of an inductive proof.

    You say you understand the single-recursion problems like factorial; it's really not that different. In the case of printing a binary tree in order, the proof would go something like:
    1) If the tree is of height 0, the function will certainly print the entire tree (nothing).
    2) If the tree is of height n, and we assume that the function will correctly print a tree of height n-1, then we can guarantee that calling it on the left subtree will print that entire subtree, and calling it on the right subtree will print that entire subtree, and that we are printing the current element; and we are printing the left subtree, then the current element, then the right subtree.
    3) Therefore, the function will correctly print a tree of any size using an inorder traversal.

    If you need an intuitive understanding, draw out a tree, and then trace with a pen the order in which this code causes individual elements to be printed.
    Last edited by Lindley; March 7th, 2010 at 11:59 AM.

  7. #7
    Join Date
    Mar 2010
    Posts
    4

    Re: How divide and conquer algorithms are implemented

    Quote Originally Posted by Lindley View Post
    It sounds to me like you should enroll in your college's Algorithms course, they cover this sort of stuff in detail.
    ;-) I have it in next semester. Will surely pay good amount of attention to these topics then.
    Do you understand the basic principal of proof by induction? Divide-and-conquer is basically the algorithmic equivalent of an inductive proof.

    You say you understand the single-recursion problems like factorial; it's really not that different. In the case of printing a binary tree in order, the proof would go something like:
    1) If the tree is of height 0, the function will certainly print the entire tree (nothing).
    2) If the tree is of height n, and we assume that the function will correctly print a tree of height n-1, then we can guarantee that calling it on the left subtree will print that entire subtree, and calling it on the right subtree will print that entire subtree, and that we are printing the current element; and we are printing the left subtree, then the current element, then the right subtree.
    3) Therefore, the function will correctly print a tree of any size using an inorder traversal.

    If you need an intuitive understanding, draw out a tree, and then trace with a pen the order in which this code causes individual elements to be printed.
    Yes I do know induction. Also your explanation was quite understandable. Really u people are very great and my sincere thanks to all your help. Moderators can kindly close this thread as my question is quite solved now.
    Again my sincere thanks to those who helped me solve this query!

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center