Multi-dimensional arrays and the importance of arrangement

When I wrote about the lockers, I mentioned that the row of lockers was similar to a single dimension array. So, I guess it behooves me[I love to use words like behooves -makes my nose go up in the air, on its own accord ;^)] to talk about some array that has more than a single dimension. As people living in a 3D world, we are all quite comfortable with 2D and 3D but not quite as much with more than 3D [unless we are a theoritical physicists with a penchant for string theory] and hence I believe that understanding 2 dimensional and 3 dimensional arrays should be rather straight forward. But tell you what, in this article, let's not even go to 3D yet [or ever]. Let's make life simpler, and look at a 2D array.

Have you ever been to a small shoe shop? Most of them have at least an entire wall covered with pigeon holes that can hold a single shoe box each. From the floor to the roof, there are rows upon rows of pigeon holes. That entire wall and the bank of shelves there is what a 2D array looks like, and each pigeon hole is an element of that array. Basically, a 2D array is an array of arrays.

In a shoe shop near where I live, works a man, a short man, about 4ft tall on his toes. He is not very educated I think, definitely knows no programming, but nevertheless, can teach us a few things about data structures and algorithms and the importance of good data organization.

As a first step, he has built the 2D array of a shelf (with about 30 columns and 12 rows) on the wall. Then he has arranged the different makes, brands and models of shoes in such a way that each column of pigeon holes contain shoes of one brand and model. So far, so good. So, if we were to go in and ask to see a specific brand and model, he knows which column to go to.

Additionally, he has learnt from experience that the fastest selling shoes are those in sizes 6 through 8, and the next fastest moving sizes being children's sizes 3, 4, and 6. So what he has done is to keep all the shoes of sizes 6, 7, and 8 in pigeon holes that are at a convenient height for him [ in his case, rows 4 through 6]. Children sizes 3, 4, and 6 he has kept in rows 1, 2 and 3 [ for, he finds bending down to reach those shoes easier than having to use the ladder]. All other sizes, the slow moving ones, he has kept in rows 7 to 12. The little diagram below shows a section of the shelf and the arrangement of the shoes.


Finally, he has also used some judgement in assigning the various columns to the various brands and models. The more popular ones occupy columns that are closer to where he usually sits, near the entrance of the store, and the less popular ones occupy columns further inside the store.

In this way, he has ensured that he can access the most common brands, models and sizes with the least amount of effort.

Over the next few articles, lets take a leaf out of the shoe seller's book and look at ways of storing and arranging data so as to make our lives easier.

Deleting from Arrays

What do we do when we are done with swimming? We have a shower, take the stuff out of the locker, dress up and leave. Let us skip over the showering part and concentrate on the "take the stuff out of the locker" portion, shall we?
If we breakdown the task further, we can see that what we need to do is:
1. Find our locker
2. Remove the contents of the locker and thereby made the locker empty
3. Leave all other lockers as they were, undisturbed.

How do we find our locker? One way is to have remembered the number/location of our locker. Or the key to the locker had the locker number written on it. That way, we just go straight to the locker [ remember, the lockers are numbered sequentially, so finding the nth locker is a fairly easy step].

If we have not remembered the number of the locker, then we need to open each locker and check if it contains our stuff - a laborious and time-consuming activity.

Removing the contents of the locker is fairly easy - we transfer the contents of our locker into our hand, thereby making the locker empty.

Finally, we leave the other lockers as they are, provided, that is what we want to do. Now, supposing we had used the "fastest draw" method that we had seen earlier in Inserting into arrays part 4 to insert? Then, we may want to move the stuff in other lockers back to where they were before we inserted our stuff. To do that, we will have to repeat our activity of moving the empty locker back to where it was, pretty much the same way we moved it to where we wanted it to be. Try out the code for that yourself, if you can.

Was in IIT on Thursday.

I had a month's dose of fresh, bright faces all in 1 hour! I was in IIT Madras last thursday to address the 4th year Computer science students. It was part of their Industrial Lecture series and I talked about the "essential questions to ask when embarking on a technology startup". Basically, I wanted the students to see the startup in its native environment, namely the business world.

Quite often, as technology people, we tend to look more at the innards of the technological nucleus of the startup and, as they say, miss the woods for the trees, linked lists, arrays and other data structures. This talk was an attempt to see how the startup would need to interact, adjust and live with the outside world entities such as clients, partners, competitors, friends, guides, and VCs, in order to be successful.

The session was fairly interactive and one could see that the students were all a lot more savvy already, than I was until my second startup was spiralling down the drain. I am fairly convinced that the next inflection point in the tech. space will be driven by tech. plays initiated by some of these guys.

I kept the speech short, to about 45 minutes and then had a 15 minute Q&A session and promptly wrapped it up within the stipulated 1 hour - though I wanted to talk on for another hour or so, at least. Anyway, if it was interesting, they will call me again to talk to them and that would give me another chance.

As always, I found the experience of talking to students exhilarating. Thanks Nari, for the opportunity.

Feedback...

Two very nice people who read my blog were a little pessimistic about the chances of people using this blog and benefiting from it.
To quote one, "But really, if someone has the initiative to read the blogs,he/she could probably have read their lessons well".

There is nothing logically wrong with the sentiment. However, the ground reality is that I see a lot of people who seem reasonably smart, have had formal computer science education, and yet don't have a good grasp of the basics of programming. And the few times, I have been forced to recruit such people, I have found that creating an interest in the subject makes them better programmers quite quickly.

So, apart from a possible lack of interest in their chosen area of education, there may be other factors such as uninspired teaching, uninteresting teaching material and excessive emphasis on passing exams involved in creating graduates with no knowledge. Add to this the highly amoral "copy and paste" plagiarism culture juxtaposed with the availability of good material on the ubiquitous net and we have the perfect environment for getting degrees without gaining knowledge!

Anyway, this entry is mainly to convince myself that though there may be some truth in what the two people have said, it may not be the whole truth and so I should gamely continue to write this blog and hope that it is useful for someone somewhere in a way other than as a place to "copy & paste".

What are arrays for?

Before we go into other nice things we can do with arrays, let us look at why we need arrays at all?

Let's say, we have the ages of 6 people and we are asked to write a program to calculate mean(average). What would our program look like?
Maybe something like this:

public double calcAverageAge (int johnAge,
      int janniAge,
      int janardhanAge,
      int AmarAge,
      int AkbarAge,
      int AnthonyAge)
{
   double averageAge = (johnAge + janniAge + janardhanAge + AmarAge + AkbarAge + AnthonyAge)/6;
   return averageAge;
}

Now, supposing, we were to be asked to do the same for 100 or a 1000 people. If we continue with the way we are going, we would soon be up sh*tcreek without a paddle. What we will need is a nice way to access the ages of a 100, 1000 or any reasonable number of people using a single variable.

That is where an array comes in. With an array, our function would look like

public double calcAverageAge (int [] ages, int noOfPeople)
{
   double sumOfAges = 0;
   double averageAge = 0;
   for (int i = 0; i < noOfPeople; i++)
      sumOfAges += ages[i];
   averageAge = sumOfAges/noOfPeople;
   return averageAge;
}
public void callAverage()
{
   int noOfStudents = 100;
   int [] agesOfStudents = new int[100];
/* from file or database fill up the the ages array with values */
   double avgAge = calcAverageAge(agesOfStudents, noOfStudents);
}

As you can see, arrays provide us a nice way to handle situations where we have to access and manipulate many variables of the same data type.

Every once in a while, we should take our heads out of the details and look for the "raison d'etre", question the obvious, take a closer look at the trees, whatever.

Inserting into arrays – part 4

In the article First look at arrays we saw one more way of inserting our stuff into the locker which was nice and easy.
Quote(from the earlier article):
"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!"

Let us look at the code for that:
Already we have the findEmptyLocker function written. We shall write that function again (with a minor change) so that we don’t have to scroll all the way down to the first article to see it.

public int findEmptyLocker(int insertPos)
    {
    for (int i=insertPos; i < 10; i++)
    {
         if (arr[i].content.equalsIgnoreCase("empty"))
              return i;
     }
    return -1;
}

Now we can write the new function which we will call insertIntelligently. It looks like

public void insertIntelligently(int insertPos, String myStuff)
{
    int pos = findEmptyLocker(insertPos);
    if (pos != -1)
    {
         for (int i = pos; i > insertPos; i--)
              arr[i].content = arr[i-1].content;
         arr[insertPos].content = myStuff;
    }
}

First we find the first empty locker at or to the right of the locker we are interested in.
Once we find it, we move the contents of the locker just before the empty one into the empty one. What we have effectively done is moved the empty locker closer by one slot to where we want it to be! This is the magic I was talking about. We keep doing this until the empty locker is where we want it to be. Having done that, we come out of the for loop and then insert our stuff into the empty locker. Done.
The logic is elegant. We have not used any temporary storage/variables. The code is efficient. What more can we ask for?

The articles on arrays that we have seen so far illustrate a few basic concepts. One is that there are many ways of doing the same thing. Some ways will be better than others, so we should think of at least a few different ways of achieving our goals before comparing them and arriving at the best way forward.
Second, if we can find a real-life analogy to our algorithm, we are able to better grasp the logic behind it.
One caveat: The way we do things physically/mentally need not necessarily be the best way for the computer. Gradually we will have to learn to think in more abstract terms so that we can exploit the inherent strengths of the computer.

Arrays, indexes and memory

Before we go into the next article on inserting into arrays, I thought we could take a quick detour to answer one of the questions we had raised earlier:
Why do array indexes go from 0 to n-1 in languages like java, C, C++, etc?

In order to understand the reasons, we need to understand how memory is allocated for variables in general and arrays in particular.

Let us imagine the computer memory to be a large tract of land owned by the government. Whenever we want some land, we can approach the government and they will provide us the land we want, if available, as long as it is for a fixed time period, we agree to use it only to build temporary structures and we promise to return it back to the government when we are done using it.

When the government allocates the land to us, they ensure that no piece of it has already been allocated to anybody else. They also assume that we will not usurp/use any land outside of what has been allocated to us.

Some governments will keep a close watch to ensure that we do not build outside our area, while other more liberal governments will leave that responsibility with us.

If we have asked for place for 10 stalls and surreptitiously or unknowingly build the 11th one, we could end up building our stall on top of somebody else’s toilet, for example. Then when they use their toilet (or what used to be their toilet), they may end up pooping on our sofa creating a mess all around. This is exactly what happens when we misuse memory and overwrite some other variable – in unix the system will crash with a “core dump” message – kind of apt for our analogy, don’t you think?

We could ask for, say,
(1) 1000 sq. meters of land in order to put up my circus tent for a period of one month, or
(2) some contiguous space for a dozen 10 meters wide (and 20 meters long) stalls for me to run a carnival for the next one week.

The first request above is similar to asking for space for a primitive data type or a structure:

Int i;
Exchanger e = new Exchanger();

The second request is similar to asking for an array, and each stall is an element in that array, each element being the same size.

int [] intArray = new int[12];

The government will probably tell you that your area starts at a particular point and extends till some other point. The lease agreement will be for the period you have requested the land for (the scope of the variable).

Our location provided by the government is the starting address of our piece of land, which incidentally, in the second case, is also the starting address of our first stall.

Leaving the land analogy behind, we can now see how this maps to arrays.
The array variable contains the starting address of the entire memory that has been given to us, which incidentally, is also the starting address of the first element.
So the address of each of the elements can be calculated as
Address of first element = starting address of array + 0 * size of each element.
Address of second element = starting address of array + 1 * size of each element
Address of nth element = starting address of array + (n-1) * size of each element.

So it is only natural, in the programming world, that we give the array subscripts ranging from 0 to n-1. This is quite counter-intuitive for us [who has heard a door number 0, for example?] and thus some languages, like most variations of BASIC, have chosen to go with subscripts ranging from 1 to n. They would internally calculate the address of the different elements as
Address of first element = starting address of array + (1-1)* size of each element.
Address of second element = starting address of array + (2-1) * size of each element.
Address of nth element = starting address of array + (n-1) * size of each element.
Which as you can see is identical to the previous set of formulae.
I hope this has given you a brief idea about memory allocation and management.
Next article will be about the 3rd insertion technique I promised to write.

Inserting into array – part 3

First look at this: First look at arrays
Then look at this: Inserting into arrays – part 2
The second method of inserting that we discussed in First look at arrays was the two handed “fastest draw in the west” approach where we start with the locker where we want to keep our stuff, remove its contents with our free hand and replace it with the contents of the other hand. We continue down the row until both hands are free [that is, we find an empty locker].
Let us look at the code for that.
We will start with a class called Exchanger. Like so:

public class Exchanger {
    private String leftHand = "empty";
    private String rightHand = "empty";

This class contains one left hand and one right hand. Initially both are empty.

Then, let us write a function to make us hold our stuff in our, say, left hand.

void initialize(String myStuff)
{
    leftHand = myStuff;
}

Now, we will come to the function for the exchange of contents in locker with the contents of our hand. You may want to practice this in front of the mirror.

void moveRightByOneLocker(int pos)
{
     if (leftHand.equalsIgnoreCase("empty") == true)
     {
          leftHand = arr[pos].content;
          arr[pos].content = rightHand;
          rightHand="empty";
     }
     else // rightHand is empty
     {
          rightHand = arr[pos].content;
          arr[pos].content = leftHand;
          leftHand = "empty";
     }
}

Basically, what we are doing is as follow:
If our left hand is empty, we use that hand and pick up the contents of the locker in front of us and replace the contents with what we are holding in our right hand and if our right hand is empty, we use that hand and pick up the contents of the locker in front of us and replace the contents with what we are holding in our left hand.

Finally one more function to check if we are done, that is to check if both hands are empty:

boolean areBothHandsEmpty()
{
    if ((leftHand.equalsIgnoreCase("empty")== true) && (rightHand.equalsIgnoreCase("empty")== true))
         return true;
    else
         return false;
    }
}

Our exchanger class is ready.
Now we can call it as follows:

public void insert(int pos, String myStuff)
{
     Exchanger fastDraw = new Exchanger();
     fastDraw.initialize(myStuff);
     int startPos = pos;
     while (fastDraw.areBothHandsEmpty() == false)
     {
          fastDraw.moveRightByOneLocker(startPos);
         startPos++;
    }
}

A word of caution: I am using funny variable names in an attempt to be, um..., funny. Please use variable and function names that reflect their purpose. So, basically, what I am saying is that when it comes to variable naming, “Do as I say, not as I do”. Also, I am leaving out a lot of error checking in order to concentrate on the core functionality. As we progress, we will see how we should take care of the various possible error conditions.

In the next article, we shall see how we can move the empty locker to where we want it to be. Sheer magic.

Inserting into arrays – part 2

Today, let us write a program to insert our stuff into an empty locker. As a first step, let us just find an empty locker and put our stuff in.
Assumptions:
(1) There are only 10 lockers in the locker room, numbering 0 to 9.
(2) A locker is empty if its content contains the string “empty” in it.

Question: Why are the lockers numbered 0 – 9 instead of 1 to 10? We shall see that a little later. For now, let us just assume that they are numbered 0 – 9.

In order to put our stuff into an empty locker, we need to first find one. Assuming all the lockers are closed, irrespective of whether they are empty or not, we would have to open and inspect each locker to check whether it is empty or not. Let us do the same with our function, as below:

public int findEmptyLocker()
{
   for (int lockerPosition=0; lockerPosition < 10; lockerPosition++)
   {
       if (arr[lockerPosition].content.equalsIgnoreCase("empty"))
          return lockerPosition;
    }
    return -1;
}

Let us examine the above function closely. The for loop can be read as follows:
(1) Start from locker at position 0.
(2) Repeat the code below as long as locker position is less than 10.
(3) At the end of each loop, increment the locker position by 1.

So, first the function starts from locker 0. It checks whether its contents is equal to “empty”. If it is, the function returns the position of the empty locker [ We do not need to check further as we have found a empty locker and so the loop does not proceed further]. If not, the loop continues with locker number 1 and so on until locker number 9 [or we find an empty locker]. If no empty locker is found, it returns -1 indicating that there are no empty lockers.

Let us see how this function can be used:

public static void main(String[] args)
{
    //… some code here
    ////////////////////////////////////////////////////////////////////
    int emptyLockerPos = lockerRoom.findEmptyLocker();
    if (emptyLockerPos != -1) // that is if there is an empty locker.
       lockerRoom.arr[emptyLockerPos].content = myStuff;//put my stuff into it.
    /////////////////////////////////////////////////////////////////////
    // … some more code here
}

That’s it. Now we have found an empty locker and put our stuff into it.

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?

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!