Algorithm in computer science

Presentation
Previous Year Question Solution(2005)
By: To:
Md. Mehdi Hasan Md. Mahfuz Reza
Id: CE-14002 Assistant Professor,
2nd Year 2nd Semister, Dept Of Cse,
Dept Of Cse,MBSTU. MBSTU

What Is Meant By Divide & Conquer
Algorithm???
• In divide and conquer approach, the problem in hand, is
divided into smaller sub-problems and then each
problem is solved independently. When we keep on
dividing the subproblems into even smaller sub-
problems, we may eventually reach a stage where no
more division is possible. Those "atomic" smallest
possible sub-problem (fractions) are solved. The solution
of all sub-problems is finally merged in order to obtain
the solution of an original problem.
• Broadly, we can understand divide-and-
conquer approach in a three-step process.

Advantages Of Divide & Conquer
Algorithm
• The first, and probably most recognizable benefit of the divide
and conquer paradigm is the fact that it allows us to solve
difficult and often impossible looking problems, such as the
Tower of Hanoi, which is a mathematical game or puzzle.
Being given a difficult problem can often be discouraging if
there is no idea how to go about solving it. However, with the
divide and conquer method, it reduces the degree of difficulty
since it divides the problem into sub problems that are easily
solvable, and usually runs faster than other algorithms would.
Another advantage to this paradigm is that it often plays a
part in finding other efficient algorithms, and in fact it was the
central role in finding the quick sort and merge sort
algorithms.

Min Max Using Divide & Conquer
Algorithm
• Divide the array into two parts and compare the maximums and minimums of the
the two parts to get the maximum and the minimum of the the whole array.
• Pair MaxMin(array, array_size) if array_size = 1 return element as both max and
min else if arry_size = 2 one comparison to determine max and min return that
pair else /* array_size > 2 */ recur for max and min of left half recur for max and
min of right half one comparison determines true max of the two candidates one
comparison determines true min of the two candidates return the pair of max and
min Implementation
• /* structure is used to return two values from minMax() */
• #include<stdio.h>
• struct pair
• {
• int min;
• int max;
• };
•

• struct pair getMinMax(int arr[], int low, int high)
• {
• struct pair minmax, mml, mmr;
• int mid;
•
• /* If there is only on element */
• if (low == high)
• {
• minmax.max = arr[low];
• minmax.min = arr[low];
• return minmax;
• }
•

• /* If there are two elements */
• if (high == low + 1)
• {
• if (arr[low] > arr[high])
• {
• minmax.max = arr[low];
• minmax.min = arr[high];
• }

• else
• {
• minmax.max = arr[high];
• minmax.min = arr[low];
• }
• return minmax;
• }
•
• /* If there are more than 2 elements */
• mid = (low + high)/2;
• mml = getMinMax(arr, low, mid);
• mmr = getMinMax(arr, mid+1, high);
•
• /* compare minimums of two parts*/
• if (mml.min < mmr.min)
• minmax.min = mml.min;

• else
• minmax.min = mmr.min;
•
• /* compare maximums of two parts*/
• if (mml.max > mmr.max)
• minmax.max = mml.max;
• else
• minmax.max = mmr.max;
•
• return minmax;
• }
•

• /* Driver program to test above function */
• int main()
• {
• int arr[] = {1000, 11, 445, 1, 330, 3000};
• int arr_size = 6;
• struct pair minmax = getMinMax(arr, 0, arr_size-1);
• printf("nMinimum element is %d", minmax.min);
• printf("nMaximum element is %d", minmax.max);
• getchar();
• }

Basic Algo
• Pair MaxMin(array, array_size) if array_size = 1
return element as both max and min else if
arry_size = 2 one comparison to determine
max and min return that pair else /*
array_size > 2 */ recur for max and min of left
half recur for max and min of right half one
comparison determines true max of the two
candidates one comparison determines true
min of the two candidates return the pair of
max and min.

Distinguish Between Divide & Conquer
& Dp
• Divide and Conquer basically works in three steps.
1. Divide - It first divides the problem into small chunks or
sub-problems.
2. Conquer - It then solve those sub-problems recursively
so as to obtain a separate result for each sub-problem.
3. Combine - It then combine the results of those sub-
problems to arrive at a final result of the main problem.
Some Divide and Conquer algorithms are Merge Sort,
Binary Sort, etc.

• Dynamic Programming is similar to Divide and Conquer when it
comes to dividing a large problem into sub-problems. But here,
each sub-problem is solved only once. There is no recursion. The
key in dynamic programming is remembering. That is why we store
the result of sub-problems in a table so that we don't have to
compute the result of a same sub-problem again and again.
Some algorithms that are solved using Dynamic Programming are
Matrix Chain Multiplication, Tower of Hanoi puzzle, etc..
Another difference between Dynamic Programming and Divide and
Conquer approach is that -
In Divide and Conquer, the sub-problems are independent of each
other while in case of Dynamic Programming, the sub-problems are
not independent of each other (Solution of one sub-problem may
be required to solve another sub-problem).

Advantages OF Dp
• Finding no. of ways kind of problems, can also be done by
combinatorial formulae, which means the input size can be as
big as 10^9(with some modulo in the end), but DP will time
out.
Finding optimal solution type of problems has the same
problem. Sometimes, greedy works, which means, the
complexity of solution can be much lower, and DP again times
out. Even though DP won't give a wrong solution, but if
greedy is O(n), DP will likely be more than O(n) , because DP
searches a large part of the solution space, which is usually
some orders bigger than n^1.

What Is Algorithm???
• An algorithm is defined as a step-by-step procedure or method for solving a
problem by a computer in a finite number of steps. Steps of an algorithm
definition may include branching or repetition depending upon what problem the
algorithm is being developed for.
• algorithm has five important features:
• Finiteness. An algorithm must always terminate after a finite number of steps.
• Definiteness. Each step of an algorithm must be precisely defined; the actions to
be carried out must be rigorously and unambiguously specified for each case.
• Input. An algorithm has zero or more inputs, i.e, quantities which are given to it
initially before the algorithm begins.
• Output. An algorithm has one or more outputs i.e, quantities which have a
specified relation to the inputs.
• Effectiveness. An algorithm is also generally expected to be effective.

Insertion Sort
• We take an unsorted array for our example.
• Insertion sort compares the first two elements.
• It finds that both 14 and 33 are already in
ascending order. For now, 14 is in sorted sub-list.
• Insertion sort moves ahead and compares 33
with 27.
• And finds that 33 is not in the correct position..

It swaps 33 with 27. It also checks with all the elements of sorted sub-list.
Here we see that the sorted sub-list has only one element 14, and 27 is
greater than 14. Hence, the sorted sub-list remains sorted after swapping.
By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with
10.
These values are not in a sorted order.
So we swap them.
However, swapping makes 27 and 10 unsorted.
Hence, we swap them too.
Again we find 14 and 10 in an unsorted order.
We swap them again. By the end of third iteration, we have a sorted sub-list
of 4 items.

Best Case Of Insertion sort
• Basically, it is saying:
-Suppose the insert function, at most,
performs 17 comparisons each time it is called
(because the array is almost sorted )
-A comparison costs c and we perform 17 of
them per insert, so the cost of an insert is 17 *
c

Worst Case
• Suppose that the array starts out in a random order. Then, on average,
we'd expect that each element is less than half the elements to its left. In
this case, on average, a call to insert on a subarray of kk elements would
slide k/2k/2 of them. The running time would be half of the worst-case
running time. But in asymptotic notation, where constant coefficients
don't matter, the running time in the average case would still
be Theta(n^2)Θ(n2), just like the worst case.
• What if you knew that the array was "almost sorted": every element starts
out at most some constant number of positions, say 17, from where it's
supposed to be when sorted? Then each call to insert slides at most 17
elements, and the time for one call of insert on a subarray of kk elements
would be at most 17 cdot c17⋅c. Over all n-1n−1 calls to insert, the
running time would be 17 cdot c cdot (n-1)17⋅c⋅(n−1), which
is Theta(n)Θ(n), just like the best case. So insertion sort is fast when given
an almost-sorted array.

• To sum up the running times for insertion sort:
• Worst case: Theta(n^2)Θ(n2).
• Best case: Theta(n)Θ(n).
• Average case for a random array: Theta(n^2)Θ(n2).
• "Almost sorted" case: Theta(n)Θ(n).
•
• If you had to make a blanket statement that applies to all
cases of insertion sort, you would have to say that it runs
in O(n^2)O(n2) time. You cannot say that it runs
in Theta(n^2)Θ(n2) time in all cases, since the best case
runs in Theta(n)Θ(n) time. And you cannot say that it runs
in Theta(n)Θ(n) time in all cases, since the worst-case
running time is Theta(n^2)Θ(n2).

Algorithm in computer science

Recommended

More Related Content

What's hot (20)

Similar to Algorithm in computer science (20)

More from Riazul Islam (7)

Recently uploaded (20)

Algorithm in computer science