Thursday, March 31, 2005

Subsets of a given set



I read this interesting problem in Sahni, the problem is to generate all given subsets of a set. Sahni's answer is given on the web site at solution to exercise 5. I tried to solve the problem using iteration. There are two ways to do it

  1. Convert Sahni's solution to use iteration
  2. Use the method I describe (its a bit complex, but interesting)


The solution described in (1) eventually ends up generating all possible binary numbers for a word of length n. Where n is the number of elements in the set. This method will definitely not work for multisets. I solved the problem by first coming up with a method to generate combinations of C(n, k) which prints out all combinations of n taken k at a time. I have the C# implementation of the code, if you want to see it, let me know. This method can be easily extended to handle multisets (I think!)

Here is my implementation



//
// I am not an expert C# programmer,
// I am learning the language please
// feel free to comment on the style
// and/or on the code
//
using System;

class Combo
{

int[] c; // counter for holding c1 .. ck
int k; // k of C(n, k)

Combo(int k)
{
init(k);
}

// For C(n, k), call it with k
void init(int k)
{
c = new int[k+1];
for (int i = 0; i <= k; i++)
c[i] = i;
this.k = k;
}

// prints all combinations of C(n, k)
// assuming they are in lexicographic
// order
void combination(int n, int k)
{
int j;
bool uc = false;

do {
visit();
j = k;
// counter reached max limit, increase the
// counter next in the chain
while (j > 0 && (c[j] == ((n - k) + j))) {
j--;
uc = true;
}
if (j == 0) break;
c[j]++;
if (uc) {
// reload counters
for (int i = j+1, l = 1; i <= k; i++, l++)
c[i] = c[j]+l;
uc = false;
}
} while (true);
}

void visit()
{
for (int i = 1; i <= k; i++)
Console.Write(c[i] + " ");
Console.WriteLine();
}

// Find all subsets of a set
void subset(int n)
{
for (int i = 0; i <= n; i++) {
init(i);
combination(n, i);
}
}

public static void Main(string[] args)
{
int n;
if (args.Length != 1) {
Console.WriteLine("usage is subset ");
return;
} else {
n = int.Parse(args[0]);
}

Combo p = new Combo(n);
p.subset(n);

}
}

Wednesday, March 30, 2005

CodeWorker

I found this interesting tool CodeWorker. I cannot wait to get started with it, hopefully sometime soon! If you guys start earlier, please feel free to share your experience as comments on my blog

GCC now has a Wiki

GCC now has a wiki at GCCWiki. I loved the Deadly Sins of a Compiler Writer. I think I committed most of those sins while working on my tiger clone

Monday, March 28, 2005

The Elements of Style Online


This classic has been available online for a while now. The Amazon Page for the book has reviews, sales ranking and other good information about the book.

Fascicles 1 and 2 available as books

Don Knuth's Fascicles are finally available in book form. Fascicles 1 and 2 have been released.

Sunday, March 27, 2005

References for Permutations

In the article Iterative Permutations, I mentioned about my experience with permutation generation. I would like to give further references (this list will grow)

  1. Permutation generation methods
  2. Art of Computer Programming, Fascicle 2
  3. Permutation Generation Methods (ACM paper)

Cell Phone with Built In Projector


PhysOrg.com is reporting this story on a cell phone with a built in projector. The image is taken from there. This sounds like fun, I can't wait to get hold of a device like that. The article is published here

Saturday, March 26, 2005

Tool turns English To Code


Please see
Tools Turns English To Code

Holi Hai

Today is Holi Indiatimes has a good article on the Changing colours of Holi. I played a little bit of Holi myself (unexpectedly though, I must admit), I was cornered and coloured with colours.

Unix PATH overload

Many of us, customize our shells under Unix (for the difference between Unix and UNIX - see the Art of Unix Programming). We usually add to our PATH environment variable. Usually what we do is

PATH=$PATH:[paths to add]

Lets assume this file is called .profile and is read by the shell on start-up. This approach is good, but if the user were to change our .profile and run

. $HOME/.profile

Then on seeing the PATH variable, it would have repeated path names.

If the change to PATH was

PATH=$PATH:$HOME/bin:.

The on running . $HOME/.profile for the first time the user would see PATH as

[original]:[user's home directory]/bin:.:[user's home directory]/bin:.


One easy way to work around this problem is to use the following approach in your .profile

OLDPATH=${OLDPATH=$PATH}
export OLDPATH
export PATH=
export PATH=$OLDPATH:/sbin:/usr/sbin:$HOME/bin:.

and then customize PATH as the user did previously, repeated running of
. $HOME/.profile shall now not cause the PATH environment variable to grow uncontrollably

Friday, March 25, 2005

Adobe Acrobat 7 Reader Available

This was posted on our local TUG group (TUGIndia)

Adobe have released GNU/Linux version of Acrobat Reader 7.0.
Please grab from:
ftp://ftp.adobe.com/pub/adobe/reader/unix/7x/7.0/enu/



The screenshot above is Adobe Reader 7 running on my computer. This reader seems much better than Adobe Reader 5. As you can see I am reading chapter 2 of the Linux Device Drivers 3rd Edition PDF book available for free online.

Thursday, March 24, 2005

Linux Device Drivers 3rd Edition (The Indian print is out)


The Indian Edition of LDD3 is now out. The Indian Edition is printed by Shroff Publishers. As of now, the publishers have not announced availability of the book on their web site.

Iterative permutations

I spent quite a bit of time investigating permutations. The easiest known method for generating permutations is recursion. Iterative permutations are hard but not impossible. A quick comparison showed the following results. The C/C++ code without profiling was about 4-7 times faster than the java implementation.

The profiling had an impact on the C/C++ code. Java did better with profiling.

The recursive and the non-recursive versions did almost equally well. Here are some results for lengths 10 and 12.

Java Profile


Flat profile of 17.65 secs (1569 total ticks):
main

Interpreted + native Method
0.2% 3 + 0 permu.permute
0.1% 1 + 0 permu.rpermute
0.1% 1 + 0 permu.main
0.3% 5 + 0 Total interpreted

Compiled + native Method

50.5% 792 + 0 permu.permute
49.2% 772 + 0 permu.rpermute
99.7% 1564 + 0 Total compiled

Flat profile of 0.01 secs (1 total ticks):
DestroyJavaVM

Thread-local ticks:

100.0% 1 Blocked (of total)

Global summary of 17.74 seconds:

100.0% 1577 Received ticks

java -Xprof permu 12

Flat profile of 215.68 secs (18868 total ticks):
main

Interpreted + native Method
0.0% 1 + 0 permu.rpermute
0.0% 1 + 0 Total interpreted

Compiled + native Method

50.6% 9544 + 0 permu.permute
49.4% 9323 + 0 permu.rpermute
100.0% 18867 + 0 Total compiled


C++ execution time


/usr/bin/time ./permu 10
0.23user 0.00system 0:00.31elapsed

/usr/bin/time ./permu 12
30.44user 0.20system 1:28.34elapsed



rpermute is the recursive version of the permutation generator and permute is the lexicographic permutation generator. As can be seen, the execution times are almost the same. As far as the stack size is concerned, the iterative version uses a stack size of "s" and the recursive version goes upto a worst case of "ns".

The development of rpermute is much easier compared to the iterative version

Wednesday, March 23, 2005

Visual Programming

There is a new project called GIPSpin. It talks about graphical visualization of code and thread creation.

Ramanujan's work on partitions extended

Please see Classic maths puzzle cracked at last. For those who want to know a little bit more about Ramanujan, please see Srinivasa Ramanujan There is another reference to the above mentioned article.

Friday, March 18, 2005

Bucknor vs India


In today's match, Steve Bucknor cost India dearly. The batsmen (Tendulkar) kept complaining about the bad light. In the end Bucknor gave him out when he was not, the fielding team themselves were not appealing as much. Please see Bucknor is useless. I wonder if ICC will ever take any action against such bad umpires, who are biased. He has made so many bad decisions and mostly against India. Do a google search and you will find out what many people think about him.

It is sad to say that he is the first umpire to umpire 100 tests.

Steve Bucknor, India is furious with you. Please get your act right! ICC please do something about this!

But looking at another aspect, life balances out and hopefully Sachin Tendulkar will get lucky and given not out when out. Today he was in a great nick, it could affect the end result of the match.

Google code on sourceforge

Google has released a couple of tools on sourceforge. Please see google's code website. I have not downloaded the tools or registered for using the API's yet. May be in the future?

Google seems to provide good Python support. I must start using python more.

Thursday, March 17, 2005

Yet Another Template Change

I changed my template for several reasons

  • I like the new look and feel of this template
  • I removed the sitemeter tool

Lets hope you like it better this way.

The Games Complements Play

I recently came across a program, that converted negative values to positive by using the following logic.

if (n < 0) {
n = -n;
}

It seemed correct and would work almost all the time. Why do we use the word almost. I was reading some parts of Don Knuth's famous Art of Computer Programming and the MMIX architecture


The only number that cannot be represented in signed integers of length k is 2k. The number -2k can be easily represented. What if n = -2k

Taking two's complement (add one to ones' complement of the number) of returns the same value. If you are interested in the reason for difference in the apostrophe placement for the ones' complement and two's complement - see Art of Computer Programming volume 2

Coming back to "n = -n", this code does not work for n = -2k.
The same thing has been mentioned in Andrew Koenig's C Traps and Pitfalls

Wednesday, March 16, 2005

Tendulkar joins 10,000 club


Even though his 35th century is evading him, he did join the 10,000 club. His performance has gone almost unnoticed, due to Sehwag's performance. The photo of him after getting there and a link to the story of his achievement. The story points to the location where the photo resides

I hope the Indian selector's will be patient with V V S Laxman. He is a great player and is one innings away from his display of class.

The Art of Unix Programming


I owned the book for a while, but just started reading it in detail. The book is available online at Eric's Web Page. See if you finding it interesting?

Tuesday, March 15, 2005

LDD3 is now online


I was scared that this might not happen, but it has as it did the last time. The book is available as PDF (as of now) online. Please see Linux Device Drivers, Third Edition for more details and the PDF files.

Saturday, March 12, 2005

Linux now has a security team

Please see the following email from Chris Wright. The new team talks about security disclosure, disclosure dates. This makes sense for enterprise installations and for security of Linux. The average geeky Linux programmer might complain, but I am glad to see the good things being adopted by the Linux maintainers.


Friday, March 11, 2005

Indo Pak Cricket Series



Well, the much talked about cricket series is here.

Here is my favourite picture of day 4, test 1 from rediff.com



I have a prediction for the series

  • India WILL win the test series
  • Pakistan MIGHT win the one dayer's

Monday, March 07, 2005

Blogging is addictive

Once I start blogging, I feel addicted. Blogging gives one the sense of satisfaction of sharing and expressing ones thought.

The Two Way Thought Process

Sometimes while solving a problem, I have discovered for myself that the discovery works two ways
  1. If a small problem is solved, one can generalize the solution and it becomes a learning
  2. If a generic problem is solved, one can apply it to niche areas and problems to solve complex problems
Usually, I keep oscillating between (1) and (2). However, I wonder whether one should apply (1) or (2) to a problem first? I suspect it should be (1) and the authors of Concrete Mathematics seem to agree. What do you think?

Thought for the day

Think many times before doing something that you cannot undo
Balbir Singh

Lazy Programmers Thought for the day

Why do now what you can postpone until later? Why postpone something that can be avoided all together?
anonymous

Wednesday, March 02, 2005

The C++ Programming Language

I was re-reading some portions of The C++ Programming Language especially chapter 5, I think every C/C++ programmer must read it atleast once a year.

Being good at everything (allrounder)

I think it is normal for everyone to expect a person good in one field to be generally good in others and that might be true. But I have come across people who are narrowly focused in their domain, that they might not be good at anything else. Technology is growing at such a rapid phase that it is not possible to keep up and be good at everything. So here's a suggestion

  1. Be good at what you do
  2. Use common sense everywhere else (including above)