Divide and Conquer Algorithms

James Le
James Le
Sep 28, 2018 · 8 min read
Image for post
Image for post

Divide-and-Conquer Algorithm

Counting Inversions Problem

Image for post
Image for post
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

Image for post
Image for post
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}

The Master Theorem

Image for post
Image for post
Image for post
Image for post

Cracking The Data Science Interview

Your Ultimate Guide to Data Science Interviews

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store