Recitation02 Notes

From 6.006 Wiki

Solving recurrences

1. T(n) = T(n-1) + n; T(0) = 1

  T(n) = Theta(n^2)

2. T(n) = T(n/2) + c; T(1) = c

  T(n) = Theta(lg(n))

Improving an algorithm's running time

# Recitation 06- WF3
# Last Updated: September 10, 2008
#
# An implementation of the solution algorithms described in 
# Bentley's "Maximum Sum of a Contiguous Subvector" problem. 

import random
sample_input = [31, -41, 59, 26, -53, 58, 97, -93, -23, 84]
sample_input_lg = [random.randint(-1000, 1000) for i in range(1000)]

def max_subarray_v1(arr):
    """
    A O(n^3) algorithm that finds the maximum sum of a contiguous
    subarray from an input array of integers.
    """

    maxsofar = 0
    
    for i in xrange(len(arr)):
        for j in xrange(i, len(arr)):
            # alternatively: curr_sum = sum(arr[i:j+1])
            for elem in arr[i:j+1]:
                curr_sum += elem
            maxsofar = max(maxsofar, curr_sum)
            
    return maxsofar



def max_subarray_v2(arr):
    """
    A O(n^2) algorithm that finds the maximum sum of a contiguous
    subarray from an input array of integers.
    """

    maxsofar = 0

    for i in xrange(len(arr)):
        curr_sum = 0
        for elem in arr[i:]:
            curr_sum += elem
            maxsofar = max(maxsofar, curr_sum)

    return maxsofar



def max_subarray_v3(arr):
    """
    A O(n*lg(n)) algorithm that finds the maximum sum of a contiguous
    subarray from an input array of integers.
    """

    def maxsum3(arr, left, right):
        if (left > right): #zero elements
            return 0
        if (left == right): #one element
            return max(0, arr[left])

        #Find max left-crossing subarray
        mid = (left + right)/2
        leftmax = curr_sum = 0
        for i in xrange(mid, left-1, -1):
            curr_sum += arr[i]
            leftmax = max(leftmax, curr_sum)

        #Find max right-crossing subarray
        rightmax = curr_sum = 0
        for i in xrange(mid+1, right+1):
            curr_sum += arr[i]
            rightmax = max(rightmax, curr_sum)

        return max(leftmax+rightmax, maxsum3(arr,left,mid), maxsum3(arr,mid+1,right))

    return maxsum3(arr, 0, len(arr)-1)



def max_subarray_v4(arr):
    """
    A O(n) algorithm that finds the maximum sum of a contiguous
    subarray from an input array of integers.
    """

    maxsofar = 0
    maxendinghere = 0

    for elem in arr:
        maxendinghere = max(maxendinghere + elem, 0)
        maxsofar = max(maxsofar, maxendinghere)

    return maxsofar