### Lecture 10 / PS 5 Reminder

**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:

- Lecture 10 (spans June 21–July 4, 2010):
- Divide and conquer methods, merge sort, exceptions (video)
- Handout (PDF)

- Assignment
- PS5 (due July 4): PS5: Word games (PDF)
- ps5.py (Exercise template, problems 1-5)
- test_ps5.py (Unit tests)
- ps5_ghost.py (Exercise template, problem 6)
- Word list (Text file)

### Quiz 1, Lecture 9, PS5 Links

Links:

- Quiz 1:
- Lecture 9 (spans June7–June20, 2010):
- Binary search, bubble and selection sorts (video)
- Handout (PDF)

- Assignment
- PS5 (due July 4): PS5: Word games (PDF)
- ps5.py (Exercise template, problems 1-5)
- test_ps5.py (Unit tests)
- ps5_ghost.py (Exercise template, problem 6)
- Word list (Text file)

### PS4: Problem 4 » Solution

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

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

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

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

### 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 else: return 1 + countSubStringMatchRecursive( target[(target.find( key ) + len(key)):], key )

### Lecture 6 / PS 3 Reminder

Links:

- Lecture 6 (spans April 19–May 2, 2010):
- Assignment
- PS3 (due May 2): PS3 (PDF)
- ps3_template.py (Exercise template)

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

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

### Lecture 5 / PS 3 Start

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:

- Lecture 5 (spans April 5–April 18, 2010):
- Assignment
- PS3 (due May 2): PS3 (PDF)
- ps3_template.py (Exercise template)

### PS1: Problem 2 » Solution

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

### PS1: Problem 1 » Solution

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 ' '

### Lecture 3 / PS1 Start

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:

- Lecture 3 (spans March 8–21, 2010):
- Common code patterns: iterative programs (video)
- Handout (PDF)

- PS1 (due March 21): Computing prime numbers, product of primes (PDF)

### Update on reset

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.

### If there are only four of us...

...I think we'd be safe making our own rules and setting our own pace. If you've read the comments to the last post, you know where each of the others stands. I've watched and read through the lecture 8 material and finished PS4, but I don't mind back-tracking if that's beneficial to everyone.

So...what say you all? Would you like to back up to an earlier lesson and take it at a more relaxed pace? If so, where would you like to start? From the beginning, or pick up at lecture 2, as everyone seems to have watched the first one? If you'd rather not back up, would you be willing to wait until everyone can catch up?

Re: pacing, how would you like to proceed? The current schedule is based on one lecture per week. We could do one every two weeks, which would work out to approximately one problem set per month. Would that be better?

One last thing: We might be able to help each other better if it's clear what each person hopes to get out of the course and if/where you may need specific help.

To alleviate the shyness factor, I'll begin: I wanted to follow this for three reasons: to pick up Python; to get a feel for the MIT OpenCourseware (because I want to take some others); and to see what sort of topics I might want or need to include—and exclude—from a programming concepts course I'm developing for non-programmers. As for help, I'm okay so far, though I've had to dredge up some math I haven't used in a while.

How 'bout you?

### Question re: Class Calendar/Schedule, Check-in

As **winterthunder** mentioned, I've agreed to take over the admin duties. However, as I'm in the middle of two major projects, I really need to relax the schedule a bit. Does anyone have any objection to this?

Also, I'd like to get an idea of how many are still following the class and your status—whether you're up-to-date, and if not, where you are in terms of the lectures, readings and problem sets.

Hope to hear from everyone who's still following!