Divide and Conquer Algorithms

Sep 28, 2018 · 8 min read

Counting Inversions Problem

`Merge-and-Count(A,B)1 - Maintain a Current pointer into each list, initialized to point to the front elements.2 - Maintain a variable Count  for the number of inversions, initialized to 0.3 - While both lists are nonempty:4 -     Let a_{i} and b_{j} be the elements pointed to by the Current pointer.5 -     Append the smaller of these two to the output list.6 -     If b_{j} is the smaller element then:7 -         Increment Count by the number of elements remaining in A.8 -     Endif:9 -     Advance the Current pointer in the list from which the smaller element was selected.10 - EndWhile11 - Once one list is empty, append the remainder of the other list to the output.12 - Return Count and the merged list.`
`Sort-and-Count (L)1 - If the list has one element, then there are no inversions.2 - Else:3 -     Divide the list into two halves:4 -         A contains the first [n/2] elements.5 -         B contains the remaining [n/2] elements.6 -     (rA, A) = Sort-and-Count (A).7 -     (rB, B) = Sort-and-Count (B).8 -     (r, L) = Merge-and-Count (A, B).9 - Endif10 - Return r = rA + rB + r,  and the sorted list L.`

Multiplication of Long Numbers Problem

`Recursive-Multiply (x, y)1 - Write x = x_{1} * 2^(n/2) + x_{0} and y = y_{1} * 2^(n/2) + y_{0}2 - Compute x_{1} + x_{0} and y_{1} + y_{0}3 - p = Recursive-Multiply(x_{1} + x_{0}, y_{1} + y_{0})4 - x_{1} * y_{1} = Recursive-Multiply(x_{1}, y_{1})5 - x_{0} * y_{0} = Recursive-Multiply(x_{0}, y_{0})6 - Return x_{1} * y_{1} * 2^n + (p — x_{1} * y_{1} — x_{0} * y_{0}) * 2^(n/2) +  x_{0} * y_{0}`

Written by

Written by

The Journey of a Soldier in the Minefield

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just \$5/month. Upgrade