DIVIDE AND CONQUER
We break the problem down into smaller chunks to solve. It’s similar to recursion. We must be able to understand when to pause.
let’s see we have 8 numbers :
4 5 6 3 2 8 1 9
And we’d like to combine them both. We divide the problem into eight bits, each with its own set of numbers. Then we add two numbers at a time, then four numbers into eight, which is the resultant.
So, if we take 8 separate numbers, we get:
4 5 6 3 2 8 1 9
and then break into 4 parts we get :
4+5 ,6+3, 2+8, 1+9
and so on .
A divide and conquer algorithm attempts to split a problem down into as many small chunks as possible, as small chunks are simpler to solve. It usually accomplishes this by recursion.
Merge sort and Fibonacci number calculations are two examples of divide and conquer. The code for Fibonacci number calculations is as follows:
#include <iostream>
using namespace std;
int main() {
int n1=0,n2=1,n3,i,number;
cout<<”Enter the number of elements: “;
cin>>number;
cout<<n1<<” “<<n2<<” “;
for(i=2;i<number;++i)
{
n3=n1+n2;
cout<<n3<<” “;
n1=n2;
n2=n3;
}
return 0;
}
Merge Sort:
A sorting algorithm known as merge sort. The following is a rough description of how the algorithm works:
1:- Divide the n-number sequence into two halves.
2:- Sort the two halves in a recursive manner.
3:- Join the two sorted halves together to form a single sorted sequence.
Natural Merge Sort
A natural merge sort is similar to a bottom-up merge sort, except it takes advantage of any naturally occurring runs in the input. Lists are useful data structures for both alternative up and down .
Since there are fewer runs to combine, the natural merge sort can not need as many passes because in best cases , input is already sorted.
In this image we break down the 6 numbers into separate digits.
Once we do this we can start the sorting process.
We compare 4 and 8 and place the smallest on the left and largest on the right. We do this for 13 and 2, 23 and 16.
We do that for the next level as well until eventually we get a fully merged sorted list at the top.
In the second level from the top where we have 2 boxes of 3numbers we create 2 pointers. one is pointing towards 8 and another is pointed towards 23
In the third level, we divided columns into two sections, with the first having subparts of columns and the second having no’s that divide on the behavior of that.
In the fourth we divided all numbers separated from columns
In the fifth we repeated same process which we did on third one for sorting the numbers in next columns
In the sixth we compare three numbers and arrange them in the sorted way in both the columns
Finally, we combine all columns and sort the numbers to find our new pairs of sorted numbers.
Time Complexity
When discussing algorithms, time complexity is an essential factor to consider. When compared to other sorting algorithms, merge sort is thought to have a high time complexity.
Running time in the worst-case scenario- O (n log n)
In the best-case scenario, the running time is O. (n log n)
Running time on average- O (n log n)
Tower Of Hanoi
The Towers of Hanoi is a mathematical problem which consists of 3 pegs and 3 and a number of discs. In this instance, 3 discs.
The size of each disc varies. All discs should be transferred to peg C, with the largest on the bottom, second largest on the bottom — 1, and so on.
Just one disc can be moved at a time.
A disc cannot be stacked on top of another disc of the same size.
We’d like to make the fewest number of moves possible.
We only need to switch one disc if we only have one.
If we have two discs, we must transfer them three times.
We need to store the smallest disc in a buffer peg (1 move), move the largest disc to peg c (2 moves) and move the buffer disc to peg c (3 moves).
When we have 4 discs we need to make 15 moves. 5 discs is 31.
These move numbers are powers of 2 minus 1.
To find out how many moves a Tower of Hanoi solution takes you calculate (2^n)-1 where n is how many discs there are.
Notice how we need to have a buffer to store the discs.
We can generalize this problem.
If we have n discs: move n-1 from A to B recursively, move largest from A to C, move n-1 from B to C recursively.
If there is an even number of pieces the first move is always into the middle. If there are an odd number of pieces the first move is always to the other end.
ToH(numDisc, source, destination, spare)
if (numDisc > 1)
ToH(numDisc-1, source, spare, destination)Move a disc from source to destinationif (numDisc > 1)
ToH(numDisc-1, spare, destination, source)
This is what the execution tree looks like for the above algorithm with ToH(3, A, C, B).
Once we call that we 2 calls to:
- ToH(2, A, B, C)
- ToH(2, B, C, A)
Since 2 is more than 1, we move it down one more level again.
Fibonacci Series
The Fibonacci sequence can be found in nature. They begin with 1, and the next number is the current number plus the previous number. 1 + 1 = 2 in this situation. Then 2 + 1 equals 3. 3 + 2 = 5, and so on.
This is the formal definition of the Fibonacci numbers. If n = 0 or n = 1, output 1. Else sum the previous numbers.
Algorithm F(n)if n == 0 or n == 1 then
return 1
else
return F(n-1)+F(n-2)
The value of N in this case is 6. Since N is greater than 0 or 1, we disregard that section.
Then we compute F(5) + F (4).
F(5) is transformed into F(4) + F. (2).
As we get down to the fundamental cases (when F is 0 or 1), we end up with
the number 1. The previous number is returned to the upper level.
So F(1) + F(0) = 2, followed by F2 + F1 = 2 + 1 = 3.