Hilarious spoof by SNL on the Republicans:
Month: February 2009
Trivial subset sum problem
I was asked in a telephone interview how to find out if there are two numbers in
a list that sum to a certain value. I did an O(N^2) algorithm, then refined it to an O(n lg n) algorithm. Unfortunately, there’s an O(n) algorithm which I didn’t think of on the phone but came up with after the fact:
def somePair(values, Z):
"""
Given a list of numbers and value Z, are there any pair of numbers such that X+Y = Z?
This does this in O(N) time looking at each value, val, and checking if Z-val is
already in a lookup table.
"""
lookup = set() # Store the values
for val in values:
diff = Z - val
if diff in lookup:
return True
else:
lookup.add(val)
return False
if __name__ == '__main__':
assert somePair([], 4) == False
assert somePair([4], 4) == False
assert somePair([1,2,3,4], 1) == False
assert somePair([1,2,3,4], 2) == False
assert somePair([-8, 12], 4)
assert somePair([1,2,3,4], 3)
assert somePair([1,2,3,4, 4], 3)
assert somePair([1,2,3,4], 4)
Stimulus and the Economy
This chart from the Fed shows how far below capacity the economy currently expressed as a percentage of total capacity.
It’s the counter argument to the proposition that the stimulus is just going to crowd out private investment. Businesses have cut back on production because of reduced demand which further reduces demand.
If bankers were…
From The Salt Lake Tribune:
Job losses as a percent of peak
Ah, here’s the version normalized to the peak employment level before recession a started. From calculatedriskblog.com:
TED and Saturn
I watched this TED talk on the Cassini probe to Saturn.
You can grab images here. It’s a great collection especially for setting as backgrounds. Here’s one from Nov 2007:
or this one from Oct 2007:
Job losses and consumer spending
Is the past prelude? Here’s a comparison of job losses in all the post-WW2 recessions. Note how bad the slope is for the current recession. Be careful though, these are absolute numbers and not relative to population.
And here is the change in consumer spending over the past 50 years smoothed to six months — meaning some bad months have gotten smoothed over with the surrounding better months. Is this really the only the second time it’s gone negative in five decades? And that first time was only barely negative.
The White House fights back
Barack Obama has an op-ed in the Washington Post
starts to fight back at the short sighted, self-serving views that the Republicans have been using the past two weeks.
The Action Americans Need:
In recent days, there have been misguided criticisms of this plan that echo the failed theories that helped lead us into this crisis — the notion that tax cuts alone will solve all our problems; that we can meet our enormous tests with half-steps and piecemeal measures; that we can ignore fundamental challenges such as energy independence and the high cost of health care and still expect our economy and our country to thrive.
I reject these theories, and so did the American people when they went to the polls in November and voted resoundingly for change. They know that we have tried it those ways for too long. And because we have, our health-care costs still rise faster than inflation. Our dependence on foreign oil still threatens our economy and our security. Our children still study in schools that put them at a disadvantage. We’ve seen the tragic consequences when our bridges crumble and our levees fail.
I particularly liked the modest identification at the end of the article:
The writer is president of the United States.
Pete Ware 
