Interesting combinatorics problem

I saw this problem in an old book on combinatorics I had, it took me a while to solve, but it is easy if you are familiar with the work of Euler.

Prove that an even length palindrome of integers is divisible by 11

If you know the answer - post it in the comments. If not, wait for a post by me :)

My first useful JavaScript program

I was recently going through my son's workbook and it had an interest way of teaching addition - probably the Montessori method. The idea was to create a table of sum's of a few numbers and color numbers to see a pattern. I was quite amused and decided to see if I could write the code in JavaScript, a language I am trying to learn, I am going to do some additional work like graphical Towers of Hanoi with it as well, but for now I wanted to start simple

Guess what - I succeeded in writing what I consider as a useful program (although I wrote it quite badly)

Here is the code
Here is the Javascript Here is the output

Your code is only as good as the tests you run on it

Computer programs have an interesting well known quality - even incorrect programs can produce the desired output for a subset of inputs. I recently re-learnt this while doing my graphical convex hull implementation

I started with a test strategy of random test generation. Use  a good random number generator to generate

1. Number of random points as input
2. The random points themselves

This strategy helped me test the program from crashes/instability and showed a potential functional issue that showed up when a large number of points were generated. See the diagram below

Can you spot the problem? I now need a specific test case to isolate the problem, random inputs did not provide the necessary clue with smaller inputs. Luckily for me, I found a good set of inputs at http://stackoverflow.com/questions/482278/test-case-data-for-convex-hull

I ran three test cases and found the first two ran fine

The third one was a hit, it broke my algorithm

Beautiful visualization, but the code was clearly broken. After looking at the diagram and looking at the code, I realized that I was not handling co-linear points correctly. Finally, I got

Now, I am back to the random testing strategy and have gotten satisfactory results so far

NOTE: My test feedback strategy is based on visualization, one could even automate the tests

Who inspires you?

Many of us are inspired by role models around us, in person, in media, in history, men and women who lead by example. I remember an instance - a colleague of mine was asked about role models and he was selected because he mentioned his grandfather. Other colleagues who mentioned names like Mahatma Gandhi were rejected, because in the HR's mind, a role model has to be someone you personally know. I felt those were very strong opinions to make a judgement for employment

In the past, I've had several role models

• My dad - for simplicity, integrity and courage to do the right thing and caring for others. Ability to network, empathize. Social causes and care for poor.
• My mom - for her ability to manage so many things, manage the family, swiftness, love and extreme courage. Her ability to network
• Mahatma Gandhi - For large traits of what I saw in my dad.
• Don Knuth - For being so nice, smart and humble
• Ex-leads - technical leads in my first job, software architects, distinguished engineers from whom I've learnt a lot. Learnt virtues of caring for people beyond the scope of work.
• Relatives and friends - who've stood by thick and thin, good and bad times

Today I was inspired by our security guard. His simplicity, his dedication to work and sincerity inspired me. I write this blog and dedicate it to all those who inspired me. I think we don't need to look very far for inspiration, it is right around the corner, in my case right at my doorstep.

I hope all of us find many role models who inspire us to do the right thing for ourselves and the society we build together.

The call for better reading/writing skills

I am sure you've faced it and done it to others - not read the entire email in totality or communication in full and missed parts of it. With the abundance of information comes the challenge for the new age of engineers to read and parse information completely. There is a challenge that people writing blog posts such as me, do a good job of delivering the information in manner that key points are not missed

Summary of the problem

• Of late, I've seen people ask questions already answered in the email they are replying too
• People chain emails expecting everybody to read things top to bottom
• Most people reply on top of emails. Top Posting

I think the open source community solved this problem with rules and netiquettes, but most of us who are not aware of them - fail to see the importance of communicating clearly so as to get maximum retention benefits from the audience of the communication.

In my mind, here are the best practices

• Make sure that the key information is not hidden in a paragraph, but upfront
• Try to summarize, re-emphasize
• Use best practices, netiquettes
• Don't forward or reply to long chains, clearly snip out irrelevant content
• Use smart subjects
• Highlight important points

If you are on the receiving side

• Spend some time on important emails, if required re-read
• Try to limit the amount of emails you read - batch process, don't switch too often
• Remember, email is official communication

A poor way to do sorting in an OO language (java)

Going back to Java after so many years is an interesting experience. I made the classic rookie mistake with implementation of a sorting library. All good programming practices tell you that manipulation methods on a collection should always be static and not bound to the class. To top it all, this was the first time I was using generics after spending some time reading about them :)

I had done things the other way around, almost as if I had implemented a stack with data. My ego was too big for me not to succeed with that technique. Here is an implementation of selection sort. Below is what I ended up implementing

/**
 *
 * @author balbir
 * @param 
 */
public class SelectionSort < Item extends Comparable > {
    private Item[] elements;
    SelectionSort(int N)
    {
        elements = (Item[]) new Comparable[N];    
    }

    public void sort()
    {
        int min;
        for (int i = 0; i < elements.length; i++)
        {
            min = i;
            for (int j = i+1; j < elements.length; j++)
            {
                if (elements[j].compareTo(elements[min]) < 0)
                    min = j;
            }
            Item tmp;
            tmp = elements[i];
            elements[i] = elements[min];
            elements[min] = tmp;
            
        }
    }
    
    public void dump()
    {
        for (int i = 0; i < elements.length; i++)
            System.out.print(elements[i] + " ");
        System.out.println();
    }
    
    public void load(Item a[])
    {
        for (int i = 0; i < elements.length; i++)
            elements[i] = a[i];
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Integer[] a = {1, 2, -1, 3, 0, 5, 7, 9, 4};
        SelectionSort s = new SelectionSort(a.length);
        s.load(a);
        s.dump();
        s.sort();
        s.dump();
    }
    
}

It is funny how I had to use a load class to get the data and call the sort method. What a bad decision, the reason I shared this post is just to show that with generics one can indeed mix classes and class templates. I for example mixed Integer and Comparable and the default implementation worked.

I keep going back to concrete math, but this time I went with a tool

Of late, I seem to be stuck in a loop with books. I read parts of them and then seem to come back to the very beginning of the same book and discover something new. I am stuck in a partial loop in an "open form". Of late that has happened with Concrete Mathematics. I started with the first chapter on Recurrent problems - you seen the irony :)

Anyway, one of the problems is Towers of Hanoi with limitation. Don't go to the intermediate peg directly, go to the destination peg and then go to the intermediate peg. I remember reading somewhere that Knuth used Macsyma for a bunch of verification on Metafont (I could be wrong). I decided to use Maxima. I used the solve_rec procedure

load(solve_rec);

The recurrence equation is

solve_rec(a[n] = 3*a[n-1] + 1, a[n]));


and Maxima was quick to respond with the answer

I wonder if Knuth is right, in the future most of the burden of mathematical complexity of finding a solution will be delegated to computers.

Fedora 17 EOL

For those who missed it, the notification is at Fedoa 17 EOL announcement. Looks like I'll be forced to upgrade :)

My prediction for the new wave of consumer electronics

Remember the time when new laptops/desktops were fun to have. A laptop was a must have for college (I never had one, but thanks to my brother I had a great computer, where I learnt all my programming). The new rage is now the new era of merged functionality

• Mobile
• Photos
• Email
• Maps & GPS
• Games
• Internet browsing
• Video calling

The gadgets out there are amazing, to be honest I own quite a few of them. I've had a prediction for a while on what would happen next (happen next to the laptop/notebook world). Lets look at the pros and cons of the mobile computing era devices versus laptop/desktop world

Pros

1. Easier to carry around
2. Single device to carry (integrated functionality)
3. Cheaper software licensing cost (games for $5, etc)
4. Touch capability (better user experience)
5. Growing compute and memory capacity

Cons

1. Limited storage
2. More frequent recycling
3. Not upgradable in any sense
4. Faster obsolescence
5. Harder to create content (programming to be done on laptops/desktops, documents are hard to create)
6. Very limited screen size

Gadgets are fun and most people don't care about limited storage today or content creation, but limited storage along with faster obsolescence along with limited ability to create content will help the desktop/laptop world emerge back.

My prediction based limited storage and changing laptop world (touch screen) is that the laptop world will emerge back and win again.

Operating Systems and their UI era

This afternoon as I had free time to ponder on something totally unrelated to the need of the hour, I was thinking of user interface evolution through time. I'd like to quickly classify them as

1. *NIX era
2. Desktop era//Gaming console era
3. Mobile device/Tablet/Cloud computing

NOTE: *NIX/Desktop and Mobile devices do co-exist today, but the era classification is based on popularity as read through magazine articles/online and casual discussions

The first *NIX era was a terminal era, with limited terminals (remember the phosphor screens) and wonderful keyboards that lacked (arrow keys, I just have to assume looking at the design of the original vi). The UI was quite straight forward (text), of course there were some high end workstations as time evolved. The most popular *NIXes were BSD and AT&T variants

The desktop era started with the PC and DOS. Keyboards were designed for non programmers, they were friendlier. With the introduction of GUI OS's, mice and keyboard were the primary input devices (supplemented by new generation pen & other new input techniques, but the focus was mice and keyboard). They had good GUI's, nice video and sound cards and were optimized for keyboard and mice. This lead to a sporadic growth in Internet usage, gaming. DOS/Windows/OS-X and MAC-OS variants with new design inspired from *NIX, but still different were the ruling OSes. *NIX were pushed to large systems where they would continue to run and serve large workloads as before.

The latest trend is mobile/tablet computing, this is again a market captured back by variants of *NIX (Linux - Android) and iOS (BSD) variants. Touch screen with LCD front ends with gesture awareness and multiple sensors are dominant UI inputs. It is good to see OS's designed on older principles race into the new era where voice input/GPS sensors/Cameras/touch screens/gestures are the primary interaction points with a lot of automation and simplicity built into the software on top of them. As I write, these devices are making their way into gaming consoles as well. These workloads are well supported in the back end with cloud computing work flows that provide the necessary horse power for calculating complex map routes, document editing and much more (most of these are again based on Linux servers).

I suspect the next generation will be projector driven devices, it will be interesting to see how *NIX variants will drive the next generation of computing devices.