Algorithms-C1-Foundations

INSERTION-SORT(A)
for j = 2 to A.length
    key = A[j]
    // Insert A[j] into the sorte sequence A[1...j-1].
    i = j - 1
    while i > 0 and A[i] > key
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key

MERGE(A,p,q,r)
    n_1 = q - p + 1
    n_2 = r - q
    let L[1..n_1+1] and R[1..n_2+1] be new arrays
    for i = 1 to n_1
        L[i] = A[p + i - 1]
    for j = 1 to n_2
        R[j] = A[q + j]
    L[n_1 + 1] = infty
    R[n_2 + 1] = infty
    i = 1
    j = 1
    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else 
            A[k] = R[j]
            j = j + 1

MERGE-SORT(A,p,r)
    if p < r
        q = floor (p + r)/2
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q + 1, r)
        MERGE(A, p, q, r)

FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)
    left-sum = -infty
    sum = 0
    for i = mid downto low
        sum = sum + A[i]
        if sum > left-sum
            left-sum = sum
            max-left = i
    right-sum = -infty
    sum = 0
    for j = mid+1 to high
        sum = sum + A[j]
        if sum > right-sum
            right-sum = sum
            max-right = j
    return (max-left, max-right, left-sum+right-sum)

FIND-MAXIMUM-SUBARRAY(A,low,high)
    if high == low
        return (low, high, A[low])
    else
        mid = (low + high) / 2
        (left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)
        (right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY(A, mid+1, high)
        (cross-low, cross-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
        if left-sum >= right-sum and left-sum >= cross-sum
            return(left-low, left-high, left-sum)
        else if right-sum >= left-sum and right-sum >= cross-sum
            return(right-low, right-high, right-sum)
        else return (cross-low, cross-high, cross-sum)

SQUARE-MATRIX-MULTIPLY(A,B)
    n = A.rows
    Let C be a new n x n matrix
    for i = 1 to n
        for j = 1 to n
            c_ij = 0
            for k = 1 to n
                c_ij = c_ij + a_ik b_kj
return C

SQUARE-MATRIX-MULTIPLY-RECURSIVE(A,B)
    n = A.rows
    Let C be a new n x n matrix
    if n == 1
        c_11 = a_11 b_11
    else
        partition A,B,and C as in equations(4.9)
        C_11 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_11,B_11) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_12,B_21)
        C_12 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_11,B_12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_12,B_22)
        C_21 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_21,B_11) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_22,B_21)
        C_22 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_21,B_12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_22,B_22)
return C

HIRE-ASSISTANT(n)
    best = 0    //candidate 0 is a least-qualified dummy candidate
    for i = 1 to n
        interview candidate i 
        if candidate i is better than candidate best
            best = i
            hire candidate i