DAA Answers 7 - Divide & conquer, search, heaps

DAA-Q49 Divide & conquer

Divide, conquer (recurse), combine. Needs a relational formula and a stopping condition. Applications: max-min, binary search, merge/quick sort, Hanoi, closest pair, Strassen, FFT, Karatsuba. Pros: beats brute force, cache-friendly, parallel. Cons: memory use, stack overflow.

DAA-Q50 Max-min problem

General: 2n-2 comparisons. D&C: T(n)=2T(n/2)+2, T(2)=1 -> 3n/2-2 comparisons. For n=8: 14 vs 10.

DAA-Q51 Binary search

Sorted array; compare target with the middle, discard the impossible half. T(n)=T(n/2)+1 -> O(log n).

DAA-Q52 Sequential (linear) search

Scan and compare with key K. Best Cbest=1; worst Cworst=n; average with success probability p: Cavg=p(n+1)/2+(1-p)n (p=1 -> (n+1)/2; p=0 -> n).

DAA-Q53 Max-priority-queue operations

MAXIMUM O(1); EXTRACT-MAX, INCREASE-KEY, INSERT, DELETE all O(log n).