views:

5272

answers:

114

In my question Insert Update stored proc on SQL Server I explained an efficient way of doing an insert/update - perhaps THE most efficient. It's nothing amazing but it's a small algorithm that I came up with in a mini-Eureka moment. Although I had "invented" it by myself and secretly hoped that I was the first to do so I knew that it had probably been around for years but after posting on a couple of lists and not getting confirmation I had never found anything definitive written up about it.

So my questions: What software algorithm did you come up with that you thought that you'd invented? Or better yet, did you invent one?

A: 

Median-Heaps :(

eplawless
+1  A: 

(Granted, none of these were as formally defined when I did them...)

Edit: Derek called me out on a slight miswording. By "none of these were as formally defined when I did them," I meant that my implementations weren't as complete as their formal definitions.

Ryan Fox
This entry seems to be a duplicate of one with 5 up-votes. It should probably be removed.
Jonathan Leffler
+2  A: 

@martinatime

Math is generally considered "discovered" as opposed to invented. And programming and related studies are considered applied math.

I've generally seen the opposite. e.g. Newton invented calculus. On the other hand, natural properties are generally "discovered." e.g. Pythagoras discovered the Pythagorean theorem.

Derek Park
Insofar as mathematics is immutable (which is debatable when dealing with the extremities of physics, for instance, but generally considered to be a property of the field), it is inherently discovered rather than invented. The methodology and the practices can be invented, but the underlying theory is a matter of discovery just like any other science.
eyelidlessness
Answers should not be addressed to other answers; only to the question. That's why the order of answers can change as people upvote and downvote, and why comments exist.
jprete
Calculus existed long before Newton found it. Nature is built on calculus.
seanmonstar
Yeah but he got to name it, since nothing in nature really has a name, until bunch of people decide on one.
Azder
jprete, comments have not always been available on Stack Overflow. Note that my answer was posted in August 2008, *the same month that the site launched*. New answers were the only way to comment.I see no value in going back and deleting all my existing "comment" answers. I really don't understand why you (and others) are digging into old questions to criticize a practice that predates comments.
Derek Park
Actually the Egyptians were the first to use the 'Pythagorean' theorem. When building temples they used a piece of string with knots tied at intervals of 3, 4 and 5. When the string was held taught at each knot, the triangle was always right-angled. For some reason Pythagoras was accreditted with the discovery.
rmx
A: 

After I was first exposed to selection sort I immediately saw room for improvement and created shaker sort. This was several years before I learned the name for either one.

Jeff
A: 

@Ryan

(Granted, none of these were as formally defined when I did them...)

Either the age on your profile page is way off, or you are drastically underestimating the development of computer science. It's a young field, but it's not that young.

Depth-first and breadth-first are both so old that no one seems to know who "invented" them first. A* (of which both are merely special cases) was published in 1968. Binary search is probably as old as sorting. If statements have been around since at least 1978 (K&R C), and probably quite a bit longer. Temporal difference learning was first described by that name in 1988. The Design Patterns book came out in 1994 (when you were presumably about 8 years old.

It's cool that you reinvented these things without being exposed to them first, but I'm pretty sure they were all formally defined before you did so.

Derek Park
um i think he means that when HE did them, HE didn't formally define them.
Epaga
Answers should not be addressed to other answers; only to the question. That's why the order of answers can change as people upvote and downvote, and why comments exist.
jprete
Well, many people I think, "invented" most of the design patterns described in the Design Patterns book. That's why they are patterns. At least, when I was reading it, I came across many that were similar to my designs, only a lot better...
Ricardo Ferreira
A: 

I rewrote strcmp in C before I knew it existed (silly, I know. I learned the syntax well before the library). Of course, my strcmp was not as good as the C library's.

Ed Swangren
Having ported a couple of C libraries to various places, and seeing the various default `strcmp()` implementations they ship with, I would not to be too sure of that...
Louis Gerbarg
Hehe, perhaps you're right
Ed Swangren
+13  A: 

Recursive descent parsing.

Michael Neale
+1 Same here. I used it in a bunch of projects before I found out it has a specific name.
Mehrdad Afshari
me too .. and I thought it was quite clever!!
hasen j
Yep, me too, though rather than thinking I invented it, I assumed it must be how all existing parsers worked.
Daniel Earwicker
+23  A: 

I invented the Internet. ;)

On a more serious note:
I was setting up my home network one day and thought "I should have a machine that is purposely weak so that hackers go after it instead of my other machines". For about five minutes I thought I had an original idea... Needless to say, I quickly found the term honeypot in Wikipedia and realized I'm just an average joe.

Esteban Araya
I thought that was Al Gore?
Matthew Whited
I don't think Al Gore ever claimed he invented the internet.
Breton
To be exact: The inventor of the environment and first emperor of the moon, Al Gore.
Daniel Earwicker
@Breton: don't let facts get in the way of cheap political jabs.
Lèse majesté
A: 

This wasn't necessarily an algorithm at all, but as a homework for my C/Assembly class we had to write and implement our own malloc.

If anyone did the google code jam qualification round this year, they did a load balancing algorithm, a scheduling algorithm, and a surface area algorithm.

contagious
A: 

While I have the opportunity, I'd like somebody to show that something I came up with independently was invented before. It's so simple, I'm surprised that I haven't heard of it, but maybe one of you have. Namely, if you want to maintain a structure in order by the number of times an element occurs, in the worst case, you have to swap every two times. But, if you are willing to tolerate the elements being out of order by some small percentage of the overall count, then you only need swaps in the log of the number of arrivals (the log base depends on the percentage). You can prove this with the Master theorem. I did this in ~2005.

John the Statistician
A: 

I re-created PHP's word_wrap here. Mine's grammatically better.

Ross
+4  A: 

Enigma machine (substitution, altering & rotating cipher).

kokos
Me too. My 2nd semester at college. And I was convinced this was an unbreakable cipher and I would win a Nobel prize, become a billionaire an marry a supermodel.
sal
@sal because that's exactly what hapened to Turing? ;-)
Steven A. Lowe
A: 

1992: Auto-rebalancing AVL trees, where the re-balance is done on the tail of the recursive insert.

In a university assignment.

Tim Williscroft
+1  A: 

I got a surprise the day before I was scheduled to present my findings on how to combine multiple source of soft bit decisions. I asked a colleague to review my presentation. He informed me that I had reinvented Maximal Ratio Combining.

Mark Borgerding
A: 

Recursive descent parsing supporting left recursion.

DrPizza
A: 
Pascal
You came up with the Ant Colony optimization on your own? impressive!
Amro
A: 

Binary searches.

I had been working on a C program to organize card game tournaments and wanted it to be really fast -- enough so that a large number of players could be handled on as little as a 486. When I started to realize how long looking up players was going to take, I tried to come up with a better solution than repeated linear searches and wound up with a binary search.

A: 

Not sure it really qualifies as an algorithm, but I "Invented" the technique of disabling a button on an HTML form with javascript so that the user doesn't inadvertently post the form twice.

Joel Martinez
+12  A: 

I invented bubble sort in 1993. The year prior I had attended a computer camp (for pre-high school kids) and studied BASIC and Pascal. '93s summer computer camp we graduated up to C and had to sort an array of numbers. I, along with several kids in the group, arrived at the worlds most common bad implementation of sorting.

Our instructor then explained Big-Oh notation (and I believe the implementation of quick-sort) and the rest, as they say, is history!

Matt Rogish
That reminds me, I 'invented' insertion sort. They showed us bubble sort instead, for some reason.
Darius Bacon
+1  A: 

Sequential Quadratic Programming with constraints. I "invented" a way to turn a nonlinear optimization problem with constraints into a sequence of linear (or in this case, quadratic) problems. I was not amused when I discovered it had been around for decades! (in my defense, optimization was not my field).

+5  A: 

Monads.

Apocalisp
+9  A: 

Bresenham's line algorithm.

I wanted to draw lines with dashes or colors that vary along the length in GWBasic, but it had no facility for these, so I worked out how to generate a line very similar to Bresenham's method - no gaps, and a single width of pixels for a line of any angle.

I was very proud of myself, but my parents and siblings just didn't understand how cool it was.

Then I discovered the real Bresenham years later, and the awesome optimizations for linear memory implementations of it. It didn't dim my happiness - I was very young at the time and there was no such thing as the Internet back then.

Algorithms are so cool...

Adam Davis
That's one of my all-time favorites though I can't claim to being a co-inventor for this one. I also used it with GWBasic though I think I wrote an assembly language version because IIRC GWBasic didn't support "Super VGA" screen resolutions.
C. Dragon 76
I did a similar thing back when I was using turboc with the bgi.
graham.reeds
+1  A: 

Whilst it isn't really an algorithm, I did completely code a lolcat compiler/translator in Python, before actually googling it and finding out there were already a couple existing.

And I was so proud of myself...

joshhunt
A: 

I guess I must have "invented" pretty much every array function in PHP :D And maybe some of the string functions too (but who hasn't, in any language ?)

Since library functions written in C seemed not good enough for me, I had to rewrite them in pure PHP (performance is for sissies ;)

Then I learned to check the docs at php.net more often...

Ced-le-pingouin
+2  A: 

@Ross

Amusingly enough, I wrote the original version of the word_wrap function in PHP, before it became part of the core PHP function set.

It was originally written because I needed to be able to create quoted text areas for an online messaging system.

Extra amusing - It's listed as an alternative in the comments to PHP's word_wrap.

Dominic Eidson
+4  A: 
Hafthor
@Hafthor, what does that last thing have to do with the question. You hold the patent to it so how was it invented before hand?
Simucal
Clearly you are not familiar with our patent system. ;)
Hafthor
I think selection sort is far more "inherent" than bubble.
st0le
A: 

Anagram Trees - apparrently also known as an 'addagram'.

Cryptographically secure IOUs - of course, there is a lot of research in this area.

Nick Johnson
A: 

When I was in grad school I "invented" the composite design pattern. I was coding a graphics editor in Java 1.0, with the requirement of being able to group multiple shapes into a single shape. I came up with what I thought was the clever idea of writing a class that implemented the Shape interface but contained a collection of Shape instances. I almost injured myself while patting myself on the back.

Sometime in the next year, I was introduced to the Gang of Four Design Patterns book. That burst my bubble.

Scott Bale
+73  A: 

When I was in 2nd grade, I figured out that if you have a square, like 9 = 3^2... to get to the next square (4^2), you simply add 3 and 4.

I generalized it, so if you had any number squared, you could get the next number squared by adding the first number and the next to the first one squared.

So, I kind of invented algebra.

xn+12 = xn2 + xn + xn+1
Bill James
Me too! Only I went with a geometric explanation: you have a square (say 4x4), you add one row to it (making it a 5x4 rectangle), and then you add a column to finish the square (5x5).
Michael Myers
I "invented" that one much later (sometime after having taken Calculus). So I was kind of fascinated that in the discrete/integer domain, the derivative of x^2 is 2x + 1. In the traditional real number domain, the + 1 "approaches" zero and becomes just 2x.
C. Dragon 76
I was a fan of another, similar shortcut when I was in elementary school: if you're computing the square of X and X is near a multiple of 50 (e.g. x = 93) you can take 100^2 - (100*2*7) + 7^2 to easily compute 8649 in your head. I was proud of proving this when I learned about algebra!
mquander
lol, seems much obvious now...(a+b)^2 = a^2 + 2ab + b^2... but when I was 10 I thought I discovered something new XD
kentaromiura
You guys must have been a big hit with the girls.
Ishmael
Rosdi
@Ishmael, just the girls who were as interesting to talk to as they were biologically bound to have vaginas and breasts.
eyelidlessness
@mmyers: I came up with something similar in grade school. Only I noticed that the difference between n^2 and (n+1)^2 represented the series of odd integers: 1, 3, 5, 7 ... 1^2=1, 2^2=4, 3^2=9, 4^2=16 ... 1 + 3 = 4, 4 + 5 = 9, 9 + 7 = 16, etc.
Robusto
+1  A: 

Huffman Coding, in 6502 assembly, while trying to improve an existing compression routine to squeeze an extra "cracked" Commodore 64 game onto a floppy disk, in 1991.

Carry Save Adder

finnw
+1  A: 

I reinvented Insertion sort as a kid when sorting our-of-order volumes of the encyclopedia at school.

Paul Reiners
+12  A: 

Not quite an algorithm.. but way back in elementary school I saw an episode of Bill Nye the Science Guy where Bill said something along the lines of "..but it would take the force of exploding stars to rearrange matter". I immediately thought: "Man.. What if a giant explosion created all the matter in the universe out of something else?" I thought I was on to something!

Yeah but what exploded and what else was all the matter in the universe created out of?
eyelidlessness
A: 

Canny (sp?) Line Detection in images (like photographs).

A: 

I happily invented the "One Time Pad".

My idea was that if the weakness of encryption comes from repeatedly applying the same key (albeit with mathematical manipulations) to a large data file, you could get around this by just having a key of pure entropy (or as close to it as you have on hand :) that is bigger than the data you wish to encrypt. My other idea was that if the key was totally random your algorithm could be as simple as adding for encrypting and subtracting for decrypting. I also predicted this would be unbreakable.

I found out later that this is a one time pad, and it is indeed unbreakable.

(I also invented steam engines as a kid, and a space shuttle with 3 booster rockets because, you know, its 1 better!)

dicroce
+8  A: 

√i - i√i = √2

(not an algorithm, I know, but I still thought it was the coolest thing when I discovered in in 7th grade algebra... until I got to complex analysis in college. Actually, I still think it's cool, but I'm a math geek)

rampion
This is awesome! Love it when non-standard numbers combine to a real number, like the whole e^(iPi) thing
Bill James
+1  A: 

I "invented" Bubble Sort, floor(), ceil(), and sleep() in C.

computergeek6
Let me guess, you invented sleep during school?
poke
A: 

I "invented" linked lists as a junior in high school, armed only with the knowledge of pointers and classes (but not inheritance yet).

Jacob
+6  A: 

Like many others, I invented bubble sort, binary search, etc in high school.

For a more interesting example, I recently "invented" an algorithm for approximating Fourier integrals, based on applying a specific sequence transformation to partial integrals. Turned out, upon consulting specialized literature, that someone already thought of this in the 1960s.

As a rule of thumb, if you come with a brilliant new algorithm, someone already thought of it in the 1960s.

fredrikj
Actually, if you come with a brilliant new algorithm, Gauss already thought of it. cf. Fast Fourier Transform, for example.
Jason
+1, That last sentence is going in my sig on forums.
Joe D
A: 

When I first started tinkering with assembly language, I figured out how to make a dynamically allocated list by storing a pointer to the next piece of memory in each allocated block. It wasn't till a few years later when I took a data structures class that I learned that my "invention" was called a linked list.

Ferruccio
+4  A: 

How about... ARRAYS!

I was 7 or 8, fiddling with BASIC, trying to make a prime number generator. I invented the exact concept of an array, tried in vain to figure out how it was done in BASIC (anyone used PHP's variable variables? I tried that kind of thing but it didn't work) and in the end used sequential files to simulate arrays. To read a certain element I'd open the file, read n lines, and there was my value.

At exactly the same time I had invented primality testing by trial division! Hehe. I even thought up the "only test primes, and only up to the square root of n" optimisation.

Needless to say I discovered BASIC's arrays a few months later. And as a matter of fact, I'm man enough to admit that I still use BASIC.

Artelius
-1, still using BASIC past the age of 7 or 8
Kevin Panko
People who love to hate BASIC are small-minded. Sure it's a haphazard, inconsistent thing from another era. That's what makes it such a pleasure. There's so much history and marvel and carelessness wrapped up in it.
Artelius
"it's a haphazard, inconsistent thing" It's like the PHP of the 70s and 80s!
Matthew Crumley
A: 

I once wrote a recursive descent parser, without knowing the concept beforehand.

Among other - then unnamed to me - Design Patterns I invented the Visitor Pattern and the Facade Pattern (who did not?).

pi
A: 

Lazy synchronization with asynchronous method calls, i.e. functional programming.

Pyrolistical
+19  A: 

I was about ten and playing with the Basic interpreter on my very own 386 workstation. QBASIC actually, was a much nicer editor. Anyway, I knew counters and variables and GOTO, and needed a repeater structure, and I had constructed a bit of code that nicely incremented and checked a value, and jumped out of the loop if it exceeded the amount.

It wasnt until two years later I got a book on programming in C and I discovered I had invented For and While loops!!

Karl
did you know that qbasic has a for/next, do/loop, while/wend?
Matthew Whited
I did not at the time, it was non-obvious that such keywords existed or how to use them. I had If and Goto, and managed to do a lot of work with them.
Karl
This is why i hate GOTO.
Behrooz
A: 

Bubble sort :)

Jon DellOro
+10  A: 

I can honestly claim I never "invented" bubble sort.

Nope, I went and "invented" bucket sort instead.

I'm so ashamed. :)

J.T. Hurley
Argh! I totally forgot that one when I posted my answer. I once invented bucket sort too, when a friend 'tried me out' with an interview question she'd been given at a certain large search company. I was so proud, until she told me to check out 'bucket sort' on Wikipedia...
Cowan
I "invented" a linear time sort that almost always lost to bubble sort.
Joshua
Just to mention that bucket sort is a kick-ass algorithm that gets a lot of bad rap in algorithms class (presumably because it “cheats” and has a more complicated asymptotic runtime, making it seem as though it breaks the magical nlogn barrier) but is really the best solution in many real-world situations (well, in combination, e.g. as radix sort).
Konrad Rudolph
A: 

When I was in 'upper school' (high school if you like), I was writing a program in Fortran IV (with BASIC as the prior language) and I discovered that I had created a looping construct that was different from a DO loop, but not supported by Fortran directly. It was actually a WHILE loop (supported in Fortran 77, of course). I discovered that what I'd invented was a WHILE loop a year or two later, when I was reading more books about programming. (That program was also unrolling tail recursion with an array representation, but that took me still longer to realize.)

Jonathan Leffler
+5  A: 

Like everyone else who was primarily self-taught, most common data structures: lists, trees, queues, etc. I didn't know what they were called until college, several years later.

One day the trie just popped into my head, for no apparent reason - it didn't even solve the problem I was working on.

The major object-oriented elements (objects, messages, inheritance) were invented/derived out of necessity while working on a 2D CAD application (in assembly language).

Steven A. Lowe
I came up with tries quite naturally while trying to figure out a way to index a lot of plain text for full text searching. First I stored a tree in which each node had an array of characters, then I replaced the array with a binary search tree to cut down the storage requirement. It never felt like inventing anything though - just plugging together simple ideas where they made sense.
Daniel Earwicker
A: 

I couldn't believe it when I researched IoC that I had 'invented' it 6 months earlier for an object engine in our local metadata repository.

johnc
Yep, I invented IoC in 1995. But (as with a lot of these things) there isn't much to invent; it's just well-designed loosely coupled components, with the specifics of the coupling decided on elsewhere. Hardly deserves a fancy name if you ask me.
Daniel Earwicker
+3  A: 

I invented a way of turning infix to postfix using just an array in 1989. For many years I though I had reinvented something else, but lately I'm not so sure. All I can find when I google or run into how-to articles is Dijkstras shunting yard, which uses a stack.

So I have decided to publish it tonight on my blog. If anybody can point out that it is just a reinvention I'll be a bit disappointed and you can share that with me.

Guge
That's nice if you're low on memory, but it's O(n^2) in the length of the array...
Thomas
I think it's closer to O(n^2)/2.
Guge
+2  A: 

I have a few.

  • Most recently, I was the only programmer on a medium-sized CRUD-type application that incidentally did have some meaningful logic as well. So for the first time in my career (I was still in college at the time) I was in total charge of UI, domain layer, and the DB.

    I had this great idea that in order to give data to the UI, I should "flatten" my domain objects into what amounted to a big struct. This way, the UI could focus on mapping field to UI control and have as little non-UI logic as possible. Then I found out that these were actually Data Transfer Objects.

  • I also hand-coded my own strategy to save domain objects into a relational database. Imagine my surprise when I found out that this was called the object-relational impedance mismatch, and there was an entire sub-industry devoted to the problem.

  • Even earlier in college I had to write a smaller tool that would grab spec data from a bunch of servers on our network, and then dump out a suggested plan for how to make sure each server had the minimum amount of some resource, like RAM, in the smallest amount of swaps. It was really ugly procedural soup because I wrote it in VBA in an MS Access DB (they forced me to, don't hate me).

    I ended up with a heuristic algorithm that was correct most of the time, and it was a feeble attempt at a dynamic programming algorithm, which I wouldn't learn about until three years later in grad school.

moffdub
+2  A: 

Fermat's Little Theorem. I only discovered the binary case, so thank goodness Fermat realized it worked with other bases.

C. Dragon 76
A: 

I was pleasantly surprised to find out some years later that I had independently invented a technique for lossless compression.

I had written a program (Turbo Pascal on a Tandy 1000) for drawing images (basically a keyboard-only version of paint) and was concerned with how much space the saved images were taking up, leading me to a basic lossless compression algorithm that drastically reduced the size of the image files.

J c
+18  A: 

When I was just a kid I "discovered" that when you multiply a number XY (less than 100) by 11 you just have to put to sum of X+Y in the center, and X, Y in the extrema to get the result (no more calculator).

11*45 = 4 (4+5) 5 = 495
95 * 11 != 9 (9+5) 5 = 9145 ;) That works only if their sum is less than 10.
Technofreak
If the sum is more than 10, you carry over to next digit. `95 * 11 = 9 (9+5) 5 = 9 (14) 5 = (9+1) (4) 5 = 1045`.
abhin4v
+2  A: 

When I was second grade middle school, our teacher gave us a homework: Make an alghorithm in pseudo code that prints the first n Fibonacci numbers. So I made my own iterative procedure:

a = 0  ;
b = 1  ;
n = 10 ;
i = 0  ;
while ( i < n ) {
  b = b + a ;
  a = a + b ;
  println b ;
  i = i + 1 ;
  println a ;
  i = i + 1 ;
}

Much later I learnt that this was one of the most used examples for recursive alghoritms.

Azder
What kind of school did you go to where you got to write pseudocode in middle school? Lucky.
jprete
And your own iterative procedure is much much faster than the recursive solutions.
Joshua
Well, the Haskell recursive solution is pretty fast...
Steven Huwig
I went to ordinary High School, only our class was slightly math and natural sciences oriented.
Azder
A: 

Hyper operators when I was 13. And some cryptographical and compression algorithms (RLE, Vigenère) ;-)

I actually invented another a little compression algorithm - I don't know 'til today whether it already exists. It's based on eliminating the leading 0-bits in the binary representation of source bits which have been ordered according to their probability.

And Cantor's pairing function.

Dario
A: 

Merge sort, radix sort, bucket sort, see in wiki: sorting algorithms.

egaga
A: 

Recently we designed and built a set of PL/SQL packages on an Oracle database, for use as an interface to the database by multiple front ends. Normally things like data validation and error reporting might be implemented in procedural code in the form, but in this case we needed the form to get all its information about each column including whether it was mandatory, and if it failed any validation checks, from the database.

We pretty much solved it with what we called "instructions", which encompassed a number of different things that the database packages could "tell" the form, e.g. "item X is mandatory", "item Y has error ZZZ", "hide item M", "make item N disabled", etc.

After we'd implemented it we found we'd just reinvented the Command pattern.

Jeffrey Kemp
A: 

Not sure if you could call it an "algorithm", but I came up with a generic form validation mechanism for jquery that was VERY similar to the 'validate' plugin.

Also, in high school I wrote a program on my TI-89 that was the Sieve of Eratosthenes, all on my own. Of course, what I didn't realize was that there was already a built in method for testing primality.

TM
+5  A: 

During an interview, I came up with the Knuth shuffle (or Fisher-Yates Shuffle, as it is also known). I was quite proud after I looked it up later, as I'd never really considered the problem of randomizing a list before (sorting, on the other hand...)

Jimmy
Voted up for the fact that you did it during an interview... unless you got the job, you'll never know if they thought you were a genius or if they were laughing at you the whole time. Ouch.
Cowan
I remember being told about this in uni, by a fellow student, after spending ages trying to come up with a good shuffling algorithm. It surprised me how simple it was.
Matt Ellen
+1  A: 

Got in an argument with a professor (I can TOO have pointers to functions!), ended up with a propensity for using sparse jump tables, which I didn't hear of until a few years later.

Kim Reece
It's amazing the arguments you can have with professors of CS. I once met one who was adamant that code and data are totally separate things; apparently had no idea about LISP, Von Neumann architecture, shared libraries (DLL), interpreters, compilers, self-modifying programs, `eval`, etc.
Daniel Earwicker
+1  A: 

Ugh. One embarrassing project of mine was porting some code written for a processor with floating-point math to one without. Fixed point was out of the question, so I "invented" what I thought was a novel approach: a structure containing a set number of bits for the value and another set of bits for the magnitude of the number. And then I wrote functions for performing mathematical operations on them. Yep, I basically duplicated the floating point number (and probably not that well). I should have taken computer science in school.

Jacob
I think that's a great story! That was a great solution, especially considering your limited background at the time.
Dinah
A: 

I happened to partially re-invent the quicksort during my masters. I was a nerd not attending Data structure lectures. I was always believing there must exists one more way to sort the numbers. I spent half-a-night designing my algo. for sorting numbers and next day my colllegue told me it's quicksort and it's already there. poor me! :(

this. __curious_geek
+43  A: 

Once, as I was walking home from the train, I thought to myself "wow, Linked Lists are totally awesome, except for the whole O(n) lookup thing, which makes them useless for a great many purposes. If only there was a way to quickly find things in a linked list and still have the very-fast insertion/removal..."

By the time I got home (almost exactly 20 minutes), I had completely specified every possible nuance of a truly incredible algorithm which made linked list lookups extremely efficient while still largely keeping their advantages. I mean, this this was flawless, it was going to revolutionise the world of data structures and probably make me famous.

I don't know what terms I put into Google that night which revealed the existence of the Skip List, but let me assure you I was crushed.

On the plus side, my algorithms were basically identical to Bill Pugh's, so at least I reinvented it properly. Small mercies.

Cowan
It's always disappointing to realize you arrived at an idea second (even if it was only because you were born after the original inventor), but you should at least take solace in the fact that great minds think alike. The fact that you had the intellectual capacity and drive to come up with the idea completely independently of the original inventor means a lot.
Lèse majesté
+2  A: 

When I was in 9th grade and into number theory I went to sleep really tired and started thinking about an algorithm to find is a number is prime or not, I doing some head calculations and then waking up a few hours later screaming "I found it!".

Turns up I had discovered the formula 2^p - 2 / p == 0 when p is prime, also known as Chinese Hypothesis and a derivative from one of the Fermat's formulas - I found out about it two weeks later and I also found that it fails for pseudo primes (numbers such as 341) - it was a really bad double deception.

Since then I've never done any more work on number theory again.

Alix Axel
A: 

The ones that have stuck with me:

  • LR parsing
  • Spectral Methods (a type of numerical solver)
  • Marching Cubes Algorithm (I was especially indignant about this, because despite it being relatively obvious -- to the point that a sophomore in college with no relevant training beyond an intro CS course and a good knowledge of differential geometry could come up with it -- GE managed to patent it, which prevented its use in the project for which I was a research assistant. Patent expired in 2005, thank god)
Stephen Canon
+10  A: 

I knew a girl who at a young age wasn't paying attention and was generally being a hyperactive kid. At one point, she swung a full cup around a vertical circle and nothing spilled out. She thought she'd broken gravity or something. She tried it again and again and it worked. She showed her dad who had an expression of "yeah... and?" She couldn't conceive that other people already knew.

When she got old enough to encounter this taught in the classroom, she was quietly really proud of herself, knowing she'd found it all on her own and before any of her friends knew what it was.

Dinah
Cute story. Hope her name was Dinah.
Jeff Meatball Yang
@Jeff Meatball Yang: nope, just some girl I knew back a long while back. I don't even remember her name but the way she told her story stuck with me all these years.
Dinah
Having "encountered" something first doesn't make one precocious. Now, if she had understood the principle of the centrifugal force, before being taught it in a classroom, then that would have been impressive.
Lèse majesté
A: 

I invented display lists in 1980 when I was in 8th grade for games that I was writing.

I invented non-recursive flood fill in 1983 when I was a junior in high school as part of a graphics package I was writing.

I invented divide and conquer in 1982 while I was trying to write a line drawing routine that only used addition and shifting (it worked--looked like crap--but it needed fixed point arithmetic).

plinth
+1  A: 

As a kid I "invented" sine and cosine in order to figure our how to draw a circle point by point using QBasic.

Larsenal
+28  A: 

I "invented" the infinite loop because of never updating the termination condition.

bool crush = "Meg";
bool girlfriend = "";
int daysAlone = 1;
while( crush != girlfriend )
{
  Output( "Days alone: " + daysAlone );
  SeeGirl(crush);
  TellSelf("Try to talk to her again tomorrow");
  daysAlone++;
}
Greg
bool girlfriend = ""; .... well, there's your problem!
Mike Robinson
There's also the problem that if you get over your crush (crush == ""), the loop will exit, even though daysAlone should still increment.
expedient
You can take a crack at rewriting it you want ;)
Greg
that is funny. and I needed a good chuckle just now.
alesplin
It is funny, but it's also sad that none of you thought to suggest refactoring. Replace that call to TellSelf(it's deprecated, you know), with the much more effective ApproachGirl(). Really. It's the recommended practice. I think Josh Bloch has a tip for it: "Prefer Approaching Over Watching From A Distance".
CPerkins
I'm sure that was inventing the exception pertaining to type mismatch given that "Meg" and "" are not valid bools.
ridecar2
Anybody else notice that you'll eventually be a negative number of `daysAlone`?
Joe D
+14  A: 

Another grade school one: In fifth grade my student teacher in math class asked if anyone knew how to find the area of a triangle. I thought, hey, a triangle's kind of like half a rectangle. So I raised my hand and said, "Maybe multiply height times width and then just divide by two?" I must say she was quite shocked, and I felt very proud. In retrospect that's probably not all that clever for fifth grade...

Dan Tao
No, it's probably pretty good for anyone.
Ian Boyd
A: 

Spent a few days writing an algorithm to shuffle Arrays when I found several, more concisely written methods already in existence!

samfu_1
A: 

I invented bucket sort (w/o realizing what pigeonhole principle is. I thought quicksort was slow for use in a project of mine and since I was using only integers I could do so much better) and divide-and-conquer form of convex hull algorithm (that works with only integer coordinates) just from sheer repetitive doodling of convex hulls around points :) I just have to find out the first and last points of each row, get the top left most and bottom right most point, join a line between them, then repeatedly add a point in between them to expand the convex hull in a divide-and-conquer manner. Eventually a convex hull is formed.

Upon learning raycasting algorithm (the one generally thought to be used in Wolfenstein), I invented one that instead of using a matrix of walls (zero value = non-wall, non-zero value = wall), it uses an array of vectors (each vector represents a point, and a wall is made from two such points).

jian2587
+1  A: 

Stopping short.

expedient
A: 

Snapshot isolation

I wrote an in-memory database which can handle multiple concurrent transactions (for a hobby project). When thinking about how to isolate the transactions, I decided to use a revision number system similar to Subversion. I realized that the resulting isolation level was not serializable, but anyways quite good. Afterwards I did some digging and found out that I had implemented snapshot isolation and multiversion concurrency control.

Esko Luontola
A: 

When I first started to try to get my head around the new weirdness before me that was OOP, I "invented" a way of doing stuff which was essentially the strategy pattern. I only knew of encapsulation and inheritance at the time. The descriptions of polymorphism that I found were totally incomprehensible to me and it would also be almost a year before I discovered design patterns. I thought I'd really invented something ground-breaking!

Dinah
+5  A: 
Dave DeLong
A: 

I "invented" binary search when I was still a teenager and had just started out with the programming language C. That was about two years before I got internet access at home.

Although Internet took away the 'magic' I associate with learning by 'trial and error' and having little access to relevant literature, I can't say I miss those times either. I envy the youth nowadays.

Mads Elvheim
+10  A: 

I invented modern supercomputing/distributed computing. I was only about five or six years old and don't remember ever thinking of it (thankfully Dad still has the paper somewhere).

When in Church I'd doodle on paper, and one day I drew an interesting diagram. Basically there were lots of boxes filled with 1's and 0's that encircled a central, larger, box (computer). When Dad leaned over to ask me what I'd drawn, I explained that the central computer was the boss of all the others. The central computer would delegate pieces of the problem to the other computers, and then assemble the final answer.

The Wicked Flea
lol at "boss of all the others". great answer, btw
Michael Easter
A: 

I was working with QBASIC and was too dumb to know what a SUB was.

So I figured out structured programming to deal with my spaghetti code.

Then, later, I started figuring out how to actually pass parameters internally.

Paul Nathan
+1  A: 

I invented a way of picking a random line from a file in a single pass through the file. The comments to this answer in StackOverflow show that it was a known technique long before I figured out my answer.

This is just the latest example of a long history of figuring stuff out. It was a much more valuable skill before you could look up anything you want on the internet.

Mark Ransom
A: 

Once someone had asked me a puzzle question: To write a program to add two numbers without using arithmetic operators. For this I made an algorithm to add numbers using bit-wise operators, and was quite happy with what I did. Because until then I had never known of what full-adder was. Later when I studied about full adder and its implementation in Digital Electronics, I realized that it was exactly what I had written code for :)

Technowise
A: 

Not an algorithm, but I invented high-order-functions (specifically map).

I also invented versioned FUSE (file system in user space) in a shamefully ugly way (stat() everywhere).

fsanches
A: 

I "invented" switch/case. I begun my programming career with a BASIC that did not have switch/case and turned to 68k assembly on the amiga. I didn't like to use multiple conditionals for a set of values and "invented" switch/case via jump lists.

A little later I connected the amiga and a PC via parallel port with a special selfmade cable and wrote a program for each machine (both in assembly!) for sending files back and forth. I "invented" all kinds of error corrections, multilevel handshakes and discovered the "Two Army Problem". I thought I must be a genius. What a disappointment when I learnt all that a couple of years later in college as pretty basic stuff...

EricSchaefer
+5  A: 

Not exactly an algorithm, but I "invented" AJAX back in the late 90's to support dynamically loading branches of a navigation tree without a full page refresh. It was some pretty hack-y code that used JS to load data into a hidden I-Frame then read it out into the parent page and manipulate the DOM.

JohnFx
I did that too.
erikkallen
A: 

XOR drawing of a cursor so as to avoid a need to redraw the screen.

Elsewhere in the same program I also developed the other technique for avoiding a redraw--copying off the block containing the cursor.

How were patents ever granted for such things??

Loren Pechtel
This was common with ZX Spectrum in 1981When did you invented it?
UVL
@UVL: Mid 80's, I don't recall exactly when. I learned nothing about graphics in school, I hit the need for a cursor in my first job.
Loren Pechtel
A: 

Sqaures of 5

I think i came up with this when i was in 9th grade or something. I was just playing with numbers and doing some divisibility test when i discovered this peculiar trend in squares of numbers ending with 5.

Let X be the number ending with 5 and let Y be the number before 5. For example if X=25 Y=2; X=625 , Y=62

Then if X' is the square of X. Then Y' = Y(Y+1) and the number is {Y(Y+1)}25

For example 15^2 = {1(1+1)}25=225 15^2 = {1(1+1)}25=225 25^2 = {2(2+1)}25=625 35^2 = {3(3+1)}25=1225 45^2 = {4(4+1)}25=2025 55^2 = {5(5+1)}25=3025 65^2 = {6(6+1)}25=4225

bakore
A: 

I have a lot of ideas for an OS I want to make someday (but may never have the expertise or time to), and one of my best ideas was for a memory management algorithm. Basically I had (unknowingly) reinvented Doug Lea's algorithm, with the one exception that, because of the way my idea had developed, I was still thinking you'd want to use a hash table to store the next-bin information, when in reality you don't need one at all.

I've also invented a few sorting routines, which may or may not be useful (or even practical), and some of them are variations or crosses between other, existing sorting algorithms. http://inhahe.blogspot.com/search?q=sorting

I also invented a method for finding primes (when i was young) but it's not as good as the sieve of whoever and it's probably obvious anyway. (for every odd number, try to divide by each prime already found in between 3 and sqrt(n). if none divides, add this number to the list of found primes.)

oh, just recently i came up with a way to use SQL to efficiently find substrings within a document. i have no idea if this method is already known.. (i can only post one hyperlink, so i'll just tell you that the SQL algorithm is curretnly on the front page of the aforementioned blog)

here's a Python one-liner I made once for returning all permutations of a string, but i don't know if the basic algorithm behind this has already been done.. i would guess it has.

perms = lambda a: a[1:] and [c+r for i, c in enumerate(a) for r in perms(a[:i]+a[i+1:])] or a

inhahe
A: 

It was in High School and I was working on the shortest-path problem, when I came up with the flood-fill algorithm. It wasn't a recursive or queue-based like the actual algorithm but an iterative version of it instead.

There was no Wikipedia back then, or I wouldn't have spent those numerous days and infinite revisions in coming up with a solution.

Anurag
A: 

I was very proud to invent a search tree for storing sequences. I then showed it to my tutor and he said "oh, that's a trie" (aka digital search tree, retrieval tree, prefix tree). I'm not sure if I was disappointed or not...

Also, Sir Clive Sinclair reportedly invented binary.

Joe
A: 
  • I didn't invent Bubble sort.
  • I invented a non-recursive version of Merge sort(10% equal to recursive version;I'm looking for a name).
Behrooz
A: 

I "invented" the iPhone's scrolling method. A few years before it came out, I had drawn up a complete design for a touch screen interface controlled by dragging content in the direction you wanted it to move.

Tmoc
+1  A: 

I "invented" Sorting Networks while trying to find ways of sorting that could be vectorized (with SIMD architectures). Unfortunately it turned out that Knuth, Batcher, et al, beat me to it by about 40 years or so. ;-)

Paul R
+2  A: 

In 1988 I did a high school science project that implemented parts of the "Sorting out Sorting" video. It was done in BASIC on a C64. Quick sort posed a challenge as C64 BASIC subroutines did not accept parameters, only the instruction pointer was saved on the stack.

I solved this problem by using an array as a stack to store the range of the left partition for later processing and "invented" tail recurssion removal to handle the right partition without an additional subroutine call.

I was devastated the following year in my first college CS course to learn that the technique had a name and it was invented well before I was born.

At least I won first place at the science fair.

ChrisH
+1  A: 

My friend and I once decided to "invent" a compression algorithm that eventually boiled down to an incomplete version of Huffman code.

Jordan
A: 
Roger Nelson
A: 

Abstract syntax trees.

Billy ONeal
A: 

I reinvented a few suffix array algorithms in the literature. Actually kind of surprised when I ran across them because I just thought that was the way everyone did it.

Chad Brewbaker
A: 

A thread pool. I was screwing around in a totally un-thread-safe environment and decided that I could put a function and it's arguments into a table, then call it from another thread when that thread wasn't busy. Now, it was hideous and non-functional, but when I saw the diagram for a real thread pool, I instantly recognized it.

DeadMG
A: 

Long back, when i had just started programming, a friend asked me if there was a way if we could calculate the square root of a number without using a library function.

Spent an evening, comming up with a brilliant algorithm that actually worked.

Next Semester, in Math class, they taught us the Bisection Method which was oddly similar to my ingenius algorithm. I was heartbroken. ='(

I never realized it could have been used for any function (not just sqrt)...

st0le
A: 

I have combined B-Tree and hashing to solve problem of

  1. representing hashtable on file system;
  2. solve problem of grooving hashtable so entire set must be rebuilt.
Dewfy
A: 

I was working on a mapping project using visual basic 6.0 when I was in grade 12. The project started just to display lists of businesses on a map. (I was actually inspired by shows like "24" at the beginning ). But long story short I started to wonder how computers would know how to find a path from point a to b. and using primitive tools available on vb 6 like lines I came up with an algorithm which is very similar to Dijkstra's path finding algorithm. my next movie inspired project will be called "Enhance -- Enhance..."

user1
A: 

In high school I was asked to do a program for my father's office's TRS-80 Model II. Basically I had to sort a lot of numbers and the algorithm I'd learned for sorting in school (bubble sort) was obviously woefully inadequate. I therefore "invented" the merge sort.

Imagine how crushed I was a few years later in university when it became clear that I'd been scooped on my "secret sort" by slightly under 40 years. :(

JUST MY correct OPINION
A: 

I thought I came up with a new sorting algorithm besides what was being taught in 2nd semester of my masters. I explained one of my friend this new sort algorithm that I came up with, in the end he told me it was quick-sort. he advised me I better start attending lectures regularly and not waste my time re-inventing the wheel, but I knew I actually did find the algorithm.

this. __curious_geek
Considering that the average programmer can't even understand quicksort when reading the algorithm, that's still an amazing accomplishment.
Windows programmer
Waitaminute. Your accomplishment was amazing the first time you posted it, but not the second time.
Windows programmer
rolled back the edit.
this. __curious_geek
I don't know what your edit was. But if you sort the answers by poster instead of date ... and omit the -u flag if you're using a *nix style sort command ...
Windows programmer
A: 

The first time I played with a calculator, I was eleven (Cuba 1981). At that time it was a rare great thing for me and I was fascinated. I calculated many times n^2 for two-digits n. I found out that:

[ab]^2 = [a^2][2ab][b^2] -> where a,b digits.

For example:

[34]^2 = [9][24][16] -> write 6 and carry over 1

= [9][25][6] -> write 5 and carry over 2

= [11][5][6] = 1156

I think that was the first time, when I experienced an Aha-effect and thought I had invented a formula.

Later on I learned algebra and realized that "my formula" was a special case:

(10a + b)^2 = 100a^2 + 10(2ab) + b^2

Jogusa
+1  A: 

In the 90s when I was doing game graphics programming on the Mac we needed to compress the size of our image.

I came up with a scheme that I didn't realize was very similar to BMP-RLE (run-length encoding), which I think was pretty commonly-used in Windows.

anroy
A: 

I was playing around with sorting and how to use threaded sorting, and I sort of reinvented quicksort in the process.

Maister
A: 

I "invented" recursion over 20 years ago in college as a way to solve the Towers of Hanoi problem. Unfortunately, the language we were using (Vax Basic) didn't support recursive calls so I could never get it to work properly.

I didn't learn the term or the concept of recursion until the next year :)

wcm
+1  A: 

When I was about 10, my father would make Sunday omelette in a square pan for the 7 of us. But it was too difficult to divide the omelette evenly into 7 so he divided into 8.

But wait! Who gets the last piece?

Divide it and distribute it of course! Same problem: it's too difficult to divide it into 7 so divide it into 8.

And in theory, you can continue dividing and distributing until your piece is the size of an atom and the omelette ends up evenly divided into 7.

From this I realised that 1/7 = 1/8 + 1/82 + 1/83 + 1/84 + ...

And I could easily generalise this to 1/(n-1) = 1/n + 1/n2 + 1/n3 + 1/n4 + ...

Adrian Pronk
A: 

I thought my XOR and bit rotating encryption algorithm was awesome until I read the introduction to Schneier's book. I'm not sure I would have kept my kid sister locked out either.

nonnb
A: 

When I was a young kid in kindergarten or there abouts, the teacher asked all us little students how high we could count on our fingers. I sat there for a while and figured out I could count to 2047. It took me years to realise I'd 'invented' binary.

JBirch
You have 11 fingers?!?
P Daddy
Apparently I invented some awesome compression algorithm too :/
JBirch
A: 

I "invented" Object-Relational Mapping (like hibernate) in the course of implementing my undergrad thesis. I was writing a web spider, based on the GNU wget source, and I was using a database to store my data already. When I found myself needing to conditionally escape from a 1000-line function 500-lines in, with lots of conditional allocations in between, I found it easier to just dump state to a database, and exit with a code that told the parent process to restart it with arguments instructing it to restore state from the database. It was an ugly hack, but it made me way more productive. Once I had invested in the code for that, I ended up using it in a bunch of other places for more sensible things as well.

Also in college, I "invented" the treap while implementing LRU virtual memory in a toy OS. It turned out it was only efficient for highly-randomized memory access patterns, since sequential access would turn large sections of the treap into high-overhead linked lists, but it was still neat that my intuition that such a data structure would have to have a unique representation turned out to be correct.

Since college I've found it a better use of my time to re-use proven algorithms than reinvent the wheel, but reinventing the wheel can be a good educational exercise.

Chris
A: 

When I was a kid, in the early 1980s, my first bigger program I wrote was a relational database. Written in BASIC. Granted, it was for small datasets as all the data had to fit in RAM, but it consisted of multiple tables (as arrays) and a connection between them (one field contained a number that referenced a row number in another table.

I had never before seen a database in my life.

But if you think of it: with data all in a similar structure, a table becomes a natural choice; and in an attempt to reduce redundancy, move identical data out to a different location and reference it from different points instead of blindly repeating it, it just comes naturally.

bart