## Paper and Puzzle a Day 6

It’s been a while since I posted a paper and puzzle since I last made a blog post on a paper and puzzle. Other things have been occupying my time, but hopefully, I’ll be going back to my usual schedule with the Paper and Puzzle a Day posts.

So, first, a paper. I’ve been looking into some computational geometry problems and one particularly interesting paper that I’ve been reading is that of what are called “hinged dissections.” The paper’s title is appropriately titled, “Hinged Dissections Exist.” A hinged dissection is one where all pieces of a dissected shape are connected with a series of “hinges.” For example, the following figure shows a hinged dissection of a triangle into a square discovered by Dudeney in 1902.

Dudeney’s hinged dissection of triangle into square.

The paper shows that any finite collection of polygons of equal area has a hinged dissection such that it can folded into any polygon that is in the collection. It’s quite an intricate paper, and I’m still reading some of the details but it’s quite interesting so far. I may post more in future Paper and Puzzle a Day posts about this paper.

Now, for the puzzle. Since we are talking about computational geometry, I will use a computational geometry puzzle for today.

A tangram consists of the following pieces that form a square.

Even though all of the following figures are made from the same seven pieces, why does the equivalent black and white pieces seem to differ by a piece?

Puzzle courtesy of http://www.archimedes-lab.org/workshoptangram4.html.

Now, the solution to Day 5’s puzzle:

The trick to this puzzle is not to be bogged down with probability calculations. There is a way to ensure that at least 5 prisoners are released regardless of what the distribution of hats is (in which case, the fact that the hats are distributed randomly is irrelevant). Each prisoner decides beforehand what her partner is. Then, one partner decides to say the color hat that is opposite the color of her partner’s hat and the other says the same color as that on the partner’s head. When the hats are distributed, the partners find each other and carry out the strategy. If the hats on both partners’ heads are the same color, then the partner who says the same color will answer correctly. If the hats are different colors, then the partner who says the different color answers correctly. Therefore, one partner in each pair will always answer correctly.

## Iterated Log Algorithms

The iterated logarithm is the number of times the logarithm function must be applied to a number before the result is at most $1$. A runtime of $O(\log^*{n})$ is almost, very nearly almost constant but not quite as good as constant from an algorithmist standpoint. The iterated log of the number of atoms in the universe is at most $5$. Perhaps this is the reason why implementationists regard it as a constant for all intents and purposes.

Here, I will introduce three problems with algorithms that have log star runtime factors. Some of these algorithms are quite old but I’ve been thinking about iterated log algorithms in relation to a couple of research questions so thought I would still share some of what I read in the process.

Union-Find:

A logical way of representing a set is to represent the set as a tree with the name of the set attached to the root of the tree. Each element in a set is a node in the tree. We may perform a merge (union operation) between two sets by adding a pointer from the root of one tree to the root of the other tree. To find which set an element belong to (find operation), we can follow parent pointers from the element up the tree to the root to find the name of the set. If we maintain a balanced tree for each set, then each merge operation takes $O(n\log{n})$ time and each lookup operation would take $O(\log{n})$ time. Not yet quite what we want.

The two key ideas that will help us improve the runtime of Union-Find is that of a special rank that is used to determine which of the two trees’ roots becomes the root of the new merged tree and the idea of lazy updates of root pointers.

First, we’ll explain briefly the idea of root pointers and lazy updates of such pointers. Rather than searching from the node of a tree (representing an element of a set) to the root of the tree each time we perform a find operation, we maintain pointers from each node to the root of its tree. Thus, to find the set that an element belongs to, we simply have to follow the root pointer to the corresponding root with the label of the set that the element belongs to. However, we do not update the root pointers with each merge because that could be time consuming. Instead, we perform a type of lazy update depending on whether a set was constructed, merged (union operations) or the element of a set was queried (find operation):

1. make_set(x): $x$ is the element to be added to the newly created set. The rank of $x$ is set to $0$ and a pointer is added that points to itself.
2. union(x, y): if the root of element $x$ and the root of element $y$ have the same rank, then one of the roots is arbitrarily chosen to be the root of the merged set. If one of the roots has larger rank, then that root is automatically chosen to be the root of the merged set.
3. find(x): starting from $x$, follow the parent pointers until we reach the root of the set. Note that the root pointers of all nodes that are traversed during this procedure are also updated to point to the correct root.

The lazy updates only update the root pointers during the find procedure.

Although all nodes have ranks, we only care about the rank of the root. The rank of the root determines which of the previous roots remains the root of the merged tree. The root with the larger rank becomes the root of the merged sets. We define and update rank as follows:

1. When creating a set (a single new node), we set the rank of the node to be $0$ and create a parent pointer to itself.
2. When two sets are merged and one root has a larger rank than the other, then we create a parent pointer from the root with smaller rank to the root with larger rank and make the root with smaller rank a child of the root with larger rank. If the roots have equal rank, we arbitrarily pick a root to be the new root of the merged sets and increase its rank by $1$.

Note that one key aspect of this rank updating procedure is that once a node becomes a non-root node, then its rank is never updated again. Therefore, all non-root nodes have ranks that are at most the rank of the root of the tree (set) it is part of. In fact, all non-root nodes have strictly smaller rank.

We also make the observation that there are at most $n/2^{r}$ nodes of rank $r \geq 1$. This can be proven by noticing that for a root to gain $1$ in rank, the size of its tree must double. Therefore, a root of rank $r$ must have $2^r$ nodes in its tree. We know that all non-root nodes in a tree have smaller rank. Thus, there can be at most $n/2^r$ trees with roots of rank $r$. Using these observations, we may proceed with the proof of the runtime of Union-Find.

Theorem 1: Given $m$ Union-Find operations, the runtime of performing all $m$ operations is $O(m\log^*{n})$. We also reasonably assume that $m \geq n$.

Proof Ideas: The main idea of the proof is to divide the non-root nodes into buckets that contain nodes of rank $[r, 2^r - 1]$. This gives us a total of $O(\log^*{n})$ buckets. Therefore, there is a maximum charge of $O(\log^*{n})$ for elements in different buckets. Furthermore, a bucket with maximum value $2^r$ gets charged $O(n)$ since we have at most $n/2^r$ elements with range $2^r$. For a more detailed proof, please refer to the original paper or a very good summary of the proof.

Distributed 6-Coloring of a Tree:

The definition of the $6$-coloring problem is given a graph with vertices and edges, we produce a coloring of the graph by assigning each node a color. A valid $6$ coloring of the graph uses at most $6$ colors such that no two  adjacent vertices are colored the same color. Pages 5 and 6 of the paper presents and proves a parallel $O(\log^*{n})$ algorithm that solves this problem. The paper further extends this result to the $3$-coloring problem.

Finding an Approximate Maximum:

Given a list of $n$ unordered elements (assuming all elements are distinct), we are allowed to make $n$ comparisons each round. How many rounds of comparisons are needed to obtain an element from the $n/2$ biggest elements in the list? Turns out we only need $\log^*n + O(1)$ rounds. The proof of this bound is a bit too elaborate for me to explain here. Please refer to the original paper for the complete proof.

## John and Alicia Nash, 1928,1933–2015

My condolences.

I came across the concept of a Nash Equilibrium as a wee freshman in high school. I thought it a great concept: mathematics that showed nice, cooperative people are not always rational people. I became more interested in game theory, which also subsequently led to a more broad interest in applied math. And of course, needless to say, I venerated the man who came up with the concept that led to my interest in game theory…even before I first saw “A Beautiful Mind.”

John Nash and his wife Alicia were killed in a taxi accident on the New Jersey Turnpike Saturday afternoon. They were on their way back from Norway where he and Louis Nirenberg had just accepted the 2015 Abel Prize. Besides meeting the king of Norway, Nash had also expressed a desire to meet world chess champion Magnus Carlsen during remarks at Princeton’s celebration of his Abel Prize in March, and that was also granted this past week.

Today Dick and I join many expressing shock and offering condolences.

The time spans for the Nashes are really 1957–1963, 1970–2000, and 2001–2015. They were married in 1957, two years before the onset of John’s schizophrenia. Their divorce in 1963 came amid a nine-year series of hospitalizations that began in 1961. After his discharge in 1970, she felt he would be better off boarding in a room of the house she’d moved to…

View original post 1,234 more words

## Paper and Puzzle a Day 5

Today marks another paper and another puzzle so let’s get started.

Fractional Cascading is a pretty awesome idea for speeding up searches for the same value in multiple sorted lists. Given $k$ lists, a naive algorithm would take $O(k\log{n})$ time because it would binary search each of the $k$ lists individually. A faster solution provided by fractional cascading allows the search to be conducted in $O(\log{n})$ time by propagating certain half the elements from one list up to the next list and iteratively propagating the elements so that all lists can be searched from one list by following pointers. A more detailed description of the fractional cascading procedure can be found in a variety of online resources including: Wikipedia article, nice notes and video, and more notes!

Now the puzzle, another prisoner’s hats variant because I cannot get enough of these puzzles:

“As before, there are 10 prisoners and 10 hats. Each prisoner is assigned a random hat, either red or blue, but the number of each color hat is not known to the prisoners. The prisoners are distributed in the room such that they can see the hats of the others but not their own. Now, they must each, simultaneously, say only one word which must be “red” or “blue”. If the word matches their hat color they are released, and if enough prisoners resume their liberty they can rescue the others. A friendly guard warns them of this test one hour beforehand and tells them that they can formulate a plan where by following the stated rules, 5 of the 10 prisoners will definitely be released, so that they are able to rescue the others. What is the plan to achieve the goal?”

Slightly tricky because prisoners can no longer communicate with each other. How will you solve this?

Now the answer to Day 4’s puzzle (highlight to see the answer):

The numbers are written in binary, so the obvious first step is to convert the numbers to text (or decimals). Converting the binary to decimals gives a string of numbers:

212832200031263311822067093100

Now, if you count the number of numbers, you see that the number of numbers is a multiple of 10. What does 10 digit numbers tell you?

Turns out that 10 digit numbers signify phone numbers:

212-832-2000 312-633-1182 206-709-3100

These are not just any phone numbers, they are phone numbers for some pretty famous people. If you type these numbers into Google, you’ll see that they are the phone numbers to:

212-832-2000: Donald Trump

312-633-1182: Oprah Winfrey

206-709-3100: Bill Gates

Posted in Paper and Puzzle | Tagged , , | 2 Comments

## Paper and Puzzle a Day 4

Still a pretty early morning post considering the time I got up…

First, the paper: Recently came across the following paper, “Pessimal Algorithms and Simplexity Analysis.” This is the first couple of sentences in the paper, and I have to say, it is quite brilliantly written:

“Consider the following problem: we are given a table of n integer keys A1 , A2 , …, An and a query integer X. We want to locate X in the table, but we are in no particular hurry to succeed; in fact, we would like to delay success as much as possible.”

It goes on later to state,

“The research procedure is a prototypical example of an entirely new branch of Computer Science, the design and analysis of reluctant algorithms.”

Very great read for an early morning when all you want to do is go back to sleep. This tongue-in-the-cheek article attempts to introduce the discipline of simplexity analysis, where it is the algorithm’s designer’s job to design the slowest running algorithm. However, it is not enough to add infinite loops in the code because that is easily detectable and can be construed as wasting time. No, the goal is to produce an algorithm that is the slowest running possible but can full a naive observer that it is making progress with each time step. In this way, we can manage to create an algorithm that is indeed very reluctant.

The paper is filled with more gems that is sure to brighten up your morning, and it’s also very short.

Now, the puzzle: we’re going to steer away from the prisoners’ hats puzzles today no matter how much I like them.

00110010 00110001 00110010 00111000 00110011 00110010 00110010 00110000 00110000 00110000 00110011 00110001 00110010 00110110 00110011 00110011 00110001 00110001 00111000 00110010 00110010 00110000 00110110 00110111 00110000 00111001 00110011 00110001 00110000 00110000

That’s it, good luck.

Now the answer to yesterday’s puzzle:

Again this comes down to timing. If any prisoner sees hats of different colors on the other two prisoner’s head, then he would say the color of the 3 colored hats. If they all see the same color, then no one would say anything and eventually someone would know that the hat on each of the prisoner’s heads is the color with the 3 hats.

## Paper and Puzzle a Day 3

Early post to an early morning of paper reading.

First, the paper: I’ve been reading into the following paper for the past week or so: Parallel Graph Decompositions Using Random Shifts. One of the cool ideas from the paper is the use of sampling from the exponential distribution to determine cluster size. Turns out one can find some pretty strong expected bounds on diameter and number of edges between clusters by doing the analysis over the exponential distribution.

Now for the puzzle, this is another variant of the Prisoners’ Hats puzzles (which I am particularly fond of). I’ve never heard of this variant before, so hopefully, most of you have also not heard of it before:

3 prisoners can see each other and the hats on the other prisoners’ head. One prisoner is behind a screen and cannot see the other prisoners (and the other prisoner also cannot see her). There are 3 hats of one color and 1 hat of the other color. At least one of the prisoners must guess the hat on their head correctly in order for all the prisoners to be released. How can they ensure they go free?

Lastly, the answer to yesterday’s puzzle is given below (highlight to see the answer):

If you’ve seen rot2 or rot3, this is rot13, which replaces each letter with the one that is 13 places in front or in back of it. rot13 is special because it is self-invertible since we have 26 letters in the alphabet. The specific answer to yesterday’s puzzle is then:

well, welcome to the world of encryption

## Paper and Puzzle Day 2

Day 2 of my paper and a day promise…

First, a paper: Peter Shor’s contradiction to the triangle conjecture. Recently saw this paper that also conveniently disproved a long standing conjecture that every uniquely decodable code is commutatively equivalent to a prefix-free code (the motivation behind this is to the find a polynomial scheme to the unequal letter cost code problem). The reasons I like this paper are that it is very concise (slightly more than 2 pages) and because I am curious about how the counterexample was found. (If you read the paper, you can see that it’s not at all a trivial example to find.)

Now a relatively simple puzzle:

jryy, jrypbzr gb gur jbeyq bs rapelcgvba.

And as promised the solution to the previous day’s problem is given below (highlight the blank space below to see the solution).

4 prisoners and hats (highlight the blank space below to see the answer):

The solution to this puzzle basically boils down to timing. If the prisoner in the back of the line sees two hats of the same color in front of her, then she would say the opposite color. The next to last prisoner would wait for a response from the last prisoner. If the last prisoner does not say anything, then the second to last prisoner would know that the last prisoner sees hats of different colors in front of her. Then, the second to last prisoner would see the color of the hat of the prisoner in front of him. From this, he may deduce the color of his own hat and guess correctly.