Complaint of the day

After all these years of electricity why can't countries standardise on the shape of the plug point? I'm not even talking about the voltage, just the shape of the plug! *grumble, grumble*

Berlin Photos

I have uploaded some Berlin photos to flickr.

Back from Berlin

The first thing that struck in Berlin was how few people were on the roads. I don't think I saw more than five pedestrians in the entire trip from the airport to the hotel. There was also hardly any traffic on the roads. I don't know if it was the day or time because there were more people on the other days.

Another funny thing was the subway/metro system. You need to buy a ticket, but it is not checked anywhere. It is entirely possible to ride the subway without a ticket. In all the subways that I've seen, you have to put your ticket into a machine to be able to enter the platform, but not here. The other cool thing is that you can get a 3 or 7 day pass that not only allows unlimited travel on the subway but is also valid on the buses and trams.

The difference between east and west Berlin was also clearly evident. West Berlin was a lot more crowded during the day, but the situation was the opposite at night. The trams are mostly seen on the east Berlin side, and the building architecture is noticibly different. Oh, and of course, the pedestrian lights are different (see this).

The new Berlin station (Hauptbahnof) is really pretty (More about it here).

Another concern that I had was safety. It felt pretty safe even in the metros and the streets around midnight. Maybe the extra security for the world cup helped. Roaming the east Berlin side was nice especially around Friedrichstraße, and Unter den linden, two important roads in this part of Berlin. Kufurstendamm on the west side was also good.

Also notable was the number of cyclists. Cycling around seems to be very popular, and you can find cyclists everywhere. There is a special coach on the subway for cyclists to use. There are even some dressed in suit and tie cycling to work.

Windows and process

A former manager on the Vista team asks Are Vista-scale software projects essentially uncontrollable by nature? Or has Microsoft been beset by one too many broken windows?:

"Windows process has gone thermonuclear. Imagine each little email you send asking someone else to fill out a spreadsheet, comment on a report, sign off on a decision -- is a little neutron shooting about in space. Your innocent-seeming little neutron now causes your heretofore mostly-harmless neighbors to release neutrons of their own. Now imagine there are 9000 of you, all jammed into a tight little space called Redmond. It's Windows Gone Thermonuclear, a phenomenon by which process engenders further process, eventually becoming a self-sustaining buzz of fervent destructive activity."

Expressions UK Fashion Show

Expressions UK Fashion Show
Originally uploaded by Siddhi.

A model from the Expressions UK fashion show. The show was a part of the Singapore Fashion Week 2003.

On program optimisations

Programs should be written for people to read, and only incidentally for machines to execute. -Abelson and Sussman, Structure and Interpretation of Computer Programs

This famous quote by Abelson and Sussman sums up what software development should be about. Computers will execute anything that you throw at them, but not everything is easy for humans to read and understand. Many bugs are caused by programmers not being able to fully understand the code and design. It is strange how many programs are written to be efficient for the computer to run, but are highly inefficient when it comes to programmer understandability. This is exactly the opposite of what it should be. If there is one principle that drives the design of a software system it is to write programs that others will find easy to read and understand. Only make optimisations where it is absolutely required, and keep these optimisations to a minimum.

Premature optimization is the root of all evil (or at least most of it) in programming. - Tony Hoare, and repeated by Donald Knuth in Computer Programming as an Art, 1974 Turing Award lecture

This post is a part of the selected archive.

Broken binary searches

[via Ned Batchelder] It seems that Nearly All Binary Searches and Mergesorts are Broken

Fast forward to 2006. I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug. Once I tell you what the it is, you will understand why it escaped detection for two decades. Lest you think I'm picking on Bentley, let me tell you how I discovered the bug: The version of binary search that I wrote for the JDK contained the same bug. It was reported to Sun recently when it broke someone's program, after lying in wait for nine years or so.

On web frameworks and AJAX

I recently started working on a new project at home. Its a web application to help out with project management. The two goals were 1) to develop something that I could use for the projects at work and 2) to learn something new. This project was perfect for learning something that I had always wanted to learn more about: Web frameworks and AJAX - both hot areas of Web 2.0 (and yes, although there is a lot of hype around Web 2.0, it is clear that a new web revolution is underway, and it is not just a passing fad).

Given a choice, I prefer to work in Python, so I went around looking for web frameworks in Python (and there are a LOT of them). I finally decided upon django, having heard a lot of good things about it (the fantastic website also helped).

Having worked a bit with it, I can now say WOW. The basic framework for the site is already done and it only took two full days and two nights to get it here. Further, one of the full days was dedicated to designing the look and style of the site, so only a day and two nights were spent on programming. This includes a complete and customised administration area where you can modify any object in the system. Sure, there is still a lot to do, but to still get this far in such a short time has been amazing.

I'm now looking to refine the interface, and that means AJAX. I'm currently looking into the Dojo and Mochikit libraries. I've implemented my first drag and drop using Dojo and in-place editing with Mochikit. That has taken another day. I currently like Mochikit as it is much easier for the beginner to get started with. Dojo looks a lot richer, but its really hard to learn with very scant documentation. Of course, my lack of experience with Javascript (and especially the way OO is done in Javascript) and my familiarity with Python (which Mochikit tries to emulate) may have something to do with that.

After this preliminary experiment, I can say with some confidence that a single person working full time on an application can get a first version out within a month. Capital and resources are no longer major problems. All you need is a good idea. In other words, the next few years will be a great time to be an entrepreneur, much like the years in the late 90s.

Freshers and the "Real World"

Gaurav has a nice post on welcoming freshers to the "real world".

Bill Gates Quote

Just ran into this quote:

We always overestimate the change that will occur in the next two years and underestimate the change that will occur in the next ten.

-- Bill Gates

Lightbox feature

I've added a cool new lightbox feature to this blog. Rather than explain it, it's a lot easier to demonstrate. In order for the lightbox feature to work, you have to click on the image on the website, as it uses Javascript which does not get loaded when viewing through an RSS reader.

To see it in action, just click on any of the images posted to the blog and see what happens.

If you like it, you can get the code from here.

Enjoy!

NTFS Junction

One of my gripes with Windows XP has been the lack of proper symlinks. They have shortcuts, but a shortcut is not a symlink. Try this:

1. Create a shortcut to C:\WINDOWS and place the shortcut in C:\
2. Rename the shortcut to "mytemp"
3. Open the command prompt by doing Start->Run..->cmd and type cd C:\mytemp

If try that, you will find that you cant access the directory. This is because a shortcut doesn't create a link exactly, but creates a file mytemp.lnk. Now try cd C:\mytemp.lnk, and it will find the file, but since it is only an ordinary file, you can't do a change directory to it. In other words, a shortcut is nothing but a file which has special meaning only to Windows Explorer.

Well, it turns out that NTFS does support actual proper symlinks. These are called Junctions in NTFS. Junctions also allow you to mount filesystems at a mount point much like how it is done in UNIX. The only problem is that there is no way to create Junctions with Windows XP. That was until I found this awesome utility which allows you to create proper junctions on your NTFS drive. This is something that I have been wanting for ages. If you ever wanted proper symlinks on windows, you just have to check out Junction .

Recursion Part 6: References and Further Information

The following is a part of a series of articles I had written on recursion.

---

This, the final part of the series contains sources for the articles and where to get further information.

All Parts:

Recursion Part 1: Introduction to recursion
Recursion Part 2: Tail recursion, Accumulators and Iteration
Recursion Part 3: Exercises in tail recursion
Recursion Part 4: Tree Recursion and Dynamic Programming
Recursion Part 5: Structural and Generative Recursion
Recursion Part 6: References and Further Information

---

The best way to learn about recursion is to learn a language that doesn't support iteration. Scheme is a good language to learn in this context. A Scheme interpreter can be got from here

Another good resource is the 6.001 course from MIT. The course material for this course is available for free.

Two highly recommended books:
1. Structure and Interpretation of Computer Programs (also called as The Wizard Book). There is an Indian edition, but not very easy to find.
2. How to design programs. This book is also available in an Indian Edition, but there is often not much stock.

Both books use the Scheme language, so they also serve the purpose of those trying to learn Scheme. Both books are also available for free on the Internet.

For more on dynamic programming, see Chapter 15 of the book 'Introduction to Algorithms' by Cormen, Leiserson and Rivest. This is a college textbook and is available in any bookstore. Most other books on algorithms also include a chapter on dynamic programming. Otherwise searching Google for "dynamic programming" will provide lots of articles on this topic.

---

Any questions? Comments? Please leave a comment using the comment form below.

This post is a part of the selected archive.

Recursion Part 5: Structural and Generative Recursion

The following is a part of a series of articles I had written on recursion.

---

This part deals with two areas for which recursion is commonly applied. The first, called structural recursion, is used to traverse through different parts of a data structure, processing each part in some way. The second, called generative recursion, is used when we want to divide a problem into smaller subproblems, which are then solved.

All Parts:

Recursion Part 1: Introduction to recursion
Recursion Part 2: Tail recursion, Accumulators and Iteration
Recursion Part 3: Exercises in tail recursion
Recursion Part 4: Tree Recursion and Dynamic Programming
Recursion Part 5: Structural and Generative Recursion
Recursion Part 6: References and Further Information

---

Let us start of with structural recursion. Here is an example, an inorder traversal of a binary tree:

void inorder(node element)
{
    if (NULL == element) {
        return
    }
    inorder(element->left);
    process(element->data);
    inorder(element->right);
}

This is a classic case of structural recursion. Each recursive call processes a part of the binary tree. Put together, we process all the elements in the tree. Structural recursion is often used when dealing with self-referential data structures like lists, trees and graphs. Functions to deal with these structures are hard to implement with iteration¹, and even if we do manage to implement them with iteration, the resultant code is often very difficult to understand. Such code is best left as recursive.

In some cases, it is possible to modify the data structure itself so that common operations can be implemented iteratively. An example of this is the threaded tree data structure that modifies the classic binary tree to allow for iterative traversal.

In any case, except for exceptional cases, it is best to use recursive algorithms to implement structural recursion

Generative recursion is often used when we want to break up a problem into similar subproblems. The subproblems are solved and the results combined to get the final solution. Solving the subproblems in turn requires recursion to break the problem into smaller subproblems, and so on until we reach a trivial case. The recursive examples of factorial and fibonacci number calculations and the well known quicksort are examples of generative recursion.

Look at this fibonacci program again and convince yourself that it uses generative recursion:

int fibonacci(int n)
{
    if (0 == n) {
        return 0;
    } else if (1 == n) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

Generative recursion that operates on a known finite set (eg: fibonacci(n) operates on integers between 0 and n) are good candidates for a dynamic programming approach. Generative recursion that operates on large or unknown sets (eg: functions that work with real numbers often fall into this category) are usually not condusive to dynamic programming. Some cases of generative recursion may have good iterative solutions, but this has to be considered on a case by case basis. In most cases, it is best to just leave them recursive.

Of course, all the above only applies to tree recursion. Tail recursion, whether structural or generative can always be converted into iteration.

---

¹ The exception is linked lists. Linked lists usually result in tail recursion which can be converted to iteration.

---

Any questions? Comments? Please leave a comment using the comment form below.

This post is a part of the selected archive.

Agile is not XP

I recently heard this podcast with Dave Thomas. Dave has talked on many occasions about the Dreyfus model of Skill Acquisition, which is similar to Shu Ha Ri. He also talks in the podcast about some Agile practitioners being dogmatic in their views. So in a sense, listening to the padcast made me go and write these posts, something that I've been meaning to do for a long time anyway.

In a previous post I had said "Sometimes I think that the term Agile has been co-opted by the XP and Scrum groups, but that's a topic for another post."

What is agile development? In theory, agile processes follow the four points of the agile manifesto. However, most people use the term "agile" to actually refer to either XP or Scrum, and consequently practices from these processes are invariably attached to the term "agile". This is a pity, because agile is a general term that refers to a host of different methodologies, many of which differ very markedly from XP.

For instance, while XP says no big design up front, both FDD and DSDM have distinct modelling phases at the start of a project. Similarly, XP minimises documentation, whereas say Crystal Clear does emphasise certain documentation. This obviously irritates a lot of people. Alsitair has an AgileIsntXp page on his twiki.

I also agree with Dave's comment that agilists can sometimes be dogmatic. How many times have we seen arguments along the lines of "thats big design up front, so its not agile", never mind if it helped solve the problem or not. I was just searching around for more info on the No Fluff Just Stuff conference when I came across this link which just illustrates the point (see section on Pragmatic Tracer Bullets).

If you are having a big discussion on the level of "is this big design up front or not?" then it's a lost cause already, because that is the wrong question. The question should be "will it help me produce working software?" and if the answer is yes, then you do it. Of course, as we saw in the Shu Ha Ri post, beginners who are just starting out with the process need clear rules, and "no big design up front" is a clear rule, whereas "will it help me produce working software" is not so easy to answer. You need to be in the Ha or Ri phase to answer this one.

There is a fundamental paradox here, because agile was developed in response to the "rules" based ISO/CMMI processes, replacing them with a more intuitive understanding of project management as placed out in the agile manifesto. This is great for the intermediate and expert project managers, what about those just starting out on the process who need clear rules? We need to put in certain rules and best practices to help beginners. But in the end, guiding beginners is all the rules are for. They are not "best practices" to be followed by everyone in every situation.

Finally, go read James Bach's posts on What is agile methodology? and No Best Practices, both of which hit the nail squarely on the head.

This post is a part of the selected archive.