A different prisoner’s dilemma

Here’s a fun riddle posed by a student in the recent Algorithms: Design and Analysis course from Stanford University I participated in on the Coursera platform. I’m recording it here for posterity so I won’t forget. It’s fun to collect such riddles. That might make for cool party tricks. Note that I no longer have access to the original post so all this is paraphrasing from memory.

Riddle:

There is a sadistic warden in charge of a prison with 100 prisoners. He wants to execute these prisoners, but after much persuasion on your part, condescends to play a game with them that could result in some of them from spared. Each of the prisoners is numbered from 1 to 100. A room is set up with 100 drawers, all also numbered 1 to 100. Inside each drawer is a slip of paper, again numbered 1 to 100. However, the placement of each slip of paper in the drawers is randomized.

The game is that each prisoner is allowed to visit this room, one at a time. He is allowed to open the drawers one at a time and may open no more than 50 drawers. If he finds his own number on a slip of paper after having opened 50 or fewer drawers, he is saved. He must return each slip of paper into the drawer he found it in and is not allowed to exchange the positions of the slips of paper.

As an additional concession, you are allowed to visit the room before any of the prisoners may do so and examine the contents of all of the drawers. Furthermore, you may perform one and only one exchange before the game starts. That is after having viewed the contents of all 100 drawers, you may choose any two drawers and exchange the slips of paper inside them. You may not make any other changes and you may not communicate anything about the contents of the drawers to the prisoners.

The riddle is thus: what is the optimal strategy for the prisoners and how many the prisoners may be saved from execution using this strategy? The solution is after the break.

Continue reading A different prisoner’s dilemma

Recent Interesting Science Articles (August 2013)

August has been a terrible month for my stock portfolio but a fantastic one with regards to science news. Plenty of reading up ahead:

  • The coolest (or is it hottest?) bit of science news is, of course, Elon Musk’s hyperloop proposal. This is sort of like an inter-city elevated train that runs inside a tube. Air is pumped out of the tube until is almost a vacuum. The idea is that the lack of air resistance enables the capsules to travel at a top speed of some 1,200 kmph while reducing the weight of the infrastructure required. The whole thing is driven by linear electric motors and costs is supposed to be kept low by building the track above existing highways. While this is a very science-fiction scenario, my take on this is skeptical. Cost is everything and despite the suggested optimizations, the proposed looks implausibly low to me as many others have already pointed out.
  • In the US, recent political trends point towards white people being critical of affirmative action being black people remain strongly supportive. But are the whites truly in favour of meritocracy? This article points out a survey that does indeed find that white Californian adults are in favour of university admissions policies that prioritize standardized test scores and high school academic achievements. But when white people are reminded that Asian Americans are disproportionately represented inside the University of California system, because Asian Americans tend to do much better at standardized academic tests than other groups, they tend turned around and favoured a reduced role for test scores instead. This suggests that white people are in favour of policies that they perceive will help their own group rather than the principle of meritocracy.
  • As we all know, evolution is a continuous process that is ongoing, for us as well as all other species that we share this planet with. This article suggests that as humans have prospered and changed the environment, the animals inhabiting that environment have evolved in response. Based on the observation of increasing skull sizes, various mammals species including mice, shrews, bats etc. seem to be evolving larger brains to successfully navigate this changed environment. In particular, the brains of small mammals in cities or suburbs seem larger those of the same species in rural areas.
  • This next article requires some knowledge of black hole physics. For years now, it was thought that if someone were to fall into a black hole, he would be crushed by the awesome gravitational forces involved. This is now changing. Not that the person would die of course, just that he would first be killed by the so-called “firewall” of energy at the edge of the black hole. This is a relatively new concept stemming from the understanding that having information flow out of a black hole would be incompatible with the Einsteinian idea that the event horizon is smooth. Instead it is now thought that a discontinuity in the vacuum, manifesting as a wall of energetic particles, exists just inside the boundary of the black hole exist. Please read the full article for how this idea came about and the implications it has for physics.
  • As someone who has some red-green colour blindness, this piece of news has personal significance. It’s essentially a review of a pair of expensive glasses that addresses red-green colour blindness. The lenses apparently contain filters that increase sensitivity to specific colour temperatures and there are specific pairs for specific types of colour blindness. Given the caveat that it works only with very bright light (so it mostly won’t work indoors and won’t work with computer monitors), the writer of the review pretty unequivocally states that it makes a tremendous and immediately noticeable difference to how he perceives the world. He was able to discern colours he had never noticed before and the colours of the world became richer and more saturated.
  • Finally, here’s an article about research into how using Facebook and other social networks tend to make its users unhappy. After having controlled for the observation that those who tend to use Facebook are just unhappy in the first place, it finds that people demonstrably becomes unhappier after each Facebook session after an extended period of tracking. The reasoning is that such use arouses envy. Since those who post to Facebook tend to do so about the best things in their lives, whether they are their best photos, best moments or best lines, such moments are exaggerated and not at all representative of such people’s everyday life, forming an unhealthy point of comparison between different lifestyles.

Algorithms: Design and Analysis, Part 1

So the latest Coursera course I’ve been taking and have now completed is Stanford University’s version of its Algorithms class by professor Tim Roughgarden. Apparently enough people asked about the differences between this course and the one from Princeton University that the question has now been addressed in the FAQ sections of both courses: the Princeton class focuses on implementation and practical programming with students in their first and second university years as the target audience. This Stanford version focuses on the analysis of algorithms and is usually taken by students in their third and fourth years.

I always knew going on that with a weak maths background, this course was going to be hard for me. It also didn’t help that I find myself much more interested in practical applications of algorithms than in studying and devising proofs of an algorithm’s correctness or performance claims. As such I didn’t put as much effort into this as I did for the Princeton course. Some observations:

  • The programming homework emphasizes actual implementations, with some tweaks, of the algorithms being studied. It’s a language agnostic course so you’re free to use whatever language you want. The professor just explains everything in pseudo-code while the homework provides a data set and you just have to type in the answers you get from processing the data for evaluation. I cheated. Having already covered much of the same ground in the Princeton course, which does provide complete implementations of all algorithms in Java, I simply used the Princeton library, tweaking code only as necessary to get the correct answers. For the most part, this made the programming homework very easy for me.
  • Th quiz portion was correspondingly harder for me. I found that I usually had a decent intuitive grasp of what to shoot for, but in many cases, lacked the discipline to thoroughly walk through the entire reasoning process. Especially since many of proofs requires a solid understanding of probability. The same goes for the final examination, which honestly speaking is slightly easier than the regular quizzes, but is timed and allows only a single attempt. We were allowed two attempts for each of the quizzes. I scored 32 out of 40 in the final exam. I did not attempt any of the optional and ungraded challenge questions.
  • I have to say that Professor Roughgarden’s lecture videos and study materials are very basic compared to the Princeton course. It’s just a talking head and slides, with no animations whatsoever. One major problem I had is that the audio frequently is not in sync with what is happening on the screen. For example, he would talk about something but when he refers to a mathematical formula or a snippet of code, it doesn’t show up on the whiteboard until a few seconds later, which certainly does not help comprehension. Also while he offers typed versions of the slides he uses as a download, he prefers the handwritten versions in the lecture videos, and his handwriting isn’t always perfectly legible.
  • I did appreciate the thoroughness with which he covers the proofs and I have to admit that I’m able to follow them much more closely than I did when professor Sedgewick went through them (which he didn’t always do in the Princeton courses. I still can’t say that it’s my favorite subject though.
  • As previously mentioned, the course does cover much of the same material so there was little here that I haven’t already seen before. I did appreciate learning about bloom filters. And after being frankly puzzled by the Kosaraju-Sharir algorithm in the Princeton course (easy to code, hard to intuitively understand) I really liked how professor Roughgarden’s explanations and the associated programming homework, allowed me to finally grasp it in my head.
  • I don’t believe that I ever saw any Community TAs in this course. By and large, as far as I could tell, the students did an excellent job of posing and answering questions themselves, with professor Roughgarden himself intervening only on rare occasions mostly related to technical problems with the course itself. I do find that the student body for this course appears more mature than that of the Princeton course, with few people posting frivolous questions or appearing to be completely clueless.
  • Certainly as the professor admits, the assessment system is currently the weakest part of the course. The course really needs a way to have students submit proofs and get them evaluated (which would have utterly defeated me I believe) but there’s simply no feasible way to scale anything like this. Also, the programming homework requires just an answer (usually just a string of numbers) without any of the performance and memory usage evaluations used in the Princeton course.

No surprise when I say that I prefer the Princeton course by a very large margin. But this is still an excellent, high quality course especially for those more interested in the analysis side of things. Incidentally I’ve been invited once again to serve as Community TA for the next offering of the Princeton course which should begin at the end of August.

 

Recent Interesting Science Articles (July 2013)

Quite a few of these articles this month, so here goes:

  •  Cloning animals is nothing new these days but, still, there is something symbolic about cloning one from a single drop of blood, as this article from BBC News covers.
  • We all know that bats can navigate using ultrasound, but could prey make use of this fact as a defensive measure? This article from Popsci covers how hawk moths, found in the tropics, are able to respond to the ultrasounds emitted by bats hunting them by responding with ultrasound clicks of their own. It may be useful to just startle the moths or it could be part of an active jamming system to hamper the effectiveness of the bats’ echolocation abilities.
  • Nearly a quarter of a century after its inception, a study into the crack babies phenomenon of the 1980s has finally ended. The term refers to an epidemic of babies born to mothers who were addicted to cocaine and were exposed to the substance while in-utero. Apocryphal stories at the time talked of babies with shrunken heads, poor muscle tone and troubling behavioural symptoms. Twenty-three years later this study found that there was no difference in IQ between such babies and those of a control group with no prenatal cocaine exposure. They did find that both groups had IQ scores that were markedly lower than the national average and attribute it to the effects of poverty.
  • This next article is somewhat like the one above: conclusions that are “obvious” are not always correct. Pop quiz: which areas are safer to live in, for developed countries at least: urban areas or rural areas? As it turns out, this article from CNN explains how contrary to intuition, the risk of injury or death from violent crime and accidents are more than 20% higher in the countryside in the United States than in urban areas. We don’t know exactly why yet, but there are some educated guesses. In the US, rates of firearm ownership are higher in rural areas for example, and these residents tend to drive longer distances over more dangerous roads. Plus it’s easier and faster to get to a hospital in a city than in the countryside.
  • Finally here’s a just for fun article about a couple of physics points from the Pacific Rim film in a Scientific American blog: specifically how much force is there in a rocket-assisted punch delivered by a giant robotic fist and can a giant monster with a huge wingspan fly its way into space? It’s just the first in a series of two such articles with maybe more to come so be sure to look out for more too.

Embassytown

200px-Mieville_Embassytown_2011_UK

I’ve heard of China Miéville from his work in other genres but this is, I believe, his first science-fiction novel, and the first book of his that I’ve read. Embassytown received some very impressive reviews so I delved into it with plenty of anticipation and not a little bit of trepidation. As it turned out, the novel is less ambitious and more traditional than I expected so I needn’t have worried myself.

As its title implies, the book is about a city called Embassytown, the sole human settlement on the alien planet of Arieka. In the universe created by Miéville, humans traverse interstellar space by going through something called the immer, while hinting that some aliens, called exots, have wholly incompatible forms of FTL technology. It so happens that Arieka is located just about at the edge of explored space in the immer. This means that while Embassytown is formally a colony of a human empire known as Bremen, it is de facto semi-autonomous due to its remote location so visits from spacecraft crossing interstellar distances, called voidcraft, are both rare and the occasion for grand celebration.

Continue reading Embassytown

Recent Interesting Science Articles (June 2013)

Four articles this month, representing a fairly mixed bag of subjects. Here goes:

  • Let’s start with a very simple but effective technological innovation that applies only to countries that have four seasons. Tech-On! features a report about a new type of glass that would block sunlight in the summer while letting it through in the winter. It relies on the simple fact that sunlight in summer and winter have different incidence angles and the invention consists of nothing more sophisticated that joining two sheets of glass together. This alters the refractive qualities of the joined sheet of glass and the researchers tuned this precisely to have the desired effects. What I don’t quite understand is whether or not the glass needs to be precisely tuned to the latitude of the place where it will be installed because presumably the incidence angle of sunlight depends on the latitude of the location.
  • The next piece is not a science article but an extensive feature published in the New York Times about research on the outcomes to women and their babies who wanted abortions but were denied them. The key point is that the study manages to compare these women against similar women who wanted abortions and did get them. Not very surprisingly, the study found that these women have much poorer outcomes, with higher anxiety and depression levels, more likely to end up being poor and have poorer health. What is surprising is that despite these objectively poorer outcomes, most of these women still insisted that having that originally unwanted child was still the best thing that happened to them and significant numbers claimed years after the fact that they have never sought an abortion in the first place.
  • Then here’s an article from The Conversation about how cheetahs actually use their fabled speed. One uneducated guess about cheetahs might be that because of their reputation as the fastest land speed animal on Earth, you might expect them to hunt best of all on flat ground where they can show off their top speed. This turns out not to be true because cheetahs hunt more successfully in dense forested cover than on open ground. This is because the true advantage cheetahs have is not absolute top speed but fantastic acceleration rates and even better deceleration rates. This allows them to manoeuvre much more effectively than the prey they chase.
  • Bloomberg BusinessWeek has a very cool article about concrete, particularly the kind that the ancient Romans used. As we know from the copious amount of architectural works the ancient Romans left behind, they built a lot and a lot of it has lasted quite a long time. It turns out that ancient Roman concrete is significantly stronger than the modern variety we use today, commonly known as Portland cement. The precise formula for the kind the ancient Romans used was lost but researchers claim to have rediscovered by analysing their mineral content. By incorporating lyme and volcanic ash into their mixture, the Romans made more durable concrete than modern builders.

Favorite Films (No. 4)

It’s only been a little over a year since the last installment of this series. Previous updates to this list were in 2007 and 2009. Part of the reason is that I’ve been watching many more films recently. I was still surprised by how long it took to get to the five films worthy enough to write one such installment but now all of the movies included were released within about the past two years which is more timely than what I’ve managed in the past. As usual the standard disclaimers apply and spoilers follow.

Continue reading Favorite Films (No. 4)

The unexamined life is a life not worth living