Archive for the ‘Problems’ Category

How to Make the MacBook Pro Trackpad Less Jumpy

Thursday, April 21st, 2011

To right-click on the MacBook Pro, you put two fingers on the trackpad, then click. To scroll, you put two fingers on the trackpad and move up or down. In Visual Studio, the scrolling is extremely sensitive. When you try to right-click something, it often scrolls out from underneath the mouse. You end up right-clicking on something else entirely.

It seems that the problem is related to the horizontal motion rather than the vertical. If you reduce the number of lines that the mouse rocker moves left and right, the problem subsides. But the Mouse control panel applet won’t let you set this value to zero, so you can’t make it go away entirely.

Unless you hack the registry.

Download the attached file, examine it to make sure you understand what it does, then merge it into your registry. Reboot, and you will be able to right-click without the jumpiness.

Fibonacci solution

Sunday, November 8th, 2009

The question is how bad the recursive Fibonacci algorithm.

To calculate fib n, how many times does this method evaluate fib m, where m < n and both m and n >= 0.

The answer, as you might expect, is pretty bad.

Let’s look at the code again:

let rec fib n = 
  if n < 2 then 1 
  else fib (n-1) + fib (n-2)

When would fib n be called recursively? When fib (n+1) or fib (n+2) is called.

How many times would fib n be called? Count of fib n is count of fib (n+1) plus count of fib (n+2). Look familiar?

The count is the Fibonacci sequence in reverse.

Fibonacci inefficiency

Wednesday, November 4th, 2009

The Fibonacci function is often the first code that someone writes to learn a new functional language. Ironically, it's not always the best example of functional programming. Here's the Fibonacci function in F#:

let rec fib n =
  if n < 2 then 1
  else fib (n-1) + fib (n-2)

The code matches the mathematical definition, which is a strength of functional programming. However, it performs poorly unless the language has a feature called "memoization". F# does not have this feature.

Can you spot the difference between these two statements?

  • Each Fibonacci number is the sum of the prior two Fibonacci numbers.
  • To calculate Fibonacci of n, add Fibonacci of n-1 to Fibonacci of n-2.

They might seem to say the same thing, but in fact they are different. The first is a definition. The second is an algorithm.

Memoization is a memory/time tradeoff wherein the results of a function are stored in the expectation that the same function will be called with the same parameters. It helps us get across the gap between definition and algorithm.

Your homework
Nevertheless, F# does not have built-in memoization. So when you execute this Fibonacci function, it will execute recursively and redundantly. It will call fib for smaller numbers multiple times. Your homework is to find out how many times.

To calculate fib n, how many times does this method evaluate fib m, where m < n and both m and n >= 0.

Email or post your answers. Code is good, but proof is better.