Hello Everyone,
Welcome to the page for discussions related to programming,hacking,computer architecture and a lot of other computer related fundamentals and concepts.
Rule for posts on this page : The posts discussed here on a particular topic will last for 15 days. There will be continuous discussions on the related topic and readers can put up their questions as well as answer the questions of other members involved in that discussion. After 15 days, the post will be removed and a new topic will be introduced for discussion.
CURRENT TOPIC OF DISCUSSION : PROGRAMMING PUZZLES
PUZZLE 1 : OPTIMIZATION TECHNIQUE:
Problem 1 : Everywhere you look, you find mini-fads and their accompanying industries. Each comes with a bunch of characteristic phrases that often yield to a kind of popular jargon. To send a text message to someone becomes “to text them.” To find information using the Google search engine becomes “to google it.” Such shortening of phrases is not unique to our time. Movie sets shorten the phrase “we are about to start cameras so actors prepare yourselves and everyone else be quiet” to the single word “camera.” Languages borrow jargon from one another, because of the economy of expression they offer. Even linguistically proud France borrows “milestone” and “IP” from English, whereas it would never think of borrowing, say, “spoon.”
As puzzlists, we can help make better jargon. To show you how, we’ll abstract the phrases into letters and find an encoding in terms of bits. The marketeers can find words to fit later. We’ll be very concrete to avoid having to estimate probabilities.
Suppose that every message communicated has 60 characters and each character is one of A, B, C, or D. If you have to encode these in bits and you know nothing else, you might encode them as follows:
A–00 B–01 C–10 D–11
Because there are 60 characters and each character is encoded in two bits, the whole message requires 120 bits (15 bytes). Whereas this yields a far more succinct expression than the one byte per character encoding of ASCII, for example, some more information might improve things still further.
Suppose that we knew that every message of 60 characters consisted of exactly 30 As, 15 Bs, 10 Cs, and 5 Ds. What would be a good encoding in bits of the characters then?
Problem 2 : Two children, perhaps similar to ones you know, love cake and mathematics. For this reason, Jeremy convinces Marie to play the following game on two identical rectangular cakes chef Martine has prepared for them.
Jeremy will cut the first cake into two pieces, perhaps evenly, perhaps not. After seeing the cut, Marie will decide whether she will choose first or allow Jeremy to do so. If she goes first, she will take the larger piece. If she goes second, she can assume that Jeremy will take the larger piece.
Next, Jeremy will cut the second cake into two pieces (remember that one of the pieces can be vanishingly small if he so chooses). If Marie had chosen first for the first cake, then Jeremy gets to take the larger piece of the second cake. If Marie had chosen second for the first cake, then she gets to take the larger piece of the second cake.
Assuming each child will strive to get the most total cake possible, what is an optimal strategy for Jeremy?
| Hint: |
SOLUTIONS :
Solution to Problem 1: Intuition tells us that a good encoding should render A in the fewest bits, then B, then C, and then D. It is that intuition that guided Samuel Morse in his invention of the code that bears his name. But Information Theory could conceivably help us do better.
Solution to Problem 1: Intuition tells us that a good encoding should render A in the fewest bits, then B, then C, and then D. It is that intuition that guided Samuel Morse in his invention of the code that bears his name. But Information Theory could conceivably help us do better.
As originally conceived by Claude Shannon, Information Theory was closely inspired by a statistical mechanics interpretation of thermodynamics. Shannon defined a notion of “entropy” as a formula involving the probability of each character (e.g., A has probability 30/60 or 1/2; whereas D has probability 5/60 or 1/12), and logs of probabilities. The entropy describes the weighted average length of an optimal encoding in bits of a single character. The entropy formula in this case yields: (1/2 log(2)) + (1/4 log(4)) + (1/6 log(6)) + (1/12 log(12)) where all the logs are to the base 2. This comes out to about 1.73 bits per character. Of course, a designer is free to choose the encoding he or she wishes, and we choose a whole number of bits for each character, as follows:
A–1 B–01 C–000 D–001
In our encoding, sending A thirty times would cost 30, sending B 15 times would cost 30 as well, and so on. The total length would be 30 + (15 × 2) + (10 × 3) + (5 × 3) = 105 bits. This comes out to 105/60 or 1.75 bits per character. So the intuitive design is quite good.
Solution to problem 2: Following the hint, Marie reasons as follows: If she takes the fraction f piece, then Jeremy will take the entire second cake (he’ll cut the smallest crumb from the second cake and then will take the large first piece, leaving Marie only the crumb). So, Marie will get exactly f and Jeremy will get (1-f) + 1. If Marie takes the smaller piece of the first cake (fraction 1-f), Jeremy will do best if he divides the second cake in half. This gives Marie (1-f) + 1/2. Jeremy follows this reasoning, so realizes that the best he can do is to make f = (1-f) + 1/2. That is 2f = 1 1/2 or f = 3/4. If Marie takes the first piece of the first cake, then Jeremy will get 1/4 of the first cake and all of the second cake. If Marie takes the second piece of the first cake, then Jeremy will get 3/4 of the first cake and 1/2 of the second cake. In both cases, Marie gets a total of 3/4 of a cake and Jeremy 1 1/4. Note that if Jeremy cuts the first cake such that the larger fraction is less than 3/4, Marie will get more than 1/4 of the first cake by going second and will still get 1/2 of the second cake, thus increasing her cake amount beyond 3/4. By contrast, if Jeremy cuts the first cake such that the larger fraction is more than 3/4, Marie will just take that larger piece, again increasing her cake amount beyond 3/4.
I have discussed the warm-up at great length, because a week later a harder challenge has arisen. Chef Martine has made three new identical rectangular cakes. Jeremy and Marie both eye them greedily.
Let's discuss the problems here and try to optimize as optimization is the breath of programming.
Your comments and alternate solutions are welcome !
Note:
After this the next topic of discussion will be NETWORK TECHNOLOGY.
After this the next topic of discussion will be NETWORK TECHNOLOGY.
HTML Comment Box is loading comments...