2015-05-22

Sorting is computationally harder than playing chess

I will argue below that sorting of a big array by comparison is inherently harder than solving the problem of choosing the best reply move on a chess game.

One could say that it is not fair to put in competition a big, however finite, problem like chess with an arbitrary big problem like sorting n elements. Fair enough; the interresting thing is that sorting becomes inherently harder than chess for an "n" that is way smaller than you would expect, like sorting 3000 elements. At least in theory...

Sorting takes a minimum of n*log2(n) comparisons, 

more exactly log2(n!)


This is about sorting "by comparison only" and can be proven in 2 step. You can skip to the "chess" part if you already know this.

1. Sorting can be done in log2(n!) comparisons, that is just slightly less than n*log2(n).
We are used to consider sorting an O(n*log2(n)) problem. Actually there are algorithms that can do the sorting with little less than n*log2(n) comparisons. The sorting by insertion in an increasingly sorted array takes log2(n!) comparisons.

2015-05-18

Godel and psychological types

“There are two types of people in the world, those who divide everybody into types and those who do not”. I am part of the second type ;)


Is the text above true or false?

2015-05-07

Backup your smartphone pictures for 20 years or more - ideas

Will you have your digital pictures after 20 years from now? Will you regret to not have them? How can you safely store your digital pictures in order to still have them in 20 years or more?

I am talking, for example, about the pictures or movies that you take with your smartphone or with your digital camera. I know I will want to have them after years.

Digital pictures tends to be even more fragile than paper pictures. Do you still have all the digital pictures that you have taken 10 years ago? What if your smartphone gets stolen, or your desktop hard drive fails? What if you delete the pictures by mistake when re-installing the operating system?

Here are some ideas that I got when I evaluated the way to keep my pictures for 20 years or more. I am already using some of this methods for my pictures. I am open to other suggestions and comments.

General considerations
  •  No single solution for storing digital content is perfectly safe for 20 years or more
  • The best solution should be a combination of solutions, hoping that at least one will prove to be reliable
  • I will examine various solutions, with pros(+) and cons(-). For assuring "disaster recovery" one should be a bit paranoid, so here are some ideas:
     

On short

  • organize all pictures/movies on years/month, example:[2015] / [2015-05] / [event] / *
  • monthly, copy all raw pictures and movies to at least 2 external USB hard drives
  • yearly, do selections for each month and write it at least twice on DVD
  • re-copy the hard drives at 3 years and DVDs at 5-10 years
  • yearly, print 1-10 pictures from each month on paper
  • have some selected pictures stored in your friend's archive (if they accept)
  • (optional) yearly deposit one selection DVD in a remote location, or update a remote hard drive
  • (optional) let your smartphone/Picasa/etc to backup the pictures on the cloud, at reduced resolution (to be free of charge)
  • (optional) backup all data, also in a remote online network storage and be sure that it will be funded and secured for this many years