MergeSort & Karatsuba

Communication - Shortest Path Algorithms.

Cryptography - Number-Theoretic Algorithms.

Computer Graphics-  Geometric Algorithms.

Database Indices - Balanced Search tree data structures.

Computational biology - Dynamic Programming.

-----------------------------------------------------------------------------------------------------------

KARATSUBA MULTIPLICATION.

• Divide Number into two  parts, first part greater by 1 if no of digits is odd.
• Ie: x*y: x=10^(n/2)a+b, y=10^(n/2)c+d.
• Therefore: x*y = 10^(n)(ac) + 10^(n/2)(ab+bc) + bd.
• Three recursive calls. For the middle call, compute recursively (a+b)(c+d) and subtract ac and bd computed earlier.

The way we calculate time in algorithms is not by how they perform, but by how they scale with larger inputs.

Randomized Algorithms- Difference outputs over same inputs.

----------------------------------------------------------------------------------------------------------

MERGESORT ALgorithm:

• Two recursive calls to first and second half of array to sort each.
• Merge both arrays in ascending order.

Claim : Merge sort takes <= 6nlg(n) + 6n.

Proof: No of work done in each level = 6n

No of levels = lg(n) + 1.

Multiply.

Imagine Log as lg(n) as the number of times we need to divide n by the base(in this case, 2) to reach 1.

 

Recursive Tree Method.

• Hence: Total depth of recursion tree in merge sort : lg(n)+1.
• No. of subproblems existing at level j= 2^j.
• Array size at level j = n/2^j.

Asymptotic Analysis : Supress constant factors and lower-order terms.

Formal Definition :  T(n) < = cf(n) where n >= n0. n0 represesnts sufficiently large and c represents the constant.

------------------------------------------------------------------------------------------------------------

DIVIDE AND CONQUER PARADIGM:

• Divide.
• Conquervia recursive calls.
• Combine solutions of subproblems

Inversions in an array : ia[j];

Used to see how different two arrays are from each other based on ranking.

Inversion Algo:

sort_and_count( Array A, int n){

if (n==1)

return 0;

else

int x= sort_and_count(first half of A, n/2);

int y=sort_and_count(2nd half of A, n/2);

int z= merge_and_countSplitInv(A,n);

return x+y+z; 

NOTE: If there are no split inversions, every element in left array B is smaller than every element in right array C.

The split inversions involving an element Y in C is exactly the number of elements left in B when Y is copied to output array D.

Hence we piggyback on mergeSort for inversion, hence running time is same as merge sort.

---------------------------------------------------------------------------------------------------------------------------------

STRASSEN'S MATRIX MULTIPLICATION METHOD:

Have done it in class before. Check online. Very Straightforward.

---------------------------------------------------------------------------------------------------------------------------------