Tuesday, September 26, 2006

First look at arrays

Yesterday, I was going through a couple of DS&A books that I had used during my student days. One particular book, written by Jean-Paul Tremblay and Paul G. Sorenson uses a very small point font and runs to over 700 pages. I don’t think I will be able to go through that book today. While the book is a great one, in today’s age of diminishing attention, I do not think that students will be able to patiently read it thoroughly. So I have decided to give very simple definitions, even if they are not complete in all respects.

First some simple definitions.

Data structures help us in arranging our data in ways that make accessing and manipulating them easy.

Algorithms are logical sequence of steps that access and manipulate data. Good algorithms take advantage of the structure of the data to make themselves more efficient.

Bad data structures lead to bad algorithms, though, I dare say, you can create bad algorithms even with good data structures.

As you can see, data structures and algorithms have to be individually good and compatible with each other to result in good programs.

Some real life examples of (data) structures.

The next time you go to a public swimming pool, take your eyes off the babes/hunks for a couple of minutes and look at the row of lockers meant for keeping your stuff in while you are swimming.

They are usually arranged one next to the other in single file. You typically go there, find an empty locker and shove your things in. If there are no empty lockers, you can’t do much about it until somebody empties one of the lockers.

Now, let us say, you are more than seriously eying one of the aforementioned babes/hunks. You might want to grab the locker next to theirs for yourself. If it is empty, you are in luck, but if it is not, what can you do?

If you are really desperate, you could find an empty locker (locker n) somewhere, take all the things from the locker(locker 1) you want and move it to the empty locker and put your stuff in locker 1. There – where luck fails, initiative triumphs.

But supposing, the empty locker (locker n) that you find is quite far away and you don’t want the original occupant to scream and create a scene, what can you do?

One way of solving this problem is to do as follows:

Assume that you have your stuff in your left hand. You could open the locker you want and take all the stuff in it in your right hand. Then you could take your stuff from your left hand and put into the locker. Initial goal achieved, but you have somebody else’s stuff in your right hand. You will need to get rid of that decently.

So, you move to the next locker and take the stuff out with your left hand. Then take what is in your right hand and put it into that locker. Continue down the row of lockers alternating hands until both your hands are free. Whew! That was tough.

In another way of going about it, you would probably start at the locker before the empty one (locker n-1) and transfer all the items in that into the empty one. Then you would move to the previous locker (locker n-2) and move the items in that into the currently empty one (locker n-1). You will keep doing this (quickly – before anybody comes in) until the locker you are interested in is empty. Then you can put your things in – mission accomplished and most probably no one will notice that their stuff has been shifted by one locker! The second approach required only one hand and had the added benefit of being able to look nonchalant and guilt free if anyone walked in while you were half way through the exercise!

That row of lockers we were discussing just now is what we call an array in our programming world and is one of the first data structures that you are likely to use. And each of the lockers is an element of that array.

There, now you know some of the basics about single dimension arrays. Henceforth, whenever we discuss operations on the array, we will see how it can be achieved on the row of lockers first before diving [these swimming pool similes are too much!] into programming. Ok so far?

Thursday, September 21, 2006

As the CEO of a startup in the late '90s, one of my responsibilities was to find good software engineers and programmers. Those days, a single small advertisement in a local daily would result in 8000 resumes within 3 hours. Out of these, about 500 would meet our initial selection criteria. 50 would pass our general aptitude and programming test. We would finally recruit the 10-15 good quality programmers that we needed that year. While not everyone interviewed was outstanding, most were able to answer all the basic questions and had a reasonably good grip on what they had learnt in college.

Moving on to early 2006. I was interviewing candidates for a few developer positions for my friend's startup. The situation was abyssmal. The quality of candidates who responded was extremely poor. During the interviews, the candidates were unable to answer the most trivial of questions. Many of the interviews would not have lasted more than 3 minutes, but for my inability to be rude to people so innocently unaware of their ignorance. Despite the 4 years in college working towards a BE in computer science or 3 years getting a Masters in Computer Applications, the candidates appeared blissfully ignorant of even the rudiments of programming. Basic questions to test logic and thinking elicited text-book sounding cockamamie or, worse still, blank stares. Topics such as programming, data structures and algorithms seemed to have been mechanically digested for the sole purpose of passing term-end
examinations and promptly forgotten subsequently. When I asked "Explain to me what a linked list is?", if I got an answer at all, it was usually something like "There are three kinds of linked lists, singly linked list, doubly linked lists and circularly linked lists". That's it. They knew no more about linked lists!

Over the last decade or so, I have been witness to a steady increase in the number of computer science educated candidates with absolutely zero programming skills. I dont really care who is to be blamed for the present situation, but unless we take drastic steps, developing working software is going to get increasingly difficult. For my part, I have decided to write a book on common data structures and algorithms that will help programmers connect basic concepts with their daily work... sometime later. Till then, this blog will have to do.

I will try to keep this blog light and explain the concepts as simply as I can. I will give examples from the real world wherever possible. I will leave out any references to mathematics wherever I am able explain the concepts involved without resorting to mathematics. I will avoid using bulleted lists[except in the paragraph below!] as I dont want to encourage you, the reader, to memorize the bulleted points. I will use Java as the programming language so that I can avoid all references to pesky pointers.

I would consider this blog a success, if,
1. You understand each of the data structures that I explain and will know where to use them appropriately
2. You understand each of the algorithms I cover and know why something is done the way it is.
3. You are able to identify where some of these algorithms can be applied.
4. You are able to combine these data structures and algorithms to solve the various programming tasks that you are faced with at work.

Additionally, if this blog helps you develop an interest in delving deeper into data structures and algorithms, my joy would be boundless. For those of you in whom this blog is able to infuse the passion that I have for data structures and algorithms, I will include a list of must-read books one of these days. Please feel free to read all of them, cover to cover. You will not be disappointed.

Happy programming!