Georgia Tech’s New Theory Club!

December 10, 2014 § Leave a comment

Hello everyone,

This past Sunday, I presented my proposal to the Undergraduate Council of the College of Computing for a club to facilitate the interaction between students interested in Theoretical Computer Science and its applications. And they accepted my proposal! Starting in the Spring Semester, we will have weekly meetings where we will have student or faculty talks or a problem session (or some sort of social activity).

I will write more about the club later, hopefully, but for now, I wanted to talk a little bit about what I did not get to talk about during my presentation. See, the council seemed so worn out by the long presentation and deliberation before my presentation that they wanted me speed through everything, and I didn’t even get to use my slides. I had prepared a sample problem session, and I want to talk about that here.

The problem session was centered around randomness. I started off with a class problem which I think is one John von Neumann was quite fond of. The idea is this:

Problem 1:

You are given a coin, but you have no guarantees that it is a fair coin. You just know that is really is random — there is some probability psuch that, whenever you flip the coin, it lands heads up with probability pand will otherwise lands tails up, and 0 < p< 1. You need to make a random decision, but you really want to make a decision with probability 1/2. You really want a fair coin. How can you use this possibly biased coin to make your decision?

Without spoiling the answer, I think this is quite the neat little problem, and it has a neat little answer. When I have asked about this problem in the past, I have had students give me answers for making choices with probabilities arbitrarily close to 1/2,

Once we have a way to generate uniformly random bits, the world is our oyster. We can sample over lots of different distributions. As a sample problem, I would like to know:

Problem 2:

Given only a method for generating uniformly random bits and a positive integer Ndevise a method for generating a uniformly random integer over { 1, 2, … , N}.

Of course, we could ask about other distributions, but this gets the idea across.

Finally, I wanted to close with a problem that is much harder than the previous two — possibly too hard for the UC, but I guess I will never find out.

Problem 3:

Alice and Bob as playing the following game:

  • Bob secretly picks two distinct real numbers, a and b.
  • Alice chooses to ask for a or to ask for b.
  • Bob reveals to Alice the number Alice asked for.
  • Alice then has to guess “higher” or “lower.”

If Alice says “higher,” she wins if the remaining secret number is greater than the revealed number, and if Alice says “lower,” she wins if the secret number is less than the revealed number.

Is there a strategy that Alice can use to win with probability greater than 1/2?

Before trying to solve this problem, we should notice something. Alice’s strategy needs to involve making random choices. If Alice’s strategy is not deterministic, Bob will just always make the hidden number reflect the opposite of what Alice would think.

Next, we should notice that Alice can definitely win with probability 1/2 by just ignoring everything, and then randomly picking between guessing “higher” or “lower.”

So can we do better?

Puzzle: Infinite Hats Problem

February 24, 2014 § 2 Comments

For those of you who are unaware, I have been in Budapest for a little over a month, and I have been quite a bit busier than I expected. I know I have been much worse than I had intended about keeping up with this blog, but I heard a great puzzle the other day, and it is quite exciting. Here it is:

There are infinitely many logicians (one for each integer), and an adversary tells the logicians that he will place a hat on each of their heads. He tells each logician that each hat will either be red or blue. He then tells each logician that, once he has placed a hat on each of their heads, the logicians may see the color of all the hats that are not their own, and then they must attempt to guess their own hat color. The logicians win if only a finite number of them guess incorrectly. Is there a strategy that will allow the logicians to win if the adversary knows their strategy?

Just to make sure the problem is clear, each logician gets a different hat. At no point do they get to see their own hat color nor do they receive any information from any of the other logicians once they have received their hat. All they can see is the color of the hat placed on each other logician’s head.

Thanks for reading!

-A Student of Logic

A Pardon For Alan Turing

December 25, 2013 § Leave a comment

Today, I was informed that Alan Turing has received a royal pardon. I do not really know what to say about this. On one hand, I am glad that we have made progress in the time since Alan Turing was driven to suicide, but I feel as though this progress has taken far too long to occur. We still have a long way to go, and I do not think a royal pardon can even come close to holding the value of the life that was taken, let alone the rest of the lives that have similarly been lost as a product of intolerance.

Gödel's Lost Letter and P=NP

myturing

Elizabeth Mary, Queen Elizabeth II, is the Queen of the United Kingdom and of the other Commonwealth realms. She has just today granted Alan Turing a posthumous royal pardon under the rule of “royal prerogative of mercy.”

Today Ken and I want to add our thoughts to this event.

View original post 801 more words

Puzzle: Catch the Shark

December 1, 2013 § 2 Comments

I was speaking with my editor last night, asking for advice on something quick to write about. After running through a list of drafts and ideas that I had written and determining that none of them seemed to fit what we were looking for, he started reciting to me a list of what I will refer to as “cocktail party” pieces of Mathematics. After hearing a few items, I find myself saying “that reminds me of that problem where…” to which he says “that problem where you are trying to catch the shark in the boat?”

Of course, he was correct. The problem it reminded me of was one which I had heard him and a mutual friend recite quite a long time ago, and it was also exactly what I was looking for. The problem is as follows:

You are the captain of a boat. This boat is on a one-dimensional body of water, and this body of water goes on forever in both directions. To elaborate, each possible location on the water is an integer point, so if you are at location 2, and you go to the location immediately to your right, you will be at location 3. If you are at location 0, and you go to the location immediately to your left, you will be at -1. In general, if you are at location and you go to the location immediately to your right, you will be at location x+1, and if you instead go to your left, you will be at location x-1.

Your boat is special, however. You are not restricted to just moving to locations immediately to your left or right. You can enter an integer number into your boat’s navigation system, and at the next second, you will be at that location. For instance, if you are at location 3 and then you enter into your computer-1036, at the beginning of the next second, you will be at location -1036.

Now that you know how the boat works, here is the challenge. There is a shark in the water. You know he is somewhere in the water, but you have no idea where he is. Furthermore, he is moving at a constant rate through the water (the rate is some integer distance per second), but you also have no idea what the rate is. Can you catch the shark (that is, can you, put yourself at the same location as the shark)?

To recap the problem: You are in a boat. At each second, you can pick a new location to be in (you can think of this as being able to take a guess at where the shark is once every second). The shark moves at a constant rate, and you have no idea where he started. Can he be caught?

As always, feel free to message me with a solution or to ask for a solution. Try not to spoil it for others.

Thanks for reading!

-A Student of Logic

A Problem of an Unknown Audience

November 2, 2013 § 3 Comments

It seems that I am having trouble completing the posts that I want to share about certain topics, and it seems to be because I do not know how much I should leave to my readers to figure out and how much space I should use for definitions and motivating topics within the posts about those topics.

Certainly, some of the things will be interesting mostly just to people who already know what the words I am using are and have a reasonable level of familiarity and maturing in the area. Other times, however, I feel — particularly in the vein of the famous complexity problem P vs NP — that many people are interested by it but probably have very little background on complexity classes and models of computation (namely Turing Machines).

While I do not think I have come up with a great solution to the problem, it seems I could do any of the following. First, I could just simply ignore it. I could assume that, if someone is interested enough to know what I am talking about, they will gain the necessary background knowledge themselves or already have it. Second, I could mostly ignore it, but put lots of pointers or links in my posts to descriptions of concepts that I am talking about. This seems to make a lot of sense to me, and I can imagine it will happen more than once. Third, I could have separate posts giving small introductions to things and giving definitions so the posts to come later seem less foreign. I like this idea the most, and, I think this is what I am going to try out for now. An issue that I see with this, however, is that it may require a reader to search for my previous posts (which does not seem good, but I will think that over and gladly take suggestions regarding this or anything else, really). Another issue I see with this is that it could make a majority of my posts uninteresting to people who are already educated on these topics. I believe this is excusable, especially if I post frequently.

As a result, I think I may, for some period of time, try to have at least a daily post, most of which will be definitions leading up to something that I think is interesting. I will try to post things interesting to my readers that already know all the definitions about as frequently as you might expect a normal blog to post interesting things. I will try to go no more than a week without posting things that are substantial. Maybe if I structure and categorize the posts well enough (at least on my wordpress site), this may be a useful learning tool for someone in the future.

Thanks for reading!

-A Student of Logic

An Interview Question: Dynamic Median Structure

October 30, 2013 § Leave a comment

While I was thinking about puzzles, I thought it might be nice to do something useful for my readers that actually want jobs (jobs in the technology industry, I mean). I was browsing the internet, and I came across an interview question that I myself have been asked before, and I think it is actually a pretty good technical question. Anyway, enough beating around the bush.

The problem is phrased as follows: you are to design a system (a datastructure, if you want to call it that) which can receive numeric elements as input and can deliver the median at any time as output.

Of course, this is somewhat open-ended as there are so many ways to accomplish this. Of course, that is what interviewers usually want, as it helps them (or so they claim) to take a look at your thought process. So, while I can not gauge your thought process, if you would like to benefit from this, you should find ways to optimize your structure. Try to see how much efficient of a solution you can deliver and how what trade-offs you might be able to make from time and space.

Thanks for reading!

-A Student of Logic

Puzzle: Magic Square

October 29, 2013 § 7 Comments

Hello Math people. I heard this puzzle a few weeks ago, and I thought it was pretty great. Here is how it goes:

You and a friend are playing a game against an adversary. The game is played as follows. You walk into a room with the adversary, leaving your friend outside. The room contains a checker board (the typical 8 by 8 kind), and each square has on it exactly one coin. Each coin can either be heads-up or tails-up. Then, the adversary chooses exactly one square which he calls the magic square. You, then, based on the arrangement of the coins and which square is the magic square, will choose exactly one square and turn its coin over (either from heads-up to tails-up or from tails-up to heads-up). Then, you will leave the room through a back door and wait in a separate room. Your partner then comes into the adversary’s room, looks at the board, and proceeds to take a guess at which square is the magic square. If your partner guesses correctly, you win.

Assuming you and your partner have no idea of what arrangement the board will be in when you enter the room, come up with a strategy for you and your partner to use so that you can always win.

Note: the only information you or your partner can have from looking at a coin is which square it is on and whether or not it is heads-up. The solution does not involve doing something silly by rotating the coins; the adversary chooses the orientation of the coin after you flip it.

Thanks for reading, and feel free to message me if you would like the answer!

-A Student of Logic