undefined | unit 2 divide and conquer

DAA

Unit 2Divide and Conquer Q1) Write short notes on divide & conquer?A1) Divide & conquer Divide & conquer is an efficient algorithm. It follows three steps: ● DIVIDE : divide problem into subproblems● RECUR : Solve each sub problem recursively● CONQUER : Combine all solutions of sub problem to get original solution

Q2) Write some advantages and disadvantages of divide & conquer?A2) Some Advantages ● Divide to overcome conceptually challenging issues like Tower Of Hanoi , Divide & Conquering is a versatile instrument.● Results with powerful algorithms● The algorithms of Divide & Conquer are adapted to the execution of enemies in multi-processors Machines● Results for algorithms that effectively use memory cache.Disadvantages of divide & conquer ● Recursions are sluggish,● It could be more complex than an iterative approach to a very simple problem. Example: n numbers added etc. Q3) Explain a general method?A3) General MethodGeneral divide and conquer recurrence :It is possible to divide an example of size n into b instances of size n/b, with a need to resolve them. [a around 1, b > 1].Assume that size n is a b-power. For running time T(n), the recurrence is as follows:

T(n) = aT(n/b) + f(n)

Where, f(n) - A function that accounts for the time spent on the problem being split intoSmaller ones and to merge their alternatives.The order of growth of T(n) therefore depends on the values of the a & b constants and the order of growth of the f function (n).Master theorem Theorem: If f(n) Є Θ (nd ) with d ≥ 0 in recurrence equation T(n) = aT(n/b) + f(n), then

Example :

solve T(n) = 2T(n/2) + 1, using master theorem.

Sol : Here,

a = 2

b = 2

f(n) = Θ(1)

d = 0

Therefore:

a > bd i.e., 2 > 20

Case 3 of master theorem holds good.

Therefore:

T(n) Є Θ (nlog b a )

Є Θ (nlog 2 2 )

Є Θ (n)

Q4) Define quick sort and also write features?A4) Quick Sort● Quick sort algorithm works on the pivot element.● Select the pivot element (partitioning element) first. Pivot element can be random number from given unsorted array.● Sort the given array according to pivot as the smaller or equal to pivot comes into left array and greater than or equal to pivot comes into right array.● Now select the next pivot to divide the elements and sort the sub arrays recursively. Features ● Developed by C.A.R. Hoare ● Efficient algorithm ● NOT stable sort ● Significantly faster in practice, than other algorithms Q5) Explain merge sort?A5) Merge Sort ● Merge sort consisting two phases as divide and merge.● In divide phase, each time it divides the given unsorted list into two sub list until each sub list get single element then sorts the elements.● In merge phase, it merges all the solution of sub lists and find the original sorted list.Features :● Is an algorithm dependent on comparison?● A stable algorithm is● A fine example of the strategy of divide & conquer algorithm design● John Von Neumann invented it.Steps to solve the problem:Step 1: if the length of the given array is 0 or 1 then it is already sorted, else follow step 2. Step 2: split the given unsorted list into two half partsStep 3: again divide the sub list into two parts until each sub list get single element
Step 4: As each sub list gets the single element compare all the elements with each other & swap in between the elements.Step 5: merge the elements same as divide phase to get the sorted list Q6) Write an algorithm for quick sort?A6) Algorithm of Quick Sort

ALGORITHM Quicksort (A[ l …r ])

//sorts by quick sort

//i/p: A sub-array A[l..r] of A[0..n-1],defined by its left and right indices l and r //o/p: The sub-array A[l..r], sorted in ascending order

if l < r

Partition (A[l..r]) // s is a split position

Quicksort(A[l..s-1])

Quicksort(A[s+1..r]

ALGORITHM Partition (A[l ..r])

//Partitions a sub-array by using its first element as a pivot

//i/p: A sub-array A[l..r] of A[0..n-1], defined by its left and right indices l and r (l <r)

//o/p: A partition of A[l..r], with the split position returned as this function‘s value p→A[l]

i→l

j→r + 1;

Repeat

repeat i→i + 1 until A[i] >=p //left-right scan

repeat j→j – 1 until A[j] < p //right-left scan

if (i < j) //need to continue with the scan

swap(A[i], a[j])

until i >= j //no need to scan

swap(A[l], A[j])

return j

Analysis of Quick Sort Algorithm

Best case: The pivot which we choose will always be swapped into the exactly the middle of the list. And also consider pivot will have an equal number of elements both to its left and right sub arrays.

Worst case: Assume that the pivot partition the list into two parts, so that one of the partitions has no elements while the other has all the other elements.

Average case: Assume that the pivot partition the list into two parts, so that one of the partitions has no elements while the other has all the other elements.

Best Case	O (n log n)
Worst Case	O (n2)
Average Case	O (n log n )

Q7) Write the algorithm for merge sort?A7) Algorithm for Merge sort

ALGORITHM Mergesort ( A[0… n-1] )

//sorts array A by recursive mergesort

//i/p: array A

//o/p: sorted array A in ascending order

if n > 1

copy A[0… (n/2 -1)] to B[0… (n/2 -1)]

copy A[n/2… n -1)] to C[0… (n/2 -1)]

Mergesort ( B[0… (n/2 -1)] )

Mergesort ( C[0… (n/2 -1)] )

Merge ( B, C, A )

ALGORITHM Merge ( B[0… p-1], C[0… q-1], A[0… p+q-1] )

//merges two sorted arrays into one sorted array

//i/p: arrays B, C, both sorted

//o/p: Sorted array A of elements from B & C

I →0

j→0

k→0

while i < p and j < q do

if B[i] ≤ C[j]

A[k] →B[i]

i→i + 1

else

A[k] →C[j]

j→j + 1

k→k + 1

if i == p

copy C [ j… q-1 ] to A [ k… (p+q-1) ]

else

copy B [ i… p-1 ] to A [ k… (p+q-1) ]

Q8) Describe an example of merge sort?A8) Example of Merge Sort Apply merge sort for the following list of elements: 38, 27, 43, 3, 9, 82, 10

Analysis of merge sort:

All cases having same efficiency as: O (n log n)

T (n) =T ( n / 2 ) + O ( n )

T (1) = 0

Space requirement: O (n)

Advantages

● The number of comparisons carried out is almost ideal.

● Mergesort is never going to degrade to O (n2)

● It is applicable to files of any size.

Limitations

● Using extra memory O(n).

Q9) Describe the binary search and also write algorithm?A9) Binary Search ● It is the searching method where we search an element in the given array● Method starts with the middle element.● if the key element is smaller than the middle element then it searches the key element into first half of the array ie. Left sub-array.● If the key element is greater than the middle element then it searches into the second half of the array ie. Right sub-array.
This process continues until the key element is found. If there is no key element present in the given array then its searches fail. Algorithm

Algorithms can be implemented as algorithms that are recursive or non-recursive.

ALGORITHM BinSrch ( A[0 … n-1], key)

//implements non-recursive binary search

//i/p: Array A in ascending order, key k

//o/p: Returns position of the key matched else -1

l 0

r n-1

while l ≤ r do

m ( l + r) / 2

if key = = A[m]

return m

else

if key < A[m]

r m-1

else

l m+1

return -1

Analysis :

● Input size: Array size, n

● Basic operation: key comparison

● Depend on

Best – Matching the key with the middle piece.

Worst – Often a key is not identified or a key in the list.

● Let C(n) denote the number of times the fundamental operation is performed. Then one, then Cworst t(n)= Performance in worst case. Since the algorithm after each comparison is the issue is divided into half the size we have,

● Cworst (n) = Cworst (n/2) + 1 for n > 1

● C(1) = 1

Using the master theorem to solve the recurrence equation, to give the number of when the search key is matched against an element in the list, we have:

C(n) = C(n/2) + 1
a = 1
b = 2
f(n) = n0 ;
d = 0
case 2 holds:
C(n) = Θ (nd log n)
= Θ (n0 log n)
= Θ ( log n)

Application :

Guessing Number game

Word Lists/Dictionary Quest, etc

Limitations :

Interacting badly with the hierarchy of memory

Allows the list to be sorted

Because of the list element's random access, you need arrays instead of a linked list.

Advantages :

Efficient on an incredibly broad list

Iteratively/recursively applied can be

Q10) Write an example of binary search?A10) Example of Binary SearchLet us explain the following 9 elements of binary search:

The number of comparisons required to check for various components is as follows:

1. Searching for x = 101 low high mid

1 9 5

6 9 7

8 9 8

9 9 9

Found

Number of comparison : 4

2. Searching for x = 82 low high mid

1 9 5

6 9 7

8 9 8

Found

Number of comparison : 3

3. Searching for x = 42 low high mid

1 9 5

6 9 7

6 6 6

7 6 not Found

Number of comparison : 4

4. Searching for x = -14 low high mid

1 9 5

1 4 2

1 1 1

2 1 not Found

Number of comparison : 3

The number of element comparisons required to find each of the nine elements continues in this manner:

No part needs seeking more than 4 comparisons. Summarizing the

Comparisons were required for all nine things to be identified and divided by 9, yielding 25/9 . On average, there are around 2.77 comparisons per effective quest.

Depending on the value of x, there are ten possible ways that an un-successful quest will end.

If x < a[1], a[1] < x < a[2], a[2] < x < a[3], a[5] < x < a[6], a[6] < x < a[7] or a[7] < x < a[8] The algorithm requires 3 comparisons of components to decide the 'x'

This isn't present. Binsrch needs 4 part comparisons for all of the remaining choices.

Thus, the average number of comparisons of elements for a failed search is:

(3 + 3 + 3 + 4 + 4 + 3 + 3 + 3 + 4 + 4) / 10 = 34/10 =3.4

The time complexity for a successful search is O(log n) and for an unsuccessful search is Θ(log n).

Sign Up