[sticky entry] Sticky: Welcome post!

Oct. 27th, 2009 08:53 pm
elz: (chuck)
[personal profile] elz
Taking advantage of DW's new community sticky feature:

This is a community for people following along with MIT 6.00: Introduction to Computer Science and Programming, which is part of their OpenCourseWare project; the lectures, reading assignments and problem sets are all free and available online. The goal is to do a first run-through from November 2009 - February 2010, although obviously you can go at your own pace, and it would be great to muster up enough people to support each other on different timeframes (one lecture a week or starting after the new year).

Feel free to join in at any point! No programming experience necessary.

ETA: If you don't have a dreamwidth account but would like one, check out [site community profile] dw_codesharing or drop me a line.
[personal profile] aranthe
I apologize for not having posted this sooner, but I've been swamped. As that will continue for the foreseeable future, I no longer have time to keep up with the assignments and postings. If there is anyone monitoring this community who would like to step in and take over at this point, that would be great. If not, I'll resume when I can, but that may not be until after the beginning of the year (if then).
[personal profile] aranthe

Note:Apparently, MIT re-arranged the furniture a few weeks ago. If you've tried to follow the links in the online calendar that I created for this session or links in posts prior to the previous one, they will redirect you to the main page for this course.

Also, if you're still following the course, could you post a quick reply to this post and let me know whether you're up-to-date or whether we need to pause for a catch-up?

Links:

[personal profile] aranthe

Links:

[personal profile] aranthe

PS4 » Problem 4

def findMaxExpenses(salary, save, preRetireGrowthRates, postRetireGrowthRates,
                    epsilon):

    assert salary > 0, 'Salary must be greater than 0:' + str(salary)
    assert 0 < save < 100, 'Savings percentage must be between 0 and 100:' + str(savePct)
    assert 0 < epsilon < 1 , 'Upper boundary must be between 0 and 1:' + str(epsilon)

    # Generate the savings record.
    savingsRecord = nestEggVariable(salary, save, preRetireGrowthRates)

    # Savings at retirement will be the last entry;
    # it is also the upper limit on possible expenses.
    savingsAtRetirement = savingsRecord[-1]
    high = savingsAtRetirement
    guess = high # Seed initial guess.
    low = 0.0 # Seed lower guessing limit.
    found = False # Initialize search check.
    count = 1 # Initialize a counter, so search doesn't get out of hand.

    # Upper limit on count protects against process overruns.
    while not found and count < 100:

        # Calculate the fund balance with the current guess.
        fundBalances = postRetirement(savingsAtRetirement, postRetireGrowthRates, guess)
        endingBalance = fundBalances[-1] # Obtain the ending balance for testing.

        # Check to see if it is within episilon on either side of 0.
        if abs(endingBalance) < epsilon:
            found = True
        else:
            # If not, check to see if it's too high or too low.
            if endingBalance < 0:
                # Guess was too high. I need a new guess halfway between
                # the old one and the low.
                high = guess
                guess = (low + high)/2
            else:
                # Guess was too low. I need a new guess halfway between
                # the old guess and the last high.
                low = guess
                guess = (low + high)/2
            count = count + 1
    return guess
[personal profile] aranthe

Sorry these are late! I completely forgot that it was due this week.

Note: To simply readability, I've removed all of the triple-quoted comments found in the template and will post problem 4 separately because it's longer.

PS4 » Problem 1

def nestEggFixed(salary, save, growthRate, years):

    assert salary > 0, 'Salary must be greater than 0:' + str(salary)
    assert 0 < save < 100, 'Savings percentage must be between 0 and 100:' + str(savePct)
    assert 0 < growthRate < 100, 'Growth rate must be greater than 0:' + str(growthPct)
    assert years > 0, 'Years must be greater than 0:' + str(years)

    savingsRecord = [] # Initialize savings list.

    # Add one to years to capture last year.
    for year in range( 1, years+1 ):

        # First year is different.
        if( year == 1 ):
            savingsRecord.append( salary * save * 0.01 )
        else:
            # savingsRecord[-1] is the savings at the end of the last year.
            savingsRecord.append( savingsRecord[-1] * (1 + 0.01 * growthRate) + salary * save * 0.01 )
    return savingsRecord

PS4 » Problem 2

def nestEggVariable(salary, save, growthRates):

    assert salary > 0, 'Salary must be greater than 0:' + str(salary)
    assert 0 < save < 100, 'Savings percentage must be between 0 and 100:' + str(savePct)

    savingsRecord = [] # Initialize savings list.
    years = len(growthRates) # Compute number of years from input variable.
    
    # Add one to years to capture last year.
    for year in range( 1, years+1 ):
        
        # First year is different.
        if( year == 1 ):
            savingsRecord.append( salary * save * 0.01 )
        else:
            # savingsRecord[-1] is the savings at the end of the last year.
            savingsRecord.append( savingsRecord[-1] * (1 + 0.01 * growthRates[year-1]) + salary * save * 0.01 )
    return savingsRecord

PS4 » Problem 3

def postRetirement(savings, growthRates, expenses):

    assert savings > 0, 'Savings must be greater than 0:' + str(savings)

    fundBalances = [] # Initialize fund list.
    years = len(growthRates) # Compute number of years from input variable.
    
    # Add one to years to capture last year.
    for year in range( 1, years+1 ):
        
        # First year is different.
        if( year == 1 ):
            fundBalances.append( savings * (1 + 0.01 * growthRates[year-1]) - expenses )
        else:
            # fundBalances[-1] is the fund at the end of the last year.
            fundBalances.append( fundBalances[-1] * (1 + 0.01 * growthRates[year-1]) - expenses )
    return fundBalances
[personal profile] aranthe

Links:

[personal profile] aranthe

Oops! I almost forgot about problem 4. I didn't have time to attempt a recursive solution for this one. (Off the top of my head, I think the key would be to encapsulate the loop portion into a recursive function, rather than to make the entire subStringMatchExactlyOneSub function recursive.) If you've done one, please post it.

PS3: Problem 4 » Solution

def subStringMatchExactlyOneSub( key, target ):

    subOneMatches = sorted(subStringMatchOneSub( key, target ))
    exactMatches = sorted(subStringMatchExact( target, key ))

    exactOneMatches = ()
    for subOneMatch in subOneMatches:
        if subOneMatch not in exactMatches:
            exactOneMatches += subOneMatch,
    return exactOneMatches
[personal profile] aranthe

PS3: Problem 3 » Solutions

# Problem 3: constrainedMatchPair, constrainedMatchPairR (recursive)
def constrainedMatchPair( firstMatch, secondMatch, length ):
    allN = ()
    for n in firstMatch:
        tryK = n + length + 1
        if tryK in secondMatch:
            allN += n,
    return allN

def constrainedMatchPairR( firstMatch, secondMatch, length ):
    if not firstMatch:
        return ()
    else:
        tryK = firstMatch[-1] + length + 1
        if tryK in secondMatch:
            return (firstMatch[-1],) + constrainedMatchPairR(firstMatch[:-1], secondMatch, length)
        else:
            return constrainedMatchPairR(firstMatch[:-1], secondMatch, length)
[personal profile] aranthe

The non-recursive version can be done as easily with find as with rfind, so I've shown both. My recursive version uses rfind. If someone has a recursive version that uses find, I'd be curious to see it. I have a theory about why I found rfind necessary to work the recursive version, but it could be way off base; I'd like to find out.

PS 3: Problem 2 » Solutions

# Problem 2: subStringMatchExact (uses find), subStringMatchExact2 (uses rfind),
# subStringMatchExactR (recursivem uses rfind)
def subStringMatchExact( target, key ):
    if key:
        offsets = ()
        offset = target.find( key )
        while offset != -1:
            offsets += offset,
            offset = target.find( key, offset+1 )
    else:
        # A little something he didn't mention: In Problem 3, if the key 
        # is a single letter and key1 or key2 is empty, n+m+1 overrun the last
        # index and won't return it, even though the last index is an
        # acceptable value. Therefore, we have to add an extra index when key
        # is empty. INELEGANT!
        offsets = range(0, len(target)+1 )
    return offsets

def subStringMatchExact2( target, key ):
    if key:
        offsets = ()
        while target.rfind( key ) != -1:
            offsets += (target.rfind( key ),)
            target = target[:target.rfind( key )]
    else:
        offsets = range(0, len(target) )
    return offsets

def subStringMatchExactR( target, key ):
    if key:
        if target.rfind(key) == -1:
            return ()
        else:
            offset = target.find(key) + 1
            return (target.rfind(key),) + subStringMatchExactR(target[:target.rfind(key)],key)
    else:
        return range(0, len(target)+1 )
[personal profile] aranthe

I'll be posting the remaining solutions over the next few days, as soon as I have time to finish reviewing them.

PS3: Problem 1 » Solutions

# Problem 1: countSubstringMatch, countSubstringMatchRecursive
def countSubStringMatch( target, key ):
    count = 0
    while target.find( key ) > -1:
        count += 1
        target = target[target.find( key ) + len( key ):]
    return count

def countSubStringMatchRecursive( target, key ):
    if target.find( key ) < 0:
        return 0
    else:
        return 1 + countSubStringMatchRecursive( target[(target.find( key ) + len(key)):], key )
[personal profile] aranthe

Links:

[personal profile] aranthe

Links:

[personal profile] aranthe

When I worked problem 3, I happened to do it in such a way that it also solved problem 4, so I don't have separate solutions for problems 3 and 4.

Also, I added some code that cuts down on the process count by quickly eliminating obvious factors. I've marked this "OPTIONAL" to avoid confusion with the required parts of the script.

PS 2: Problems 3 and 4

# Initialize configuration variables ##########################################
packages = 6, 9, 20            # IMPORTANT: order from smallest to greatest!
upper_limit_of_n = 200         # Imposes upper limit on processes.

# Working variables. ##########################################################
terms = len(packages)          # Yeah, we know, but it saves some processes.
x, y, z = packages             # This allows the rest to handle Problem 4, too.

n = 1 # init n
a = 0 # coefficient is x
b = 0 # coefficient is y
c = 0 # coefficient is z

success = 0 # consecutive success counter
stop = 0    # while switch

# OPTIONAL: Derive obvious factors for quick elimination.
# If python thinks smart, sorting will help.
factors = sorted([x, y, z, x+y, y+z, z+x, x+y+z])

while not stop:

    # Initialize solution switch
    has_solution = False

    # OPTIONAL: Weeds out obvious values of n without the combinatorial work.
    # LOGIC: If n is evenly divisible by any of the factors above, it has a
    # solution set. (We don't need to identify that set.)
    if not n%factors[0] or not n%factors[1] or not n%factors[2] or \
       not n%factors[3] or not n%factors[4] or not n%factors[5] or not n%factors[6]:
        has_solution = True

    else:
        # Aargh! No easy way out; brute force, then:

        # Initialize list to hold test ranges.
        ranges = []

        # Don't waste time on values of n < the largest coefficient.
        if n > z:

            # Generate a test range for each term.
            for i in range(0, terms):

                # LOGIC: For each term, the upper limit will be n divided by
                # the coefficient of that term. Proof: a*x + 0*y + 0*z = n =>
                # => a*x = n => n / a = x; x is the upper limit.
                limit =  int( n / packages[i] ) + 1
                i_range = range( 0, limit )
                ranges.append(i_range)

            # Loop through the test ranges.
            for a in ranges[0]:
                for b in ranges[1]:
                    for c in ranges[2]:
                        # Test solution set against n.
                        if (a*x) + (b*y) + (c*z) == n:
                            has_solution = True
                            # No need to look further.
                            break
                    if has_solution:
                        break
                if has_solution:
                    break

    # Check to see if we have a solution.
    if has_solution:

        # If so, increment success count.
        success += 1

    else:
        # If we find a fail, record it and reset the success counter.
        last_fail = n
        success = 0

    # Check success counter. If equal to smallest coefficient
    # we've passed the last failure.
    if success == x:
        stop = 1

    # If not, check to see if we've reached the upper process limit.
    elif n > upper_limit_of_n:
        stop = 1
        last_fail = 0

    # Otherwise, increment n.
    else:
        n += 1

if last_fail == 0:
    print 'Stopped at upper process limit. No max purchase within limit.'
else:
    print 'Largest number of McNuggets that cannot be purchased in exact quantity: '
    print last_fail
[personal profile] aranthe

Here are the solutions to problems 1 and 2. I'll be posting 3/4 as soon as I have it annotated.

PS 2: Problem 1

# Initialize configuration variables
coefficients = 6, 9, 20
mcnuggets = range( 50, 56 )
terms = len(coefficients)
combos = [] # Holds list of combinations.

a = 0 # coefficient: 6
b = 0 # coefficient: 9
c = 0 # coefficient: 20

# Loop through the mcnuggets range.
for n in mcnuggets:

    ranges = [] # Holds test ranges.

    # Create test ranges for the coefficients for this value of n.
    for i in range(0, terms):
        limit =  int( n / coefficients[i] ) + 1
        i_range = range( 0, limit )
        ranges.append(i_range)

    n_combos = [] # Holds all combos for a given n

    # Loop through the test range.
    for a in ranges[0]:
        for b in ranges[1]:
            for c in ranges[2]:

                # Check to see if the sum of the terms is equal to n. 
                if (a*coefficients[0]) + (b*coefficients[1]) + (c*coefficients[2]) == n:

                    # If so, create an array of this combination.
                    combo = [ a, b, c ]

                    # Append it to the collection of combos for this n.
                    n_combos.append(combo)

    #Print combos for this n.
    print 'For n = ', n
    print 'Combos:', n_combos

PS 2: Problem 2

Theorem:If it is possible to buy x, x+1,…, x+5 sets of McNuggets, for some x, then it is possible to buy any number of McNuggets >= x, given that McNuggets come in 6, 9 and 20 packs.

Explain, in English, why this theorem is true.

The key is in the given: The smallest coefficient is 6. Once you find solutions for six consecutive amounts, every amount beyond the last one can be derived by adding 6-packs to one of the consecutive solutions.

In the abstract, the minimum number of consecutive solutions required to insure that every subsequent number has a solution is equal to the smallest coefficient of the terms.

[personal profile] aranthe

I'll post the solutions to PS2 within the next day or two. (If you'd like to post your own solutions, jump right in.)

Links:

[personal profile] aranthe

PS 1: Problem 2

# Import math module.
from math import *

# Enter the upper limit.
n = int(raw_input( 'Compute for primes between 2 and this number: '))

# Initialize state variables.
primes = [2]
count = 1
log_sum = 0
limit = n - 1  # Do this because we're incrementing by 2.
# Do this until we reach the limit.
while count < limit:

    # Increment counter by 2. (Eliminates all divisible by 2.)
    count += 2
    
    # Set prime switch true.
    is_prime = True

    # Loop through the testing slice.
    for prime in primes:

        # Check to see if count is prime.
        if count % prime == 0:

            # Not a prime, set switch to false.
            is_prime = False

            # Don't waste any more time on this number.
            break

        # Check for testing limit.
        if prime**2 > count:
            break

    # Check the switch; if it's still true...
    if is_prime:
        #...count is prime. Add it to the primes array.
        primes.append(count)
        
# Loop through the primes and add up the logs.
for prime in primes:
    log_sum += log(prime)
        
# Compute the ratio of the sum to the limit
ratio = log_sum / limit
length = len(primes)

# print
print 'The upper limit (n) is:', n
print 'Computed for', length, 'primes.'
print 'The sum of the logarithms of these primes is', log_sum
print 'The ratio of the sum to the limit is:', ratio
[personal profile] aranthe

I haven't had time to edit Problem 2 yet, but will post it as soon as I do.

PS 1: Problem 1

# Initialize state variables.
primes = [2]
count = 1
sum_candidates = 0
sum_tests = 0

# Do this until we have 1000 primes
while len(primes) < 1000:

    # Increment counter by 2. (Eliminates all divisible by 2.)
    count += 2

    # Set prime switch true.
    is_prime = True

    # Loop through the testing slice.
    for prime in primes:

        # Check to see if count is prime.
        if count % prime == 0:

            # Not a prime, set switch to false.
            is_prime = False

            # Don't waste any more time on this number.
            break

        # Check for prime limit.
        if prime**2 > count:
            break

    # Check the switch; if it's still true...
    if is_prime:
        #...count is prime. Add it to the primes array.
        primes.append(count)

# print
ordinal = str(len(primes)) + 'th'
print 'The', ordinal, 'prime is', count
print ' '
[personal profile] aranthe

I apologize for the late posting. Last week was, well, one of those weeks. I'll post the solutions to PS1 as soon as I review the second exercise. It's complete, but I want to be sure that is annotated well enough.

Links:

[personal profile] aranthe

In order to keep this straight in my head, I've collated a calendar with the start/due dates of the problem sets and the time spans of the lectures. The calendar has links to the major resources (PDFs, PY templates, lecture videos). As we complete the problem sets, I'll add links to the solutions. Of course, I'll also post the links here on the key dates.

Links:

[personal profile] aranthe

From the responses, I think we might be safe to start at lecture 3 and do 1 lecture every 2 weeks. If everyone is cool with that, I'll create a schedule that begins on Monday, March 8, and we'll start from there.

Page generated Oct. 23rd, 2014 01:33 am
Powered by Dreamwidth Studios