JDSL - a good library to learn Data Structures And (some) Algorithms

I have always considered Goodrich and Tamassia's Algorithm Design as one of the best book on algorithms. It strikes a right balance by giving justice to Discrete Math (for algorithms ) , Algorithm Analysis ( O,Omega , Theta stuff ) , Data Structures (AVL,Tree, Red Black Tree etc ) , Graph and Flow Algorithms, Computational Geometry , Algorithmic Techniques (Greedy , Dynamic Programming , Divide and Conquer , Approximation algorithms , Randomized Algorithms etc ) and NP completeness.

The book contains Java code snippets in every chapter. I have thought that some code snippets are incomplete.To get the full code , download JDSL as
the book contains snippets from the JDSL library (G & T are authors of the library ).

There is an excellent tutorial available for the library and i really liked the implementation of Tree drawing sample.

Compiling Mono (C# / LINUX ) from Tar Balls on Fedora 10

I was learning more about AutoConf , Automake and GNU build conventions today. Out of curiosity , I to build the Mono system from Tar balls ( from here )

It was a 27.2 MB download. I copied it into a directory under my home directory.


tar -xvf tar_file

cd mono-20100522

./configure --prefix=/home/mono
make
su
make install

After installing the stuff , i went and modified Mono C# compiler driver (driver.cs ) to build a version of compiler with my name also in the credit. I installed the whole system by repeating the above process.

Then i changed the path environment variable ($PATH)

export PATH="/home/mono/bin:$PATH"

I re-compiled some simple programs to test the change made by me.

I also compiled SLANG4.net as well.

I plan to hack the source code base , especially LINQ implementation in the future.

GNUStep - a step towards Cocoa development

I have blogged about Objective-C Programming using the GCC run time in the past. GNUStep is a project which is trying to build a cross platform application development framework based on OpenStep standard. Sun Micro systems and Next ( Steve Job's company taken over by Apple corporation ) collaborated on the Open Step framework. When Apple bought Next , they renamed the NextStep framework in to Cocoa . Even though it is hard to port a Cocoa app into GNUstep , conversion in the opposite direction is much more easier. GNUStep also implements Foundation Framework.

if you do not have access to a MAC OS X machine and want to learn about Objective C and Cocoa , you can start with GNUstep ( on Linux or Windows ) to gain valuable exposure to Objective C language , Foundation Framework and AppKit with out much effort ( using GNUstep ).

GNUStep is available in the Debian Lenny DVDs. In Fedora , you can use "yum search GNUstep" to search for the packages to install. On Windows , you can download an installer from here.

Happy Objective C coding.

The NewYorker , Spiders of Allah are at your door steps

Some time back , I used to go to Oberon mall (@Kochi,Kerala) to visit Reliance TimeOut ( a book stall ) and there is a shelf ( full of books ) which talks about ( the dangers of ) Political Islam. One Title which caught my attention was "Spiders of Allah". (see the book's Web site @ http://www.spidersofallah.com/ )

Building a Mosque anywhere near the Ground Zero , (IMHO) will only be seen as an act of aggression by most non-muslims all over the world. Rather than building a bridge , it can divide people ( it has already divided ) .

As far as West is concerned , Christianity is a used "shirt" (like any used items , most have thrown it out ) and all across the world people are shunning religion (Even in India , most (so called) Hindus are concerned about their religious identity only when they see creeping islamic fundamentalism in political life. I do not think "Internet Hindus" are deeply religious ). Why there is a need for an Islamic center at the heart of American capitalism ?

There is a sizeable number (99% ? ) of Muslims who feel America should one day become a Islamic Theocratic state. The strategy these people employ ( which has been successfully implemented all across kerala ) is build a Mosque in a non muslim locality. This will trigger an exodus of non muslims from that area and Muslims will be ready to buy the land "vaccated" and soon , it will become a "muslim" area. Even Police will fear to go there. ( My friend has told me about BradFord , England as another example )

I think such a fate is awaiting NewYork and most part of the world. The only exception is Christian belt of Central Kerala where these people do not sell land to the Muslims.

An Instituition which is trying to stem this is Catholic Church of Kerala. They have asked Politicians symphatic to their cause to unite under a single umbrella ("United Kerala Congress")
to become the second biggest coalition partner in the future ministry of Kerala , India. Right now , a Muslim party ( which some call secular ?) is the second biggest coalition partner in the current opposition (who is supposed to get back to power soon) .

Due to "Youth bulge" among muslims in Kerala , they will form 51% of the kerala within a decade and half . The Catholic church sees it as a threat to it's existence. Some time back , some priests even asked Catholics to start procreating to maintain the demographic balance. ( Kerala is already overcrowded and cannot support these kind of compettitive religious games )

The bottom line is "Newyorkers should learn to negotiate these people who will do any thing in the name of religious cause"

Compiling Java at the Bash Command Line in MAC OS X

The Compilation of Java on MAC OS X is very similar to the way we compile Java Programs on Windows.

Javac <JavaProgram>.java

Java <JavaProgram>

//////////////////////
// SwingDemo.java
//
// javac SwingDemo.java
// java SwingDemo
//

import javax.swing.*;
import java.awt.*;

class SwingDemo
{
    public static void main(String [] args )
    {

        JFrame jfrm = new JFrame("Mac.... Window....");
        jfrm.setSize(275,100);
        jfrm.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        JLabel jlab = new JLabel("This is a text label");
        jfrm.add(jlab);
        jfrm.setVisible(true);
    }
}

Hello Objective C++

The Primary Programming Language for MAC OS X ( and iPhone ) development is Objective C. The language can be considered as a superset of C Programming language. As far as i am concerned Objective C is

"C Language " + "Run Time " + " a Domain Specific Language for manipulating this Run time";

In this case the domain is realization of Object Oriented Concepts.

Now Apple allows us to mix Objective C and C++ code in the same module ( .mm extension ). Here is a small program which demonstrates the idea. ( There are some restrictions in mixing these languages ...consult Apple's documentation on this )

///////////////////////////
// test.mm
//
// An Objective C++ Program to demonstrate
// most of the features of the language...
//
// g++ -x objective-c++ -framework Cocoa test.mm
//
// Written by Praseed Pai K.T.
//            http://praseedp.blogspot.com

#import <Foundation/Foundation.h>


//////////////////
//
//  Forward declaration of a Objective-C class
//
 @class ObjTester;


/////////////////////////
// A C++ class to test the mixing of
// Objective C and C++ code...
//


class Test { 
public:     
  /////////////////////////// 
  // A simple C++ method   
  //     

  void Say() { printf("hello from C++\n"); }

  ////////////////////////////
  // A C++ method which takes a reference    
  // to Objective C Object.    

  void Foo(id r) {     
          if ( [ r respondsToSelector:@selector(Hell) ] ) { 
                   [r Hell];       
          }  
          printf(" Finished invoking objective C method \n");
       }
};

////////////////////////
// A Protocol is similar to interface
// keyword in Java and C#
//

@protocol Spitter 
-(void)Haha;
@end


///////////////////////////////////
//
// ObjTester inherits from NSObject and
// implements Spitter protocol
//
//

@interface ObjTester : NSObject<Spitter> {
Test *t ;
}
-(id) init;
-(void)Spit;
-(void)Hell;
-(void)Haha;
@end

@implementation ObjTester

-(id) init  {
 [super init];
  t = new Test();
  return self;
}

-(void)Spit {
   t->Foo(self);
   t->Say();
}

-(void)Hell {
  printf("Hellllllll\n");
}

-(void)Haha {
  printf("Hahahahaha.....\n");
}

@end

/////////////////////////////////////////
// Entry Point.....
//
//
int main() {  
NSAutoreleasePool *pool = [NSAutoreleasePool new];
@try {    
      ObjTester *r = [ObjTester new];
      [r Spit];   
      @throw [NSException exceptionWithName:@"hello"
          reason:@"" userInfo:nil];      
}
@catch(NSException *e )  
{   
   printf("Exception thrown....\n");
   [e dealloc];;
}
@finally {  
     printf("I will always be called...\n");
}
[pool release];
return 0;

}

No , It is not Hindsight Bias

I was fortunate to sat in front of the Television set to watch Australia vs Pakistan T20 semi final match. During the middle overs , i thought Pakistan will win by a handsome margin and was about to switch off the television set. Fortunately , I did not do it and got an opportunity to watch the climax of a fantastic match.

Long back , when i was in my teens , I was playing a local tournament and opposition had lost six wickets and batsmen in the crease were well built less technically sound "sloggers". Suddenly ,The Captain of my team decided to give the ball to a Leg spinner ( who is good at Theory of spin bowling and had some success to back it against well known top order batsmen of that area. ) and I questioned this citing that Spinners are effective against top order batsmen ( as attempt to slog them can be costly...at early stage ) and for the batsmen in the crease , it is better to have a quickie. ( We had couple of genuine quickies in our team )The captain gave the ball to the spinner and it cost us 23 runs. ( For a lower order batsmen Spin bowling is something to give a whack at it )

I felt Afridi should have given the ball to a quickie.This might have made it difficult for Hussey to hit back to back balls for six runs.


Moral of the story is "It is easier to send back to back balls to stands against a spinner than a quickie "

Compiling Objective C Programs using GCC under MAC

////////////////////////
//
// first.m
// gcc -x objective-c -framework Cocoa first.m
// ./a.out
//
#import <Foundation/Foundation.h>

int main()
{
    NSObject * obj = [NSObject new ];
    return 0;

}

64 bit C/C++ Program

In a 64 bit MAC ( Unix/Linux ... ! ) program , int is 32 bit and long is 64 bit. Here is a program i wrote to test this.

////////////////////
//
// A simple MAC program
//
// g++ test.cpp
// ./a.out

#include <stdio.h>

int main()
{
printf("%d\n",(int)sizeof(int));
printf("%d\n",(int)sizeof(long));
return 0;
}

Benoy:~ Binoy$ g++ test.cpp
Benoy:~ Binoy$ ./a.out
4
8

Hello .. MAC OS X / iPhone Programming

I am blogging now using a MAC notebook which runs MAC OS X . I just wrote some Objective C Programs , 64 bit C/C++ programs using XCode and GCC ( from the command line of the terminal window ). I am using VI editor to write some
small C/C++ programs and funny fact is MAC machines do not have a insert key. I struggled for a while to key in some code into the VI editor.

After Jalapa , It is Halapa ..

When I was in School , news papers of the day used to carry news about a Jalapa. He was a influential Karnataka Minister alleged to have been responsible for the murder of a Keralite. One of my neighbhour (who went to study Engineering in Karnataka ) is
called by that name to this day.

I had almost forgotten Jalapa. Today some Halapa (Karnataka Minister ) has resigned his position as there is allegation of rape against him. May be some one from every locality in Kerala would have got that name , had the girl was from Kerala.

I have not understood on what criteria beauties are selected..

After reading a news item about some Manasvi Mamgai ( A girl who won the Miss India contest 2010 ) , I did a search on her where abouts. Her Pic seems to be very ordinary one and I am curious to learn about the factors which affect the judgement. May be , My eyes cannot spot the beauty in her ..!!!

Marriage - Why go for it ?

One day Prem and Tilak were discussing the plight of their married friends.

Prem =>"I do not see much point in marriages now a days "

Tilak => "Why did you say so ?"

Prem =>"Most marriages are a failure and their sole purpose is to prove that
Instituition of Marriage is still a viable entity ..."

Tilak => "It seems there is a point in your observation...."

Tilak =>"Why cannot we ask Raj about this ?"

Together they went to Raj and told about the discussion...

Raj =>"I do not know about others ....For me , getting a girl was just an
attempt to silence the people around me about me not getting married ..."

Why Can't Kavya act ?

Yesterday ( May 1 , 2010 ) , Prem watched malayalam movie "Benares" starring Vineeth , Navya Nair and Kavya Madhavan through a Television Channel. He was watching the movie with his mother. She liked the climax of the movie and her remark startled Prem... " she acts well.... had she acted in her life like this , she would have been able to save her marriage ..!!!!".

Kaliyug meim Kuch bhi Ho Saktha hai !

I just finished reading a story where a Granny is going to have a kid ( through a surrogate mother of course ) from her daughter's son.

Learn Graphs , You have pretty much covered DS&A !

To learn more about idiomatic C# Programming (using Generics,Lambdas,Delegates,type inferencing) , I wrote a small Graph Library. I started with Generic Vertex class , Edge class , Adjacency List , Adjacency Matrix ( I did code both ) as usual.

Then I started coding classic Depth First Traversal ( DFS ) and Breadth First Traversal of the graph with a Callback function (Delegates and Lambdas ) for processing. I implemented Recursive DFS , Iterative DFS (with custom Stack class... I know C# has a generic Stack class ) and BFS with Custom Queue class. I stored
Vertexes as a Custom List ( Generic ) .

By now , i had custom implementations of

a) Generic List
b) Generic Stack
c) Generic Queue
d) Priority Queue (Heap )
e) Graph Data structure

After coding the traversal algorithm , i proceeded to write

a) Djisktra's Shortest Path
b) All Pairs shortest Path
c) Topological Sort
d) Prim's Minimum Spanning Tree
e) Cycle Detection
f) Strongly connected Components

You will learn more about Greedy Algorithms and Dynamic Programming while coding for this. Implementing a handful of Graph Algorithms will give you great insight into pros and cons of most of the useful data structures which we use regularaly.

After writing code for three days , I began to scan through

A) Algorithm Design Manual By Skiena
B) Algorithms by Coremen , Rivest et al.
C) Algorithmics by David Harel.

Now , I can read these books very easily. It is highly recommended to learn Data Structures and Algorithms this way.

My primary source for implementation ( besides Wikipedia was )

a) Algorithms in a Nutshell (Orielly )
b) Data Structures and Algorithms using java (Robert Lafore)

For Professional assignments , I will prefer to use Boost Graph Library ( C++ ) or
QuickGraph (C# - http://quickgraph.codeplex.com/).