22 Jul

DataGenetics – The Two Egg Problem

You are given two eggs, and access to a 100-storey building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst case for the number of drops it will take?)

There are no tricks, gotchas or other devious ruses. Don’t rat-hole with issues related to terminal velocity, potential energy or wind resistance. This is a math puzzle plain and simple.

Think about the puzzle for a few minutes, and then read on.

via DataGenetics – The Two Egg Problem. Like brain-teasers and computer science algorthims, read on indeed.

21 Feb

Mailinator(tm) Blog – How Mailinator compresses email by 90%

Given the title of this article, the first thing that should pop into your mind is probably – “well, use a compression algorithm – right?”.

Right! Well, yes, well, not exactly. Read on.

via Mailinator(tm) Blog – How Mailinator compresses email by 90%. A fun journey through algorithms to find a solution to getting some awesome compression stats.

15 Feb

Incubaid Research – Rediscovering the RSync Algorithm

Don’t walk the folder and ‘rsync’ each file you encounter. A small calculation will show you how bad it really is.

Suppose you have 20000 files, each 1KB. Suppose 1 rsync costs you about 0.1s (reading the file, sending over the signature, building the stream of updates, applying them). This costs you about 2000s or more than half an hour.

System administrators know better:they would not hesitate: “tar the tree, sync the tars, and untar the synced tar”.

Suppose each of the actions takes 5s (overestimating) you’re still synced in 15s.

via Incubaid Research – Rediscovering the RSync Algorithm. The right way to synch two remote file systems.

19 Aug

Ars Technica – Does not compute: court says only hard math is patentable

On Tuesday, the United States Court of Appeals for the Federal Circuit rejected a patent on a method of detecting credit card fraud. The result was unsurprising, but the court broke new ground with its reasoning. Citing the Supreme Court’s famous rulings against software patents from the 1970s, the court ruled that you can’t patent mental processes—even if they are carried out by a computer program.

Of course, all computer programs implement mathematical algorithms that could, in principle, be implemented with a pencil and paper. So is this the end of software patents? Unfortunately not. The court ruled that the no-patenting-math rule doesn’t apply if the math in question complicated enough that "as a practical matter, the use of a computer is required" to perform the calculations.

In order to justify this result, the court gives the most thorough defense of software patents that we’ve ever seen from the judiciary. We don’t think the line they draw—between ordinary math and math that requires a computer—makes much sense from either a legal or policy perspective. But the ruling at least signals that, for the first time in over a decade, the courts are thinking hard about how to apply the Supreme Court’s old software patent cases in the modern world. We’re hopeful that as the confusion in this week’s decision becomes more obvious, we’ll see further progress.

via Ars Technica – Does not compute: court says only hard math is patentable. It’s nice to see the courts limit patents somewhat, but the logic still has a real problem which is that practically speaking all math can be performed by a human being it may just either be tedious or time-consuming. The other question becomes raised if the math is complicated enough that a computer becomes required does that mean that the math itself is patentable (which the courts have said no math isn’t patentable)? The court seems to be trying to not rule against all software patents while acknowledging they are broken and need to be reformed.

The core of the legal problem with software patents is that they are just algorithms, logic and math, neither of which is patentable. Combine the two and describe a possible computer program and bam, that logic and math is now patentable. Ignoring all practical aspects of patents and software patents in particular, legally speaking software patents seem to me to be indefensible.

08 Mar

NYTimes.com – Software Progress Beats Moore’s Law

There are no such laws in software. But the White House advisory report cited research, including a study of progress over a 15-year span on a benchmark production-planning task. Over that time, the speed of completing the calculations improved by a factor of 43 million. Of the total, a factor of roughly 1,000 was attributable to faster processor speeds, according to the research by Martin Grotschel, a German scientist and mathematician. Yet a factor of 43,000 was due to improvements in the efficiency of software algorithms.

The rate of change in hardware captured by Moore’s Law, experts agree, is an extraordinary achievement. “But the ingenuity that computer scientists have put into algorithms have yielded performance improvements that make even the exponential gains of Moore’s Law look trivial,” said Edward Lazowska, a professor at the University of Washington.

The rapid pace of software progress, Mr. Lazowska added, is harder to measure in algorithms performing nonnumerical tasks. But he points to the progress of recent years in artificial intelligence fields like language understanding, speech recognition and computer vision as evidence that the story of the algorithm’s ascent holds true well beyond more easily quantified benchmark tests.

via NYTimes.com – Software Progress Beats Moore’s Law. Humans beat a law made up by humans.