Picasaweb Cameras

Which photo cameras make cool pictures?

I took a sample of 100 featured pictures from Picasa.

• 59 Canon
• 23 Nikon
• 18 others

Out of the Canon pictures, 27 where taken by EOS 5D Mark II, 8 where taken by various flavors of EOS DIGITAL REBEL, and 24 by other Canons.

Solitaire

Yet another “Is this NP-complete?” question. The problem is of a kind that I discussed before.

In the game Solitaire you sometimes visualize the state you want to achieve and regard the necessary intermediate moves as chore. A friend wondered how to reach the goal with a minimum number of key presses. (He plays on a Blackberry with no mouse.) Let us look at a simplified example.

□,1,□,□,4,3,□,2,5                     (1)   ↝ □,1,□,□,4,23,□,□,5                     (2)   ↝ □,1,□,□,234,□,□,□,5                     (3)   ↝ □,□,□,□,1234,□,□,□,5                     (4)   ↝ □,□,□,□,□,□,□,□,12345                     (5)

In this example there are 9 slots into which cards 1–to–5 are placed. In a valid state, each slot contains a contiguous sequence of cards, possibly empty (□). Each move consists of transporting a contiguous sequence of cards from one slot to another. (Take a moment to convince yourself that a valid state is reached only if the whole sequence of a slot is transported.) The cost of a move is the distance between the source and the target slots (and is independent of the size of the transported sequence). In the example above there are 4 moves with a total cost of 2+1+3+4=10. The goal is to put all the cards in one slot.

This problem has a dynamic programming solution, which works on a different representation of the states.

2,8,6,5,9                     (6)   ↝ 2,6,5,9                     (7)   ↝ 2,5,9                     (8)   ↝ 5,9                      (9)   ↝ 9                     (10)

The first state tells us that card 1 is in slot 2, card 2 in slot 8, card 3 in slot 6, and so on; the last state tells us that all cards are in slot 9. In general, a state tells us in which slots there are cards, and does so in increasing order of cards’ values. With this representation a move consists of crossing out a number. The cost of a move is the absolute difference between the crossed out number and the following number. (The last number in a state cannot be crossed out.) With n cards there are 2ⁿ⁻¹ possible states. For each state there are <n possible moves. Therefore, if each possible state and each possible move is examined at most once, then this algorithm works in O(n2ⁿ) steps.

Note that there are (n−1)! sequences of moves that attain the goal. A similar reduction (from n! to around n2ⁿ) appears when one moves from a brute force solution to a dynamic programming solution of the Hamiltonian cycle problem. In general, it is often possible to look at all subsets when it seems that looking at all permutations is necessary.

Questions: Can you do better? Is this problem NP-complete?

Mathematical Logic 1

Motivation by analogy.

Logic studies reasoning. Many people that are not familiar with logic are able to think (reasonably). For example, many children find the explanation “because I say so” less satisfying than “if you do not solve your homework then you will not receive a high grade, therefore you will receive a high grade only if you solve your homework.” A child may not agree that a high grade is a worthy goal, but the point is that the second explanation is somehow more satisfying. Some hidden mechanisms are at work, mechanisms that are transfered to children by training. Children learn how to reason mostly by imitation. I believe it is a very bad idea to teach a child how to reason by exposing him to logic, for that would be akin teaching a child how to walk by exposing him to the laws of mechanics, or teaching a child how to sing by exposing him to music theory, or teaching a child how to speak by exposing him to the rules of grammar. It is preposterous to try to teach a child how to speak by explaining the rules of grammar, because language is necessary in order to communicate the rules of grammar. Such circularity exists in the case of logic too. One cannot learn logic, unless one already knows how to reason.

Are then mechanics, music theory, grammar, and logic useless? Although mechanics does not help people to walk, it does help them to build cars; although grammar does not help people to speak, it does help them to communicate effectively. Mechanics is useful because cars are useful; grammar is useful because the ability to communicate is useful. Note that people built carts before understanding the laws of mechanics and they probably built engines before understanding the laws of thermodynamics. However, cars are better because we understand the laws of mechanics. Similarly, people may communicate without knowing grammar. However, people communicate better if they follow the rules of grammar.

Logic enriches the way people think. A logician immediately parses the sentence “if you do not solve your homework then you will not receive a high grade, therefore you will receive a high grade only if you solve your homework” as “(if (you do not solve your homework) then (you will not receive a high grade), therefore ((you will receive a high grade) only if (you solve your homework))”. Certain logical connectives (like if…then, not, therefore, only if) are emphasized, because logic cares more about how statements are chained together into an argument, rather than what those statements mean. In fact, when being careful about what they say (or hear), logicians will likely translate on the fly that statement into a symbolic form that makes it easier to visualize the structure: “(¬ p ⇒ ¬ q) ⇒ (q ⇒ p), where p stands for ‘you solve your homework’ and q stands for ‘you will receive a high grade’”. Here, logical connectives are represented by some standard symbols (¬ and ⇒) and the rest is hidden behind letters (p and q).