Modifier keys

All keyboard keys should be modifier keys.

--

Mobile Email from a Cingular Wireless Customer http://www.cingular.com

Google redirect

Google has circumvented the guarantee that the address (of a search result) displayed in the status bar when hovering over a link is actually the link you go to when you click. I had dom.disable_window_status_change set to true, so I thought I was immune to Javascript tricks that modify the status bar.

On Firefox 1.5.0.8 [Win], the way to see the real address it to right-click and then hit the Escape key. I'm not sure how consistently they use the redirector. The magic seems to be some Javascript invoked on the "onmousedown" property of the <a> tag.

<a class=l href="http://www.pandora.com/" onmousedown="return rwt(this,'','','res','1',...)" and above function(){window.rwt = function(el,oi,cad,ct,cd,sg_url,sg) {var e = window.encodeURIComponent ? encodeURIComponent : escape;var oi_param="";var cad_param="";var p = el.href.split("#");var sig_url="";if (oi) oi_param="&oi="+e(oi);if (cad) cad_param="&cad="+e(cad); if (sg_url) sig_url="&usg="+sg_url; el.href="/url?sa=t" +oi_param+cad_param+"&ct=" +e(ct)+"&cd=" +e(cd)+"&url=" +e(p[0]).replace(/\+/g,"%2B")+ ...

English Huffman 0

Preorder tree traversal of a binary Huffman compression tree
of an English corpus, all words concatenated.

:::::gy:m:v::j:::+zqxkt::hre::::cus:n:d:bf::io:a::wpl

Internal nodes are denoted as colons. "Plus" is escape
character for further extension.

It is a zero-order compressor, utilizing no prediction from
previous letters.

context on data

contexts on data type declarations in Haskell are weird:
they don't get propagated as one might expect.

Mandelbrot deep zoom

Let's produce a very deep zoom of the Mandelbrot set, deep enough to require use of arbitrary precision arithmetic. How would one scale the colors? How many iterations should frames go? Should there be supersampling and antialiasing? How can the video be losslessly encoded efficiently? How can one keep the zoom aesthetically and artistically interesting? How can we avoid regions of extravagantly fine detail which will render to chaos at limited resolution? A human operator might be able to solve the previous two problems by trial and error, though an interactive system to produce deep zooms of the fractal will require considerably computational horsepower. Wouldn't it be nice to print it to IMAX and truly push the level detail that that film format can display?

Hiding letter frequencies with Huffman codes

To hide letter frequencies, one can Huffman code. Is there a standard Huffman code for English? A tree can be encoded in preorder. To hide double-letter frequencies, one can have a Huffman code for each letter predicting what the subsequent letter will be. Is there such a standard code? Next, bits can be grouped by (say) 5, and the key, one of the (2^5)! permutations is applied as a substitution cipher. How would one crack such encryption?

Topology

There is a sphere, then a torus. We can continue punching more and more "parallel" holes into the torus, but that is not too interesting. What, if any, is aesthetically the next interesting surface?

Trees and Kanji

How many unrooted trees are there with N nodes? How many such that every node has one or three neighbors? One three or four? The latter two can be the basis for a Kanji style character system -- all characters are topologically different. How does it change if we permit loops? It begins to look a lot like the Sprouts game.

Another way of producing a system is to lay down some points, say a 4x4 grid, and consider the power set of all possible connections between them.

Consider a large grid of points. Edges drawn (or not drawn) to a point's eight neighbors allow the encoding of 4 bits (not 8 because edges are undirected). Choose 4 out of 8 neighbors such that no two are 180 degress across from each other. A larger local neighborhood allows a denser encoding -- thus bitwise enformation may be encoded in a spiderweb-like diagram.

A sentence may be grammatically parsed into a tree. If we establish a mapping between trees and (say) bits, information may be steganographically encoded in the grammar of a sentence as opposed to the semantics of the words it contains.

Sudoku computation

Given two completed sudoku grids, can we quickly determine if one can be tranformed to the other by a sequence of sudoku-preserving operations? The sudoku group may be a basis for a Rubik's cube style puzzle.

If they are different (i.e., they cannot be transformed), by what algorithm can we minimize the difference between them? What is the maximum possible minimized difference (minimax)? What is the largest possible clique such that the pairwise distance between any two is that minimax distance?

Sudoku may be generalized to larger sizes. What is the largest size completed grid that has ever been produced? What is the computational complexity as the grid size gets larger? What is the computational complexity of producing two grids of maximum distance? The motivation for the previous question is "how can we produce a large number of qualitatively different grids?" -- given one grid, it is easy to perturb (or sudoku-preservingly transform) it to a different puzzle, but such constructions do not seem qualitatively very different.

We call a puzzle (not a completed grid) is minimal if no clue may be removed while preserving the uniqueness of the completed solution. Whereas producing a short proof of non-uniquess is straightforward (simply give two solutions), how can we produce a short proof of uniqueness? What is the largest puzzle that has been proved minimal?

Sudoku may generalized to more dimensions. Regular sudoku is almost four-dimensional, using only three of the six planes though each point. For a given number of dimensions, what is the minimum width greater than one of the hypercube? (Is the answer constantly 2?) Does 6D sudoku of width 3, a 3x3 collection of 9x9 puzzles with Choose(6,2)=15 constraints per point, exist? What is the complexity of producing completed and minimal grids of a given width and dimension?

567719161

567719161 is an interesting prime:

*Main> filter (is_primitive_root 567719161) [1..200]

[43,172,173,177,193,197,199]

43 is its only primitive root less than 172.

GPL as a way of control

Sun's release of Java with the GNU Public License got me thinking about it. It is subtly powerful to use the GPL.

When there is an active maintainer, (this is key), the GPL allows the maintainer, let's say, Sun, to stay "on top".

Let's say a competitor takes the Java source code, and modifies it to make it better. By the GPL, the competitor must release the changed source code under the GPL, and Sun's active maintainer can merge the improvements back into the original source.

Thus, Sun can always claim to have "the best" (assuming a linear measure of what is good) Java, unless a competitor decides to build the whole thing from scratch.

Maybe if the software distribution is partly being used as a name-recognition or other advertising program, the world will always keep going to (say) java.sun.com to download the best version of Java.

Eratosthenes sieve

There are many different ways to code Eratosthenes sieve, depending on how much memory you want to use. One method is to keep a list of primes found so far, and check the current number for divisibility by those primes up to the square root of current number. If the current number is prime, add it to the list of primes found so far.

The straightforward implementation uses a lot of memory: the list of primes found so far grows quite quickly. We observe that the list of primes have a "leading edge" and "trailing edge". At the leading edge are the most current prime found. At the trailing edge is the prime approximately at the square root of the current number. Only the primes between zero and the trailing edge are needed for the divisibility test. By storing only those primes, we can save N/log(N)-sqrt(N) memory, a tremendous savings.

However, it appears that when we discover a prime on the leading edge, we must forget it (to save memory) and somehow unforget it when it exists within the trailing edge. There is no free lunch: the solution is to run two parallel sieves, one up to the leading edge and the other up to the trailing edge. Sure, the trailing edge computation repeats something the leading edge already did (but forgot); this is the price we pay for memory savings. However, the trailing edge moves quite slowly -- it's that square root again -- so the amount of extra computation is quite small. Benchmarking reveals no time difference for sieving the first million primes.

It is a complex interleaving of leading edge and trailing edge sieving, but a lazy programming language like Haskell takes care of it automatically and painlessly. The trailing edge is a 0-ary function that is simply a list of "small" primes. The leading edge is a one-argument function, taking an input of the Unit type, i.e., "()" and returning a list of primes.

Predictive Text Input

Two questions regarding predictive text input for cell phones:

1. Given a prefix as a series of digits (thus letter ambiguity), what data structure and algorithm can efficiently, in both time and space complexity, return the completion in order of likelihood? (Assuming precalculated word frequency.) Is this problem already solved by current phones? Or are the words returned in some dumb order, like alphabetical?

2. Suppose we allow the letters of a word to be input in arbitrary order, that is, any permutation. What data structures and algorithm can quickly find the possible words? The motivation for "any permutation" stems from English suffixes. The predictor cannot disambiguate two words until it sees the suffix. By allowing any permutation, the user and type some letters of the prefix, then some letters of the suffix, then the rest of the word, hopefully reaching unambiguity with fewer keystrokes.

We need not allow the complete flexibility of arbitrary permutations. Instead, we may enforce that the initial letter be typed first, then a permutation corresponding to at most two "passes". As we follow the bouncing ball over the letters as they are typed, the ball moves backwards at most once. This corresponds to exactly "type the prefix, type the suffix, then type the middle letters exactly in order."

superlinear

Is there a name or notation for a the class of functions which grow slower than O(n^(1+eps)) for arbitarily small positive eps? So n*(log n) is in the class, and so is even n*((log n)^1000), but n^1.1 is not.

I am hoping this class covers all the interesting problems that scale well. However perhaps it still is too big, and O(n log n) is actually what we want.

Buying a computer

I wish, when I go to a website to choose a computer I want built for me, I am NOT first steered toward "Intel or AMD?", "What Form Factor", "What 'Series' or 'Line' or Do I want a 'Workstation' or 'Desktop'": such details are of lesser importance. First, let me choose by the criteria that are important to me, say "I want 8GB of RAM", and filter out the combinations that satisfy them.