[personal profile] aranthe2010-06-08 03:31 pm

Quiz 1, Lecture 9, PS5 Links


[personal profile] aranthe2010-06-03 01:54 pm

PS4: Problem 4 » Solution

PS4 » Problem 4

def findMaxExpenses(salary, save, preRetireGrowthRates, postRetireGrowthRates,

    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
            # 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
                # 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] aranthe2010-06-03 01:42 pm

PS4: Problems 1–3 » Solutions

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 )
            # 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 )
            # 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 )
            # 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] aranthe2010-05-05 02:34 pm

PS3: Problem 3 » Solutions

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 ()
        tryK = firstMatch[-1] + length + 1
        if tryK in secondMatch:
            return (firstMatch[-1],) + constrainedMatchPairR(firstMatch[:-1], secondMatch, length)
            return constrainedMatchPairR(firstMatch[:-1], secondMatch, length)
[personal profile] aranthe2010-05-04 01:03 pm

PS3: Problem 2 » Solutions

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 )
        # 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 )]
        offsets = range(0, len(target) )
    return offsets

def subStringMatchExactR( target, key ):
    if key:
        if target.rfind(key) == -1:
            return ()
            offset = target.find(key) + 1
            return (target.rfind(key),) + subStringMatchExactR(target[:target.rfind(key)],key)
        return range(0, len(target)+1 )
[personal profile] aranthe2010-05-03 03:17 pm

PS3: Problem 1 » Solutions

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
        return 1 + countSubStringMatchRecursive( target[(target.find( key ) + len(key)):], key )
[personal profile] aranthe2010-04-08 01:19 pm

PS2: Problems 3, 4 » Solution

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

        # 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 )

            # 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.
                    if has_solution:
                if has_solution:

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

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

        # 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.
        n += 1

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

PS2: Problems 1, 2 » Solutions

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 )

    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.

    #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.

Readings and PS4

As per my last post, I have not read these nor done the problem set. Any more volunteers to take over or possibly tag team with [personal profile] aranthe? Doing these posts doesn't require comprehension of the material (as some of my discussion questions have indicated, I'm sure), it just requires that you do the readings and watch the lectures on schedule.

Analysis of Algorithms
Wikipedia Binary Search Algorithm with the focus on the Implementations section.
Asymptomatic Notation (PDF)

Problem Set 4 (PDF)
Supporting File
jetamors: Yoruichi is really hot (Default)
[personal profile] jetamors2010-02-07 07:35 pm

Solution to ps3

As always, please feel free to critique my code, ask questions, or post your own code in the comments. I did problems 2-4 using iterative solutions, so I'd be especially interested in seeing recursive solutions for those problems. Also note that several of these functions call each other, so they need to be placed in the same file.

Solution to ps3 )

Readings and PS3

As of this week's readings, we're over halfway done with all the readings for the course! \0/ It gets a lot lighter, reading wise, from here on out, and I have to admit to being a bit relieved. Maybe now I'll actually manage to do the problem sets before I put up this post...

Anyway, for Lecture 6 we're supposed to read through Chapters Eight and Ten, using part of the Python Tutorial as a reference. I have one question to toss out for discussion. I know the long form came up in lecture last week, but I didn't realize until I did today's readings that you could force Python into the long form. I just thought it was something that Python switched into when the numbers got too long. Why would you want to start your calculations in long form? Wouldn't it be easier to let Python do it on its own?

Open to: Registered Users, detailed results viewable to: All, participants: 2

PS 3 is

View Answers

roasted and ready to eat
1 (50.0%)

a little undercooked yet
1 (50.0%)

still raw
0 (0.0%)

Now, I'm still working on PS3 myself, and given that I'm fast approaching the point of garbled language exhaustion, it ain't happening tonight. Any volunteers to put up their code?
jetamors: Yoruichi is really hot (Default)
[personal profile] jetamors2010-01-24 08:13 pm

Solution to ps2

Putting my code for ps2 behind the cut. Please feel free to critique it, ask questions, or post your own code in the comments.

Solution to ps2 )

(Also a question: when I have a really long print statement like this, how do I break it up so it doesn't stretch the screen? I looked through some of the documentation, but I couldn't find anything on it.) ETA: Figured it out and updated my code :)
jetamors: Yoruichi is really hot (Default)
[personal profile] jetamors2010-01-16 01:59 am

Solution to ps1

The solution I wrote is behind the cut. Please let me know if you have any questions about the math or the code itself, or feel free to share your own solution in the comments.

ps1.py )

Readings and PS1

Hi everyone!

First, class business... I went poking around the website, and I found a suggested schedule for the problem sets. They actually correspond to the lectures, imagine that! Anyway, armed with this new info, I've made some tweaks to the problem set schedule.

They're below the cut, if anyone's interested. )

I also discovered that there are three quizzes associated with this course. So I'm putting the question to you all - do you want to do them?

Poll #2096 Quiz? What Quiz?
Open to: Registered Users, detailed results viewable to: All, participants: 7

I would like to include the quizzes in the course.

View Answers

Yeah, sure, extra practice is good.
7 (100.0%)

No way, I've got enough on my hands with the problem sets.
0 (0.0%)

If you would like to do the quizzes, how should we incorporate them?

View Answers

Add them on top of the lecture and reading in the week where they fit in the sylabus.
7 (100.0%)

Push the lectures back a week to make time for the quiz
0 (0.0%)

Some other idea which I'll tell you about in the comments
0 (0.0%)

Okay, that's out of the way, on to the readings.

I gotta say, this week kicked my ass, and these readings were right there with work and family issues, putting their prints on my bum. The wikibook chapters in particular just are not working for me. Is anyone else having that issue? My notes on those chapters are scattered with big red question marks and underlines with "What does this mean??" written off to the side. Part of this, I think, is that I really don't do numbers. I had to go look up the definition of a prime for the problem set...

Anyway, I've got some questions to toss out for discussion.

1- From the Data Structures reading, what are stacks and queues and why do we care about them? The reading just goes, 'This makes it easy to use lists in stacks and queues, whee!' (Or at least, that was my impression...)
2- From the same reading, why is it useful to be able to unpack a tuple?

Anyone else have questions for the class? This set of readings certainly provides fertile ground for questions. All of section 5.8 of the Data Structures had me going, "Bzuh?" And I just gave up on the wikibook...

Poll #2097 Who rocked problem set one?
Open to: Registered Users, detailed results viewable to: All, participants: 1

I have...

View Answers

Knocked it out of the park.
1 (100.0%)

Struck out.
0 (0.0%)

There's still another at bat to go!
0 (0.0%)

I thought problem set one...

View Answers

Was easy peasy
0 (0.0%)

Was a pain, but achievable
1 (100.0%)

Was way too hard... when did we learn how to do this stuff, again?
0 (0.0%)

Now, [personal profile] aranthe has generously posted answers to some of the exercises in the readings. Anyone want to volunteer to do that for PS1?

Readings and PS0

All right! Looking at my schedule for the coming weeks, I think I'm going to add a readings and problem set post on Fridays, just to keep them separate from the lectures and to give everyone time to digest and discuss the information before we dive into the next lecture. (This will also give me an extra kick in the rear mid-week to get everything done!)

Thusfar, I've read through chapter 1 and chapter 2 of How to Think Like a Computer Scientist, the variables and strings and input and output sections of Python Programming, and the variables tutorial on Pythonista. They're a bit repetitive, but repetition is good for my brain! If you're a visual learner, do the tutorial on Pythonista first, because there's a really nice series of images there.

Out of the readings, the only thing that gave me pause was the minutes since midnight program in Chapter 2. I'm not sure exactly why... I didn't define hours and minutes when I first ran the example, and then after defining them it seemed a bit useless to write a program that only gave the correct answer at that exact moment. (Anyone watch Alice in Wonderland as a kid? That scene where they're cleaning the attic - "This old clock; it tells the right time twice a day. As for the rest? While, maybe not...") Regardless, I ought to go back to that when I'm not tired and trying to do all the readings in one chunk. Did anyone else have trouble with that one, or with anything else in the readings?

And then, PS0! As [personal profile] smc1225 graciously pointed out, you have to open a new window to write your code and then run it. This link, which she (guessing gender from the list of feeds on your profile, [personal profile] smc1225; my most humble apologies if I'm wrong) found when the November group went through PS0, is massively helpful.

So, who's finished PS0? I can't create polls, apparently, but let's report in on our successes and mistakes before we plunge onward into lecture 2!

Edit: Oh, wow, someone gave me paid time! Thanks, oh anonymous benefactor!

Edit 2: Ok, it appears I'm not allowed to insert polls into pre-paid time posts. But, in the future, there will be fun with polls! :D
elz: (ada-tubes)
[personal profile] elz2009-11-16 09:41 pm
Entry tags:

Problem Set 2

Post and discuss your answers in the comments! (And yay for everybody who posted problem set 1 answers!)
elz: (ada-tubes)
[personal profile] elz2009-11-11 10:52 pm
Entry tags:

Poll & solutions


Open to: Registered Users, detailed results viewable to: All, participants: 25


View Answers

Finished lecture 2
24 (96.0%)

Finished problem set 1
15 (60.0%)

Also, it occurs to me that it might be handy to have a place to post/discuss solutions to the problem sets, to see what we can learn from each other in the absence of TAs. If you actually go to MIT and the problem sets are still the same, don't read these. ;)

Fire away!