In grade school we learn an algorithm for multiplying two \(N\) digit integers. Let our basic operation to be the multiplication or...
Suppose we have \(N\) points in a plane, and we wish to find the closest pair. The brute force algorithm takes \(\Theta(N^{2})\). We can...
Why would we want to count the number of inversions? One application may be to see how close two different people’s rankings of the same...
Useful Identities \begin{equation*} \sum_{k=m}^{n}\dbinom{k}{m}=\dbinom{n+1}{m+1} \end{equation*} The mnemonic for this is: Suppose you...
A merge sort works recursively: Split the list into two roughly equal halves. Sort each half using mergesort. Merge the two...