Recursive dropsort

December 8th, 2012

I had a unique interview question today.  ”What sorting algorithm would you take to a party?”  After covering some of the common sorting algorithms (quick sort, counting sort, etc.), I got to the lesser known Bogosort and Dropsort.  Dropsort is a O(n) algorithm that sorts a list by simply dropping elements that are out of order.  Usually, this is the end which isn’t very interesting.  What if you recurse on the dropped list then merge them back together?  It’s now very similar to merge sort.

As this is similar to merge sort, the recurrence relation would optimally be something like T(n) = T(n/2) + O(n).  If that were the case, this would be a O(n) sorting algorithm.  To be sure, I had to run some tests.

I went ahead and implemented a script to test the amount of dropped elements in each recursive call.  I also took into account the probability distribution from which the original list was sampled.

Recursive percent of n histogram

After 1000 different sorts on different probability distributions for input, I got these averages:

Poisson: 0.667483

Uniform: 0.756339

Normal: 0.690133

So, it’s clearly not n/2. For the case of uniform distribution, I’ll make the argument that T(n) = 3T(n/4) + O(n). Looking back through Cormen’s algorithms bible, there’s this exact example in the 2nd edition (section 4.2).  So, T(n) = 4n + O(n) = O(n).  I’m still skeptical about this because from the python I’ve written, it takes a while to sort.

Read the rest of this entry »

Posted in Programming, Uncategorized | No Comments »

apt-rate — Why is there still no feedback built into the apt-get system?

May 18th, 2012

apt-cache search “something useful” always returns tons of things and I have to go to google and read blogs to figure out which one I actually want.

Why hasn’t apt-get integrated a ratings and feedback system the way that the app store started out? It would solve the problem once and for all and significantly help improve the quality of the apt-get repository.

I’ve wanted to have this for years and considered building it a few times but always figured it would happen eventually.   I would really like to see this happen.

While we’re at it, can we add support for paid applications in apt-get?

Tags: , , ,
Posted in Programming | No Comments »

Socrates on writing – he was on the money all those years ago.

May 5th, 2012

I’ve long pondered and discussed with friends what happens when we shorten the distance from our questions to the answers using the internet.

If you have Google in your hand, you barely need to remember anything at all or even how to do almost anything. What portion of the population is going to know how to do multiplication or division in their head (or even on paper) in 30 years?

In college I saw the transition. Organic chemistry used to be memorization of reactions and the periodic table. Now they teach how to look things up and how to think about the problems — in my opinion this was a huge step forward.

However, I found that over the years I’ve memorized the periodic table, as many of the  chemistry reactions as I can and always try to avoid using a calculator or computers to do math – at least until after I’ve done the math myself — then I check everything using WolframAlpha.

I’ve never seen the topic addressed historically, usually people simply get worried and start beleving “someday no ones going to know how to do anything and the world will end.” I think it’s probably best to just call it evolution and leave it at that.

Here’s what Socrates’ had to say about writing and the damaging effect it was going to have on the human experience.

…this discovery of yours will create forgetfulness in the learners’ souls, because they will not use their memories; they will trust to the external written characters and not remember of themselves. The specific which you have discovered is an aid not to memory, but to reminiscence, and you give your disciples not truth, but only the semblance of truth; they will be hearers of many things and will have learned nothing; they will appear to be omniscient and will generally know nothing; they will be tiresome company, having the show of wisdom without the reality.
…

…writing is unfortunately like painting; for the creations of the painter have the attitude of life, and yet if you ask them a question they preserve a solemn silence. And the same may be said of speeches. You would imagine that they had intelligence, but if you want to know anything and put a question to one of them the speakers always gives one unvarying answer. And when they have been once written down they are tumbled about anywhere among those who may or may not understand them, and know not to whom they should reply, to whom not: and if they are maltreated or abused they have no parent to protect them; and they cannot protect or defend themselves.

 

Socrates, from me to you: Respect.

Posted in Uncategorized | No Comments »

Over write file with same file? Yes? No? Please stop already.

April 25th, 2012 
if ( old_file.size == new_file.size
    && old_file.size < SOMETHING_REASONABLE
    && md5(old_file) == md5(new_file) ) {
             // Please for the love of all things holly stop asking me
             // if I want to replace the file with the same one!!!!!!!!!
}

How many times in my life do I have to answer the question “Do nothing? Yes or No?”

I don’t expect computers to learn… but I do have some expectations of programmers!

Tags:
Posted in Programming | No Comments »

Good times with Maxwell’s laws.

March 30th, 2012

I was poking around with the good ol’ Maxwell’s equations and decided to estimate the internal current in the earth from our magnetic field.

From wikipedia, Ampere’s law states:

The earth’s magnetic field “ranges from about 25,000–65,000 nT” and I’m going to make the extremely rough estimate that it’s constant throughout the integral. This is far from the true but I’m guessing the minimum is 1/3 the maximum so my calculation should be within 30% ? (If I’m wrong about this feedback is appreciated).

The dE/dt term is going to be pretty close to 0 — I’m speculating this is actually term that causes the magnetic field to change polarity every few millennia.

 

Using the line from the south pole to the north through the center of the earth and back to the south pole along the surface we can write:

“Circumfrence of Earth” * (1/2 + 1/pi) * “Earth’s Magnetic Field” = “permeability of free space” * “Current of Earth”

It’s not obvious at first glance what the physical form of this current is. The current could be, for example, ionized magma, or the pressure in the core might be high enough to “squeeze out the electrons” or the entire earth could simply have a net static charge. I believe all these hypothesis are false. I think the generally accepted theory is that there is current flowing in the earths core.

Wolfram Alpha:
65,000 nT *(60*360 nmi) * (1/2 + 1/pi) / (permeability of free space) = 1.7 * 10^9 amps.

Checking the answer with Google I found: “Today, scientists think the earth is an electromagnet; the source of the magnetic field is probably a large electric current—billions of amperes—circulating in the earth’s fluid core.”

1.7*10^9 = billions of ampere’s — my 20 minute distraction doesn’t seem to be too bad of an estimate. — I’ll take it.

Tags: , , , , , ,
Posted in Math and Physics | No Comments »

Wow! This is an amazing data point.

March 30th, 2012

Conducting a survey across the population is not a good idea when it involves math.

 

When I watch this I can’t help but see similarities between the way our democracy “asks the audience” every time we vote and the relationship between our nations finances, health care and the public comprehension of math.

We keep asking the audience and slipping further and further into debt — this kid was lucky, he only lost 15K.

 

Posted in Math and Physics, Politics | No Comments »

When you completely redesign a user interface… (talking to you Ubuntu).

March 30th, 2012

 

When you completely redesign a user interface, please make it bloody obvious how to figure out how to use it….

Upgrading to Ubuntu 11.04 and 11.10 from the last n revisions is like punching yourself in the face.

  • I now have a bunch of bars that take up most of my screen.
  • I can’t resize any such bars.
  • I can’t right click on anything.
  • There is no obvious way to get to any settings panels or configure anything.
  • There is no obvious way to find help.
  • There are no longer any menu’s.
  • Googling is not producing anything but Rabbit Holes.

I upgraded to 11.04 and found it to be totally crippling.

It’s like trying to stick a Vim user in Emacs. or vic-a-versa.

Somedays I love Ubuntu and somedays I feel like WTF are they thinking…

Tags: ,
Posted in Uncategorized | No Comments »

Standing Square Wave on a string?

January 23rd, 2012

I don’t think we succeeded in making a square wave, at least not as well as I’d wanted. (Though we did get closer than some other videos I’ve seen on the internet.)

It’s still pretty cool. Hopefully there will be a better one along shortly. We’ve improved the design considerably since we made this one.

We’re using 2 teensy’s, python running in a virtual machine, an ipad app, a windows freeware tone generator, wikipedia and a bunch of different scopes and meters.

We’re plotting this function into a DAC and piping it into a 100watt amp.

a1*sin( 2*pi*t ) + a3*sin( 3 * 2*pi*t ) + a5*sin( 5 * 2*pi*t ) …. according to wikipedia the constants should be 1/3, 1/5, 1/7… but we’re having some good debate over the physics of a real string vs an ideal medium.

 

The disagreement is cool. It’s lead to lots of different and unexpected waveforms, all superpositions of the harmonics!

String Waves from colin street on Vimeo.

Tags: , , , , , , , , , , , ,
Posted in Math and Physics, Programming | No Comments »

Inverse of Python id function, di — or a[a]=a in Python.

January 23rd, 2012

In the spirit of giving matches to children, here’s a terrible little nugget.

Feel free to try this at home, but you didn’t learn it here and if you try to claim otherwise, we’re denying it.

The “di()” function

def di( id_val ):
    """Given an objects id, returned by the function id, return the original object"""
    for x in globals().values():
        if id(x) == id_val: return x

But why on earth would you do this? Well, this horribleness is motivated by the following:  The set of sets that contain themselves.

In javascript you can execute this:

a = {}
a[a]=a

It’s worthless but it works.

In python you get “TypeError: unhashable type: ‘dict’”

But you can do:

a = {}
a[id(a)]=a

Only this is useless without an inverse function for id. So I give you di(id_number) (which I scraped together from a quick google).

Now the self-referencing sets aren’t useless, they’re dangerous. Wonderful trade!

See Also: BF

Tags: , , , , , , , ,
Posted in Math and Physics, Programming | No Comments »

Republican 2012 Primary Schedule by States and their Delegate Counts by Type.

January 12th, 2012

I was browsing through Nate Silvers stuff on the 2012 Republic Nomination and noticed the question: Estimate the schedule of the certainty vs the date. In short “When can we expect it to be clear who will win the Republican Nomination?”

After some googling and picking around on Wikipedia I noticed I wasn’t finding a good answer, and I couldn’t even find a CSV of the calender schedule for delegates being voted vs date.

I’m sure it’s out there but until google does it’s job perfectly there’s only so much I can do.

Hence, I’ve compiled another one. It might have errors. It’s based on the data from wikipedia:
Republican_Party_presidential_primaries,2012

Here’s a link: 2012 Republican Primary Schedule/Calendar . CSV

According to Wikipedia there are 3 types of delegates:

“There are 3 kinds of delegates: Parti- or Superdelegates (RNC), Delegates elected in congressional districts (CD) and Delegates elected statewide (AL)”

Taken from http://en.wikipedia.org/wiki/Republican_Party_presidential_primaries, _2012
Date        , State/Territory          , Type                       , RNC , CD  , AL
1/3/2012    , Iowa                     , nonbinding caucus          , 3   , 12  , 13
1/10/2012   , New Hampshire            , semi-closed prmry          , 0   , 0   , 12
1/21/2012   , South Carolina           , open prmry                 , 0   , 14  , 11
1/31/2012   , Florida                  , closed prmry               , 0   , 0   , 50
2/4-11/2012 , Maine                    , nonbinding caucus          , 3   , 6   , 15
2/4/2012    , Nevada                   , binding caucus             , 3   , 12  , 13
2/7/2012    , Minnesota                , caucus                     , 3   , 24  , 13
2/7/2012    , Colorado                 , nonbinding caucus          , 3   , 21  , 12
2/25/2012   , Northern Mariana Islands , nonbinding caucus          , 3   , 0   , 6
2/28/2012   , Arizona                  , semi-closed prmry 29       ,     ,     ,
2/28/2012   , Michigan                 , open prmry 30              ,     ,     ,
3/3/2012    , Washington               , binding caucus             , 3   , 30  , 10
3/6-10/2012 , Wyoming                  , nonbinding caucus          , 3   , 3   , 23
3/6/2012    , (Spr Tues) Massachusetts , semi-closed prmry          , 3   , 27  , 11
3/6/2012    , (Spr Tues) Idaho         , binding caucus             , 3   , 6   , 23
3/6/2012    , (Spr Tues) North Dakota  , nonbinding caucus          , 3   , 3   , 22
3/6/2012    , (Spr Tues) Virginia      , open prmry                 , 3   , 33  , 13
3/6/2012    , (Spr Tues) Tennessee     , open prmry                 , 3   , 27  , 28
3/6/2012    , (Spr Tues) Alaska        , binding caucus             , 3   , 3   , 21
3/6/2012    , (Spr Tues) Georgia       , open prmry                 , 3   , 42  , 31
3/6/2012    , (Spr Tues) Oklahoma      , closed prmry               , 3   , 15  , 25
3/6/2012    , (Spr Tues) Ohio          , open prmry                 , 3   , 48  , 15
3/6/2012    , (Spr Tues) Vermont       , open prmry                 , 3   , 3   , 11
3/10/2012   , Guam                     , nonbinding caucus          , 3   , 0   , 6
3/10/2012   , U.S.                     , Virgin Islands caucus      , 3   , 0   , 6
3/10/2012   , Kansas                   , binding caucus             , 3   , 12  , 25
3/13/2012   , Alaabama                 , semi-closed prmry          , 3   , 21  , 26
3/13/2012   , Mississippi              , open prmry                 , 3   , 12  , 25
3/13/2012   , American                 , Samoa caucus               , 3   , 0   , 6
3/13/2012   , Hawaii                   , binding caucus             , 3   , 6   , 11
3/17/2012   , Missouri                 , binding caucus             , 3   , 24  , 25
3/18/2012   , Puerto                   , Rico binding caucus        , 3   , 0   , 20
3/20/2012   , Illinois                 , open prmry                 , 3   , 54  , 12
3/24/2012   , Louisiana                , open prmry                 , 3   , 18  , 25
4/3/2012    , Wisconsin                , open prmry                 , 3   , 24  , 15
4/3/2012    , Maryland                 , closed prmry               , 3   , 24  , 10
4/3/2012    , Washington D.C.          , closed prmry               , 3   , 0   , 16
4/3/2012    , Texas                    , open prmry                 , 3   , 108 , 44
4/24/2012   , Connecticut              , closed prmry               , 3   , 15  , 10
4/24/2012   , Delaware                 , closed prmry               , 3   , 3   , 11
4/24/2012   , Pennsylvania             , closed prmry               , 3   , 54  , 15
4/24/2012   , Rhode                    , Island semi-closed prmry   , 3   , 6   , 10
4/24/2012   , New                      , York closed prmry          , 3   , 81  , 11
5/8/2012    , North                    , Carolina semi-closed prmry , 3   , 39  , 13
5/8/2012    , Indiana                  , open prmry                 , 3   , 27  , 16
5/8/2012    , West                     , Virginia semi-closed prmry , 3   , 9   , 19
5/15/2012   , Oregon                   , closed prmry               , 3   , 15  , 10
5/15/2012   , Nebraska                 , semi-closed prmry          , 3   , 9   , 23
5/22/2012   , Kentucky                 , closed prmry               , 3   , 18  , 24
5/22/2012   , Arkansas                 , open prmry                 , 3   , 12  , 21
6/5/2012    , California               , semi-closed prmry          , 3   , 159 , 10
6/5/2012    , New Jersey               , closed prmry               , 3   , 36  , 11
6/5/2012    , South Dakota             , closed prmry               , 3   , 3   , 22
6/5/2012    , Montana                  , semi-closed prmry          , 3   , 3   , 20
6/5/2012    , New Mexico               , closed prmry               , 3   , 9   , 11
6/26/2012   , Utah                     , closed prmry               , 3   , 12  , 25

Tags: , , , ,
Posted in Math and Physics, Uncategorized | No Comments »

« Older Entries