Algorithms: Design and Analysis Part 1 - Notes

These are my personal notes about the course of the same name on Coursera. Feel free to fork these and make your own notes. I'm open to suggestions.

The sub-titles of these notes correspond roughly to a various group of lectures for each week, however, I do occasionally stray for the sake of clarity.

Introduction

Why should we study algorithms?

Algorithms play an important role in almost every branch of C.S.
Better algorithms are the key to modern technological innovation.
Algorithms allow us to frame different problems in a different context, allowing us to make new insights into these fields.

When we analyze an algorithm, we're interested in the number of computational steps required for the algorithm to complete, as a function of the size of it's input.

For example, the grade-school algorithm we use to multiply 2 n-digit numbers requires n^2 steps, as each digit from the first number is multiplied by each digit of the second number. This assumes however, that the basic computational step is a single 1 digit multiplication, and that the addition which occurs at the end is "free" (or constant, regardless of n).

When designing algorithms, you should always be asking yourself the question: Can we do better? You should never the satisfied with the naive solution, as the naive solution is often not the most optimal. With sufficient ingenuity, you can get far, far better results.

For exampe, Karatsuba multiplication is a recursive alternative to grade school multiplication which allows you to compute the product of two n-digit numbers x and y using 3 recursive calls and some mathematical trickery. This could, potentially, yeild faster results than the n^2 grade school algorithm, as the recursive nature of our solution means that we will be dealing with subsequently smaller n as the algorithm progresses.

An Analysis of Merge Sort

Merge sort is a very old algorithm for sorting an array of numbers. It accepts as input an array of n unsorted numbers, and outputs a permutation of this array, wherein the numbers are sorted in increaasing order.

Why study Merge Sort?

Good introduction to the divide and conquer algorithm design paradigm
Merge Sort is fast and useful in real life, better than the quadratic running times of naive sorting algorithms
Good introduction to the guiding principals of algorithm analysis
The analysis of Merge Sort generalizes to the Master Method

Merge sort, ignoring base cases, works as follows:

Recursively sort the right half of the input
Recursively sort the left half of the input
Merge the two sorted arrays

Assuming the recursive calls have correctly done their work, all we have to do is implement a merge subroutine which is quite fast.

The merge will traverse through the two subarrays simoultaneously, at every step, taking the minimum of each array, which is obviously the first element in the array.

In pseudocode this would look like this:

  C = output [length = n]
  A = left half of input
  B = right half of input
  i = 1
  j = 1

  for k = 1 to n
    if A[i] < B[j]
      C[k] = A[i]
      i++
    else if B[j] < A[i]
      C[k] = B[j]
      j++
  end

So what makes this any better than a naive sorting algorithm?

Well, intuitively, the final merge steps takes at most n steps, because we're performing n comparisons, increments and so forth.

Furthermore, the recursive steps are doing work on problem sets which are half as big as the orignal problem size, which leads us to believe this process will converge to the base case fairly quickly.

Claim: This algorithm runs in "about" nlg(n) + n steps.

To prove this claim, we will resort to using a recursion tree method. The root of this tree corresponds to the input array of size n, and each subsequent branch corresponds to the recursive functions called in the root function.

Level 0 -------------------- Input /
Level 1 -------------- Input/2 Input/2 / \ /
Level 2 ------------- I/4 I/4 I/4 I/4

... ------------- | | | | | | | |

Level lg(n) --------- All base cases

Notice that the "depth" of the tree is at most lg(n), as after lg(n) recursions, we reduce to the base case. Ergo, the size the the input being reduced by a factor of 2 at each level.

Furthermore, notice that at each level j, 2^j subproblems, and each sub- problem is of size n/2^j. This means, that at every level of the tree, we are doing 2^j * n/2^j = n work as a function of the size of the input n.

Now, because we are doing work of size n at each level, and there are lg(n) levels, in total we are doing n * lg(n) work.

Intuitively, this can be explained by the fact that the problem size is halving, but the number of problems is doubling, and this perfect balance results in a constant amount of work being done at each level of the recursion.

Now, we've already stated that the merge routine looks like it only takes n steps as a function of the input size, and the recursive steps take nlg(n) steps as a function of the input, so the total amount of work required is:

nlg(n) + n

Furthermore, notice that as n tends to infinity, the nlg(n) term begins to dominate the expression.

siddMahen/algorithms-design-and-analysis-part-1.md

Algorithms: Design and Analysis Part 1 - Notes

Introduction

An Analysis of Merge Sort