# Pancakes Sorting Algorithm

There is a recent Slashdot article about pancake sorting. Somebody seem to have proved that optimal sorting of pancakes is NP-hard. If you look at the citations in the paper[arxiv], you’ll notice the mentioning of a paper by a certain “W. Gates”… the by the very same Bill Gates that everybody knows about.

I mentioned the problem to my father, and he, having a Ph.D. in mathematics came up with the operational gadgetry to perform comparison on any two pancakes, and declared the problem done. Later on he called me and told me to use this problem to attract a date to bed…. sigh…. Btw, his gadget for comparing two pancakes uses only two flips, mine used three. sigh….

So during our latter discussion, as he gave me this great idea, we also chance upon another interesting solution to the sorting problem, which has complexity
O(hλ)

where h is the height of the stack and λ condition number:the ratio of the largest pancake to the smallest pancake in the stack. How? Consider this algorithm:

* Flip the stack side ways so one side of all pancakes are flush
* Flip back upright.
* Cut from flush side λ cuts starting from the flush side towards the non-flush side. The widths of all cut is to be equal. That width can be any width smaller than the width of the smallest pancake. To achieve fewest cut we use the width of the smallest pancake.
* The pieces of pancakes will fall, producing a stack of pancakes including all sizes of original sizes with the largest at the bottom and the smallest at the top.

It takes a small bit of animation skill, which the blogger does not have, to illustrate it. Or if you can just imagine for me.  The rate at which object fall is roughly proportional to the height from which it falls. Since we are on earth, and there is a terminal velocity, the time it will take for all pieces of pancake to fall into place after each cut is height divided by terminal velocity–so linear in height of the stack. since there are λ cuts, the algorithm takes O(hλ) to run. The proof will be in the pudding after breakfast by induction:

Base case: We start with one pancake. Slice laser down at any width less than this pancake’s width.The pieces fall to no where and the pancake is now sorted.

Induction Hypothesis: suppose we can sort in n-1 pancakes using the above algorithm using λ laser slices,

Induction Step: W.L.O.G. add one pancake on top of the n-1 stack to create a stack of size n: Suppose the newly added pancake is smaller than the smallest pancake in the existing stack of size n-1. then the problem is solved: Slicing from it’s right side keeps it on top, and since new slicing width is same as lower stack’s slicing width, using this width to continue slicing will sort the stack of n-1 pancakes below as well.

Suppose the top nth pancake is not the smallest slice in the n-1 stack, let us use the smallest slice width from n-1 stack. By slicing the top pancake by that width creates a new pancake of the smallest size. The remaining portion of the top pancake in the n stack falls down and becomes part of a pancake in an n stack. Note that this operation has swapped the position of the lowest pancake in n-1 stack taking on the smallest size with the top pancake from n stack. Smallest pancake is on top, and we have a stack of n-1 unsorted pancakes. We can proceed using the current width and sort the remaining n-1 pancakes by I.H. in O((h-1)
λn) time. Adding the one cut from this step yields a total of O(hλn) running time.

Q.E.D!

Rule of physics challenge: okay, so the pancake may fall out of order from the torque exerted by gravity as it receives support from only one side. This issue may be mitigated if we set up λ lasers in λ time and perform all of the the slicing simultaneously, thus all pieces fall vertically, solving the torque problem.

Btw, if we do not know lambda, then clearly it takes O(n) time to compute it using the comparison gadget. in that case we have

O(hλ+2n)

running time. Linear time is still superior to  O(nlg(n)) using only pair-wise comparisons and swaps.

# J. Edgar

I am trying very hard to keep the image of Robert Ebert after his throat cancer surgery out of my head as I sit down and type my thoughts on this movie. I have been having a throat pain on and off for several months now and it is scaring the shit out of me. And why do I taste salt every time I drink water?

Anyway, another image that I have trouble keeping out of my head is Clint Eastwood, the director of this film, chewing the words: “He is a fucking cock sucker!!!”

The simple days… The really simple days when FBI originally started, in the first decade of the 20th century, things seem so simple then. The cars had simple engines… the liquor was hard, and the vegies all organic. And you could meet women in a club and they would offer to warm your bed for ya.

It makes me reflect on today, we are into second decade of the 21st century, at the end of which, will I look back and think, “wow… those were the simple days, they measured computer performance in peta-flops.”, and they didn’t even have to sign a pre-date to go on a date.

Anyway, snap back to reality, wow! I thought half way into this movie, this whole country is created not by white men, it was created by homosexual men! The film portrays J. Edgar Hoover, founding director of the FBI and Clyde Tolson, founding Associate director of the same TLA as homosexual couples. Various reports (wiki) quotes Clint Eastwood saying that he chose the script because it was not homosexual! But that was clearly a statement of the opposite, that the script did not focus on his homosexuality.

Was the script a PSA (public service announcement) for personal fitness? Because Clyde got a stroke for saying that he doesn’t like to exercise and Hoover dies hours after revealing that he wasn’t working out either to Clyde.

Because it wasn’t a promo piece for the FBI either. Though it did show that the underlines, the nameless agents do do good work that hoover takes credit for.

I don’t know why, but I have a fairly positive impression of the FBI, despite my deep seeded hatred for spying of all form be it organized or disorganized, effective or ineffective, and government sanctioned or not. So the movie is a slight understatement there for me too.

Perhaps it is for the best that the movie does not go into great detail about the things that we find lacking. The details of his extortions, the details of his relationship with Clyde, the details of all the political struggles that he won.

Btw, did Rober Ebert get throat cancer from HPV when he had oral sex with his black wife or through his promiscuous Hollywood lifestyle?… sorry, my most feared thoughts escape my skull some times…

The movie overall felt like it fits the demographics–most of the people in the audience, me excluded, were older couples same age as the dying Hoover. People from a simpler times… like when in a hundred years they’ll complain about lack of details: “oh man, that old geezer is posting into a blog about his java code about such a simple system called Hadoop. That’s soooo simple and unscalable.”

# Email Fraud

I recently received a bounced email on my gmail account. It would appear some body at this IP-address (192.83.180.224) attempted to send an email as me to jobs@selabs.com. that IP-address is in the range 192.83.180.* registered to “Ministry of Education Computer Center, Taipei Taiwan” There is a middle man (87.98.235.52) which is ovh.net a polish web hosting company located in France.

I’m actually kind of flattered that somebody from taiwan’s ministry of education wanted to send email as me. But I do not appear to have any apparent relevant skills for the company selabs.com. This is very odd. I should ask my taiwaneese roommate if he’s playing a prank on me, or if I should ask friends at gmail how serious this is to my online identity?

 from: Mail Delivery Subsystem mailer-daemon@googlemail.com to: huan.chang@gmail.com date: Wed, Nov 16, 2011 at 12:45 PM subject: Delivery Status Notification (Failure) mailed-by: googlemail.com : Important mainly because of the people in the conversation.

Delivery to the following recipient failed permanently:

Technical details of permanent failure:
Google tried to deliver your message, but it was rejected by the recipient domain. We recommend contacting the other email provider for further information about the cause of this error. The error that the other server returned was: 550 550 5.1.1 Mail Refused – Address <jobs@selabs.com> Recipient Unknown (state 14).

—– Original message —–

Received: by 10.52.23.242 with SMTP id p18mr49440063vdf.79.1321476306469;
Wed, 16 Nov 2011 12:45:06 -0800 (PST)
Received: by 10.52.23.242 with SMTP id p18mr49440062vdf.79.1321476306426;
Wed, 16 Nov 2011 12:45:06 -0800 (PST)
Return-Path: <huan.chang@gmail.com>
Received: from 87-98-235-52.ovh.net (lolth.cyber-host.pl. [46.105.112.83])
by mx.google.com with SMTP id cg1si2765747vdc.124.2011.11.16.12.45.04;
Wed, 16 Nov 2011 12:45:06 -0800 (PST)
Received-SPF: neutral (google.com: 46.105.112.83 is neither permitted nor denied by domain ofhuan.chang@gmail.com) client-ip=46.105.112.83;
Authentication-Results: mx.google.com; spf=neutral (google.com: 46.105.112.83 is neither permitted nor denied by domain of huan.chang@gmail.com) smtp.mail=huan.chang@gmail.com
Received: from 192.83.180.224 by 87.98.235.52; Wed, 23 Nov 2011 23:05:15 +0200
Message-ID: <IYVOSPVZJDKZIRWTTWKMCBH.OCIJODhuan.chang@gmail.com>
From: “�u�{�N�ԴڡC” <huan.chang@gmail.com>

Subject: �U�ؿĸ�CThu, 24 Nov 2011 03:02:15 +0600
Date: Wed, 23 Nov 2011 15:07:15 -0600
X-Mailer: eGroups Message Poster
MIME-Version: 1.0
Content-Type: multipart/alternative;
boundary=”–4382705805593925″
X-Priority: 1
X-MSMail-Priority: High

—– End of message —–

# sales tax

Are some restaurants out there in California still charging 9.4% tax because they haven’t reprogrammed their cash registers?

I found at least one.

The sales tax in Menlo Park should be 8.25%. The new rates effective Oct. 1 2011 are listed can be found on this page.