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++).
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.
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
.
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.
Re: How divide and conquer algorithms are implemented
Quote:
Originally Posted by
sherkhan2010
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.
Quote:
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.
Re: How divide and conquer algorithms are implemented
Quote:
Originally Posted by
D_Drmmr
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.
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.
Re: How divide and conquer algorithms are implemented
Quote:
Originally Posted by
Lindley
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.
Quote:
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!
