Basic Frameworks of Algorithms

Sorting Problem

Input: A sequence of n numbers <a₁, a₂, …, a_n>.

Output: A permutation (reordering) <a₁’, a₂’, …, a_n’> of the input sequence such that a₁’ ≤ a₂’ ≤ … ≤ a_n’

Introduction - Insertion Sort

void insertionSort(int* arr, int size) {
    for(int j = 1; j < size; j++) {
        int key = arr[j];
        int i = j - 1;
        while ( i >= 0 && arr[i] > key ) {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = key;
    }
}

Loop invariant: At the start of each iteration of the for loop, the subarray arr[1 : j] consists of the elements originally in arr[1 : j], but in sorted order.

Loop invariant

A loop invariant is a property of a program loop that is true before (and after) each iteration. We use loop invariants to help us understand why an algorithm is correct. We must show three things about a loop invariant:

1. Initialization: It is true prior to the first iteration of the loop.
2. Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
3. Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Analyzing algorithm

Analyzing an algorithm has come to mean predicting the resources that the algorithm requires. Occasionally, resources such as memory, communication bandwidth, or computer hardware are of primary concern, but most often it is computational time that we want to measure.

Carefully defined “size of input” and “running time”

• The best notion for input size depends on the problem being studied. (number of items in the input, total number of bits, etc.)

• The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed. We usually concentrate on finding only the worst-case running time, that is, the longest running time for any input of size n. Because

  1. The worst-case running time of an algorithm gives us an upper bound on the running time for any input. Knowing it provides a guarantee that the algorithm will never take any longer.
  2. For some algorithms, the worst case occurs fairly often.
  3. The “average case” is often roughly as bad as the worst case.

Order of growth (Rate of growth)

• ignore the lower-order terms and the leading term’s constant coefficient to ease analysis

The divide-and-conquer approach

Divide-and-conquer approach break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem. The divide-and-conquer paradigm involves three steps at each level of the recursion:

1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
2. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
3. Combine the solutions to the subproblems into the solution for the original problem.

Reference

• Introduction to algorithm

• Loop invariant - Wikipedia