I, ME AND MYSELF !!!

Character Device Driver

2011-07-25T01:54:00.008+06:00

Linux Kernel Programming: Writing a simple character device driver

Probably the simplest example for a simple linux device driver is a character device driver using virtual buffer, i.e. without using any real device, a block of memory will be used to simulate the properties of a buffer.

We will be dealing only with the major device number, minor device number is used internally by the driver, but will be skipped in this example for simplicity. Also, the major number will be statically declared. I call this device "chardev", however, you can put any name you like.

Like any other kernel driver modules, it has 6 basic functionalities, among which, two are module_init and module_exit functions, namely, device_init and device_exit. The rest four functions are from file_operations structures, read, write, open and release which are accomplished by device_read, device_write, device_open and device_release functions here.

Actions of each functions are quite simple, device_init registers the device when the module is loaded and device_exit unregisters it upon removal.

device_open tracks whether the device is already open or not, and device_release may be used to free any used space, however, we are allocating memory statically, so nothing much to do here.

And finally, device_write is used to write a string to the device buffer which is in kernel space from an address which is in user space, for example, when we use `echo "hi" > /dev/chardev`, string "hi" (without quotes) will be written to device buffer. device_read is the opposite of device_write function. It is used when user space calls the device to read something from the buffer, for example `cat /dev/chardev`. Basically what it does is, just exports buffer data to a user space address.

More details of each operation and functions used here in the text books or from online resources. Now here is a simple implementation. Don't expect it to be too smart anyway.


/*
AUTHOR: Zobayer Hasan
PROGRAM: Character Device Driver
DATE: Monday, 25 July 2011
VERSION: 1.0
*/

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/moduleparam.h>
#include <linux/init.h>
#include <linux/slab.h>
#include <linux/fs.h>
#include <linux/fcntl.h>
#include <linux/stat.h>
#include <linux/types.h>
#include <linux/errno.h>
#include <asm/system.h>
#include <asm/uaccess.h>

#define DEVICE_NAME "chardev"
#define BUFFER_SIZE 1024

MODULE_LICENSE("Dual BSD/GPL");
MODULE_AUTHOR("Zobayer Hasan");
MODULE_DESCRIPTION("A simple character device driver.");
MODULE_SUPPORTED_DEVICE(DEVICE_NAME);

int device_init(void);
void device_exit(void);
static int device_open(struct inode *, struct file *);
static int device_release(struct inode *, struct file *);
static ssize_t device_read(struct file *, char *, size_t, loff_t *);
static ssize_t device_write(struct file *, const char *, size_t, loff_t *);

module_init(device_init);
module_exit(device_exit);

static struct file_operations fops = {
    .read = device_read,
    .write = device_write,
    .open = device_open,
    .release = device_release
};

static int device_major = 60;
static int device_opend = 0;
static char device_buffer[BUFFER_SIZE];
static char *buff_rptr;
static char *buff_wptr;

module_param(device_major, int, S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP);
MODULE_PARM_DESC(device_major, DEVICE_NAME " major number");

int device_init() {
    int ret;
    ret = register_chrdev(device_major, DEVICE_NAME, &fops);
    if(ret < 0) {
        printk(KERN_ALERT "chardev: cannot obtain major number %d.\n", device_major);
        return ret;
    }
    memset(device_buffer, 0, BUFFER_SIZE);
    printk(KERN_INFO "chardev: chrdev loaded.\n");
    return 0;
}

void device_exit() {
    unregister_chrdev(device_major, DEVICE_NAME);
    printk(KERN_INFO "chardev: chrdev unloaded.\n");
}

static int device_open(struct inode *nd, struct file *fp) {
    if(device_opend) return -EBUSY;
    device_opend++;
    buff_rptr = buff_wptr = device_buffer;
    try_module_get(THIS_MODULE);
    return 0;
}

static int device_release(struct inode *nd, struct file *fp) {
    if(device_opend) device_opend--;
    module_put(THIS_MODULE);
    return 0;
}

static ssize_t device_read(struct file *fp, char *buff, size_t length, loff_t *offset) {
    int bytes_read = strlen(buff_rptr);
    if(bytes_read > length) bytes_read = length;
    copy_to_user(buff, buff_rptr, bytes_read);
    buff_rptr += bytes_read;
    return bytes_read;
}

static ssize_t device_write(struct file *fp, const char *buff, size_t length, loff_t *offset) {
    int bytes_written = BUFFER_SIZE - (buff_wptr - device_buffer);
    if(bytes_written > length) bytes_written = length;
    copy_from_user(buff_wptr, buff, bytes_written);
    buff_wptr += bytes_written;
    return bytes_written;
}

/*
End of Source Code
*/

Ha, quite tiny code. obviously huge optimization and improvement await here. Now, we have assigned major number 60, before doing anything, make sure your system has not assigned 60 as a major number for any device. To check this, just use the command:


$ ls -l /dev

Just try to find out a number which is not already used as a major number (1st number) and assign it to the variable device_major, or you can do it through command line also when using insmod command to insert the module.

To compile this program, just use the following Makefile (name the file Makefile):


obj-m := chardev.o

all:
    make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) modules
clean:
    make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) clean

Note, do not copy this, you must write it by typing to avoid problems, and spaces before keyword make must be tab character. And I assumed the source file name 'chardev.c'. I am using ubuntu platform, so you might need to change this a bit, however I think it will work just fine.

To run the makefile, go to the directory it is in along with the sourcefile,


$ sudo make

If you don't get any errors, that means you have successfully compiled the source file to generate chardev.ko which is the kernel module.
Now, you need to create a device with major number 60 or what you want to assign:


$ sudo mknod /dev/chardev c 60 0
$ sudo chmod 666 /dev/chardev
$ sudo insmod chardev.ko

In mknod command, c defines that it will be a character device, then we give read+write permissions for everyone, so that the device can be usable. Then insmod command inserts chardev device in modules, you can see it in various ways, like, using `lsmod | grep chardev` or `ls -l /dev | grep chardev` or `modinfo chardev` or you can just use `dmesg` to display kernel log to see whether the loading printk printed anything (last line of the output of dmesg command).

Now it's upto you to do some experiments, like to write to device, just redirect the output of any program with a output redirect operator `>` (be careful, buffer here is allocated only 1KB). And to read from the device, open it (/dev/chardev) with any program and read from it, like, just using `cat /dev/chardev`.

Finally, when done with experimenting, you may wish to unload the driver and remove the device:


$ sudo rmmod chardev
$ sudo rm /dev/chardev

That's pretty much of it. Good luck & have fun!

Writing My Own 'ls'

2011-07-02T11:15:00.004+06:00

It was the 2nd assignment for System Programming Lab, we had to implement the "ls" directory listing program on our own.

However, it was not a hard task, but it was a bit time consuming, specially when it came around the output formatting for different type of options. We were asked to implement a limited amount of options, and all of those are short options. So, I've implemented accordingly, with some more short options, that the real "ls" has. According to most of my classmates, the real hard part seem to be implementing the "-R" i.e. recursive traversal option. But actually it is quite easy if you know how to implement a DFS algorithm.

So, it's basically simple, you start from starting parameter, use opendir() and readdir() to get the contents of the the directory, process them, and then recursively call on the child directories in a DFS fashion.

Well, there is a catch here. The dirent structure has a field "d_name" which will give you the name of the entry of a specific directory. As we know, in ls, we need various information regarding the entries which can be found using stat() or lstat() calls, which takes the path to the entry as a parameter, but not just the name. So, using the d_name directly will cause you run into troubles pretty easily (as I have seen this mistake was made commonly in lab). Obviously the first time it works if you test it on current directory (most of the cases), because, for the current directory, the relative path is actually just the entry name. So for all the other cases, you will need to provide the full path (also can be the relative path from pwd) to stat() or lstat() whatever you use.

Another thing was to follow or read symbolic links. Well, opendir() by defaults follow symbolic links, and thus this is not a problem at all. For long formatting, we had to print the target entry name as well, and readlink() did that for us. Be careful when using stat(), if a link is pointing to a directory, it will tell you that the link is also a directory, so to test whether it is actually a link, you have to use lstat().

The man page for stat() (as far as I remember, $ man 2 stat) contains a code that will show you how to use the bit flags on st_mode field. To manage everything, I created a switchboard first, then switch specific flags regarding which options are present in the argument list.

There are two more tiny works to do. for the "-1" option, you need to detect whether your output stream is tied to a terminal or not. This can be checked by isatty(fileno(stdout)), if it returns non-zero, then it is a terminal. Also, for some other options, you need to detect whether you are a super user or not. You can use geteuid() i.e. get effective user id to see if it is 0. In case you are not a super user, you will have a non-zero return.

This is pretty much the work, here is my implementation if you think it might help you.

Beginning Kernel Programming

2011-07-01T15:40:00.017+06:00

I have started to learn kernel programming shortly, well, this thing is not much interesting to me, mostly due to academic purpose.
I have been following The Linux Kernel Module Programming Guide which was suggested by our instructor. However, I've found that this one is already a bit old and I faced a lot of trouble even to see the simple yet extremely popular "hello world" on my kernel log. As I use ubuntu distribution (version 11.04), there are lot of differences inside and outside. So I have cooked the first code as followed (as in the guide, it is explained there.)


#include <linux/module.h>
#include <linux/kernel.h>

int init_module(void) {
    printk(KERN_ALERT "Hello world 1.\n");
    return 0;
}

void cleanup_module(void) {
    printk(KERN_ALERT "Goodbye cruel world 1.\n");
}

However, this goes quite well without any trouble. But I have to change the "Makefile" a bit to successfully compile this Hello World code (tabs will be expanded as spaces here).


obj-m += hello-1.o
all:
    make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) modules
clean:
    make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) clean

I'm lucky that I figured out only pwd is not working, I had to add shell instruction with it.
After this, everything went on quite well:
$ sudo make
This generated the following output with no errors:


make -C /lib/modules/2.6.38-8-generic/build M=/home/zobayer/Lab/system/kernel modules
make[1]: Entering directory `/usr/src/linux-headers-2.6.38-8-generic'
  Building modules, stage 2.
  MODPOST 1 modules
make[1]: Leaving directory `/usr/src/linux-headers-2.6.38-8-generic'

Now to install the module:
$ sudo insmod ./hello-1.ko
So I opened the file /proc/modules to check if I was successful and whoa, it was there...
The I removed it from modules:
$ sudo rmmod hello-1.ko
Now I had to make another change, when I try to open /var/log/messages as the guide suggest, I've found that there is no such file, instead, I had to open /var/log/kern.log, and at the far bottom, I've found what I had been looking for:


... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 
Jul  1 14:17:38 zobayer kernel: [   48.569441] 
Jul  1 14:17:38 zobayer kernel: [   48.569447] nouveau 0000:01:00.0: VGA-1: EDID block 0 invalid.
Jul  1 14:17:38 zobayer kernel: [   48.569452] [drm] nouveau 0000:01:00.0: DDC responded, but no EDID for VGA-1
Jul  1 14:17:38 zobayer kernel: [   48.596016] [drm] nouveau 0000:01:00.0: Load detected on output A
Jul  1 14:18:12 zobayer kernel: [   82.640352] Marking TSC unstable due to cpufreq changes
Jul  1 14:18:12 zobayer kernel: [   82.640450] Switching to clocksource acpi_pm
Jul  1 15:23:31 zobayer kernel: [ 4001.644627] hello_1: module license 'unspecified' taints kernel.
Jul  1 15:23:31 zobayer kernel: [ 4001.644636] Disabling lock debugging due to kernel taint
Jul  1 15:23:31 zobayer kernel: [ 4001.647429] Hello world 1.
Jul  1 15:24:58 zobayer kernel: [ 4088.648118] Goodbye cruel world 1.

I think I have to change many things in future, but so far, this may be a good start...

Edit: An addition by Surid vai:

Mellowhost Surid
/var/log/messages is the general log file and kern.log is the kernel log file. In redhat system, until explicitly defined, there is no kern.log, I believe that book is written based on redhat kernels, that is why they are using messages. B...ut for any system, the command "dmesg" should print those module outputs. dmesg is the kernel ring buffer log. You are using Ubuntu, this is why by default it is using kern.log

If you would like to change the kernel log file, you would need to use klogd. It is a daemon to catch and handle kernel messages. Now find how can you make the change :)

http://linux.die.net/man/8/klogd

Writing My Own Shell

2011-05-17T03:05:00.004+06:00

Hello everyone, I am back after a huge pause, actually I was busy for nothing the past few months, and felt the necessity to write something here. So I am going to note down something I recently did. I just finished writing my own shell program for linux, which is simple, doesn't support piping or redirection, but most of the features are available, so, it actually looks like the common "sh" shell. I am not going to describe the big code, you have to understand what it is doing :p
The source code. Its free to use. I have written the whole code by myself and surely I am not an expert, so if anything happens to your computer, I don't know you :p

To compile, you can use this makefile in su mode (note tab character is important).

Some features, you can invoke single commands like this:
$ doit <command [arguments...]>

Also, you can start the shell by simply calling it without any argument:
$ doit

Then it will behave like a shell program and you can give commands one by one just like a simple shell. It implements its own "cd", "pwd" and "jobs" command (you should know what they mean). You can call background processes by appending & at the end of the command... and so on. You can display resource utilizations as well. Just dig through the code, I will enhance it more if I get time :)

DP @ UVa

2011-03-19T01:03:00.012+06:00

300 DP problems from UVa, enjoy!


  103   108   111   116   147   164   166   182   231   242 
  250   323   357   431   437   473   481   495   497   507 
  526   531   559   562   580   585   590   607   647   662 
  672   674   682   702   709   714   751   757   825   828 
  836   861   882   899   900   907   909   910   926   950 
  957   959   963   970   976   983   986   988   990   991 
10003 10029 10032 10050 10051 10066 10069 10072 10074 10081 
10086 10091 10097 10100 10118 10128 10130 10131 10149 10154 
10157 10163 10192 10198 10201 10207 10239 10243 10247 10254 
10261 10271 10280 10304 10306 10313 10324 10328 10337 10359 
10364 10365 10405 10419 10444 10446 10453 10454 10465 10487 
10497 10502 10516 10518 10529 10532 10534 10536 10541 10559 
10564 10568 10590 10593 10597 10599 10604 10616 10617 10625 
10626 10634 10635 10643 10648 10651 10654 10658 10667 10681 
10684 10688 10690 10692 10694 10702 10711 10712 10715 10721 
10722 10723 10733 10739 10743 10747 10755 10759 10788 10791 
10811 10817 10819 10820 10826 10827 10835 10839 10859 10860 
10874 10888 10891 10904 10908 10910 10911 10913 10918 10930 
10934 10943 10953 10980 11002 11003 11008 11022 11026 11031 
11040 11052 11067 11069 11077 11081 11084 11088 11091 11104 
11125 11126 11133 11137 11151 11162 11169 11171 11176 11181 
11191 11218 11229 11252 11258 11259 11261 11264 11266 11280 
11282 11284 11285 11288 11293 11303 11307 11310 11311 11318 
11320 11324 11328 11341 11361 11365 11370 11372 11375 11391 
11394 11400 11404 11405 11413 11420 11421 11427 11431 11432 
11433 11441 11444 11450 11456 11471 11472 11481 11485 11486 
11499 11502 11514 11515 11517 11523 11531 11532 11534 11545 
11546 11552 11553 11555 11566 11569 11578 11584 11590 11598 
11601 11605 11611 11617 11645 11653 11691 11753 11790 11908

Courtesy: Jane Alam Jan & Felix Halim

C++ log() and log10()

2011-03-11T14:16:00.001+06:00

log (or written commonly as ln) has a great significance in the world of mathematics, however, for computer implementation on some specific cases, I am not sure which one is better.
Yesterday, I was trying to solve a problem from uva online judge where I needed to find log_ba, which is calculated as log(a) / log(b) in C++. However, doing so led to a "wrong answer". Then, just to check, rewrote that formula with an equivalent one using log10(a) / log10(b), and this time it worked fine. Really confusing, so I come to this conclusion, log (e based) is not quite precise on computer implementation, especially with gcc/g++. Because, both produces same output on my machine, but different in uva's gcc/g++ compiler. Any other reason?

3D to 2D vector?

2011-03-03T03:19:00.012+06:00

I was just curious to see some mathematical approach to justify the transformation of a 3D vector to 2D vector in the following way:
x' = y-x
y' = z-x ... ... (1)

This is quite simple and obvious, that the mapping can be performed (as shown below). Now the question is, why do we do that? As the exact answer is unknown to me, my answer is, it will be easier to handle linear systems of certain type, i.e. involving 3D vectors, as we can change them to systems of 2D vectors easily (from a programming perspective).

Here, I will denote [x, y, z] format as a 3D vector with components x, y, z and [x', y'] as a 2D vector with components x', y' where, [x, y, z] and [x', y'] satisfies the transformation showed in (1).

Lets assume we have a linear system consisting of 2 such 3D vectors:
α[x₁, y₁, z₁] + β[x₂, y₂, z₂] = [γ₁, γ₂, γ₃] ... (2)

Now if we apply the transformation from (1), we get a system of 2D vectors as follows:
α[y₁-x₁, z₁-x₁] + β[y₂-x₂, z₂-x₂] = [γ₂-γ₁, γ₃-γ₁] ... (3)

Now lets see if we can show (2) and (3) to be equivalent:

From (2), we get 3 equations:
αx₁ + βx₂ = γ₁ ... (I)
αy₁ + βy₂ = γ₂ ... (II)
αz₁ + βz₂ = γ₃ ... (III)

Similarly from (3) we get 2 equations:
α(y₁-x₁) + β(y₂-x₂) = γ₂-γ₁
α(z₁-x₁) + β(z₂-x₂) = γ₃-γ₁

It is quite obvious to see that, we can get the later 2 equations from the first set, by subtracting (I) from both (II) and (III).

Similarly, this can be extended to a more general format:
α₁[x₁, y₁, z₁] + α₂[x₂, y₂, z₂] + ... ... + α_n[x_n, y_n, z_n] = [γ₁, γ₂, γ₃]

Thus, we can conclude, (2) and (3) represents the same system. And, following this way, we can always reduce the dimensions of vectors involved in a linear system.

Additionally, if γ₁ = γ₂ = γ₃ = γ then clearly, this is more simple, as in 2D, the vector in right side will be just [0, 0].

Actually, one of my desperate friend hit me today with this, as, if we can't get the answer, he will suicide... So, this is what I told him. Unfortunately, I am not from a mathematics background, and therefore, I may have abused some mathematical terms, sorry for that, and if anyone can tell me something more details and more general about it (what should I call this? I don't know either), or, if you find this post is totally wrong, please, save my friend from committing suicide by letting me know :p

Thank you!

A C++ Mistake

2011-01-23T19:49:00.002+06:00

Consider this piece of code:


int f = 10;
int ff() {
    return f = 5;
}
int main() {
    printf("%d %d\n", ff(), f);
    return 0;
}

As I have expected it to print "5 5" (I was using Dev C++) so did I get, but I didn't know it was wrong until the judge showed me the famous and fabulous "WA". The correct output is "5 10", because, function parameters are though of to be similar as assignment operation and should be performed from right to left. Now it makes sense. But got some penalty for stupid yet adorable Dev C++. However, I've learnt this... that's the good side of it! So, you too be careful if you don't know that already.

Huffman's Code

2011-01-22T00:46:00.004+06:00

Here is a program I have written this afternoon, for one of my old friends. Basically, it's a simple one, reads character values and their frequency and generate Huffman Coding for each character. Not going to describe here what is huffman's algorithm, but it is widely used for data compression and stuff...


#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

vector< pair< string, int > > V;

class Node {
public:
    Node *left, *right;
    int weight, ch;
    Node() {}
    Node(int _w, int _c) : weight(_w), ch(_c) { left = right = NULL; }
    ~Node() {}
};

class comp {
public:
    bool operator() (const Node &a, const Node &b) {
        return a.weight > b.weight;
    }
};

void generate(const Node *a, char *code, int depth) {
    if(a->left == NULL && a->right == NULL) {
        code[depth] = 0;
        V.push_back(pair< string, int > (code, a->ch));
        return;
    }
    if(a->left != NULL) {
        code[depth] = '0';
        generate(a->left, code, depth + 1);
    }
    if(a->right != NULL) {
        code[depth] = '1';
        generate(a->right, code, depth + 1);
    }
}

int main() {
    priority_queue< Node, vector< Node >, comp > Q;
    int ch, weight;
    char code[100];

    // read ascii and frequency
    while(cin >> ch >> weight) {
        Q.push(Node(weight, ch));
    }

    // build 2-tree
    while(Q.size() > 1) {
        Node *a = new Node;
        *a = Q.top(); Q.pop();
        Node *b = new Node;
        *b = Q.top(); Q.pop();
        Node c(a->weight + b->weight, 0);
        c.left = a, c.right = b;
        Q.push(c);
    }

    // traverse tree to generate code
    generate(&Q.top(), code, 0);

    // display character and code
    for(int i = 0; i < (int)V.size(); i++) {
        cout << V[i].first << " --> " << V[i].second << endl;
    }
    return 0;
}

Writing compressor decompressor is also easy, just make sure, you use 1 bit for each '0' or '1', not 1 byte :p

Pollard's Rho in Java

2011-01-13T03:41:00.005+06:00

This is a Pollard's Rho implementation in java. Not very fast, but works for uva online judge. The reason behind using java is the default support of the BigInteger class.


import java.math.BigInteger;
import java.security.SecureRandom;
import java.io.*;
import java.util.*;

public class PollardRho {

    private final static BigInteger ZERO = new BigInteger("0");
    private final static BigInteger ONE  = new BigInteger("1");
    private final static BigInteger TWO  = new BigInteger("2");
    private final static SecureRandom random = new SecureRandom();

    static Vector<BigInteger> v = new Vector<BigInteger>();

    public static BigInteger rho(BigInteger N) {

        BigInteger divisor;
        BigInteger c  = new BigInteger(N.bitLength(), random);
        BigInteger x  = new BigInteger(N.bitLength(), random);
        BigInteger xx = x;

        if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;

        do {
            x  =  x.multiply(x).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            divisor = x.subtract(xx).gcd(N);
        } while((divisor.compareTo(ONE)) == 0);

        return divisor;
    }

    public static void factor(BigInteger N) {

        if (N.compareTo(ONE) == 0) return;

        if (N.isProbablePrime(20)) {
            v.add(N);
            return;
        }

        BigInteger divisor = rho(N);
        factor(divisor);
        factor(N.divide(divisor));
    }

    public static void main(String[] args) throws Exception {

        String string = "";
        InputStreamReader input = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(input);

        while(null != (string = reader.readLine())) {
            BigInteger N = new BigInteger(string);
            v.clear();
            factor(N);
            Collections.sort(v);
            for(int i = 0; i < v.size(); i++) System.out.println(v.get(i));
            System.out.println();
        }
    }
}

I have seen this piece of code years ago somewhere in the internet, but can't remember exactly where. So, I will be glad if anyone can comment/mail me the original source. However, for spoj, I need to write a much much better version of this in C++ :( Exam sucks life...

Java Access Modifiers

2011-01-06T14:38:00.022+06:00

Overview:

There are 4 types of access modifiers which are applicable to the members of a class, i.e. the variables and methods. Namely:

Public

Protected

Default or no modifier

Private

However, for a class declaration, protected and private are not allowed, and in a .java file, there can be only one public class, the rest must have been declared with default access. Well, we are more concerned about the access modifiers for the members of a class, as they are quite confusing on some aspects. Each of the four types is described below:

Public

As we can guess, the public members are visible from anywhere regardless of which package or file it is in. Then can be accessible from any other class of same or another package using just a '.' {dot} operator with the class reference.

Protected

This is probably most confusing modifier of java. Protected members are similar as members having default modifier, however, the difference is, protected members can be accessible outside the package it is in through inheritance, i.e. extending the parent class.

Default or no modifier

When no modifier is specified explicitly, it becomes the default modifier. Default modifiers can be thought of as a subset of the Public modifier. As, they are essentially same as Public when they are in the same package. However, members with default modifiers are not accessible from anywhere outside the package the class is in. When we don't specify a package, still there is a default package maintained by the java environment.

Private

It is also straight-forward as public, a private member can not be accessed from anywhere out side the class it is in.

More on "protected"

There are something more notable regarding protected type. As they are often very confusing with it's two near relatives, default and public.

Say, we have a "protected int x" in "class A" in package "pack1". And we derived "class B" from "class A" in package "pack2". In this case, variable x in "class B" is known as if it is just a member of "class B". so, in "class B", we can write in a method "System.out.println(x);". But note, we can't do this: "System.out.println(new A().x);". So, if the subclass is outside the package, we can't access it's parent class' protected member by a class reference. There is another interesting thing, Say, we have another "class C" which is extending the above "class B", then in "class C", we can't use 'x' as when a derived class have some protected member, it becomes a private data in the derived class, so farther extensions can not use those variables anymore.

Summery of the above

	public	protected	no modifier	private
Same class	Yes	Yes	Yes	Yes
Same package subclass	Yes	Yes	Yes	No
Same package non-subclass	Yes	Yes	Yes	No
Different package subclass	Yes	Yes	No	No
Different package non-subclass	Yes	No	No	No

I think these are the cases.

Blogger Spacing Problem

2011-01-04T14:11:00.012+06:00

Spacing problems in blogger blogs

Blogger blogs have some serious spacing issues, especially with some specific html tags, for example, if you use a <table> tag on your post, you will see it leaves a huge blank spot before and after it. Same things might happen for your <pre> or <p> tags. This is probably because blogger treats every line breaking white space to be a <br/>. However, we can easily overcome this by adding a simple css script in the post (So, we will be using the "Edit Html" option, and in my opinion, the Rich Text Editor is shit. If you are not familiar of what we are talking about, don't be afraid, you'll see, your posts are going to be just fine).

Just add the following css in your post to create a class, and name it whatever you like, I'll call it 'nobr':


<style type="text/css">
.nobr br { display: none; }
</style>

Don't worry, it will not be visible in your actual post. Now, wrap around the elements for which you don't want to see extra line gaps before and after it using this class:


<div class="nobr">
<!-- your elements -->
</div>

Here is an example for using a <table> tag using and not using the above "nobr" class:
[Not using]

Name	Age
Pulok	17
Payel	20

[using]

Name	Age
Pulok	17
Payel	20

So, the spacing problem is significantly reduced. Hope you'll give it a try!

Story of Centipede

2011-01-03T05:13:00.004+06:00

The centipede was very good at walking with its hundred legs. It never spent a thought on just how it could walk. Until one day, when a big black bug asked the centipede “How can you manage to walk with all those feet? Don’t you find it hard to coordinate their rhythm?” The black bug already left, when the centipede was still sitting down, pondering how it could walk, wondering, and (for the first time in his life) even worrying a little bit. From that day on, the centipede couldn’t walk anymore.

So you better not think too much if you want to achieve something.

SPOJ - POSTERS

2011-01-03T03:06:00.006+06:00

138. Election Posters

Although this problem is actually a good data structure problem, which is meant to be solved by range tree, but as that would need a trick. We only have 40000 nodes so total of 80000 points, but actual range is huge (10^7) for range trees. So, we can map the points so that they span over the minimum range (i.e. compress them). Sounds pathetic, right? However, there are easier ways to solve this.

By using STL set, you can make the problem pretty simulation type. Lets consider a set which contains the ranges, but not as given in input. At any moment, the set will represent the wall at that time, i.e. only visible ranges (so they must be mutually exclusive).

Now, whenever we need to add a new range, we find the leftmost poster (or piece of poster still visible) which must fall under the current one (probably you already got it, it's called lower_bound) and the rightmost poster segment that must fall under it. All the segment between these two segments will be covered, so we remove them from set. Now, we just again insert new left fragment, new right fragment and the new range... that simple it is!

Finally, we can keep and index with each segment so that we can calculate the number of actual different segment at the end of the day :)
For more clarification, consider the sample case:

5
1 4
2 6
8 10
3 4
7 10

The states of the set are shown after each input:

1 4
first entry
{(1,4)}

2 6
{1,4) is leftmost and rightmost at the same time (according to above discussion)
So, we remove it and insert new ranges:
{(1,1),(2,6)}

8 10
no conflict
{(1,1),(2,6),(8,10)}

3 4
conflicts with (2,6) (left and right both)
{(1,1),(2,2),(3,4),(5,6),(8,10)}

7 10
conflicts with (8,10)
{(1,1),(2,2),(3,4),(5,6),(7,10)}

Finally, segments with different id:
(1,1), (2,2), (3,4), (7,10). Note, (2,2) and (5,6) should have same id.

It's good if you have understood what to do, and it's even better if you don't, cause you should solve your problems on your own :p

CSE 202 Pseudo Codes 2

2011-01-02T22:16:00.006+06:00

Insert ans Delete operation on a Singly Linked List

Each Item on a Singly Linked List is formed with two fields, Info (which contains the data for the node) and Next (which is a pointer to the next Item). A pointer 'head' points the start of the linked list, and in case the linked list is empty, head has the value 'null'. Pseudo-codes for insertion and deletion at nth position is shown below:

Insert Procedure


Insert ( head, n, item )
    if n = 1 then
        temp := new Node;
        Info[temp] := item, Next[temp] = head;
        head = temp;
        return;
    ptr := head, pos := 1;
    repeat while pos + 1 < n and Next[ptr] != null
        ptr := Next[ptr], pos = pos + 1;
    temp := new Node;
    Info[temp] = item, Next[temp] = Next[ptr];
    Next[ptr] = temp;
    return;

Delete Procedure


Delete ( head, n )
    if head = null then return;
    if n = 1 then
        temp := head, head := Next[head];
        free temp;
        return;
    ptr := head, pos := 1;
    repeat while pos + 1 < n and Next[ptr] != null
        ptr := Next[ptr], pos := pos + 1;
    if Next[ptr] = null then return
    temp := Next[ptr], Next[ptr] = Next[temp];
    free temp;
    return;

Both of them handle all the possible cases on a singly linked list.

CSE 202 Pseudo Codes 1

2010-12-29T22:01:00.007+06:00

Iterative Tree Traversal

There are three types of tree traversals, namely, inorder, preorder and postorder. For some strange reasons, students @CSE-DU are forced to write iterative versions of these. I am just noting it down here again.

The Node is composed of three fields, namely, Info (data for this node), Left (pointer to left child), Right (pointer to right child). The pseudo-codes are shown below

Preorder


Preorder ( Info, Left, Right, root )
    top := 1, Stack[top] := NULL, ptr := root;
    repeat while ptr != NULL
        apply process() to Info[ptr];
        if Right[ptr] != NULL then
            top := top + 1, Stack[top] = Right[ptr];
        if Left[ptr] != NULL then
            ptr = Left[ptr];
        else
            ptr = Stack[top], top := top - 1;
    exit

Inorder


Inorder ( Info, Left, Right, root )
    top := 1, Stack[top] := NULL, ptr := root;
    repeat while ptr != NULL
        top := top + 1, Stack[top] = ptr, ptr = Left[ptr];
    ptr = Stack[top], top := top - 1;
    repeat while ptr != NULL
        apply process() to Info[ptr];
        if Right[ptr] != NULL then
            ptr := Right[ptr];
            go to step 03;
        ptr := Stack[top], top := top - 1;
    exit

Postorder


Postorder ( Info, Left, Right, root )
    top := 1, Stack[top] := NULL, ptr := root;
    repeat while ptr != NULL
        top := top + 1, Stack[top] = ptr, ptr = Left[ptr];
    repeat while Stack[top] != NULL and ptr = Right[Stack[top]]
        ptr := Stack[top], top := top - 1;
        apply process() to Info[ptr];
    if Stack[top] != NULL then
        ptr := Right[Stack[top]];
        go to step 03;
    exit

Really pointless though!

Facebook Like on Blogger

2010-12-24T14:21:00.035+06:00

Add facebook "like" on every post of your blogger blog

Where-ever you go today, you see facebook! Even, it might happen that, you have gone to market to buy some fish, and you see here and there, "Like"s are hanging aroung... People today are too much eager to be "Like"d on facebook or "Follow"ed on twitter. However, this is actually an experiment with blogger widget template, who cares if anyone likes or not on facebook. So, lets start.
If you look around on google, you will see many tutorials for this... however, here is the summery and some more detailed view.

Button Code: This is pretty much the button code:


<iframe
allowTransparency='true' frameborder='0' scrolling='no'
expr:src='&quot;http://www.facebook.com/plugins/like.php?href=&quot; + data:post.url + &quot;&amp;layout=standard&amp;show_faces=false&amp;width=500&amp;height=35&amp;action=like&amp;font=arial&amp;colorscheme=light&quot;'
style='border:none; overflow:hidden; width:500px; height:35px;'
/>

Customizing the button: There is nothing much to customize, however, the options are shown below:
If you look closely the expr:src tag, you will see the parameters, you can customize. These are:

layout=standard	show_faces=false	action=like	font=arial	colorscheme=light
standard	false	like	arial	light
button_count	true	recommend	lucida+grande	evil
box_count			segoe+ui	dark
			tahoma
			trebuchet+ms
			verdana

Placing the button: Go to "Design" from your dashboard and click on "Edit Html". Then you can see the template code of your blog. Check the "Expand Widget Templates". Now, before proceeding anymore, first take a backup of your template so that if anything happens, you can again revert it.
In your template, find the line:

<div class='post-header-line-1'/>

Then you can paste the above code (or modified one according to the above table). Then the "Like" button will appear just below the post header of every post.
Now, if you like to add it in/after post body, the next section is for you which looks like:

<div class='post-body entry-content'>

Or you can also scroll down to next section which looks like

<div class='post-footer'>

If you want to put it in footer of the post.

Preview: So, by exploring the template, you can put it anywhere... but, make sure you keep backup version of every working template.
Have fun and see the preview below when the above code is used in

<div class='post-body entry-content'>

after the

<data:post.body/>

Have fun!

About recent design changes

2010-12-20T21:15:00.005+06:00

Hello friends, as I have noticed, adding loads of external widgets make blogger very slow, so I have decided to remove all of it, even, including the SyntaxHighlighter 3.0, which have had some other problems as well. I switched back to SyntaxHighlighter 2.1 which are hosted on my free server. Now the blog is significantly fast looks prettier than it was before.

The blog stat widget I have added is now from originally google's blogger, and it is more accurate than any other third-party free hit counters or so.

However, I was eager to know is it possible to add some right panel items as different pages, not sure if it is possible or not. A few more design changes are also about to come, as I am adding some more css to the template. I will be glad to get any feedback on that.

Thanks for understanding.

getch() & getche() in gcc/g++

2010-12-10T19:12:00.014+06:00

As sometimes, we use the header "conio.h" in windows (although deprecated), sometimes we feel the need for it sometimes in linux as well, and unfortunately, in linux, i.e. in gcc/g++, there is nothing built in like "conio.h", to be more precise, getch() and getche() functions. getch() reads directly from console, without any buffering, and so does getche(). The difference between them is, getch() doesn't echo the pressed key on the screen while getche() does.

Well, it's not very hard to write your own getch() and getche() routines in linux if you know some system programming, and console attributes used in linux. All you need to do, is to stop stdin buffering before reading the character, and then restore the old settings again. Here goes the simple "conio.h" for gcc/g++:


/*
AUTHOR: zobayer
INSTRUCTION:
just make this file a header like "conio.h"
and use the getch() and getche() functions.
*/
#include <termios.h>
#include <unistd.h>
#include <stdio.h>

/* reads from keypress, doesn't echo */
int getch(void)
{
    struct termios oldattr, newattr;
    int ch;
    tcgetattr( STDIN_FILENO, &oldattr );
    newattr = oldattr;
    newattr.c_lflag &= ~( ICANON | ECHO );
    tcsetattr( STDIN_FILENO, TCSANOW, &newattr );
    ch = getchar();
    tcsetattr( STDIN_FILENO, TCSANOW, &oldattr );
    return ch;
}

/* reads from keypress, echoes */
int getche(void)
{
    struct termios oldattr, newattr;
    int ch;
    tcgetattr( STDIN_FILENO, &oldattr );
    newattr = oldattr;
    newattr.c_lflag &= ~( ICANON );
    tcsetattr( STDIN_FILENO, TCSANOW, &newattr );
    ch = getchar();
    tcsetattr( STDIN_FILENO, TCSANOW, &oldattr );
    return ch;
}

Hope this helps. Please let me know if any exception is found.

[Update:] However there is a library in gcc for some other similar functions of "conio.h", which is known as NCURSES library. Thanks to Muhammad Ridowan for letting me know this.

SPOJ Problem Classifier

2010-12-10T00:10:00.006+06:00

It's a bit hard to find a good classifier for SPOJ, for example, compared to uvatoolkit for uva onlinejudge. Well, so, far I have seen, this site is the best. Give it a try, although it does only have a small number of problems classified.

SPOJ - HORRIBLE

2010-12-09T15:54:00.011+06:00

Problem 8002. Horrible Queries

Another nice problem by Iqram Mahmud.

This is a data structure related problem and can easily be solved by segment tree / range tree. At each node of the tree, we can keep the sum of all elements that falls in the current range, i.e. children of current node, and add which is the value which must be added when we pass through this node.

So, for the update query, we just find the exact interval and add the given additional value with current sum (Node->sum += interval * value) and add (Node->add += value). Then we recursively update sum of all its ancestors (Node->sum = Left->sum + Right->sum + interval * Node->add). Similarly, we can make the second query, we just keep adding the add values of each node we pass (call it carry), then when we are in the exact range, we return current sum + interval * carry.

Be careful, indexes are 1 based and the calculation may easily overflow 32 bit integer.

Setup connector/j for JDBC

2010-12-04T21:50:00.025+06:00

Setting up MySQL driver connector/j for JDBC in Windows

This is basically not a hard task. Make sure you already have the following things installed and configured in your system, (this demonstration is targeted on the latest versions of the components):

Apache HTTP Server 2.2 (see here)
MySQL community server 5.1 (see here)
Java SE SDK aka JDK 1.6 (see here)

If you don't have these components installed yet, you might try taking some online help on how to install and configure those, not hard as well.

Now, to install java to mysql connector, which is know as connector/j, go to this page and download the windows ZIP package. Unzip the archive anywhere in your pc, it won't matter at all. Now, follow these steps:

Copy the file "mysql-connector-java-5.1.13-bin.jar" to your java installation directory and place it in "..\jdk1.6.0_21\jre\lib\ext".
Now, you have to add this runtime library to your systems classpath environment variable. Go to the properties of My Computer and select the Advanced tab, there you'll see Environment Variables. You will find all your system variables here. Find out the name CLASSPATH and append the location of connector/j i.e. where you just pasted. In my pc, its "C:\Program Files\Java\jdk1.6.0_21\jre\lib\ext\mysql-connector-java-5.1.13-bin.jar". Don't forget to separate this entry from the previous one with e semi-colon. Now click ok and close the dialogue boxes, you are done! But if you don't have the CLASSPATH variable, you need to create it yourself.

That's pretty much all of the work, now we are going to test if it works.

Lets assume that you already have a mysql database named "mysqltest" and you are the "root" user with password "adminadmin" using default host "localhost" with default http port 80, the following code should work then:


import java.sql.*;

public class Main {
    public static void main(String[] args) {
        Connection conn = null;
        try {
            Class.forName("com.mysql.jdbc.Driver") ;
            System.out.println("MySQL JDBC driver loaded ok.");

            conn = DriverManager.getConnection("jdbc:mysql://localhost/mysqltest?user=root&password=adminadmin");
            System.out.println("Connected with default port.");

            DatabaseMetaData meta = conn.getMetaData();
            System.out.println("Server name: " + meta.getDatabaseProductName());
            System.out.println("Server version: " + meta.getDatabaseProductVersion());
            System.out.println("Driver name: " + meta.getDriverName());
            System.out.println("Driver version: " + meta.getDriverVersion());
            System.out.println("JDBC major version: " + meta.getJDBCMajorVersion());
            System.out.println("JDBC minor version: " + meta.getJDBCMinorVersion());

            Statement query = conn.createStatement();
            int count = query.executeUpdate(
            "CREATE TABLE test (" +
            "id INT PRIMARY KEY NOT NULL AUTO_INCREMENT," +
            "username VARCHAR(20) NOT NULL," +
            "password CHAR(40) NOT NULL );"
            );
            System.out.println("Table created.");

            conn.close();
        } catch(Exception e) {
            System.err.println("Exception: " + e.getMessage());
        }
    }
}

As you see, you are using "DriverManager.getConnection()" method to connect it using connector/j which you previously specified by "Class.forName("com.mysql.jdbc.Driver") ;" So, make proper changes to test various things. Here, you will get some more methods of connecting and testing.

Well, if this doesn't work for you, then there must be something which is beyond the scope of this post, else "congratulations!".

CRC - 32 (IEEE)

2010-11-30T04:25:00.015+06:00

In our Data Communication Lab, we were supposed to write a CRC-32 implementation with C/C++. CRC stands for cyclic redundancy check, which is an error detection algorithm based on modulo-2 division. We used IEEE 32 bit polynomial 0x04C11DB7 to generate CRC-32 of a given string, and recheck it against the generated CRC whether an error occurred or not.

However, we looked for it in the net but could not find much information about it, probably because many languages (like php) already include functions as a built-in library to generate CRC checksum. So, I guess, people don't do these stuffs with C/C++ anymore.

The first tricky thing about generating CRC-32 is the polynomial is of 33 bits, which is an unnatural size for computers as it will need longer data type. However, after a slight observation, it becomes clear that, the 33th bit (or msb) is always 1 and thus, this is not present in the polynomial, rather, it is handled by the algorithm itself. Following the algorithm, the msb will be always 0 after we perform the XOR operation, and shifted out from the remainder. For this reason, we do not waste a bit to store that value, or add complexity to the code.

Here is my implementation goes, it is not very efficient, because, most of the implementations I have found later on in internet, use look-up tables to speed up the generation. However, this is quite simple and follow the algorithm straight:


/*
zobayer hasan
03/03/2011
*/

#include <cstdio>
#include <cstring>
using namespace std;

typedef unsigned int int32;

// key is the crc-32 ieee 802.3 standard polynomial
const int32 poly = 0x04C11DB7;
const int MAXLEN = 1024;

int32 reflect(int32 data, int bits) {
    int32 ret = 0;
    for(int i = bits-1; i>=0; i--) {
        if(data & 1) ret |= (1 << i);
        data >>= 1;
    }
    return ret;
}

int32 crc32(char* msg, int len) {
    int32 crc = 0xffffffff;
    int i, j;
    for(i = 0; i < len; i++) {
        crc ^= ((char)reflect(msg[i], 8) << 24);
        for(j = 8; j; j--) {
            crc = (crc << 1) ^ ((crc & 0x80000000) ? poly : 0x0);
        }
    }
    return reflect(crc, 32) ^ 0xffffffff;
}

int main() {
    int32 crc;
    int len;
    char msg[MAXLEN];

    gets(msg);
    len = strlen(msg);

    // generate crc32 for msg
    crc = crc32(msg, len);
    printf("CRC: 0x%08X\n", crc);
 
    return 0;
}

Here, reflect() just reverses the 'bits' number of lsb (from right) bits from 'data' passed to it.

Now, how to check consistency? It is simple, before sending message over ports, we generate the CRC and pass it with original message, in receiver end, the CRC is appended with the message and then it generates CRC again, this time, if now error has occurred, CRC will be 0.

Ahh, quite short code :)

Matrix Exponentiation

2010-11-20T14:12:00.008+06:00

Introduction:

Don't be confused with the title, this article has nothing to do with "how to calculate an exponent of a given matrix", rather it will discuss on how to use this technique to solve a specific class of problems.

Sometimes we face some problems, where, we can easily derive a recursive relation (mostly suitable for dynamic programming approach), but the given constraints make us about to cry, there comes the matrix exponentiation idea. The situation can be made more clear with the following example:

Let, a problem says: find f(n) : n'th Fibonacci number. When n is sufficiently small, we can solve the problem with a simple recursion, f(n) = f(n-1) + f(n-2), or, we can follow dynamic programming approach to avoid the calculation of same function over and over again. But, what will you do if the problem says, given 0 < n < 1000000000, find f(n) % 999983 ? No doubt dynamic programming will fail!

We'll develop the idea on how and why these types of problems could be solved by matrix exponentiation later, first lets see how matrix exponentiation can help is to represent recurrence relations.

Prerequisite:

Before continuing, you need to know:

Given two matrices, how to find their product, or given the product matrix of two matrices, and one of them, how to find the other matrix.
Given a matrix of size d x d, how to find its n'th power in O( d³log(n) ).

Patterns:

What we need first, is a recursive relation, and what we want to do, is to find a matrix [ ] which can lead us to the desired state from a set of already known states. Let, we know k states of a given recurrence relation, and want to find the (k+1)th state. Let [ ] be a k x k matrix, and we build a matrix A:[k x 1] matrix from the known states of the recurrence relation, now we want to get a matrix B:[k x 1] which will represent the set of next states, i.e. [ ] x A = B, as shown below:


      |  f(n)  |   | f(n+1) |
      | f(n-1) |   |  f(n)  |
[ ] x | f(n-2) | = | f(n-1) |
      | ...... |   | ...... |
      | f(n-k) |   |f(n-k+1)|

So, if we can design [ ] accordingly, job done!, the matrix will then be used to represent the recurrence relation.

Type 1:
Lets start by the simplest one, f(n) = f(n-1) + f(n-2).
So, f(n+1) = f(n) + f(n-1)
Let, we know, f(n) and f(n-1); we want to get f(n+1)
From the above situation, matrix A and B can be formed as shown below:
Matrix A Matrix B
| f(n) |
| f(n-1) |
| f(n+1) |
| f(n) |
[Note: matrix A will be always designed in such a way that, every state on which f(n+1) depends, will be present]
So, now, we need to design a 2x2 matrix [ ] such that, it satisfies [ ] x A = B as stated above.
The first element of B is f(n+1) which is actually f(n) + f(n-1). To get this, from matrix A, we need, 1 f(n) and 1 f(n-1). So, the 1st row of [ ] will be [1 1].
| 1 1 | x | f(n) | = | f(n+1) |
| ----- | | f(n-1) | | ------ |
[Note: ----- means, we are not concerned about this value]
Similarly, 2nd item of B is f(n) which we can get by simply taking 1 f(n) from A. So, the 2nd row of [ ] is [1 0].
| ----- | x | f(n) | = | ------ |
| 1 0 | | f(n-1) | | f(n) |
[I hope you know how a matrix multiplication is done and how the values ar assigned!]
Thus we get the desired 2 x 2 matrix [ ]:
| 1 1 | x | f(n) | = | f(n+1) |
| 1 0 | | f(n-1) | | f(n) |
If you are confused about how the above matrix is calculated, you might try doing it this way:

We know, the multiplication of an n x n matrix P with an n x 1 matrix A will generate an n x 1 matrix B, i.e. P x A = B. The k'th element in the product matrix B is the product of k'th row of the n x n matrix P with the n x 1 matrix A in the left side.
In the above example, the 1st element in B is f(n+1) = f(n) + f(n-1). So, it's the product of 1st row of matrix P and matrix B. Let, the first row of P is [x y]. So, according to matrix multiplication,
```
 x * f(n) + y * f(n-1) = f(n+1) = f(n) + f(n-1)
⇒ x = 1, y = 1
```
Thus we can find the first row of matrix P is [1 1]. Similarly, let, the 2nd row of matrix P is [x y], and according to matrix multiplication:
```
 x * f(n) + y * f(n-1) = f(n)
⇒ x = 1, y = 0
```
Thus we get the second row of P is [1 0].
Type 2:
Now, we make it a bit complex: find f(n) = a * f(n-1) + b * f(n-2), where a, b are some constants.
This tells us, f(n+1) = a * f(n) + b * f(n-1).
By this far, this should be clear that the dimension of the matrices will be equal to the number of dependencies, i.e. in this particular example, again 2. So, for A and B, we can build two matrices of size 2 x 1:
Matrix A Matrix B
| f(n) |
| f(n-1) |
| f(n+1) |
| f(n) |
Now for f(n+1) = a * f(n) + b * f(n-1), we need [a b] in the first row of objective matrix [ ] instead of [1 1] from the previous example. Because, now we need a of f(n)'s and b of f(n-1)'s.
| a b | x | f(n) | = | f(n+1) |
| ----- | | f(n-1) | | ------ |
And, for the 2nd item in B i.e. f(n), we already have that in matrix A, so we just take that, which leads, the 2nd row of the matrix [ ] will be [1 0] as the previous one.
| ----- | x | f(n) | = | ------ |
| 1 0 | | f(n-1) | | f(n) |
So, this time we get:
| a b | x | f(n) | = | f(n+1) |
| 1 0 | | f(n-1) | | f(n) |
Pretty simple as the previous one...

Type 3:
We've already grown much older, now lets face a bit complex relation: find f(n) = a * f(n-1) + c * f(n-3).
Ooops! a few minutes ago, all we saw were contiguous states, but here, the state f(n-2) is missing. Now? what to do?

Actually, this is not a problem anymore, we can convert the relation as follows: f(n) = a * f(n-1) + 0 * f(n-2) + c * f(n-3), deducing f(n+1) = a * f(n) + 0 * f(n-1) + c * f(n-2). Now, we see that, this is actually a form described in Type 2. So, here, the objective matrix [ ] will be 3 x 3, and the elements are:
| a 0 c | | f(n) | | f(n+1) |
| 1 0 0 | x | f(n-1) | = | f(n) |
| 0 1 0 | | f(n-2) | | f(n-1) |
These are calculated in the same way as Type 2. [Note, if you find it difficult, try on pen and paper!]

Type 4:
Life is getting complex as hell, and Mr. problem now asks you to find f(n) = f(n-1) + f(n-2) + c where c is any constant.

Now, this is a new one and all we have seen in past, after the multiplication, each state in A transforms to its next state in B.
f(n) = f(n-1) + f(n-2) + c
f(n+1) = f(n) + f(n-1) + c
f(n+2) = f(n+1) + f(n) + c
................................. so on
So, normally we can't get it through the previous fashions. But, how about now we add c as a state?
| f(n) | | f(n+1) |
[ ] x | f(n-1) | = | f(n) |
| c | | c |
Now, its not much hard to design [ ] according to the previous fashion. Here it is done, but don't forget to verify on yours:
| 1 1 1 | | f(n) | | f(n+1) |
| 1 0 0 | x | f(n-1) | = | f(n) |
| 0 0 1 | | c | | c |

Type 5:
Lets put it altogether: find matrix suitable for f(n) = a * f(n-1) + c * f(n-3) + d * f(n-4) + e.
I would leave it as an exercise to reader. The final matrix is given here, check if it matches with your solution. Also find matrix A and B.
| a 0 c d 1 |
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 0 1 |
[Note: you may take a look back to Type 3 and 4]
Type 6:

Sometimes, a recurrence is given like this:
```
f(n) = if n is odd, f(n-1) else, f(n-2)
In short:
f(n) = (n&1) * f(n-1) + (!(n&1)) * f(n-2)
```
Here, we can just split the functions in the basis of odd even and keep 2 different matrix for both of them and calculate separately. Actually, there might appear many different patterns, but these are the basic patterns.

Type 7:
Sometimes we may need to maintain more than one recurrence, where they are interrelated. For example, let a recurrence relation be:
g(n) = 2g(n-1) + 2g(n-2) + f(n), where, f(n) = 2f(n-1) + 2f(n-2). Here, recurrence g(n) is dependent upon f(n) and the can be calculated in the same matrix but of increased dimensions. Lets design the matrices A, B then we'll try to find matrix [ ].
Matrix A Matrix B
| g(n) |
| g(n-1) |
| f(n+1) |
| f(n) |
| g(n+1) |
| g(n) |
| f(n+2) |
| f(n+1) |
Here, g(n+1) = 2g(n) + 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n).
Now, using the above process, we can generate the objective matrix [ ] as follows:
| 2 2 1 0 |
| 1 0 0 0 |
| 0 0 2 2 |
| 0 0 1 0 |

So, these are the basic categories of recurrence relations which are used to be solved by this simple technique.

Analysis:

Now that we have seen how matrix multiplication can be used to maintain recurrence relations, we are back to out first question, how this helps us in solving recurrences on a huge range.

Recall the recurrence f(n) = f(n-1) + f(n-2).
We already know that:


[ ] x |  f(n)  | = | f(n+1) |
      | f(n-1) |   |  f(n)  |

............(1)

How about we multiply [ ] multiple times? Like this:


[ ] x [ ] x |  f(n)  | = | f(n+1) |
            | f(n-1) |   |  f(n)  |

Replacing from (1):


[ ] x [ ] x |  f(n)  | = [ ] x | f(n+1) | = | f(n+2) |
            | f(n-1) |         |  f(n)  |   | f(n+1) |

So, we finally get:


[ ]^2 x |  f(n)  | = | f(n+2) |
        | f(n-1) |   | f(n+1) |

Similarly we can show:


[ ]^3 x |  f(n)  | = | f(n+3) |
        | f(n-1) |   | f(n+2) |


[ ]^4 x |  f(n)  | = | f(n+4) |
        | f(n-1) |   | f(n+3) |


...............................
...............................
...............................


[ ]^k x |  f(n)  | = | f(n+k) |
        | f(n-1) |   |f(n+k-1)|

Thus we can get any state f(n) by simply raising the power of objective matrix [ ] to n-1 in O( d³log(n) ), where d is the dimension of square matrix [ ]. So, even if n = 1000000000, still this can be calculated pretty easily as long as d³ is sufficiently small.

Merge Sort Improvement?

2010-11-20T13:03:00.017+06:00

C++ STL uses a trick to improve the performance of merge sort. Which is, when the number of elements in a call goes down to a few 50 or something near, it uses insertion sort to sort those elements instead of recurring farther. However, this doesn't seem to be much helpful when we write the merge sort procedure manually.

Probably this happens to STL because of, being OOP nature, STL methods have huge overhead on mostly each of them, so allocating more recursive calls might turn out to be more costly than a small O(k^2) sub-routine. As we have seen on the previous posts, recursive calls of merge sort procedure creates a binary tree like structure and the deeper it goes, the number of nodes increases dramatically. Moreover, allocating new functions on call stack always has a overhead for computer systems. So, the just change the algorithm a bit so that the bottom few depths are cut from the tree reducing huge number of nodes from it, i.e. reducing huge overhead which in result, improves performance.

So they changes the algorithm of MERGE-SORT() a bit:


MERGE-SORT(A, p, r):
    if r - p < k    ;k is the tolerance limit
        INSERTION-SORT(A, p, r)
        return
    if p < r
        then q := (r + p) / 2
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q+1, r)
        MERGE(A, p, q, r)

Now, what happens when we use it manually? I tried it using a huge range and used k = 15, which means, when the number of elements are below 15, it will use insertion sort. I found interesting result in this experiment. Insertion sort seems better under certain range, but after that, it keeps getting slower. So, the value k is a tread off between the overhead of recursive calls and running time. This graph shows the result of my experiment, certainly it will vary if you try to do the same.

[click on the image to get a clear view]

Here is a simple java tester I used for this comparison. Have a look:


import java.util.*;
import java.io.*;

public class Main {

    static final boolean useInsertion = false;
    static final int limit = 15;
    
    public static void main(String[] args) throws IOException {
        Scanner stdin = new Scanner(new FileReader("in.txt"));
        PrintWriter out = new PrintWriter(new FileWriter("out.txt"));
        int n = stdin.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) a[i] = stdin.nextInt();
        out.println("Elements: " + n);
        long start = System.nanoTime();
        mergeSort(a, 0, n-1);
        long end = System.nanoTime();
        for(int i = 0; i < n; i++) out.println(a[i] + " ");
        out.println("Elapsed Time: " +(double)(end - start)/1000000.0 + "ms.");
        out.flush();
        stdin.close();
        out.close();
    }
    
    static void mergeSort(int[] a, int p, int r) {
        if(useInsertion && r-p < limit) {
            insertionSort(a, p, r);
            return;
        }
        if(p < r) {
            int q = (p + r) / 2;
            mergeSort(a, p, q);
            mergeSort(a, q+1, r);
            merge(a, p, q, r);
        }        
    }
    
    static void merge(int[] a, int p, int q, int r) {
        int n1 = q-p+1, n2 = r-q;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for(int i = 0; i < n1; i++) L[i] = a[p+i];
        for(int j = 0; j < n2; j++) R[j] = a[q+j+1];
        for(int k = p, i = 0, j = 0; k <= r; k++) {
            if(j >= n2 || (i < n1 && L[i] <= R[j])) a[k] = L[i++];
            else a[k] = R[j++];
        }
    }

    static void insertionSort(int[] a, int p, int r) {
        for(int i = p+1; i <= r; i++) {
            int t = a[i];
            for(int j = i - 1; j >= p; j--) {
                if(t > a[j]) break;
                a[j+1] = a[j];
            }
            a[j+1] = t;
        }
    }
}

Change the value of static final boolean useInsertion = false; to 'true' to enable using insertion sort and change the value of static final int limit = 15; to suitable limit, this is the number of elements when to apply insertion sort.

Keep digging!

Threaded Merge Sort

2010-09-29T00:10:00.029+06:00

What?

In my previous post about Merge Sort, the algorithm for merge sort was discussed. Although the pictures shows something which appears to be apparently parallel, but actually they are not. In fact, as the procedure introduced there was recursive, it works in a post-order fashion, meaning, first it solves the left half, then the right half, and then it works with the current range. The following picture shows the actual work-flow of the standard recursive merge sort algorithm:

The red lines and numbers shows the actual call sequence of the algorithm merge sort, for reference, the basic algorithm, is shown here again:


MERGE-SORT(A, p, r):
    if p < r
        then q := (r + p) / 2
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q+1, r)
        MERGE(A, p, q, r)

So, from the above example, we can see that no two calls are concurrent, i.e. parallel. Each call is one of the three calls made in MERGE-SORT(A, p, r) procedure stated above, also shown below (according to the picture, p=0, r=6):


Step-00: MERGE-SORT(A, 0, 6)
Step-01: MERGE-SORT(A, 0, 3)
Step-02: MERGE-SORT(A, 0, 1)
Step-03: MERGE-SORT(A, 0, 0)
Step-04: MERGE-SORT(A, 1, 1)
Step-05: MERGE(A, 0, 0, 1)
Step-06: MERGE-SORT(A, 2, 3)
Step-07: MERGE-SORT(A, 2, 2)
Step-08: MERGE-SORT(A, 3, 3)
Step-09: MERGE(A, 2, 2, 3)
Step-10: MERGE(A, 0, 1, 3)
Step-11: MERGE-SORT(A, 4, 6)
Step-12: MERGE-SORT(A, 4, 5)
Step-13: MERGE-SORT(A, 4, 4)
Step-14: MERGE-SORT(A, 5, 5)
Step-15: MERGE(A, 4, 4, 5)
Step-16: MERGE-SORT(A, 6, 6)
Step-17: MERGE(A, 4, 5, 6)
Step-18: MERGE(A, 0, 3, 6)

Also note that, there are no overlapping calls at a same level of the tree, which is going to be a key factor.

How threading helps:

After a few observations, we can easily find out some interesting properties about merge sort algorithm. If we closely look at the merge sort tree structure, it becomes very clear that, int the recursive call tree, parent nodes depend on children, but siblings are independent. This property helps us to deduce a threaded version of merge sort algorithm where, we can really solve the left and right sub-portion of a range in a parallel fashion by making the calls threaded.

As the algorithm here is recursive, it might look confusing at the first glance, but it is not. Because, nodes share data only with their ancestors and in a call, we can wait until the threads finish their works. So, no concurrency problem appears here. Also, we don't need to worry about mutual exclusion of the shared data, because, there is no such situation in this algorithm, already stated above.

So, the threaded version of the algorithm will look like this:


THREADED-MERGE-SORT(A, p, r):
    if p < r
        then q := (r + p) / 2
        start_thread(left_thread, THREADED-MERGE-SORT(A, p, q))
        start_thread(right_thread, THREADED-MERGE-SORT(A, q+1, r))
        wait_for(left_thread)
        wait_for(right_thread)
        MERGE(A, p, q, r)

According to the above algorithm, the flow of program changes which is shown in the picture below:

Now because of being able to run multiple THREADED-MERGE-SORT() at a time, and the job scheduling features of modern computers, the effective number of iteration is dramatically reduced, resulting a much much elegant solution for the heavy duty areas like manipulating large data on drives.

A simple implementation:

Here a simple implementation is presented using pthread library in C++:


#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

typedef struct { int i, j; } pair;
const int MAX = 1024;
int a[MAX];
pthread_attr_t attr;

void *threaded_merge_sort(void *param) {
    pair range = *(pair *)param, lrange, rrange;
    pthread_t lside, rside;
    int p = range.i, q, r = range.j, n1, n2, n = r-p+1, i, j, k;
    int *aleft, *aright;
    if(p < r) {
        q = (p + r) >> 1;
        lrange.i = p, lrange.j = q, rrange.i = q + 1, rrange.j = r;
        pthread_create(&lside, &attr, threaded_merge_sort, (void *)&lrange);
        pthread_create(&rside, &attr, threaded_merge_sort, (void *)&rrange);
        pthread_join(lside, NULL);
        pthread_join(rside, NULL);
        n1 = q - p + 1, n2 = r - q;
        aleft = (int *)malloc(sizeof(int) * n1);
        aright = (int *)malloc(sizeof(int) * n2);
        for(i = 0; i < n1; i++) aleft[i] = a[p+i];
        for(i = 0; i < n2; i++) aright[i] = a[q+1+i];
        for(k = i = j = 0; k < n; k++) {
            if(i >= n1 || (j < n2 && aleft[i] > aright[j])) a[k+p] = aright[j++];
            else a[k+p] = aleft[i++];
        }
        free(aleft);
        free(aright);
    }
    return NULL;
}

int main() {
    int n, i;
    pthread_t sorter;
    pair range;
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
    while(scanf("%d", &n)==1 && n) {
        for(i = 0; i < n; i++) scanf("%d", &a[i]);
        range.i = 0, range.j = n-1;
        pthread_create(&sorter, &attr, threaded_merge_sort, (void *)&range);
        pthread_join(sorter, NULL);
        for(i = 0; i < n; i++) printf("%d%c", a[i], (i==n-1? '\n' : ' '));
    }
    pthread_attr_destroy(&attr);
    return 0;
}

This may look a bit messy, but, actually, you may find a little difference with the original one, we just created threads instead of plain recursive calls, that's it.
To learn more about pthread, check these out:

Give it a try! :)

Merge Sort

2010-08-19T20:31:00.015+06:00

Introduction:

Merge-sort is based on the divide-and-conquer paradigm. The Merge-sort algorithm can be described in general terms as consisting of the following three steps:

Divide Step: If given array A has zero or one element, return S; it is already sorted. Otherwise, divide A into two arrays, A1 and A2, each containing about half of the elements of A.

Recursive Step: Recursively sort array A1 and A2.

Conquer Step: Combine the elements back in A by merging the sorted arrays A1 and A2 into a sorted sequence.

This diagram below shows the divide and conquer (or merging) steps stated above. We can visualize Merge-sort by means of binary tree where each node of the tree represents a recursive call and each external nodes represent individual elements of given array A. Such a tree is called Merge-sort tree. The heart of the Merge-sort algorithm is conquer step, which merge two sorted sequences into a single sorted sequence. This simple but amazing algorithm and a straight forward C++ implemented is presented below, and some cool links are added in the "Reference" section at the end of the post.

Algorithm:

Input: Array A[p...r], indices p, q, r (p ≤ q < r).
Output: Array A[p...r] in ascending order


MERGE-SORT(A, p, r):
    if p < r
        then q := (r + p) / 2
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q+1, r)
        MERGE(A, p, q, r)

MERGE(A, p, q, r):
    n1 := q - p + 1
    n2 := r - q
    create arrays L[1...N1+1] and R[1...N2+1]
    for i := 1 to N1
        do L[i] := A[p + i - 1]
    for j := 1 to N2
        do R[j] := A[q + j]
    L[N1 + 1] := INF
    R[N2 + 1] := INF
    i := 1
    j := 1
    for k := p to r
        do if L[i] <= R[j]
            then A[k] := L[i]
                i := i + 1
            else
                A[k] := R[j]
                j := j + 1

Follow this link to see a javascript demonstration that simulates the above algorithm.

Analysis:

In sorting n objects, merge sort has an average and worst-case performance of O(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists) and the closed form follows from the master theorem.

Simple proof:
The merge sort algorithm created a complete binary tree, which have d depth and at each level, a total of n elements.
So, 2^d ≈ n, which implies d ≈ lg n
Now the total numbers of operation in merge sort algorithm is:
n * 2d ≈ 2n lg n ≈ O(n lg n)

In the worst case, merge sort does an amount of comparisons equal to or slightly smaller than (n ⌈lg n⌉ - 2^{⌈lg n⌉} + 1), which is between (n lg n - n + 1) and (n lg n + n + O(lg n)).

In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case. Merge sort always makes fewer comparisons than quicksort, except in extremely rare cases, when they tie, where merge sort's worst case is found simultaneously with quicksort's best case. In terms of moves, merge sort's worst case complexity is O(n log n) — the same complexity as quicksort's best case, and merge sort's best case takes about half as many iterations as the worst case. Although, depending on the machine's memory architecture, quick sort can sometimes outperform merge sort, which is a very rare case.

Recursive implementations of merge sort make 2n - 1 method calls in the worst case, compared to quicksort's n, thus merge sort has roughly twice as much recursive overhead as quicksort. However, iterative, non-recursive, implementations of merge sort, avoiding method call overhead, are not difficult to code. Merge sort's most common implementation does not sort in place; therefore, the memory size of the input must be allocated for the sorted output to be stored in.

Merge sort as described here also has an often overlooked, but practically important, best-case property. If the input is already sorted, its complexity falls to O(n). Specifically, n-1 comparisons and zero moves are performed, which is the same as for simply running through the input, checking if it is pre-sorted.

Although heap sort has the same time bounds as merge sort, it requires only T(1) auxiliary space instead of merge sort's T(n), and is often faster in practical implementations. In case in-place sorting is necessary (Merge sort can be implemented as in-place algorithm, but the performance gain is not worth the complexity of the program, however, still merge sort runs in O(n lg n) time), heap sort is a better choice.

C++ Implementation:

Call Merge_Sort(A, start, end) to sort the closed range [start, end] of the array A.


void Merge(int A[], int p, int q, int r) {
    int i, j, k, n1 = q - p + 1, n2 = r - q;
    int L[n1], R[n2];
    for(i = 0; i < n1; i++)
        L[i] = A[p + i];
    for(j = 0; j < n2; j++)
        R[j] = A[q + j + 1];
    for(k = p, i = j = 0; k <= r; k++) {
        if(j >= n2 || (i < n1 && L[i] <= R[j])) A[k] = L[i++];
        else A[k] = R[j++];
    }
}

void Merge_Sort(int A[], int p, int r) {
    if(p < r) {
        int q = (p + r) / 2;
        Merge_Sort(A, p, q);
        Merge_Sort(A, q+1, r);
        Merge(A, p, q, r);
    }
}

For implementations in other languages, this page contains the implementation of merge sort procedure in almost all the living languages of the world: http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort

Reference:

Introduction To Algorithms (CLRS, MIT Press, 2^nd Edition): Chapter 2, Section 2.3.1 - The divide-and-conquer approach.
http://en.wikipedia.org/wiki/Merge_sort
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/mergeSort.htm

Thanks for reading.

Simple Take Away Game

2010-08-04T03:13:00.008+06:00

Combinatorial games are two-player games with an outcome (i.e. it cannot end in a draw) and the players move alternatively from one position to other position depending on their move and finally reach a terminal position. When a player reaches the terminal position, the winner is decided based on the type of game play.

There are two types of game plays – normal play and the misère play .In a normal play , the one who moves the game to the terminal position is the winner and in a misère play , the one who moves the game to the terminal position is a loser.And if the rules of the game are same for both the players , then its a impartial game and when the rules are different for the two players , then its a partisan game.An common example of partisan game is a game of chess.

Take Away Game :

A take away game is a impartial combinatorial game where there is a single pile with n chips and players remove a certain number of chips from the pile depending on the rules of the game.Let us for the ease of analysis consider a normal play where the one who takes the game to the terminal position wins the game.

Consider a pile of n chips and say the rules of the game are given

N={0,1,2,3,..,n} be the positions that the game can be and a 0 signifies a terminal position and a n signifies a starting position

S={1,3,4} be the possible set of moves

A player can take away ‘x’ chips from the current pile where x € {S}.

Say we need to analyze the game given n and S .By analysis what we mean is given n and S and assuming optimal play, who wins the game.To analyze the game we define two positions namely N position where the Next player to play wins and P position where the Previous player to have played wins.So a game ideally starts with either a P or a N position but always ends in a P position.

So we arrive at the following rules which can be recursively used to define the P and N positions.

All terminal positions are P positions in a normal play.

From an P position, any move takes us to a position.

From a N position, we can reach a P position in at least one possible way so that we emerge the final winner.

If the game starts with P position , the second player to play wins because, from P position the game can move to only to N position and the Second player wins by taking the game again to a P position according to the Rule 3 stated above(this is called playing optimally).
If the game starts with a N position , the current player wins the game by taking the game always to a P position.

So Let S be {1,3,4} for our analysis.
We use the following Algorithm to classify the P and N positions of {0,1,2,… n}.

Step 1: Label every terminal position as a P-position.

Step 2: Label every position that can reach a labeled P-position in one move as an N-position.

Step 3: Find those positions whose only moves are to labeled N-positions; label such positions as P-positions.

Step 4: If no new P-positions were found in step 3, stop; otherwise return to step 2

So we begin by adding ‘0′ to P position and let set P={0} denote the currently recognized P positions .By using Step 1, { 1,3,4} are decided to be N positions and analyzing the next number in the close proximity , we take ‘2′.

‘2′ has only one transition and its to a N position so 2 gets added to P and 1,3,4 gets added to N in this iteration. Now moving to the next iteration, 5(2+3) and 6(2+4) are N positions and analyzing for 7, we have the possible transitions as 6,4,3 which are all N positions and hence 7 gets added to P
hence at the end of second iteration, P={0,2,7} and N={1,3,4,5,6} . On continuing further, we get the following

P={0,2,7,9,14,16,21,23….} and N={1,3,4,5,6,8,10,11,12,13,15,17,18,19,20….}

So generalizing all positions which leave a remainder of 0 or 2 on dividing by 7 are P positions and others are N positions.

So say we have 21 chips then we are asked to comment on the winner assuming the optimal game play, we can conclude from the above derivations that 21 is a P position so the second player can win if he plays optimally . Say i start with 21 , the possible moves are 20,18,17 which are all N positions . Say we move to one of these

17 can move to 16,14,13 (14,16 are both P position)
18 can move to 17,15,14 (14 is a P position)
20 can move to 19,17,16 ( 16 is a P position)

For all the above cases , we observe that there is a possible transition that the second player can make such that the game proceeds to a P position and the cycle continues and finally the second player comes to a N position which could be either 1,3,4 so that the second player makes a suitable move and moves to 0 winning the game. If the Second player at any stage makes a non-optimal move , the game goes temporarily out of his control and he may or may-not win the game.

Another Example from SPOJ :

Let us analyze this Problem from SPOJ NGM which can actually be found here.

The problem states that a number n is taken and the player take turns and subtract the number by any one of its non zero digits.And the one who makes this number ‘0′ wins the game .The two players are Nikofir and Trofim. This problem helps us understand the above discussed concepts.

Analysis :

We start by adding 0 to P and 1,2,3,4,5,6,7,8,9 all lead to 0 directly hence are added to N . Now we analyze 10 which goes to 9 alone which is a N position and gets added to P . So at end of one iteration,

P={0,10) N=(1,2,3,4,5,6,7,8,9} .

Next the following numbers {11,12,13,14,15,16,17,18,19 }all have one possible move to {0,10} so they belong to N and the next P number is 20 proceeding we fins tht P is a set of multiples of 10

P={ x| x is a multiple of 10}

N={x | x is not a multiple of 10}

So given number which is not a multiple of 10 it is in N position and the player who plays first always wins i.e. Nikofir wins always .

If the given number is a multiple of 10 , then its in P position and Trofim wins.

Stress on Optimal Play :

Why do we need to analyze an optimal play? The need for all this analysis is to make the computer make the best move at the current position so that it poses a challenge to the player who plays and if the player gets lucky, he can take advantage of these analysis to make a winning move.

Binary Tree -- N Nodes & H Height

2010-08-04T02:42:00.009+06:00

The problem:

You are told that you have N unique numbers, how many different binary trees are possible with those N numbers (i.e. nodes) which has exactly H height.

Analysis:

If we look closely, it will be not that hard to figure out that, the problem actually wants to know, how many different binary trees are possible to build with N nodes, each of which has exactly H height allowing rotations. Here, two trees are different when their structures are different. For example:


           @                   @
          / \                 / \
         @   @      and      @   @
        / \                     / \
       @   @                   @   @

Solution:

I don't know whether this problem has a mathematical solution or not, I have searched for it and found nothing... But, if the values N and H supports, this problem can be solved with a dynamic programming approach.

When we want to build a tree with N nodes and H height, we can select a node as a root, so, we can put 1 to N-2 nodes on the left subtree of height H-1 or less and N-2 to 1 nodes on the right subtree of height H-1 or less, satisfying that, at least one of the subtree has a height H-1. So, by using proper base condition, we can find the number of different trees of exactly H height from this recursive formulation, and we can express the relation as follows,


if k == 1 then exactTrees( N, D ) = ( n == 1 )
if n <= 1 then exactTrees( N, D ) = 0
for all {L, R} such that L, R > 0 and L + R = N - 1:
exactTrees( N, D ) += exactTrees( L, D - 1 ) * exactTrees( R, D - 1 )
exactTrees( N, D ) += smallerTrees( L, D - 2 ) * exactTrees( R, D - 1 )
exactTrees( N, D ) += exactTrees( L, D - 1 ) * smallerTrees( R, D - 2 )

This is pretty obvious, because, if we want to get a tree of height H from any node, either one or both of its subtrees must have a height H - 1, and if we have N nodes at any step, we need to take 1 node as root, and then if we take i nodes for left subtree, we have N - 1 - i nodes left for the right subtree.
When we calculate exact height, we need to consider that a subtree may have a smaller height, so we need to calculate smallerTrees( N, D ) separately, but actually it is a bit easier:


if n < 0 or k <= 0 then smallerTrees( N, D ) = 0
if k == 1 then smallerTrees( N, D ) = ( n == 1 )
if n <= 1 then smallerTrees( N, D ) = 1
else
for all {L, R} such that L, R > 0 and L + R = N - 1:
smallerTrees( N, D ) += smallerTrees( L, D - 1 ) * smallerTrees( R, D - 1 )

Sample program:

First one goes the recursive algorithm (with dp):


// states: nodes, height
int exact[202][101], smaller[202][101];

int smallTrees(int n, int k)
{
    if(n<0 || k<=0) return 0;
    if(k==1) return n==1;
    if(n<=1) return 1;
 
    int &ret = smaller[n][k], l, r;
    if(ret!=-1) return ret;
 
    ret = 0;
    for(int i=1; i<n-1; i++)
    {
        l = i, r = n-1-i;
        if(l && r)
        {
            ret += smallTrees(l, k-1)*smallTrees(r, k-1);
        }
    }
    return ret;
}

int exactTrees(int n, int k)
{
    if(k==1) return n==1;
    if(n<=1) return 0;

    int &ret = exact[n][k], l, r;
    if(ret!=-1) return ret;
    ret = 0;
    for(int i=1; i<n-1; i++)
    {
        l = i, r = n-1-i;
        if(l && r)
        {
            ret += exactTrees(l, k-1)*exactTrees(r, k-1);
            ret += exactTrees(l, k-1)*smallTrees(r, k-2);
            ret += smallTrees(l, k-2)*exactTrees(r, k-1);
        }
    }
    return ret;
}

Here is the iterative version (a little complex):


// states: height, nodes
int exactTrees[101][202], smallTrees[101][202];

void solve(int n, int k)
{
    int d, i, j;
    exactTrees[1][1] = 1;
    for(d=2; d<=k; d++) // depth
    {
        for(i=1; i<=n; i+=2) // number of nodes
        {
            for(j=1; j<=i-1; j+=2) // left & right
            {
                exactTrees[d][i] += exactTrees[d-1][j]*exactTrees[d-1][i-1-j];
                exactTrees[d][i] += exactTrees[d-1][j]*smallTrees[d-2][i-1-j];
                exactTrees[d][i] += smallTrees[d-2][j]*exactTrees[d-1][i-1-j];
            }
        }
        for(i=1; i<=n; i+=2) // update smaller tree
        {
            smallTrees[d-1][i] += smallTrees[d-2][i]+exactTrees[d-1][i];
        }
    }
}

[P.S. The result of this problem grows very rapidly along with the increase of N and H, so, it may easily run out of range, normally problems like this requires the result with respect to some modulus values.]

BrainF**k & C++

2010-06-11T16:10:00.005+06:00

Here is my bf to C translator, so I can write some bf sh*ts and test easily on my VC++08. To run the program with command line, _NO_ARGS must be cleared with 0.


#define _CRT_SECURE_NO_WARNINGS 1
#define _NO_ARGS 0
#include <stdio.h>

FILE *fin, *fout;

void print(char *str, int tab);
int unknown(char ch);

int main(int argc, char **argv) {
    char ch, pr, temp[1024];
    int tab = 0, cnt, carr;
    if(_NO_ARGS) {
        scanf("%s", temp);
        fin = fopen(temp, "rb");
        scanf("%s", temp);
        fout = fopen(temp, "wb");
    }
    else if(argc < 2) {
        printf("insufficient arguments...\n");
        return 1;
    }
    else if(argc < 3) {
        fin = fopen(argv[1], "rb");
        fout = fopen("noname.c", "wb");
    }
    else {
        fin = fopen(argv[1], "rb");
        fout = fopen(argv[2], "wb");
    }
    if(!fin || !fout) {
        printf("file error...\n");
        return 2;
    }
    print("#include <stdio.h>", tab);
    print("", tab);
    print("char buff[1024];", tab);
    print("", tab);
    print("int main() {", tab++);
    print("char *p = buff;", tab);
    pr = 0;
    cnt = 0;
    carr = 0;
    while((ch=fgetc(fin))!=EOF) {
        if(unknown(ch)) continue;
        if(ch=='.' || ch==',' || ch=='[' || ch==']') {
            if(carr) {
                if(pr=='+') sprintf(temp, "(*p) += %d;", cnt);
                else if(pr=='-') sprintf(temp, "(*p) -= %d;", cnt);
                else if(pr=='>') sprintf(temp, "p += %d;", cnt);
                else if(pr=='<') sprintf(temp, "p -= %d;", cnt);
                carr = cnt = 0;
                print(temp, tab);
            }
            if(ch=='.') print("putchar(*p);", tab);
            else if(ch==',') print("*p = getchar();", tab);
            else if(ch=='[') print("while(*p) {", tab++);
            else if(ch==']') print("}", --tab);
        }
        else if(ch==pr || !carr) {
            carr = 1;
            cnt++;
        }
        else {
            if(pr=='+') sprintf(temp, "(*p) += %d;", cnt);
            else if(pr=='-') sprintf(temp, "(*p) -= %d;", cnt);
            else if(pr=='>') sprintf(temp, "p += %d;", cnt);
            else if(pr=='<') sprintf(temp, "p -= %d;", cnt);
            carr = cnt = 1;
            print(temp, tab);
        }
        pr = ch;
    }
    if(carr) {
        if(pr=='+') sprintf(temp, "(*p) += %d;", cnt);
        else if(pr=='-') sprintf(temp, "(*p) -= %d;", cnt);
        else if(pr=='>') sprintf(temp, "p += %d;", cnt);
        else if(pr=='<') sprintf(temp, "p -= %d;", cnt);
        print(temp, tab);
    }
    print("return 0;", tab);
    print("}", --tab);
    fclose(fin);
    fclose(fout);
    return 0;
}

void print(char *str, int tab) {
    int i;
    if(str[0]) {
        for(i=0; i<tab; i++) fputc('\t', fout);
        for(i=0; str[i]; i++) fputc(str[i], fout);
    }
    fputc('\n', fout);
}

int unknown(char ch) {
    switch(ch) {
        case '+':
        case '-':
        case '<':
        case '>':
        case '.':
        case ',':
        case '[':
        case ']': return 0;
        default : return 1;
    }
    return 1;
}

Here is a sample bf code I have written just now, and here is the translated C code.
But no matter the size, bf is really fun!!!

Euler Tour

2010-06-04T15:05:00.010+06:00

A famous drawing problem for kids, "You are given a picture, can you draw it without lifting up your pen?"... Well, in graph theory, we can determine this by checking the Euler Tour in the graph.

Actually this is about Euler Circuits and Eluer Paths. We know the conditions for an undirected graph, and we can extend it for directed graphs as well.

Undirected Graph

An undirected graph will have Eulerian tour ( either path or circuit ) if the following conditions hold:

The graph is connected.
Each node has even degree, or exactly two nodes have an odd degree.

Directed Graph

A directed graph will have Eulerian tour ( either path or circuit ) if the following conditions hold:

The undirected representation of the graph is connected.
The difference between indegree and outdegree of each node is at most 1.
Each node has equal indegree and outdegree, or, there is exactly two nodes which has different indegree and outdegree, and exactly one of them has indegree - outdegree = 1 and the other has outdegree - indegree = 1.

So, we can do this easily with the help of a bfs subroutine.
You might also like to read this and this.

MaxFlow :: Dinitz Algorithm

2010-05-28T03:46:00.012+06:00

Here is a nice implementation of Dinitz blocking flow algorithm in C++ (with special thanks to Fahim vai). Works in undirected large graph containing multiple edges and self loops as well. No STL used. This implementation is pretty fast.

Here, input is, number of nodes 2≤n≤5000, number of input edges 0≤e≤30000, then e undirected edges in the form (u, v, cap) (1≤u,v≤n and 1≤cap≤10^9). Source and Sink are assumed 1 and n accordingly, can be changed in the init() function call.


#define SET(p) memset(p, -1, sizeof(p))
#define CLR(p) memset(p, 0, sizeof(p))
#define i64 long long

const int INF = 0x7fffffff;
const int MAXN = 5005, MAXE = 60006;

int src, snk, nNode, nEdge;
int Q[MAXN], fin[MAXN], pro[MAXN], dist[MAXN];
int flow[MAXE], cap[MAXE], next[MAXE], to[MAXE];

inline void init(int _src, int _snk, int _n) {
    src = _src, snk = _snk, nNode = _n, nEdge = 0;
    SET(fin);
}

inline void add(int u, int v, int c) {
    to[nEdge] = v, cap[nEdge] = c, flow[nEdge] = 0, next[nEdge] = fin[u], fin[u] = nEdge++;
    to[nEdge] = u, cap[nEdge] = c, flow[nEdge] = 0, next[nEdge] = fin[v], fin[v] = nEdge++;
}

bool bfs() {
    int st, en, i, u, v;
    SET(dist);
    dist[src] = st = en = 0;
    Q[en++] = src;
    while(st < en) {
        u = Q[st++];
        for(i=fin[u]; i>=0; i=next[i]) {
            v = to[i];
            if(flow[i] < cap[i] && dist[v]==-1) {
                dist[v] = dist[u]+1;
                Q[en++] = v;
            }
        }
    }
    return dist[snk]!=-1;
}

int dfs(int u, int fl) {
    if(u==snk) return fl;
    for(int &e=pro[u], v, df; e>=0; e=next[e]) {
        v = to[e];
        if(flow[e] < cap[e] && dist[v]==dist[u]+1) {
            df = dfs(v, min(cap[e]-flow[e], fl));
            if(df>0) {
                flow[e] += df;
                flow[e^1] -= df;
                return df;
            }
        }
    }
    return 0;
}

i64 dinitz() {
    i64 ret = 0;
    int df;
    while(bfs()) {
        for(int i=1; i<=nNode; i++) pro[i] = fin[i];
        while(true) {
            df = dfs(src, INF);
            if(df) ret += (i64)df;
            else break;
        }
    }
    return ret;
}

int main() {
    int n, e, u, v, c, i;
    scanf("%d%d", &n, &e);
    init(1, n, n);
    for(i=0; i<e; i++) {
        scanf("%d%d%d", &u, &v, &c);
        if(u!=v) add(u, v, c);
    }
    printf("%lld\n", dinitz());
    return 0;
}

Using adjacency matrix and/or STL makes it 10 to 4 times slower.

C++ :: Get Variable's Name

2010-05-28T02:33:00.012+06:00

How to print a variables name instead of its value? (not just by giving the name yourself)

This can be easily done with a #define pre-processor directive. As #define treats the preceding expression as cstring, it is possible to get the variables name as a string. Look below:


#include <stdio.h>

#define getVarName(varName,holder) sprintf(holder, "%s", #varName)

int main() {
    int var = 100; // just any type of identifier
    char name[100]; // it will get the variables name
    getVarName(var, name);
    puts(name);
    return 0;
}

It will print "var" instead of "100" or something other. I saw it years ago somewhere I can't remember now. Today, it suddenly struck me and I think it might be useful who knows when...

Maximum Matching (DFS)

2010-05-22T01:06:00.006+06:00

Maximum bipartite matching in a bipartite graph

Although Hopcroft Karp is faster and smarter, this one is pretty simple to code specially in contest time and when the graph is relatively smaller. It uses a DFS subroutine to cut and establish matching and thus produces a maximum matching. This version of BPM takes the adjacency list of left side of the bipartite graph and updates the Left[] and Right[] arrays with their respective matches.

Here, in the DFS subroutine, there are two for loops, where, the first one checks for yet unestablished connections, and the second one is the recursive DFS step. These two steps could be written in a single loop and the condition modified as "( Right[v]==-1 || dfs(Right[v]) )", actually separating them increases performance by some factors, because, first time it checks all the unmatched nodes before going into DFS.

A sample C++ implementation:


#define SET(x) memset(x, -1, sizeof(x))
#define CLR(x) memset(x, 0, sizeof(x))
#define MAX 100

vector < int > edges[MAX];
bool visited[MAX];
int Left[MAX], Right[MAX];

bool dfs(int u) {
    if(visited[u]) return false;
    visited[u] = true;
    int len = edges[u].size(), i, v;
    for(i=0; i<len; i++) {
        v = edges[u][i];
        if(Right[v]==-1) {
            Right[v] = u, Left[u] = v;
            return true;
        }
    }
    for(i=0; i<len; i++) {
        v = edges[u][i];
        if(dfs(Right[v])) {
            Right[v] = u, Left[u] = v;
            return true;
        }
    }
    return false;
}

int match() {
    SET(Left);
    SET(Right);
    int i, ret = 0;
    bool done;
    do {
        done = true;
        CLR(visited);
        for(i=0; i<MAX; i++) {
            if(Left[i]==-1 && dfs(i)) {
                done = false;
            }
        }
    } while(!done);
    for(i=0; i<MAX; i++) ret += (Left[i]!=-1);
    return ret;
}

Notes: Here, edges[MAX] is the left side adjacency list, implemented with vector, Left[MAX] and Right[MAX] holds the matching and the procedure match() returns maximum matching. Pretty straight forward.

Expression Evaluation

2010-05-15T23:06:00.012+06:00

Infix to Postfix transformation and evaluation

Here, I would like to share a java source for converting an Infix expression to a Postfix equivalent and evaluate the Postfix expression. Postfix is also known as "Reverse Polish Notation". If you want to know more about this algorithm, this will be helpful.

Here is a simple java implementation. (Oh, we could do it a lot easily in C++, but, actually it has a academic purpose as well). A few things to note:

Fixed format of input, as this is just a demonstration. Do not use spaces.
It doesn't check whether the given expression is consistent or not.
No math error is checked here, you have to add it to your own.
Check sample execution for more details.
Only for binary operators +,-,*,/,%,^ and parenthesis ()

Java Source


//
// @author Zobayer
// @date May 10, 2010
//

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

//
// Demonstrates Expression evaluation process.
// Doesn't take care of wrong input,
// You need to handle that on your own.
//

public class Expression {

    // A sample main() method to demonstrate this process
    public static void main(String[] args) throws IOException {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        String expr;
        List<String> inFix, postFix;
        int result;

        while((expr = stdin.readLine())!=null) {
            expr = "(" + expr + ")";
            inFix = getInFix(expr);
            postFix = getPostFix(inFix);
            result = evaluate(postFix);
            System.out.println("Postfix form: " + postFix);
            System.out.println("Result: " + result);
        }
    }

    // Parse the input string and form an infix notation
    static List<String> getInFix(String expr) {
        List<String> list = new ArrayList<String>();
        int n, i;
        char ch;
        boolean hasInt;

        for(i = n = 0, hasInt = false; i < expr.length(); i++) {
            ch = expr.charAt(i);
            if(!isDigit(ch)) {
                if(hasInt) {
                    list.add("" + n);
                    n = 0;
                    hasInt = false;
                }
                list.add("" + ch);
            }
            else {
                n = n * 10 + (ch - 48);
                hasInt = true;
            }
        }
        
        return list;
    }

    // Enlist the tokens in a postfix notation
    static List<String> getPostFix(List<String> inFix) {
        List<String> list = new ArrayList<String>();
        Stack<String> oper = new Stack<String>();
        int i;
        char ch;
        String token, peek;

        for(i = 0; i < inFix.size(); i++) {
            token = inFix.get(i);
            ch = token.charAt(0);
            if(isDigit(ch)) list.add(token);
            else if(ch=='(') oper.push("" + ch);
            else if(ch==')') {
                while(!oper.empty()) {
                    peek = oper.pop();
                    if(peek.charAt(0)!='(') list.add(peek);
                    else break;
                }
            }
            else {
                while(!oper.empty()) {
                    peek = oper.peek();
                    if(peek.charAt(0)!='(' && preced(ch) <= preced(peek.charAt(0))) {
                        list.add(peek);
                        oper.pop();
                    }
                    else {
                        oper.push(token);
                        break;
                    }
                }
            }
        }
        
        return list;
    }

    // Evaluate the postfix notation passed as a list
    static int evaluate(List<String> postFix) {
        Stack<Integer> stack = new Stack<Integer>();
        int i, a, b;
        String token;
        char ch;

        for(i = 0; i < postFix.size(); i++) {
            token = postFix.get(i);
            ch = token.charAt(0);
            if(isDigit(ch)) stack.push(Integer.parseInt(token));
            else {
                b = stack.pop();
                a = stack.pop();
                switch(ch) {
                    case '+': a = a + b; break;
                    case '-': a = a - b; break;
                    case '*': a = a * b; break;
                    case '/': a = a / b; break;
                    case '%': a = a % b; break;
                    case '^': a = (int)Math.pow(a, b); break;
                }
                stack.push(a);
            }
        }
        
        return stack.pop();
    }

    // Provides operator precedence
    static int preced(char op) {
        if(op=='^') return 3;
        if(op=='*' || op=='/' || op=='%') return 2;
        if(op=='+' || op=='-') return 1;
        return 0;
    }

    // Checks if ch is a digit or not
    static boolean isDigit(char ch) {
        return (ch >= '0' && ch <= '9');
    }
}

Sample run


(3+8-90*36)*((((89-5%6+2^3-10-10-10)))-8)+100
Postfix form: [3, 8, +, 90, 36, *, -, 89, 5, 6, %, -, 2, 3, ^, +, 10, -, 10, -, 10, -, 8, -, *, 100, +]
Result: -174266
90+0
Postfix form: [90, 0, +]
Result: 90
6+763-67*2367-(54/234)
Postfix form: [6, 763, +, 67, 2367, *, -, 54, 234, /, -]
Result: -157820

The algorithm implemented here is pretty simple, so I guess I haven't made a mistake yet, but who knows? So please check it...

Maximum Matching (Hopcroft)

2010-05-07T22:36:00.008+06:00

Hopcroft-Karp is one of the fastest algorithm that finds the maximum cardinality matching on a bipartite graph. It has the best known worst case time complexity. More details can be found here [courtesy of Wikipedia].

C++ Source Code:


#define MAX 100001
#define NIL 0
#define INF (1<<28)

vector< int > G[MAX];
int n, m, match[MAX], dist[MAX];
// n: number of nodes on left side, nodes are numbered 1 to n
// m: number of nodes on right side, nodes are numbered n+1 to n+m
// G = NIL[0] ∪ G1[G[1---n]] ∪ G2[G[n+1---n+m]]

bool bfs() {
    int i, u, v, len;
    queue< int > Q;
    for(i=1; i<=n; i++) {
        if(match[i]==NIL) {
            dist[i] = 0;
            Q.push(i);
        }
        else dist[i] = INF;
    }
    dist[NIL] = INF;
    while(!Q.empty()) {
        u = Q.front(); Q.pop();
        if(u!=NIL) {
            len = G[u].size();
            for(i=0; i<len; i++) {
                v = G[u][i];
                if(dist[match[v]]==INF) {
                    dist[match[v]] = dist[u] + 1;
                    Q.push(match[v]);
                }
            }
        }
    }
    return (dist[NIL]!=INF);
}

bool dfs(int u) {
    int i, v, len;
    if(u!=NIL) {
        len = G[u].size();
        for(i=0; i<len; i++) {
            v = G[u][i];
            if(dist[match[v]]==dist[u]+1) {
                if(dfs(match[v])) {
                    match[v] = u;
                    match[u] = v;
                    return true;
                }
            }
        }
        dist[u] = INF;
        return false;
    }
    return true;
}

int hopcroft_karp() {
    int matching = 0, i;
    // match[] is assumed NIL for all vertex in G
    while(bfs())
        for(i=1; i<=n; i++)
            if(match[i]==NIL && dfs(i))
                matching++;
    return matching;
}

The implementation is quite straight forward as the algorithm on Wikipedia page. I am looking for some optimizations.

UVa, SPOJ & TopCoder

2010-03-22T10:37:00.038+06:00

First of all, thanks to Fahim vai, he gave me the idea first...

This is a very easy way to add a cool bookmark item on your browser which can easily locate UVa, SPOJ & TopCoder problems for you. After you follow these steps, you will be able to open any UVa / SPOJ problem with just a click, you even do not need to enter any web address !

UVa Locator:

Right click on bookmark toolbar of your browser. Then right click on it and select "New Bookmark...". So the new bookmark box will arrive. On the name field, put whatever you want, like "UVa" or something else and on the location field, paste the following javascript:


javascript:var%20pid=prompt('Enter%20problem%20number:');
location.href='http://uva.onlinejudge.org/external/'+pid.substring(0,pid.length-2)+'/'+pid+'.html';

Now, after clicking "Add", you will see a new bookmark item has been added to your browser's toolbar, just click on it and enter the problem number.. that's it!

Spoj Locator:

Similar process, add e new bookmark item, now, give a different name, for example, "SPOJ" and on the location, paste the following javascript:


javascript:var%20pid=prompt('Enter%20problem%20name:');
location.href='https://www.spoj.pl/problems/'+pid.toUpperCase()+'/'

Click "Add" and done!. Now you will get a similar bookmark item as the previous one. But as you know, spoj problems are recognized with their codnames, not numbers. So enter a code name in the textbox, don't bother about case, and click ok. It will open the page of the problem if it is there. For example, to open the problem "Longest Common Substring", it has a codename LCS, you should enter "LCS" in the box, (not necessarily all should be uppercase).

TopCoder Locator:

Similarly, topcoder problems are known by their respective class names, you can add a simple search box for topcoder problems by adding the following javascript in the similar way stated above:


javascript:var%20pid=prompt('Enter%20class%20name:');
location.href='http://www.topcoder.com/tc?module=ProblemArchive&class='+pid

It will not open the problem, it is a simple javascript that calls the search engine on topcoder to find the class name you provide.

As these will open in current window, make sure you open a new tab before using these to save some back, forward clicks ><><><
Have Fun !!!

Bigint Library by Jan vai

2010-03-21T11:39:00.019+06:00

Thanks to Jan vai for this, It will be a great help... :)


/*
    Author       :    Jan
    Problem Name :    Big int for contest
    Algorithm    :
    Complexity   :
*/

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

struct Bigint {
    string a;
    int sign;

    Bigint() {}
    Bigint( string b ) { (*this) = b; }
    int size() { return a.size(); }
    Bigint inverseSign() { sign *= -1; return (*this); }
    Bigint normalize( int newSign ) {
        sign = newSign;
        for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- ) a.erase(a.begin() + i);
        if( a.size() == 1 && a[0] == '0' ) sign = 1;
        return (*this);
    }
    void operator = ( string b ) {
        a = b[0] == '-' ? b.substr(1) : b;
        reverse( a.begin(), a.end() );
        this->normalize( b[0] == '-' ? -1 : 1 );
    }
    bool operator < ( const Bigint &b ) const {
        if( a.size() != b.a.size() ) return a.size() < b.a.size();
        for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != b.a[i] ) return a[i] < b.a[i];
        return false;
    }
    Bigint operator + ( Bigint b ) {
        if( sign != b.sign ) return (*this) - b.inverseSign();
        Bigint c;
        for( int i = 0, carry = 0; i < (int)a.size() || i < (int)b.size() || carry; i++ ) {
            carry += (i < (int)a.size() ? a[i] - 48 : 0) + (i < (int)b.a.size() ? b.a[i] - 48 : 0);
            c.a += (carry % 10 + 48);
            carry /= 10;
        }
        return c.normalize(sign);
    }
    Bigint operator - ( Bigint b ) {
        if( sign != b.sign ) return (*this) + b.inverseSign();
        if( (*this) < b ) return (b - (*this)).inverseSign();
        Bigint c;
        for( int i = 0, borrow = 0; i < (int)a.size(); i++ ) {
            borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
            c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
            borrow = borrow >= 0 ? 0 : 1;
        }
        return c.normalize(sign);
    }
    Bigint operator * ( Bigint b ) {
        Bigint c("0");
        for( int i = 0, k = a[i]; i < (int)a.size(); i++, k = a[i] ) {
            while(k-- - 48) c = c + b;
            b.a.insert(b.a.begin(), '0');
        }
        return c.normalize(sign * b.sign);
    }
    Bigint operator / ( Bigint b ) {
        if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 ) ;
        Bigint c("0"), d;
        for( int j = 0; j < (int)a.size(); j++ ) d.a += "0";
        int dSign = sign * b.sign; b.sign = 1;
        for( int i = a.size() - 1; i >= 0; i-- ) {
            c.a.insert( c.a.begin(), '0');
            c = c + a.substr( i, 1 );
            while( !( c < b ) ) c = c - b, d.a[i]++;
        }
        return d.normalize(dSign);
    }
    Bigint operator % ( Bigint b ) {
        if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 ) ;
        Bigint c("0");
        int cSign = sign * b.sign; b.sign = 1;
        for( int i = a.size() - 1; i >= 0; i-- ) {
            c.a.insert( c.a.begin(), '0');
            c = c + a.substr( i, 1 );
            while( !( c < b ) ) c = c - b;
        }
        return c.normalize(cSign);
    }
    void print() {
        if( sign == -1 ) putchar('-');
        for( int i = a.size() - 1; i >= 0; i-- ) putchar(a[i]);
    }
};

int main() {
    Bigint a, b, c;
    a = "511";
    b = "10";
    
    c = a + b;
    c.print();
    putchar('\n');
    
    c = a - b;
    c.print();
    putchar('\n');
    
    c = a * b;
    c.print();
    putchar('\n');
    
    c = a / b;
    c.print();
    putchar('\n');
    
    c = a % b;
    c.print();
    putchar('\n');
    
    return 0;
}

Hope this helps my friends as well. Actually many of us are afraid of big integers, and also the above code may look hard, but this is actually what we do when performing these operations in real life... Use with caution, not a very first algorithm. Do not attempt to use *, /, % if numbers are 10³ or more digits long.

FIFA World Cup 2010

2010-03-17T15:00:00.014+06:00

FIFA World Cup South Africa 2010 Official Theme Song

Lyrics

ooooooh wooooooh

give me freedom, give me fire,
give me reason, take me higher
see the champions, take the field now,
you define us, make us feel proud...
in the streets are, exaliftin',
as we lose our inhabition,
celebration its around us,
every nation, all around us

singin' forever young,
singin' songs underneath that sun
lets rejoice in the beautiful game
and together at the end of the day.

[chorus]:
we all say...

when I get older I will be stronger
they'll call me freedom
just like a wavin' flag
and then it goes back |||

when I get older I will be stronger
they'll call me freedom
just like a wavin' flag
and then it goes back |||

Oooooooooooooh woooooooooohh hohoho

give you freedom, give you fire,
give you reason, take you higher
see the champions, take the field now,
you define us, make us feel proud
in the streets are, exaliftin,
every loser in ambition,
celebration, its around us,
every nations, all around us

singin' forever young,
singin' songs underneath that sun
lets rejoice in the beautiful game.
and together at the end of the day.

[chorus]

Oooooooooooooh woooooooooohh hohoho

[chorus]
___________________________________

Song: Wavin' Flag
Artist: K'naan

Blogger Code Formatter

2010-03-16T00:25:00.005+06:00

Blogger is a wonderful place to write blogs and there are many code bloggers out there, who want to share their coding skills with the world! But, certainly there are some problems with blogger posting methods, for example, in a <pre> tag, it will ignore tabs, and it causes great problems with some operators like '<', '>' etcetera... So, we can easily write a simple program and use it easily as a code formatter for blogger. Here's an example:


#include <stdio.h>

int main(int argc, char **argv)
{
    if(argc < 3)
    {
        printf("Usage: $ %s <infile> <outfile>\n", argv[0]);
        return 1;
    }
    FILE *in = fopen(argv[1], "r");
    FILE *out = fopen(argv[2], "w");
    if(in==NULL)
    {
        printf("file %s can't be opened.\n", argv[1]);
        return 2;
    }
    if(out==NULL)
    {
        printf("file %s can't be opened.\n", argv[2]);
        return 3;
    }
    char ch;
    while(fscanf(in, "%c", &ch)==1)
    {
        if(ch=='>') fprintf(out, "&gt;");
        else if(ch=='<') fprintf(out, "&lt;");
        else if(ch=='&') fprintf(out, "&amp;");
        else if(ch=='\t') fprintf(out, "    ");
        else fprintf(out, "%c", ch);
    }
    fclose(in);
    fclose(out);
    printf("file %s was written succesfully.\n", argv[2]);
    return 0;
}

Windows:

In windows, execute this with any compiler and grab the .exe file, paste it in your C:\WINDOWS\system32 folder. So, for example, if the file name is "blog.cpp", you will get "blog.exe", just paste it to your system32 folder. So now you can use it as a command in command prompt. If you like to format a file, say, "test.cpp", cd to the directory where "test.cpp" is, and to transform, the command is "blog test.cpp blog_test.cpp". Now just open the "blog_test.cpp" file and paste it in the <pre> tags.

Linux

Run it with g++, command: "g++ -o blog blog.cpp", and give enough permissions to the executable "blog", command: "chmod 777 blog". Now, we need to paste it in the "/bin" directory, but as it is write protected, we'll need to log in as root. To do this, write on prompt: "sudo nautilus", it will ask your password, and then an explorer will be opened, and now, just go to the "/bin" directory using it and paste the file. The usage is similar as stated in the Windows part.

Makes life a bit easier...

Testing Bipartite Graph

2010-03-15T23:51:00.012+06:00

We can use BFS to check whether an undirected graph is bipartite or not, with only a little modification...

We define bipartite graph as follows: A bipartite graph is an undirected graph G = (V, E) in which V can be partitioned into two sets V1 and V2 such that (u, v) ∈ E implies either u ∈ V1 and v ∈ V2 or u ∈ V2 and v ∈ V1. That is, all edges go between the two sets V1 and V2.

In other to determine if a graph G = (V, E) is bipartite, we perform a BFS on it with a little modification such that whenever the BFS is at a vertex u and encounters a vertex v that is already 'gray', i.e. visited, our modified BSF should check to see if the depth of both u and v are even, or if they are both odd. If either of these conditions holds which implies d[u] and d[v] have the same parity, then the graph is not bipartite. Note that this modification does not change the running time of BFS and remains Θ(V + E).

Here goes a simple implementation of the above idea. We'll just run a BFS, while tracking the partition in which every node falls. If, when visiting node v from node u, and they are members of same partition, then this graph is not bipartite. Well, this time, I think, we have nothing to do with the edge weights or costs, so it will also work on a weighted graph.

Formally, to check if the given graph is bipartite, the algorithm traverse the graph labelling the vertices 0 or 1 / 2 , corresponding to unvisited or visited, and partition 1 or partition 2 depending on which set the nodes are in. If an edge is detected between two vertices in the same partition, the algorithm returns false immediately.

Note: In this implementation, only one test at a time is possible, to run it for multiple cases, definitely cares must be taken about resetting the arrays and other values as necessary.


#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define MAX 1001

int n, e;
int partition[MAX], visited[MAX];
vector< int > G[MAX];

bool is_bipartite()
{
    int i, u, v, start;
    queue< int > Q;
    start = 1; // nodes labeled from 1
    Q.push(start);
    partition[start] = 1; // 1 left, 2 right
    visited[start] = 1; // set gray

    while(!Q.empty())
    {
        u = Q.front(); Q.pop();
        for(i=0; i < G[u].size(); i++)
        {
            v = G[u][i];
            if(partition[u] == partition[v]) return false;
            if(visited[v] == 0)
            {
                visited[v] = 1;
                partition[v] = 3 - partition[u]; // alter 1 and 2
                Q.push(v);
            }
        }
    }
    return true;
}

int main()
{
    int i, u, v;
    scanf("%d %d", &n, &e);
    for(i=0; i<e; i++)
    {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    if(is_bipartite()) printf("Yes\n");
    else printf("No\n");
    return 0;
}

As this algorithm traverses the graph it labels the vertices with a partition number consisted with the graph being bipartite. If at any vertex, algorithm detects an inconsistency, it shows with an invalid return value. Partition value of u will always be a valid number as it was en-queued at some point and its partition was assigned at that point. Partition of v will be unchanged if it is already set, otherwise it will be set to a value opposite to that of vertex u. So, if the algorithm returns true, it means, the graph is bipartite, i.e. bi-color-able, and partition[] holds the colors for each vertex.

Have fun, and let me know about errors, if any.
[Note: The definition of bipartite graph is taken from this wonderful site]

Convex Hull

2010-02-26T01:47:00.006+06:00

In computational geometry, Convex Hull or Convex Polygon is a very common term and we face many problems which require the construction of a Convex Hull to generate desired solution.

A convex hull is a convex polygon which has the minimal area to contain the set of given points. In other words, for a given set of points, a Convex Hull is such a Convex Polygon that, every point on the set is either on the Polygon or inside the Polygon.

So, a typical problem might ask, "You are given n integer co-ordinates (3 ≤ n ≤ 10⁵), find the Convex Hull". It means it wants you to write down the co-ordinates of the picks or, find the convex area, or, find the center of gravity of it, or, sometimes, you are asked to create an arbitrary convex hull, or you may be asked, find whether a given point is inside a convex hull, and so on... Well, before getting into the harder ones, lets see how we can construct a convex hull smartly :P

There are a number of ways to compute convex hull from the given points. Like, I found those in wikipedia, (I know only three of them):

Direct method
Gift Wrapping (Packaging) method
Graham's scan method
Incremental (Sequential addition) method
Divide and Conquer method
Quick method (related to Quick Sort)
Inner point elimination

The graham scan method is the most widely used method that has a complexity of O( n lg n ) for n points. In this method, the algorithm starts from a extreme (topmost / leftmost / rightmost / bottommost) point and keep wrapping all the other points unless it reaches the beginning point. Here's a little animation that shows it:

For detailed reading, you can visit Wikipedia or read Introduction to Algorithm - CLRS. Here's my implementation for finding Convex Hull with the help of Graham Scan method (integer points only):


#include <algorithm>
using namespace std;

#define MAX 100009
#define i64 long long
#define sq(x) ((x)*(x))

struct point {
    i64 x, y;
} P[MAX], C[MAX], P0;

// P[] contains all points
// C[] contains convex hull ccw

inline i64 TriArea2(point a, point b, point c) {
    return (a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y));
}

inline i64 sqDist(point a, point b) {
    return (sq(a.x-b.x) + sq(a.y-b.y));
}

bool comp(point a, point b) {
    i64 d = TriArea2(P0, a, b);
    if(d<0) return false;
    if(!d && sqDist(P0, b) > sqDist(P0, a)) return false;
    return true;
}

void ConvexHull(int np, int &cp) {
    int i, j, pos = 0;
    for(i=1; i<np; i++)
        if(P[i].y<P[pos].y || (P[i].y==P[pos].y && P[i].x>P[pos].x))
            pos = i;
    swap(P[0], P[pos]);
    P0 = P[0];
    sort(&P[1], P+np, comp);
    C[0] = P[0], C[1] = P[1], C[2] = P[2];
    for(i=j=3; i<np; i++) {
        while(TriArea2(C[j-2], C[j-1], P[i]) <= 0) j--;
        C[j++] = P[i];
    }
    nc = j;
}

Here,
TriArea2() returns the double of triangular area formed by the three points passed as its argument.
sqDist() returns the square distance between two points passed as its argument.
sort() is stl sort that sorts the P[] array according to their slope.
The first loop in ConvexHull() finds the starting point, i.e. the bottommost and rightmost point. After sorting rest of the points correctly, the second loop examines which point is to be added to the Hull. Finally nc is the number of points in convex hull updated via reference. There is no checking for n < 3 or if there are duplicates (actually if number of distinct points are ≥ 3, it doesn't matter in this method), we need to handle that according to problem requirement.

Not much tough as it seems to be ... happy coding

C/C++ Array of Functions

2010-02-15T21:56:00.012+06:00

Oh, never thought of it? well, this is actually not array of functions, this is array of function pointer. You know, in C/C++, pointers are very powerful tools for accessing and allocating memory, and anything that has a logical entity in any type of memory, a pointer can access it pretty easily and this feature made all other languages jealous that they say allowing pointers are threat-full, lolzzz....

Well, here is a simple code presented that shows the use of such an array. Actually, we all know, like a character array s[100], s is the pointer to it, similarly, a function defined as f(int a), f is the pointer to it. Well, enough talk, lets examine the code...


#include <stdio.h>

inline int add(int a, int b) {
    return a + b;
}

inline int sub(int a, int b) {
    return a - b;
}

inline int mul(int a, int b) {
    return a * b;
}

inline int div(int a, int b) {
    return a / b;
}

inline int mod(int a, int b) {
    return a % b;
}

int main() {
    int (*func_array[])(int, int) = {&add, &sub, &mul, &div, &mod};
    for(int i=0; i<5; i++) printf("%d\n", func_array[i](10, 5));
    return 0;
}

Easy as usual...

Primitive Root

2010-02-11T02:02:00.032+06:00

Primitive root modulo n

This time, lets talk about some sort of modular arithmetic. Suppose, you are asked a peculiar question like the following:

"For a prime number p, check whether g, g², g³, ... , g^p-1 are all distinct (mod p)." [ No doubt, here, p is sufficiently large to prevent you from following naive approach ]

In other words, you are asked:

"Given any prime number p, and another positive number g, you are to tell whether g is a primitive root modulo p."

Now the question is, what is a Primitive Root?

A positive integer g is said to be a primitive root modulo n, if for every integer h such that h and n are co-prime, i.e. GCD(h,n) = 1, there is an integer k such that g^k ≡ h (mod n). This also means, g is a generator of the multiplicative group of integers modulo n.

According to the above problem, here, n is actually any prime number p, which makes the condition GCD(h,p) = 1 very obvious.

Example:

The number 3 is a primitive root in (mod 7) because

⁴

⁵

⁶

The remainders above which are 3, 2, 6, 4, 5, and 1 are simply a permutation of 1, 2, ..., (p-1). In this case, p-1=6 because the prime number is 7.

Now, how to solve the problem easily?

As far as I know, there is no simple formula known yet to find primitive roots, however, there is a faster way to test whether a number is a primitive root rather than simply trying out all candidates. This technique can be derived from the definition of primitive roots. From its alternate definition, we know, if the multiplicative order of a number g modulo n is equal to φ(n), then g is a primitive root. In fact, the converse is also true, g is a primitive root modulo n if the multiplicative order of g is φ(n). From this axiom, we get a way to test whether, for any given g and n, g is a primitive root modulo n, as follows:

First we compute φ(n), [ In case n is a prime p, φ(n) = p-1 ]
Factorize φ(n), let it has k different prime factors p₁, p₂, ... , p_k, [ Even if m is as large as 2³¹, k will be around 32 ]
Compute g^φ(n)/p_i mod n; { for i = 1, 2, 3, ... ,k }. Using a successive squaring algorithm, this can be done very easily and fast. If all the k results are different than 1, then g is a primitive root modulo n.

hu la la... , really easy. From programming approach, φ(n) can be calculated easily by standard division algorithm, dividing by the primes less than √n. [ obviously we can use Sieve of Eratosthenes to get a prime table up to √max, and if n is a prime, φ(n) = n-1 ]. Then factorize φ(n) with the same standard division algorithm and get k different primes p_i, { for i = 1, 2, 3, ... , k }. Then the rest can be done in linear time to k where each k modular exponentiation is of logarithmic complexity.

Have fun ...

Confidence, Trust and Hope

2010-02-05T02:56:00.019+06:00

A bit unusual words...

Confidence:
Once all the villagers decided to pray for rain. On the day of prayer all people gathered and only one boy come with an umbrella. That's confidence.

Trust:
Trust should be like feeling of a one year old baby. When you throw him in the air, he laughs because he knows you will never let him fall.

Hope:
Every night you go to bed with no assurance to wake up alive in the next morning. But still you make plans for the next day. How could you live if you don't hope for tomorrow?

So be confident, trust in your abilities, never loose hope and do at you best whatever you do to make the world more colorful...

(\(\
( - -)
((') (')

SyntaxHighlighter for Blogger

2010-01-14T12:22:00.024+06:00

Installing SyntaxHighlighter in Blogspot blogs

Hello code bloggers, here is a short description and quick guide on how to install SyntaxHighlighter in your blogs and sites as well to beautify your codes. Actually nothing is more painful than reading out rusty codes no matter how cool they really are, so presentation does matter.

To go straight forward, go to Dashboard &rArr Layout &rArr Edit Html. Here you will see your current template. First save the current code to your hard drive before changing anything, so in-case you destroy the whole thing mistakenly, you have nothing to worry, just paste that again here, and every change is reverted. Actually it is good to store every working version of the template in your hard drive.

Now find the part in the html code:


</body>

</html>

First, we need to add some javascript links here, i.e. between these two tags. The files are located on the author's own host, http://alexgorbatchev.com/pub/sh/current/. The version I used for this blog is also uploaded here.We'll use it from there. But if you have your own host, you can download the files and make changes (as this project is open source) and upload it there, then use your links.

First add (I mean copy and paste) SyntaxHighlighter Core scripts:


<!-- SyntaxHighlighter core js files -->
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shCore.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shLegacy.js' type='text/javascript'></script>
<!-- -->

Now add highlighting brushes for your favorite languages:


<!-- SyntaxHighlighter brushes -->
<!-- some are added here, explore the hosted files for more language supports -->
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushCpp.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushBash.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushJava.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushPython.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushPlain.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushVb.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushXml.js' type='text/javascript'></script>
<!-- -->

When you paste the above lines, it will include highlighting functionality for C++, Bash, Java, Python, Plain Text, Visual Basic, XML. To add more, you can add more links to the files in this directory http://alexgorbatchev.com/pub/sh/current/scripts/. You should only add the files which has a name in the following format: "shBrush<language_name>.js". Clearly, it will add the functionality for "language_name" language.

Now the core style and theme:


<!-- SyntaxHighlighter core style -->
<link href='http://alexgorbatchev.com/pub/sh/current/styles/shCore.css' rel='stylesheet' type='text/css'/>
<!-- -->

<!-- SyntaxHighlighter theme -->
<link href='http://alexgorbatchev.com/pub/sh/current/styles/shThemeDefault.css' rel='stylesheet' type='text/css'/>
<!-- -->

You can only use one theme at a time, Default theme is added here, its best in my opinion. However, you can check other themes from this directory: http://alexgorbatchev.com/pub/sh/current/styles/. You can change the link of SyntaxHighlighter theme to any of the files having name pattern "shTheme<theme_name>.js" from this directory.

Now add the main script that will invoke SyntaxHighlighter, also, here you can put some initial parameters (see below) as well:


<!-- SyntaxHighlighter main js -->
<script type='text/javascript'>
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/current/scripts/clipboard.swf';
SyntaxHighlighter.config.tagName = 'pre';
SyntaxHighlighter.defaults['wrap-lines'] = false;
SyntaxHighlighter.defaults['ruler'] = true;
SyntaxHighlighter.all()
</script>
<!-- -->

Here you see, some defaults like line wrapping disabled, ruler visible, and also, SyntaxHighlighter is associated with the <pre>...</pre> tag. The clipboardSwf is the background style. And one special parameter for blogger blogs: bloggerMode = true. For the complete configuration list, visit http://alexgorbatchev.com/wiki/SyntaxHighlighter:Configuration.
All done, just save it...

How to write codes in pre-tag? Well, all you need to do is just invoke the classes in pre tag... for example, you might want to add a c++ code, you should do this:


<pre class="brush: cpp">
/*
** write your codes here.
** make sure you convert all < to &lt; and > to &gt;, important!
** do not use tabs, use 4/8 spaces instead, no break tags needed.
*/
</pre>

Clearly, the brush names are those "language_names" that you included above, for example, "shBrushCpp.js" will be invoked with "cpp", "shBrushXml.js" will be invoked with "xml", etc etc... Actually, in general, the class inclusion might look like class="param_list"
For complete usage, demonstration, and information, visit: http://alexgorbatchev.com/wiki/SyntaxHighlighter in the For Users section.

Hope this helps... not a big deal. Happy blogging.

Kruskal's Algorithm in C++

2010-01-06T21:41:00.013+06:00

Minimum Spanning Tree, Kruskal's Algorithm

Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). This algorithm is based on greedy approach.

Performance

This algorithm needs to sort the edges and uses a disjoint set data structure to keep track which vertex is in which component. We know the best comparison sorting is O(e*lg(e)), i.e. the merge sort or quick sort, where e is the number of edges, and the set operations can be implemented such a way that they are almost constant. The algorithm itself is linear to the number of edges e. So the total complexity can be achieved is O(e*lg(e)). Also note that, e can be max v*v (when it is a complete graph).

Algorithm

Do some study and paper-work before you proceed:
1. the algorithm and analysis
2. another good pseudo-code
3. read in wikipedia
4. text: Introduction to Algorithms (CLRS, MIT press), Chapter 23.

Implementation

Here is a short and in general implementation in C++ using the STL library. This solves for one graph, if you need it for multiple graphs inputs, don't forget to reset the vectors and arrays appropriately.

Input

N, E // number of nodes and edges.
E edges containing u, v, w; where, the edge is (u, v) and edge weight is w.

C++ code


#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define edge pair< int, int >
#define MAX 1001

// ( w (u, v) ) format
vector< pair< int, edge > > GRAPH, MST;
int parent[MAX], total, N, E;

int findset(int x, int *parent)
{
    if(x != parent[x])
        parent[x] = findset(parent[x], parent);
    return parent[x];
}

void kruskal()
{
    int i, pu, pv;
    sort(GRAPH.begin(), GRAPH.end()); // increasing weight
    for(i=total=0; i<E; i++)
    {
        pu = findset(GRAPH[i].second.first, parent);
        pv = findset(GRAPH[i].second.second, parent);
        if(pu != pv)
        {
            MST.push_back(GRAPH[i]); // add to tree
            total += GRAPH[i].first; // add edge cost
            parent[pu] = parent[pv]; // link
        }
    }
}

void reset()
{
    // reset appropriate variables here
    // like MST.clear(), GRAPH.clear(); etc etc.
    for(int i=1; i<=N; i++) parent[i] = i;
}

void print()
{
    int i, sz;
    // this is just style...
    sz = MST.size();
    for(i=0; i<sz; i++)
    {
        printf("( %d", MST[i].second.first);
        printf(", %d )", MST[i].second.second);
        printf(": %d\n", MST[i].first);
    }
    printf("Minimum cost: %d\n", total);
}

int main()
{
    int i, u, v, w;

    scanf("%d %d", &N, &E);
    reset();
    for(i=0; i<E; i++)
    {
        scanf("%d %d %d", &u, &v, &w);
        GRAPH.push_back(pair< int, edge >(w, edge(u, v)));
    }
    kruskal(); // runs kruskal and construct MST vector
    print(); // prints MST edges and weights

    return 0;
}

Have fun and please notify for any bug...

Online Compiler / Interpreter

2010-01-03T22:12:00.006+06:00

Visit http://www.ideone.com/
This is a free online compiler introduced and being developed by SPOJ team, a lots of thanks goes to them! and supports almost all available languages on SPOJ system.

So, if you are a C++ programmer, or like to learn some new esoteric or functional programming, or want to use gcc/g++ but don't have linux, or server side programming languages but don't want to setup a new IDE or virtual server, you can use this site... free for all!!!

Have fun...

Happy New Year....

2009-12-31T15:46:00.010+07:00

Happy new year, wishing you all a very very happy 2010...

Let 2009 go away with all your sorrows and mistakes...

Dijkstra's Algorithm in C++

2009-12-31T14:17:00.010+07:00

Dijkstra's Algorithm

Dijkstra's algorithm is a single source shortest path (sssp) algorithm. Like BFS, this famous graph searching algorithm is widely used in programming and problem solving, generally used to determine shortest tour in a weighted graph.

This algorithm is almost similar to standard BFS, but instead of using a Queue data structure, it uses a heap like data structure or a priority queue to maintain the weight order of nodes. Here is the algorithm and pseudo-code. You can also look into Introduction to Algorithms (by C.L.R.S).

Here is a short implementation of this algorithm in C++, I assumed that, all the edge-weights are positive, and the max possible distance is less than 2²⁰ which is set as INF macro and the graph supports MAX nodes starting from 1 to MAX-1, these macros needs to be set properly.

Input format:


N E // number of nodes and edges
E lines containing an edge (u, v, w) on each line
// edge(u, v, w) means weight of edge u-v is w
// u, v in range 1 to N
S // starting node

C++ code:


#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

#define MAX 100001
#define INF (1<<20)
#define DEBUG if(0)
#define pii pair< int, int >
#define pb(x) push_back(x)

struct comp {
    bool operator() (const pii &a, const pii &b) {
        return a.second > b.second;
    }
};

priority_queue< pii, vector< pii >, comp > Q;
vector< pii > G[MAX];
int D[MAX];
bool F[MAX];

int main() {
    int i, u, v, w, sz, nodes, edges, starting;
    DEBUG freopen("in.txt","r", stdin);

    // create graph
    scanf("%d %d", &nodes, &edges);
    for(i=0; i<edges; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u].pb(pii(v, w));
        G[v].pb(pii(u, w)); // for undirected
    }
    scanf("%d", &starting);

    // initialize graph
    for(i=1; i<=nodes; i++) D[i] = INF;
    D[starting] = 0;
    Q.push(pii(starting, 0));

    // dijkstra
    while(!Q.empty()) {
        u = Q.top().first;
        Q.pop();
        if(F[u]) continue;
        sz = G[u].size();
        DEBUG printf("visiting from %d:", u);
        for(i=0; i<sz; i++) {
            v = G[u][i].first;
            w = G[u][i].second;
            if(!F[v] && D[u]+w < D[v]) {
                DEBUG printf(" %d,", v);
                D[v] = D[u] + w;
                Q.push(pii(v, D[v]));
            }
        }
        DEBUG printf("\n");
        F[u] = 1; // done with u
    }

    // result
    for(i=1; i<=nodes; i++) printf("Node %d, min weight = %d\n", i, D[i]);
    return 0;
}

This is a straight forward implementation, according to the problem solving purpose, changes are to be made here and there.

Linked List in C

2009-12-22T21:06:00.018+07:00

Linked List in C (covers insert, delete, sort, search, print)

Here it goes:


#include <stdio.h>
#include <stdlib.h>

typedef struct linked_list {
    int val;
    struct linked_list *next;
} LL;

LL *head, *tail;

void tail_insert(int v)
{
    if(head==NULL)
    {
        head = (LL *)malloc(sizeof(LL));
        head->val = v;
        head->next = NULL;
        tail = head;
    }
    else
    {
        LL *temp = (LL *)malloc(sizeof(LL));
        temp->val = v;
        temp->next = NULL;
        tail->next = temp;
        tail = tail->next;
    }
}

void head_insert(int v)
{
    if(head==NULL)
    {
        head = (LL *)malloc(sizeof(LL));
        head->val = v;
        head->next = NULL;
        tail = head;
    }
    else
    {
        LL *temp = (LL *)malloc(sizeof(LL));
        temp->val = v;
        temp->next = head;
        head = temp;
    }
}

void insert_before(int v, int n) // insert v before every n
{
    LL *curr, *temp;
    if(head!=NULL)
    {
        if(head->val==n)
        {
            temp = (LL *)malloc(sizeof(LL));
            temp->val = v;
            temp->next = head;
            head = temp;
            curr = head->next;
        }
        else curr = head;
        while(curr->next!=NULL)
        {
            if(curr->next->val==n)
            {
                temp = (LL *)malloc(sizeof(LL));
                temp->val = v;
                temp->next = curr->next;
                curr->next = temp;
                curr = curr->next;
            }
            curr = curr->next;
        }
    }
}

void insert_after(int v, int n) // insert v after every n
{
    LL *curr, *temp;
    if(head!=NULL)
    {
        curr = head;
        while(curr!=NULL)
        {
            if(curr->val==n)
            {
                temp = (LL *)malloc(sizeof(LL));
                temp->val = v;
                temp->next = curr->next;
                if(curr->next==NULL) tail = temp;
                curr->next = temp;
                curr = curr->next;
            }
            curr = curr->next;
        }
    }
}

void sort_linked_list()
{
    LL *i, *j, *k;
    int temp;
    k = tail;
    for(i=head; i!=tail; i=i->next)
    {
        for(j=head; ;j=j->next)
        {
            if(j->val > j->next->val)
            {
                temp = j->val;
                j->val = j->next->val;
                j->next->val = temp;
            }
            if(j->next==k)
            {
                k = j;
                break;
            }
        }
    }
}

void delete_all(int v) // deletes every v
{
    LL *temp, *curr = head;
    while(head!=NULL && head->val==v)
    {
        temp = head;
        head = head->next;
        free(temp);
        curr = head;
    }
    if(curr==NULL) return;
    while(curr->next!=NULL)
    {
        if(curr->next->val==v)
        {
            temp = curr->next;
            curr->next = curr->next->next;
            free(temp);
            if(curr->next==NULL) tail = curr;
        }
        else curr = curr->next;
    }
}

int search_linked_list(int v)
{
    LL *curr = head;
    int n = 0;
    while(curr!=NULL)
    {
        if(curr->val==v) return n;
        n++;
        curr = curr->next;
    }
    return -1;
}

void print_linked_list()
{
    LL *curr = head;
    while(curr!=NULL)
    {
        printf("%d ", curr->val);
        curr = curr->next;
    }
    printf("\n");
}

int main()
{
    int i, n, v;

    // insert at the end
    for(i=1; i<=5; i++)
        tail_insert(5);
    print_linked_list();

    // insert at the beginning
    for(i=1; i<=5; i++)
        head_insert(i);
    print_linked_list();

    for(i=1; i<5; i++)
    {
        scanf("%d %d", &n, &v);
        // insert v before every n
        insert_before(v, n);
        print_linked_list();
    }

    for(i=1; i<5; i++)
    {
        scanf("%d %d", &n, &v);
        // insert v after every n
        insert_after(v, n);
        print_linked_list();
    }

    // sort the list with bubble sort
    sort_linked_list();
    print_linked_list();

    for(i=0; i<5; i++)
    {
        scanf("%d", &v);
        // delete all v in the list
        delete_all(v);
        print_linked_list();
    }

    for(i=0; i<5; i++)
    {
        scanf("%d", &v);
        // see if there is v in the list
        n = search_linked_list(v);
        if(n==-1) printf("not found\n");
        else printf("found at %d\n", n);
    }
    return 0;
}

Everything is commented out, if more explanation needed, leave a comment...

Bitwise operations in C: Part 3

2009-12-22T01:36:00.028+07:00

Bitwise Operation: Some applications

Back to Part 2

Binary number system is closely related with the powers of 2, and these special numbers always have some amazing bit-wise applications. Along with this, some general aspects will be briefly shown here.

Is a number a power of 2?
How can we check this? of course write a loop and check by repeated division of 2. But with a simple bit-wise operation, this can be done fairly easy.
We, know, the binary representation of p = 2ⁿ is a bit string which has only 1 on the n^th position (0 based indexing, right most bit is LSB). And p-1 is a binary number which has 1 on 0 to n-1 th position and all the rest more significant bits are 0. So, by AND-ing p and (p-1) will result 0 in this case:


p   = ....01000 &rArr 8
p-1 = ....00111 &rArr 7
-----------------------
AND = ....00000 &rArr 0

No other number will show this result, like AND-ing 6 and 5 will never be 0.

Swap two integers without using any third variable:
Well, as no 3^rd variable is allowed, we must find another way to preserve the values, how about we some how combine two values on one variable and the other will then be used as the temporary one...


Let A = 5 and B = 6
A = A ^ B = 3 /* 101 XOR 110 = 011 */
B = A ^ B = 5 /* 011 XOR 110 = 101 */
A = A ^ B = 6 /* 011 XOR 101 = 110 */
So, A = 6 and B = 5

Cool!!!

Divisibility by power of 2
Use of % operation is very slow, also the * and / operations. But in case of the second operand is a power of 2, we can take the advantage of bit-wise operations.
Here are some equivalent operations:

Here, P is in the form 2^X and N is any integer (typically unsigned)


N % P = N & (P-1)
N / P = N >> X
N * P = N << X

A lot faster and smarter...
About the % operation : the above is possible only when P is a power of 2

Masking operation
What is a mask? Its a way that is used to reshape something. In bit-wise operation, a masking operation means to reshape the bit pattern of some variable with the help of a bit-mask using some sort of bit-wise operation. Some examples following here (we won't talk about actual values here, rather we'll look through the binary representation and using only 16 bits for our ease of understanding):

Grab a portion of bit string from an integer variable.
Suppose A has some value like A = ... 0100 1101 1010 1001
We need the number that is formed by the bit-string of A from 3rd to 9th position.

[Lets assume, we have positions 0 to 15, and 0th position is the LSB]
Obviously the result is B = ... 01 1010 1; [we simply cut the 3rd to 9th position of A by hand]. But how to do this in programming.

Lets assume we have a mask X which contains necessary bit pattern that will help us to cut the desired portion. So, lets have a look how this has to be done:


A = 0100 1101 1010 1001
X = 0000 0011 1111 1000

See, we have X which have 1s in 3rd to 9th position and all the other thing is 0. We know, AND-ing any bit b with 1 leaves b unchanged.


So, X = X & A
Now, we have,
X = 0000 0001 1010 1000

So, now we've cut the desired portion, but this is exactly not what we wanted. We have 3 extra 0s in the tail, So just right-shift 3 times:


X = X >> 3 = 0000 0000 0011 0101; // hurrah we've got it.

Well, I got everything fine, but how to get such a weird X?


int x = 0, i, p=9-3+1; // p is the number of 1s we need
for(i=0; i<p, i++)
    x = (x << 1) | 1;
x = x << 3; // as we need to align its lsb with the 3rd bit of A


Execution:
X = 0000 0000 0000 0000 (initially X=0)
X = 0000 0000 0000 0001 (begin loop i=0)
X = 0000 0000 0000 0011 (i=1)
X = 0000 0000 0000 0111 (i=2)
X = 0000 0000 0000 1111 (i=3)
X = 0000 0000 0001 1111 (i=4)
X = 0000 0000 0011 1111 (i=5)
X = 0000 0000 0111 1111 (i=6 loop ends)
X = 0000 0011 1111 1000 (X=X<<3)

So, following the same approach, we may invert some portion of a bit-string (using XOR), make all bits 1 (using OR), make all bits in the portion 0 (using AND) etc etc very easily...

So, these are some tasks for the learner,
You have an integer A with some value, print the integers which have:
1. same bit pattern as A except it has all bits 0 within 4th to 23rd position.
2. same bit pattern as A except it has all bits 1 within 9th and 30th position.
3. same bit pattern as A except it has all bits inverted within positions 2nd and 20th.
4. totally inverted bit pattern.

Subset pattern:
Binary numbers can be used to represent subset ordering and all possible combination of taking n items.
For example, a problem might ask you to determine the n'th value of a series when sorted, where each term is some power of 5 or sum of some powers of 5.
It is clear that, each bit in a binary representation correspondence to a specific power of two in increasing order from right to left. And if we write down the consecutive binary values, we get some sorted integers. Like:


3 2 1 0 ⇒ power of 2
0 0 0 0 = 0 // took no one
0 0 0 1 = 1 // took power 0
0 0 1 0 = 2 // took power 1
0 0 1 1 = 3 // took power 1 and 0
0 1 0 0 = 4 // took power 2
0 1 0 1 = 5 // took power 2 and 0
0 1 1 0 = 6 // took power 2 and 1
0 1 1 1 = 7 // took power 2, 1 and 0
...........
...........
...........

So, what we do here is, take a power of 2 or take the sum of some powers of 2 to get a sorted sequence. Well, if this work for 2.. this will also work for 5 in the same way... Instead of taking the power of 2, we'll take the power of 5.
So the n'th term will be the sum of those powers of 5 on which position n's binary representation has 1. So the 10th term is 5³ + 5¹; As, 10₁₀ = 1010₂, it has 1 in 3rd and 1st position.

Worse than worthless
A bitwise GCD algorithm (wikipedia), translated into C from its assembly routine.

Sieve of Eratosthenes (SOE)
This is the idea of compressing the space for flag variables. For example, when we generate prime table using SOE, we normally use 1 int / bool for 1 flag, so if we need to store 10⁸ flags, we barely need 100MB of memory which is surely not available... and using such amount of memory will slow down the process. So instead of using 1 int for 1 flag, why don't we use 1 int for 32 flags on each of its 32 bits? This will reduce the memory by 1/32 which is less than 4MB :D


#define MAX 100000000
#define LMT 10000

unsigned flag[MAX>>6];

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))

void sieve() {
    unsigned i, j, k;
    for(i=3; i<LMT; i+=2)
        if(!ifc(i))
            for(j=i*i, k=i<<1; j<MAX; j+=k)
                isc(j);
}

ifc(x) checks if x is a composite (if correspondent bit is 1)
isc(x) sets x as a composite (by making correspondent bit 1)

Other than this famous bit-wise sieve, we could use the technique in many places, to reduce memory for flagging.

Keep going on...

Bitwise operations in C: Part 2

2009-12-22T00:06:00.021+07:00

Bitwise Operation: LEFT SHIFT and RIGHT SHIFT

Back to Part 1

<< (SHIFT LEFT) operator

This operator also depends highly on the length of the bit-string. Actually this operator only "shift" or moves all the bits to the left. This operator is mostly used if we want to multiply a number by 2, or, some powers of 2.
Example :


int a = 4978;
printf("%d\n", a<<1);

The output will be 9956. Do you see the relation between 4978 and 9956?

YES, 4978 * 2 = 9956. For more detailed explanation, we will see it in binary:


0001001101110010 ⇒ a = 4978(16 bit)
---------------- << 1 (SHIFT LEFT the bits by one bit)
0010011011100100 ⇒ 9956

Just move left all the bits by one. The left most bit is lost! and at the rightmost, a zero is added. Second example: count 4978 << 8 (count 4978 shifted left by 8 bits)
Answer:


0001001101110010 ⇒ 4978 (16 bit representation)
---------------- << 8 (SHIFT LEFT the bits by 8 bit)
0111001000000000 ⇒ 29184

So, using 16 bit compiler, 4978 << 8 is 29184, which is incorrect! Some of the left most bits are lost...It will not, however, if we use 32 bits data type.


00000000000000000001001101110010 ⇒ 4978(32 bit)
-------------------------------- << 8 (SHIFT LEFT the bits by 8 bit)
00000000000100110111001000000000 ⇒ 1274368

I've told you before that, this operator depends the length of bit-string. Don't be surprised if you got the output of 4978 << 8 is 1274368. (this is actually correct!) As we see, no bits are lost after shifting the bits left by 8 bits if we use a 32 bit data type.
Note that you don't have to have an int to store the value! In C, you can just print like this :


printf("%d", 4978 << 8);

The output will be 29184 for 16 bit compiler as Turbo C (16 bits; some bits will be lost)
The output will be 1274368 for 32 bit compiler as GNU C (32 bits; all bits are reserved since it has bigger capacity)
Now you know why shifting left 1 bit is the same as multiply the number by 2 right?
And shifting left 8 bits is exactly the same as multiplying the number by 2⁸.

4978 << 8 = 1274368 (in 32 bits compiler)
4978 * 2⁸ = 4978 * 256 = 1274368. (exactly the same)

BTW, we need to be careful when using signed data type, as the left most bit is the sign bit. So, while left shifting, if you push a 1 at that position, the number will be negative.

>> (SHIFT RIGHT) operator

Not much different with << (SHIFT LEFT) operator. It just shifts all the bits to the right instead of shifting to the left. This operator is mostly used if we want to divide a number by 2, or, some powers of 2.

Example :

count 4978 >> 8


int a = 4978;
printf("%d\n", a>>8);

4978 >> 8 = 19 (in 16 bits compiler or 32 bits compiler, the >> has no difference, because >> will discard the right most bit, and increased capacity on the left side doesn't help here anyhow)

Detailed explanation :


0001001101110010 ⇒ 4978(16 bit)
---------------- >> 8 (SHIFT RIGHT the bits by 8 bit)
0000000000010011 ⇒ 19

and


00000000000000000001001101110010 ⇒ 4978(32 bit)
-------------------------------- >> 8 (SHIFT RIGHT the bits by 8 bit)
00000000000000000000000000010011 ⇒ 19

If you notice:

4978 >> 8 = 19 (in 32 bits compiler)

4978 / 2⁸ = 4978 / 256 = 19. (They both the same, but using bit-wise operator >> (SHIFT RIGHT) is a LOT faster!)

The RIGHT SHIFT operator is machine dependent, it may work differently on different machines for signed data types. >> empties the left most bit and that is filled either by a 0 or by a 1, depending on the machine.
Filled by a 1 (RIGHT SHIFT ARITHMETIC)
Filled by a 0 (RIGHT SHIFT LOGICAL)
Example:


signed char x = -75 /* 1011 0101 */
signed char y = x >> 2

/* result of logical right shift */
y = 45  /* 0010 1101 */

/* result of arithmetic right shift */
y = -19 /* 1110 1101 */

So this behavior of RIGHT SHIFT leads to a non-portability of a program.

A few more words

The two shift operators are generally used with unsigned data type to avoid ambiguity.
Result of Shifting Right or Left by a value which is larger than the size of the variable is undefined.
Result of shifting Right or Left by a negative value is also undefined.

Order precedence of the basic operators is:


NOT ( ~ ) highest
AND ( & )
XOR ( ^ )
 OR ( | ) lowest

Some basic operations:


X & 1 =  X; X & 0 =  0
X | 1 =  1; X | 0 =  X
X ^ 1 = ~X; X ^ 0 =  X

Bit-wise operations are quite fast and easy to use, sometimes they reduce the running time of your program heavily, so use bit-wise operations when-ever you can. But if you look on the software developing aspect, they are not much reliable because, they aren't applicable with any type of data, especially floating points, and signed types. Also, not many people understand them.

But, still, who cares? I want to give some scary looks to my code... lol :D
Hopefully, on the next post, we'll see some simple ideas which will implement some bit-wise operations...

Continue to Part 3

Bitwise operations in C: Part 1

2009-12-21T19:24:00.038+07:00

Bitwise Operation: AND, OR, XOR, NOT

In computer, all the numbers and all the other data are stored using 2 based number system or in binary format. So, what we use to say a '5' in decimal (do we use decimal only because we have 10 figures? who knows...), a computer will represent it as '101', in fact, everything is represented as some sequence of 0s and 1s. We call this sequence a bit-string.

Bit-wise operations means working with the individual bits other than using the larger or default data types, like integers, floating points, characters, or some other complex types. C/C++ provides a programmer an efficient way to manipulate individual bits of a data with the help of commonly known logical operators like AND(&), OR(|), NOT(~), XOR(^), LEFT SHIFT(<<) and RIGHT SHIFT(>>) operators.

To be fluent with bit-wise operations, one needs to have a clear concepts about how data is stored in computer and what is a binary number system.

From a programming contest aspect, we'll explore bit-wise operations for only integer types (int in C/C++) and as this is almost 2010, we'll consider int as a 32 bit data type. But for the ease of writing, sometimes only the lowest 16 bits will be shown. The above operators works on bit-by-bit, i.e. during bit-wise operation, we have to align right the bits! (just like addition, multiplication,...) The shorter bits always have leading 0s at the front. And another important thing... we do not need to convert the integers to the binary form ourselves, when we use the operators, they will be automatically evaluated and the following examples shows the underlying activities... :P

& (AND) operator

This table will clearly explains the bit-wise operator & (AND):


0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

Example:
What is the value of 24052 & 4978 ?
To solve this, we have to consider the operations in base 2.
So, we imagine both numbers in base 2 and align right the bits, as shown below using 16 bits. Now, AND the numbers : (shorter bits can have leading zeros at the front):


101110111110100 ⇒ 24052
001001101110010 ⇒ 4978
--------------- &
001000101110000 ⇒ 4464

Each bit-column is AND-ed using the AND table above.

| (OR) operator

This table summarizes the OR operations :


0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

Now, using the same example above, let's do it using | (OR) operator :


101110111110100 ⇒ 24052
001001101110010 ⇒ 4978
--------------- |
101111111110110 ⇒ 24566

Each bit-column is OR-ed using the OR table above.

^ (XOR) operator

This table summarize the XOR operations :


0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

Now, using the same example above, let's do using ^ (XOR) operator :


101110111110100 ⇒ 24052
001001101110010 ⇒ 4978
--------------- ^
100111010000110 ⇒ 20102

Easy, isn't it?

~ (NOT) operator

This operator is different from the above operators. This operator is called unary operator, since it only needs one operand. The operators &, |, ^ are binary operators, since it takes 2 operands/number to be operated.

This ~ (NOT) operator, inverts all the bits in a variable. That is, changes all zeros into ones, and changes all ones into zeros.
Remember! that the result of this ~ (NOT) operation highly depends on the length of the bit-string.

Example:


int a = 10;
printf("%d\n", ~a);

Surprisingly, the output is -11. But actually this is normal as most of the cases computer represents negative numbers in the 2's complement form. Look at the operation shown below using 16 bits:


0000000000001010 ⇒ a(16 bits)
---------------- ~
1111111111110101 ⇒ -11

This is correct! Because computer stores -11 as 1111111111110101 in binary! (in the 2's complement form). Even if we use 32 bits representation, it is still the 2's complement form of -11;


-11(10) = 11111111111111111111111111110101(2)

Anyway, if we do the same operation for unsigned int:


unsigned int a = 10;
printf("%u\n", ~a);

Hah ha, don't be surprised if you get the output of the unsigned value of -11 is 4294967285.

If you use 32 bits, you actually will get -11 as 11111111111111111111111111110101 in signed binary representation:


00000000000000000000000000001010 ⇒ 10 (32 bits)
-------------------------------- ~
11111111111111111111111111110101 ⇒ -11 (for signed) and -> 4294967285 (for unsigned)

In the unsigned data type, all the bits are considered to be the part of the magnitude, there's no bit position reserved for sign bits.

Continue to Part 2

Power Series Evaluation

2009-12-12T03:35:00.056+07:00

Power series evaluation in O(lg(n)):[n is the number of terms]

We'll try to evaluate the following power series in logarithmic time w.r.t. the number of terms n.

Well well... I may be asked, "dude, why do you want to do this in O(lg(n)) when there's already we have a O(1) solution for your problem?". Answer is simple, "I'm trying it from a programming perspective and the O(1) can get sometimes impossible when n keeps going up i.e. like 10¹⁰⁰⁰ and you are asked to return the answer w.r.t. some %m [modulus m] (meaning the final result will not reach m). This method will be suitable for this case only. Because, calculating {(x^n-1-1)/(x-1)}%m is not a very easy task and sometimes, it is not directly possible.

This series can be evaluated by binary splitting and recursively solving those building up the answer.
Let n = 6
We have, 1 + x + x² + x³ + x⁴ + x⁵
⇒ (1 + x + x²) + x³(1 + x + x²)
⇒ (1 + x + x²)(1 + x³)

So, when n is even, f(x, n) = (1 + x^n/2)f(x, n/2)

Now, what if n is odd, Let n = 7
We have, 1 + x + x² + x³ + x⁴ + x⁵ + x⁶
⇒ (1 + x + x²) + x³(1 + x + x²) + x⁶
⇒ (1 + x + x²)(1 + x³) + x⁶

So, when n is odd, f(x, n) = (1 + x^n/2)f(x, n/2) + x^n-1

So, by combining the above 2 equations, we get the final solution:
f(x, n) = (1 + x^n/2)f(x, n/2) + (n%2)x^n-1

By some clever observation, the need for -1 and %2 operation on n can be eliminated. So, the only thing we need to do is the /2 operation on n, which is easy even when n is a big integer.

Here is a python module that shows only the recursive part, no trick applied.


import math

def evaluate(x, n):
    if(n==0):
        return 0
    if(n==1):
        return 1
    ret = 0
    if(n%2==1):
        ret = ret + int(math.pow(x, n-1))
    n = n/2
    return ret + evaluate(x, n)*(1 + int(math.pow(x, n)))

If this is to be done with C/C++, some biginteger division algorithm should be implemented.

Easy, eh? Check different types of series here

Gauss–Jordan Elimination

2009-12-11T02:31:00.014+07:00

Gauss–Jordan Elimination in C++

This is my first attempt to solve linear systems with unique solutions in O(N²).


Algorithm:
1. Read augmented matrix for the system.
2. Perform Gaussian Elimination to get the matrix in row echelon form.
3. Transform the matrix to reduced row echelon form.
4. Write results.

Preview:

[click for a clear view]

My C++ solution (change MAX to desired size, it is the maximum limit of how many equations it can handle, change the macro DEBUG to "if(1)" if you want to see the intermediate steps):


#include <iostream>
#include <cstdlib>
#include <cassert>
#include <algorithm>
using namespace std;

#define DEBUG if(0)
#define MAX 5

struct MAT {
    int R[MAX+1];
} M[MAX];

int N;

int gcd(int a, int b) {
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}

bool comp(MAT A, MAT B) {
    for(int k=0; k<N; k++) {
        if(A.R[k] > B.R[k]) return true;
        if(A.R[k] < B.R[k]) return false;
    }
    return true;
}

void print(void) {
    int i, j;
    cout << "..." << endl;
    for(i=0; i<N; i++) {
        for(j=0; j<N; j++) cout << M[i].R[j] << '\t';
        cout << M[i].R[j] << endl;
    }
    cout << "..." << endl;
}

void modify(MAT &A, MAT B, int a, int b) {
    for(int r=0; r<=N; r++) A.R[r] = a*B.R[r] - b*A.R[r];
}

void eliminate(void) {
    int i, g, k;
    for(i=0; i<N-1; i++) {
        if(!M[i].R[i]) {
            sort(&M[i], M+N, comp);
            assert(M[i].R[i]);
        }
        for(k=i+1; k<N; k++) {
            g = gcd(abs(M[i].R[i]), abs(M[k].R[i]));
            modify(M[k], M[i], M[k].R[i]/g, M[i].R[i]/g);
        }
        DEBUG print();
    }
}

void reduce(void) {
    int i, g, k;
    for(i=N-1; i; i--) {
        for(k=i-1; k>=0; k--) {
            g = gcd(abs(M[i].R[i]), abs(M[k].R[i]));
            modify(M[k], M[i], M[k].R[i]/g, M[i].R[i]/g);
        }
        DEBUG print();
    }
}

void printsol(void) {
    double h, l;
    cout << "Solve for " << N << " variables:" << endl;
    for(int i=0; i<N; i++) {
        assert(M[i].R[i]);
        h = M[i].R[i];
        l = M[i].R[N];
        cout << 'x' << i+1 << " = " << l/h << endl;
    }
    cout << "..." << endl;
}

int main(void) {
    int i, j, g;
    while(cin >> N) {
        if(!N) break;
        memset(M, 0, sizeof(M));
        for(i=0; i<N; i++) {
            for(j=0; j<N; j++) cin >> M[i].R[j];
            cin >> M[i].R[j];
            for(j=g=0; j<=N; j++) g = gcd(abs(M[i].R[j]), g);
            for(j=0; j<=N; j++) M[i].R[j] /= g;
        }
        eliminate();
        reduce();
        printsol();
    }
    return 0;
}

However, I'm trying to do it in a more efficient way. I'll post that when I'm done.

Attacking Recursions

2009-12-10T11:58:00.046+07:00

Some general approach for solving recursive problems:

If anyone want to read an awesome super cool tutorial on recursion in BANGLA... read from Fahim Vai's page

#1: Forget about what you need to do, just think about any input, for which you know what your function should output, as you know this step, you can build up a solution for your problem. Suppose you have a function which solves a task, and you know, this task is somehow related to another similar task. So you just keep calling that function again and again thinking that, the function I'm calling will solve the problem anyhow, and the function will also say, I'll solve this problem, if you give me the result for another sub-problem first!!! Well, then you'll say, "So, why don't you use your twin-brother to solve that part?" and so on... The following example will show you how to start writing a recursive function.

Example: Think about computing n! recursively. I still don't know what and how my function will do this. And I also don't know, like what could be 5! or 7!... But nothing to worry about, I know that 0! = 1! = 1. And I also know that, n! = n(n-1)!. So I will think like that, "I will get n! from a function F, if some one gives me (n-1)!, then I'll multiply it with n and produce results". And, thus, F is the function for computing n!, so why don't I use again to get (n-1)! ? And when F tries to find out what could be the value of (n-1)!, it also stumbles at the same point, it wonders what would be the value of (n-2)!... then we tell him to use F again to get this... and this thing keeps going as long as we don't know what F actually should return for any k. In case of k = 1, as we know now F can return 1 for k = 1, and it don't need to call another F to solve anything first...


int factorial(int n) {
    // I know this, so I don't want my function to go any further...
    if(n==0) return 1;
    // don't bother what to do, just reuse the function...
    else return n*factorial(n-1);
}

#2: What ever you can do with loops, can be done with recursions as well. A simple technique for converting recursions and loops is shown below:

Forward:
for loop:


for(int i = 0; i < n; i++) {
    // do whatever needed
}

Equivalent recursion:


void FOR(int i, int n) {
    if(i==n) return; // terminates
    // do whatever needed
    FOR(i+1, n); // go to next step
}

Backward:
for loop:


for(int i = n-1; i >= 0; i -= 1) {
    // do whatever needed
}

Equivalent recursion:


void ROF(int i, int n) {
    if(i==n) return; // terminates
    ROF(i+1, n); // keep going to the last
    // do whatever needed when returning from prev steps
}

Well, you may wonder how this is backward loop? But just think of its execution cycle, just after entering the function, it is calling itself again incrementing the value of i, and the execution routine that you have written under the function call, was paused there. From the new function it enters, it works the same way, call itself again before executing anything...Thus when you have reached the limiting condition, or the base condition, then the function stops recursion and starts returning, and the whole process can be shown as below...let n=5, and we want to print 5 4 3 2 1...code for this might be:


void function(int i, int n) {
    if(i<=n) {
        function(i+1, n);
        printf("%d ", i);
    }
}

Explanation might look like this:


01|call function₁ with i=1
02|    call function₂ with i=2
03|        call function₃ with i=3
04|            call function₄ with i=4
05|                call function₅ with i=5
06|                    call function₆ with i=6
07|                        i breaks condition, no more calls
08|                    return to function₅
09|                    print 5
10|                return to function₄
11|                print 4
12|            return to function₃
13|            print 3
14|        return to function₂
15|        print 2
16|    return to function₁
17|    print 1
18|return to main, done!

Left side number shows the execution steps, so from the above program, we get, 5 4 3 2 1. So indeed it ran on reverse direction...

#3: Use the advantage of call stack. When you call functions recursively, it stays in the memory as the following picture demonstrates.


int f(int n) {
    if(n==0) return 1;
    return n*f(n-1);
}

You know about stack, in a stack, you cannot remove any item unless it is the topmost. So you can consider the calling of a recursive function as a stack, where, you can't remove the memory used by f(n=3) before removing f(n=2) and so so... So, you can easily see that, the functions will hold all their variables and values until it is released. This actually serves the purpose of using an array.

#4: Be careful while using recursions. From a programming contest aspects, recursions are always best to avoid. As you've seen above, most recursions can be done using loops somehow. Recursions have a great deal of drawbacks and it most of the time extends the execution time of your program. Though recursions are very very easy to understand and they are like the first idea in many problems that pops out in mind first... they still bear the risks of exceeding memory and time limits.

Generally, in loops, all the variables are loaded at the same time which causes it a very low memory consumption and faster access to the instructions. But whenever we use recursions, each function is allotted a space at the moment it is called which requires much more time and all the internal piece of codes stored again which keeps the memory consumption rising up. As your compiler allows you a specific amount of memory (generally 32 MB) to use, you may overrun the stack limit by excessive recursive calls which causes a Stack Overflow error (a Runtime Error).

So, please think a while before writing recursions whether your program is capable of running under the imposed time and memory constraints. Generally recursions in O(lg n) are safe to use, also we may go to a O(n) recursion if n is pretty small.

#5: If the recursion tree has some overlapping branches, most of the times, what we do, is to store already computed values, so, when we meet any function which was called before, we may stop branching again and use previously computed values, which is a common technique knows as Dynamic Programming (DP), we will talk about that later as that is pretty advanced.

These techniques will be used in almost all problems when writing recursive solution. Just don't forget the definition of recursion:
Definition of recursion = See the Definition of recursion

Now try this

Drawing Regular n-gon

2009-12-10T01:36:00.017+07:00

How to draw a regular pentagon with just ruler and compass?

How about a regular hexagon?

Underlying theorem:
Primes of the form 2^2ⁿ + 1 are known as Fermat primes.

A regular n-gon is constructible using straightedge (ruler) and compass if and only if n = 2ⁱ · m where m is a product of any number of distinct Fermat Prime and i is any natural number, including zero.

Only five Fermat primes are known: 3, 5, 17, 257, and 65,537.

Related study: Compass and straightedge constructions.

Practice Recursions

2009-12-08T02:19:00.066+07:00

Recursions are fun

You may like to try out some simple problems to practice recursions. Try to solve all of them without using any global variables. And try on your own before looking at the solutions. Also please notify any error to me ( zobayer1[at]gmail[dot]com ).

Before looking at the problems, you may like to read this post about how to attack recursive problems.

Problem 1:

You will be given an array of integers, write a recursive solution to print it in reverse order.


Input:
5
69 87 45 21 47
Output:
47 21 45 87 69

see answer

Problem 2:

Write a recursive function to print an array in the following order.
[0] [n-1]
[1] [n-2]
.........
.........
[(n-1)/2] [n/2]


Input:
5
1 5 7 8 9
Output:
1 9
5 8
7 7

see answer

Problem 3:

Write a recursive program to remove all odd integers from an array. You must not use any extra array or print anything in the function. Just read input, call the recursive function, then print the array in main().


Input:
6
1 54 88 6 55 7
Output:
54 88 6

see answer

Problem 4:

Write a recursive solution to print the polynomial series for any input n:
1 + x + x² + ................. + x^n-1


Input:
5
Output:
1 + x + x^2 + x^3 + x^4

see answer

Problem 5:

Write a recursive solution to evaluate the previous polynomial for any given x and n.
Like, when x=2 and n=5, we have 1 + x + x² + ................. + x^n-1 = 31


Input:
2 5
Output:
31

see answer

Problem 6:

Write a recursive program to compute n!


Input:
5
Output:
120

see answer

Problem 7:

Write a recursive program to compute n^th fibonacci number. 1^st and 2^nd fibonacci numbers are 1, 1.


Input:
6
Output:
8

see answer

Problem 8:

Write a recursive program to determine whether a given integer is prime or not.


Input:
49
999983
1
Output:
not prime
prime
not prime

see answer

Problem 9:

Write a recursive function that finds the gcd of two non-negative integers.


Input:
25 8895
Output:
5

see answer

Problem 10:

Write a recursive solution to compute lcm of two integers. You must not use the formula lcm(a,b) = (a x b) / gcd(a,b); find lcm from scratch...


Input:
23 488
Output:
11224

see answer

Problem 11:

Suppose you are given an array of integers in an arbitrary order. Write a recursive solution to find the maximum element from the array.


Input:
5
7 4 9 6 2
Output:
9

see answer

Problem 12:

Write a recursive solution to find the second maximum number from a given set of integers.


Input:
5
5 8 7 9 3
Output:
8

see answer

Problem 13:

Implement linear search recursively, i.e. given an array of integers, find a specific value from it.
Input format: first n, the number of elements. Then n integers. Then, q, number of query, then q integers. Output format: for each of the q integers, print its index (within 0 to n-1) in the array or print 'not found', whichever is appropriate.


Input:
5
2 9 4 7 6
2
5 9
Output:
not found
1

see answer

Problem 14:

Implement binary search recursively, i.e. given an array of sorted integers, find a query integer from it.
Input format: first n, the number of elements. Then n integers. Then, q, number of query, then q integers. Output format: for each of the q integers, print its index (within 0 to n-1) in the array or print 'not found', whichever is appropriate.


Input:
5
1 2 3 4 5
2
3 -5
Output:
2
not found

see answer

Problem 15:

Write a recursive solution to get the reverse of a given integer. Function must return an int


Input:
123405
Output:
504321

see answer

Problem 16:

Read a string from keyboard and print it in reversed order. You must not use any array to store the characters. Write a recursive solutions to solve this problem.


Input:
helloo
Output:
oolleh

see answer

Problem 17:

Write a recursive program that determines whether a given sentence is palindromic or not just considering the alpha-numeric characters ('a'-'z'), ('A'-'Z'), ('0'-'9').


Input:
madam, i'm adam
hulala
Output:
palindromic
not palindromic

see answer

Problem 18:

Implement strcat(), stracpy(), strcmp() and strlen() recursively.


Input:
test on your own
Output:
test on your own

see answer

Problem 19:

If you already solved the problem for finding the n^th fibonacci number, then you must have a clear vision on how the program flow works. So now, in this problem, print the values of your fibonacci function in pre-order, in-order and post-order traversal. For example, when n = 5, your program calls 3 and 4 from it, from the call of 3, your program calls 1 and 2 again....... here is the picture:


Input:
5
Output:
Inorder: 1 3 2 5 2 4 1 3 2
Preorder: 5 3 1 2 4 2 3 1 2
Postorder: 1 2 3 2 1 2 3 4 5

see answer

Problem 20:

All of you have seen the tower of Hanoi. You have 3 pillars 'a', 'b' and 'c', and you need transfer all disks from one pillar to another. Conditions are, only one disk at a time is movable, and you can never place a larger disk over a smaller one. Write a recursive solution to print the moves that simulates the task, a -> b means move the topmost of tower a to tower b.


Input:
3
Output:
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

see answer

Good Luck!!!

Volume of an irregular tetrahedron

2009-11-20T22:18:00.024+07:00

Find the volume of an irregular tetrahedron form its edges:

Suppose you are given the 6 sides of an irregular tetrahedron and you need to find the volume consumed by it.

Let the given sides to be u, v, w, W, V, U. Here, (u, U), (v, V), (w, W) are considered to be opposite edge pairs ( opposite edges means the edges which do not share common vertices ). Now the volume can be found from the following formula:

Let:
u′ = v² + w² - U²
v′ = w² + u² - V²
w′ = u² + v² - W²
Now:
volume = ¹⁄₁₂ × √(4u²v²w² - u²u′² - v²v′² - w²w′² + u′v′w′)

This formula is derived from the determinant which can be found here for more reading. As the formula is symmetric, the ordering of the pairs won't make any change to the formula.

Read more properties about Tetrahedrons from Wikipedia.

Contest Template

2009-11-17T02:59:00.016+07:00

C++ contest coding template. Edit:5.


/*
USER: zobayer
TASK: template
ALGO: template
*/
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;

template< class T > T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T _max(T a, T b) { return (!(a < b) ? a : b); }
template< class T > T _min(T a, T b) { return (a < b ? a : b); }
template< class T > T sq(T x) { return x * x; }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > bool inside(T a, T b, T c) { return a<=b && b<=c; }
template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
template< class T > void setmin(T &a, T b) { if(b < a) a = b; }

#define MP(x, y) make_pair(x, y)
#define REV(s, e) reverse(s, e)
#define SET(p) memset(p, -1, sizeof(p))
#define CLR(p) memset(p, 0, sizeof(p))
#define MEM(p, v) memset(p, v, sizeof(p))
#define CPY(d, s) memcpy(d, s, sizeof(s))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define ALL(c) c.begin(), c.end()
#define SIZE(c) (int)c.size()
#define PB(x) push_back(x)
#define ff first
#define ss second
#define i64 __int64
#define ld long double
#define pii pair< int, int >
#define psi pair< string, int >

const double EPS = 1e-9;
const double BIG = 1e19;
const int INF = 0x7f7f7f7f;

int main() {
    //READ("in.txt");
    //WRITE("out.txt");
    return 0;
}

Segment-Circle Intersection

2009-11-17T00:53:00.018+07:00

This is a sample code which verifies whether a given Circle and Segment intersects or not.


/*
**  Verifies the intersection of a segment and a circle
**  The line segment is defined from points p1 to p2
**  The circle is of radius r and centered at point c
**  There are potentially two points of intersection given by
**  p = p1 + mu1 (p2 - p1)
**  p = p1 + mu2 (p2 - p1)
**  mu1 and mu2 are updated via reference
**  Return FALSE if the segment doesn't intersect the circle
*/
bool cross(POINT p1, POINT p2, CIRCLE p, double &mu1, double &mu2) {
    double a, b, c, d;
    POINT t;
    t.x = p2.x - p1.x;
    t.y = p2.y - p1.y;
    a = sq(t.x) + sq(t.y);
    b = 2.0 * (t.x * (p1.x - p.c.x) + t.y * (p1.y - p.c.y));
    c = sq(p.c.x) + sq(p.c.y);
    c += sq(p1.x) + sq(p1.y);
    c -= 2.0 * (p.c.x * p1.x + p.c.y * p1.y);
    c -= sq(p.r);
    d = b * b - 4 * a * c;
    if(fabs(a) < eps || d < -eps) {
        mu1 = mu2 = 0.0;
        return false;
    }
    mu1 = (-b + sqrt(d)) / (2.0 * a);
    mu2 = (-b - sqrt(d)) / (2.0 * a);
    return true;
}

SPOJ Hints

2009-11-02T03:26:00.003+07:00

Thanks to the Japanese boy, from whom I got this list. But unfortunately I could not read his name.. (Sorry! I can't read Japanese language.)

I've edited the list and added some myself (uploaded on Google Docs). This list is going to updated time by time...

Here is the file, have a look.
[Last updated: Thursday, November 12, 2009]

If any mistake is found, please comment out here. Thanks...

Linux : Bash Script (Shell Script)

2009-10-22T02:01:00.015+07:00

A very simple automatic judge:

All of you studying cse must have known what is an Onlinejudge and most of us don't know how it works. Btw, I'm not going to talk about that here. It's a simple Linux Shell Scripting example / tutorial which will show you how to handle other programs in Bash and how to access all the files in a specific folder not knowing exactly how many are there.

The following snippet works very simply. It takes a target [.cpp] file as a command line argument and compiles it using g++, generates output files for all the input files provided with. And last, it compares those files with original output files and checks whether your program generated all the outputs correctly. So you can use it for your own purposes by making proper modification. It's also very easy to understand.

Note:
The folder from where you run this script must have these in it:
1. in // it will contain the input files with [.in] extension.
2. pout // it will hold the output files generated by your program.
3. jout // it will contain the correct judge output files for testing.
4. The program you are checking for with obviously [.cpp] extension and it's name is to be passed by command line argument.
Unless you change them in the code as you like. It is always a good practice to experiment with codes. :)


# Author: Zobayer Hasan
# CSE DU - 22/10/2009

# Check whether target file is provided or exists
# If available, compile and make it executableclear

if [ $# != 1 ]; then
    echo "parameter missing"
    exit
elif [ ! -f "$1" ]; then
    echo "file not found"
    exit
else
    if [ -f PROG ]; then
        rm PROG
    fi

    g++ -o PROG "$1"

    if [ ! -f PROG ]; then
        echo "Compilation Error!"
        echo "Your program could not be compiled."
        echo ;
        exit
    fi

    chmod -c 777 PROG > log.txt
fi

# Run the executable for each file in the "in" directory
# And generate their output files in "pout" directory
# Then match with the correct files in "jout" directory

echo ;

N=0
values=$( ls ./in/*.in )

for LINE in $values
do
    ./PROG < "$LINE" > "./pout/$N.out"
    diff ./pout/$N.out ./jout/$N.out > log.txt

    if [ $? -eq 1 ]; then
        echo "Wrong Answer!"
        echo "For file $LINE. Check log file."
        echo ;
        exit
    fi

    N=$(( N + 1 ))
done

echo "Accepted!"
echo "All tests passed successfully."
echo ;

# End of script :)

Have fun with bash !!!

SPOJ Solve list comparison tool

2009-09-19T14:15:00.005+07:00

Check this:

This is a tool for comparing solve list between two users in SPOJ... Of-course you can do that with your eyes, but that's no doubt tedious...

http://www.cise.ufl.edu/~mlpalii/spoj/head2head.pl?user1=<user_id_1>&user2=<user_id_2>

This is the address of the tool.... You just need to replace the <user_id_1> and <user_id_2> with your desired two spoj user ID.

Example: say, two users "zobayer" and "shiplu", their head2head comparison is here:
http://www.cise.ufl.edu/~mlpalii/spoj/head2head.pl?user1=zobayer&user2=shiplu

Also, this site is great :: https://www.otinn.com/spoj/comparer.php (thanks to Ridowan)

Segmented Sieve

2009-09-14T01:59:00.012+07:00

Memory and time efficient :)

Problem Statement:

Your are given two integers a and b. You have to find all the primes within range a and b. Here, 1 ≤ a ≤ b ≤ 2³¹-1 and b - a ≤ 10⁵.

Note: You have to handle 1, 2 and even numbers for appropriate case of your own.

Solution:


#include <string.h>

#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032

unsigned base[MAX/64], segment[RNG/64], primes[LEN];

#define sq(x) ((x)*(x))
#define mset(x,v) memset(x,v,sizeof(x))
#define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))

/* Generates all the necessary prime numbers and marks them in base[]*/
void sieve()
{
    unsigned i, j, k;
    for(i=3; i<LMT; i+=2)
        if(!chkC(base, i))
            for(j=i*i, k=i<<1; j<MAX; j+=k)
                setC(base, j);
    for(i=3, j=0; i<MAX; i+=2)
        if(!chkC(base, i))
            primes[j++] = i;
}

/* Returns the prime-count within range [a,b] and marks them in segment[] */
int segmented_sieve(int a, int b)
{
    unsigned i, j, k, cnt = (a<=2 && 2<=b)? 1 : 0;
    if(b<2) return 0;
    if(a<3) a = 3;
    if(a%2==0) a++;
    mset(segment,0);
    for(i=0; sq(primes[i])<=b; i++)
    {
        j = primes[i] * ( (a+primes[i]-1) / primes[i] );
        if(j%2==0) j += primes[i];
        for(k=primes[i]<<1; j<=b; j+=k)
            if(j!=primes[i])
                setC(segment, (j-a));
    }
    for(i=0; i<=b-a; i+=2)
        if(!chkC(segment, i))
            cnt++;
    return cnt;
}

This is a sample program which demonstrates segmented sieve. Very fast and memory efficient version. 'base' is the array which holds the flags for all the primes upto √(2³¹-1), i.e. the square-root of the max limit, and all the primes are stored in the 'primes' array. Later, these primes are used to determine whether a number is a composite or not within a certain range in the segmented sieve. To avoid overflow and sign bit problems, unsigned type is used.

A little explanation:

First of what what these macros mean?
#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032

MAX is the sqrt of maximum possible input, in case of here, the maximum is integer range sqrt of which is almost MAX used here. So, MAX is not maximum allowed input, it is just sqrt of maximum input which is pretty big as 2147483647 i.e. 32 bit signed integer maximum.
LMT is sqrt of MAX. We all know, we run sieve upto sqrt MAX
LEN is the maximum possible different primes that can be stored using this algorithm with specific range defined as RNG, on which the segmented sieve will run and collect the primes out of it.

Now the next two vital macros:
#define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))
And why we divide by 64:

Ok, yes, it is clearly bit shifting. But you must know what we do in bitwise sieve first in order to get this. Instead of using a whole array position to store just one flag, we can use its each 32 bits to store one flag, which saves memory by a factor 1/32. So its very logical to capture memory upto MAX/32, but why MAX/64 and RNG/64 here?
Because, we really have no point of handling the even number as 2 is the only even prime and we can handle it manually, without any stress. So, if we do not consider the even numbers at all, the total numbers are again reduced by a factor 1/2, isn't it? So what we get total is MAX/32/2 = MAX/64, same for RNG.

Now, the two macros chkC and setC is pretty straight forward. chkC checks if a specific bitflag is 1 or 0, and setC sets a specific bitflag 1 to mark it as a composite. They work similarly, so I will explain only the chkC part.

In bitwise sieve, where is a specific value n located? Obviously (n/32)^th index, and on that index, (n%32)^th bit from LSB (right hand side). But we just said before, we are interested with only odd numbers, so we map n with n/2 as follows:


Actual numbers
 1   2   3   4   5   6   7   8   9 ...........   n     ;[n is odd]
 |   |   |   |   |   |   |   |   | ...........   |
 0   x   1   x   2   x   3   x   4 ........... (n/2)
Position on which they are represented in the bitstrings.

So, n is actually n/2, which implies the previous statement: n's (actually n/2 's) position is in index [n/2/32] = [n/64] = [n>>6] and on the bit position (n/2)%32 = (n>>1)&31 ;[ We know, modding with a power of 2 is same as ANDing with (same power of 2)-1 ]. The rest is, how we check / set this specific bit. I have another post explaining these operations: Bitwise operations in C: Part 3, and obviously you can google it :)

Calculate nCr using dp

2009-08-23T01:58:00.007+07:00

Calculate ⁿC_r with out having overflow when it is guaranteed that the final result will not overflow:

From pascal's triangular relation, we get,
ⁿC_r = ^n-1C_r + ^n-1C_r-1

Using this recursive formula directly will lead the program to exceed the time limit, as this may calculate the same value for many times which is un-necessary and we can remove this part by saving the states which means by using dynamic programming concepts.

In this formulation, one thing is to be noted that n and r keep decreasing, and sometimes is is possible that n becomes smaller than r. So considering these cases we get our base conditions for the recursive formula.

We know,
ⁿC_n = 1
ⁿC₁ = n
ⁿC₀ = 1
and
ⁿC_r = ^n-1C_r + ^n-1C_r-1

So, we can build the recursive function as follows:


function nCr(n, r):
    if n == r:
        return 1
    if r == 1:
        return n
    if r == 0:
        return 1
    return nCr(n-1, r) + nCr(n-1, r-1)

Now, to reduce recursive steps, we maintain a table for saving the values of ⁿC_r of intermediate steps. So, when we face a sub-problem which is already solved, we can look up its value from the pre-calculation table.


table dp[N][R]

function nCr(n, r):
    if n == r:
        dp[n][r] = 1
    if r == 1:
        dp[n][r] = n
    if r == 0:
        dp[n][r] = 1
    if dp[n][r] is not yet calculated:
        dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1)
    return dp[n][r]

Here is a sample code written in C++ which demonstrates the idea. (It is assumed that MAX N is 65 and N >= R).


#include <stdio.h>

#define i64 unsigned long long

i64 dp[66][33];

i64 nCr(int n, int r)
{
    if(n==r) return dp[n][r] = 1;
    if(r==0) return dp[n][r] = 1;
    if(r==1) return dp[n][r] = (i64)n;
    if(dp[n][r]) return dp[n][r];
    return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}

int main()
{
    int n, r;
    while(scanf("%d %d",&n,&r)==2)
    {
        r = (r<n-r)? r : n-r;
        printf("%llu\n",nCr(n,r));
    }
    return 0;
}

Plain and simple!!!

Extended Euclidean Algorithm

2009-07-13T23:09:00.007+07:00

Extended Euclidean Algorithm is an extension of standard Euclidean Algorithm for finding the GCD of two integers a and b. It also calculates the values of two more integers x and y such that: ax + by = gcd(a,b); where typically either x or y is negative. This algorithm is generally used to find multiplicative inverse in a finite field, because, if ax + by = gcd(a,b) = 1, i.e. a and be are co-primes, then x is the modular multiplicative inverse of a modulo b, and similarly, y is the modular multiplicative inverse of b modulo a.

This method computes expressions of the form $r i = a x i + b y i$ for the remainder in each step $i$ of the Euclidean algorithm. Each modulus can be written in terms of the previous two remainders and their whole quotient as follows:

By substitution, this gives:

The first two values are the initial arguments to the algorithm:

r 1 = a = a (1) + b (0)

r 2 = b = a (0) + b (1)

The expression for the last non-zero remainder gives the desired results since this method computes every remainder in terms of a and b, as desired.

Example: Compute the GCD of 120 and 23. Or, more formally, compute: x, y, g for 120x + 23y = g; where x, y are two integers and g is the gcd of 120 and 23...

The computation proceeds as follows:

Initial values:
Step 1: Reminder = 120;
Combine terms: 120 = 120 x 1 + 23 x 0

Step 2: Reminder = 23;
Combine terms: 23 = 120 x 0 + 23 x 1

Iterative steps:
Step 3: Quotient = 120 / 23 = 5; Reminder = 120 % 23 = 5;
5 = 120 - 23 x 5
=> 5 = (120 x 1 + 23 x 0) - (120 x 0 + 23 x 1) x 5 ;[from Step 1 and 2]
=> 5 = 120 x 1 + 23 x -5

Step 4: Quotient = 23 / 5 = 4; Reminder = 23 % 5 = 3;
3 = 23 - 5 x 4
=> 3 = (120 x 0 + 23 x 1) - (120 x 1 + 23 x -5) x 4 ;[from Step 2 and 3]
=> 3 = 120 x -4 + 23 x 21

Step 5: Quotient = 5 / 3 = 1; Reminder = 5 % 3 = 2;
2 = 5 - 3 x 1
=> 2 = (120 x 1 + 23 x -5) - (120 x -4 + 23 x 21) x 1 ;[from Step 3 and 4]
=> 2 = 120 x 5 + 23 x -26

Step 6: Quotient = 3 / 2 = 1; Reminder = 3 % 2 = 1;
1 = 3 - 2 x 1
=> 1 = (120 x -4 + 23 x 21) - (120 x 5 + 23 x -26) x 1 ;[from Step 4 and 5]
=> 1 = 120 x -9 + 23 x 47
End of Algorithm.

The last line reads 1 = −9×120 + 47×23, which is the required solution: x = −9 and y = 47, and obviously g = gcd(120,23) = 1

This also means that −9 is the multiplicative inverse of 120 modulo 23, and that 47 is the multiplicative inverse of 23 modulo 120.

−9 × 120 ≡ 1 mod 23 and also 47 × 23 ≡ 1 mod 120.

Algorithm:
By routine algebra of expanding and grouping like terms (refer to the previous example), the following algorithm for iterative method is obtained:

Apply Euclidean algorithm, and let q_n(n starts from 1) be a finite list of quotients in the division.
Initialize x₀, x₁ as 1, 0, and y₀, y₁ as 0,1 respectively.
Then for each i so long as q_i is defined,

Compute x_i+1= x_i-1- q_ix_i
Compute y_i+1= y_i-1- q_iy_i
Repeat the above after incrementing i by 1.

The answers are the second-to-last of x_n and y_n.

Sample Program:
Here is a sample program written in C++ which implements the Extended Euclidean Algorithm:


#include <stdio.h>
/*
Takes a, b as input.
Returns gcd(a, b).
Updates x, y via pointer reference.
*/
int Extended_Euclid(int A, int B, int *X, int *Y)
{
    int x, y, u, v, m, n, a, b, q, r;
 
    /* B = A(0) + B(1) */
    x = 0; y = 1;
 
    /* A = A(1) + B(0) */
    u = 1; v = 0;
 
    for (a = A, b = B; 0 != a; b = a, a = r, x = u, y = v, u = m, v = n)
    {
        /* b = aq + r and 0 <= r < a */
        q = b / a;
        r = b % a;
 
        /* r = Ax + By - aq = Ax + By - (Au + Bv)q = A(x - uq) + B(y - vq) */
        m = x - (u * q);
        n = y - (v * q); 
    }   
 
    /* Ax + By = gcd(A, B) */
    *X = x; *Y = y;
 
    return b;
}

int main()
{
    int a, b, x, y, g;
    scanf("%d %d", &a, &b);
    g = Extended_Euclid(a, b, &x, &y);
    printf("X = %d; Y = %d; G = %d\n", x, y, g);
    return 0;
}

Python implementation:


def Extended_Euclid(a, b):
    x, last_x = 0, 1
    y, last_y = 1, 0
 
    while b:
        quotient = a / b
        a, b = b, a % b
        x, last_x = last_x - quotient*x, x
        y, last_y = last_y - quotient*y, y
 
    return (last_x, last_y, a)

For complete reading, click here. It is also useful to have a look at the Chinese Remainder Theorem.

Hope this will help...

Largest impossible score

2009-07-12T00:40:00.010+07:00

Problem:
If two possible points in a game is p and q, what is the largest impossible score of the game which can't be achieved? Or it can't be determined? In other words, for integers p, q ≥ 0, what is the maximum number m which can't be written as a linear combination of p, q, i.e. px + qy, where, x, y ≥ 0.

Solution:
The score can only be determined when p and q are co-primes, i.e. g = GCD(a,b) = 1. Otherwise, we can only make the multiples of g and the remaining numbers can't be made which means the maximum number can't be determined, or infinite! This also covers the case if exactly one of p or q is 0.

One other required condition is p,q > 1. If anyone of p or q is 1, there is no such score which can't be achieved, i.e. answer will be 0. If p and q both are 0, we can't even make any score...

Now, we can arrange the numbers from 0 to p*q-1 in a rectangular array as follows:


   0         1        .......       q-1
   q        q+1       .......       2q-1
  ...       ...       .......       ...
  ...       ...       .......       ...
(p-1)q   (p-1)(q-1)   .......       pq-1

For example, if p = 3 and q = 7, we have the following table:


(0)    1     2   (3)   4     5   (6)
 7     8    (9)   10   11   (12)  13
 14   (15)   16   17  (18)   19   20

We have circled the multiples of p in the above table and claim these observations:

There will be q circled numbers. As we have exactly p numbers in each of q columns, so each column will have exactly one circled number, i.e. multiple of p, which implies, there will be a total of q circled number in this table.

No two circled numbers are in same same column and there will be only one circled number in any column. For the same reason stated above, exactly one circled number in each column.

Any circled number is possible. This is trivial, because, the circled numbers are multiple of one of the two given numbers, i.e. in the form p*x + q*0 or p*0 + q*x.

Any number below the circled one in the same column is possible. We have seen any circled number is possible. A circled number is the first multiple of p in the respective column, i.e. n*p, where n ≥1, so the following numbers in the column will be: n*p + q, n*p + 2*q. n*p + 3*q, ... ... ... which are always possible.

Any number above the circled one in the same column is impossible. This is also explained in the previous step. As any circled number in a column is the first one which is a multiple of one element, the number above this one will be neither the multiple of any of the two numbers. So it is impossible.

Any number ≥ p*q is possible. As we complete p rows of the table with q columns, we already have one circled number in each column, so, any number > p*q-1 (i.e. the last element of the table) will be surely following any of the q circled numbers, so any number starting from the p+1^th row, starting from p*q will be possible.

Now considering all these observations, we can see that, largest impossible number is the number just above the last circled number. The last circled number is p*q-p, i.e. 21-3 = 18 and number above it is (p*q-p)-q, i.e. 18-7 = 11. So in general, largest impossible number is: p*q - p - q.

Conclusion:
If you are given p, q :: two positive numbers, the largest number, m, which can't be expressed as a linear combination of p, q i.e. in the form px + qy, where x and y are two non-negative numbers, is p * q - p - q, when p, q > 1 and GCD(p, q) is 1 i.e. p, q are co-primes.

Binary GCD algorithm

2009-07-10T22:10:00.012+07:00

Here is a sample code for calculating GCD bitwise:


typedef unsigned int ui;

ui gcd(ui u, ui v)
{
    ui shift, diff;
    
    if (u == 0 || v == 0)
        return u | v;
    
    /* Let shift := lg K,
    where K is the greatest power of 2 dividing both u and v. */

    for (shift = 0; ((u | v) & 1) == 0; ++shift)
    {
        u >>= 1;
        v >>= 1;
    }
    
    while ((u & 1) == 0)
        u >>= 1;
        
    /* From here on, u is always odd. */

    do {
        while ((v & 1) == 0)
            v >>= 1;
            
        /* Now u and v are both odd, so diff(u, v) is even.
        Let u = min(u, v), v = diff(u, v)/2. */

        if (u < v)
            v -= u;
        else
        {
            diff = u - v;
            u = v;
            v = diff;
        }
        v >>= 1;
    
    } while (v != 0);
    
    return u << shift;
}

Actually, this algorithm outperforms the basic euclidean algorithm, so their asymptotic performance are same. According to Wikipedia, it is sometimes 60% faster than normal euclidean algorithm [proven].

But who needs it when he can do the following:


int gcd(int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}

Stunned? oh that's normal...

Craziest Language Ever !!!

2009-07-09T20:59:00.002+07:00

Just have a look at these programming languages... They are really crazy as their names.

These are called esoteric programming languages.

Factorial of negative number

2009-07-08T02:41:00.004+07:00

Is it possible to compute the factorial of a negative number?

By the definition of factorial,
n! = 1 x 2 x 3 x ..... x n

So the definition does not say about n! when n<=0.

A first way to see that 0! = 1 is writing down some factorial values downward:

We know:

n! = (n+1)! / (n+1)

...................

4! = 5! / 5 = 24

3! = 4! / 4 = 6

2! = 3! / 3 = 2

1! = 2! / 2 = 1

0! = 1! / 1 = 1

Oooo, so this is how 0! = 1 and the value of 0! is very important in the world of mathematics...

So, now, we may write the recursive definition of factorial as follows:

0! = 1

n! = n * (n-1)!

But what would happen if we would go further not stopping at 0? Lets see:

0! = 1! / 1 = 1

-1! = 0! / 0 = oops!!!

So, no matter how far we go, the result is still "oops". As we know, nothing can be divided by 0, so, factorial of negative numbers are undefined.

Another school of thoughts says, dividing by 0 is infinite (I don't support this but this context is to support a special case of a programming problem from UVA OJ :: Volume-CIII, No-10323, Factorial! You Must be Kidding!!!). If we follow this and write, -1! = (+/-)infinite and follow the path of the definition, then we will be multiplying for ever, but if n is odd, so we will start multiplying from odd a number and (-1)^odd = -1, so it may be said to be -infinite; and for the same reason, even negative numbers will yield +infinite. So, we may write:

when n<0:

n! = +infinite (when n%2==0)

n! = -infinite (when n%2==1)

Now a bit complex:

Can factorials also be computed for non-integer numbers? Yes, there is a famous function, (we are not much interested about it though, some hard and tough mathematical mumbo jumbos) the Gamma Function G(z), which extends factorials to real and even complex numbers. The definition of this function, however, is not simple:


       inf.
G(z) = INT x^(z-1) e^(-x) dx    ;[INT stands for integration]
        0

Note that the extension of n! by G(z) is not what you might think: when n is a natural number, then G(n) = (n-1)!

The gamma function is undefined for zero and negative integers, from which we can conclude that factorials of negative integers do not really exist.

Hope this helps!!!

Easy problems at UVA OJ

2009-07-07T03:02:00.006+07:00

Here are some suggestion about some very easy problems on UVA Online Judge

Programming is fun!!! especially for the beginners, and new programmers find a great inspiration on solving easy problems first as these problems are good for learning the ropes. To help some of my new friends i.e. new programmer friends who intend to solve problems on UVA OJ, here is a list of very easy problems.

Some problems among these may not seem so easy at a first glance, but after a little thinking, they will be easily solved. These problems will also help you to understand common programming techniques along with the verdict variations.

136 very easy problems for beginners:


   105    119    136    138    145    154    190    200
   256    264    272    278    294    332    344    355
   362    374    378    382    389    394    401    409
   412    412    414    417    422    424    426    438
   441    444    445    455    458    460    465    466
   468    474    476    477    478    482    483    484
   486    489    490    492    494    495    496    498
   499    530    535    543    568    573    575    579
   583    587    591    621    713    834    900    944
   974  10006  10008  10013  10018  10019  10035  10055
 10060  10071  10078  10079  10093  10104  10110  10161
 10195  10209  10221  10242  10281  10297  10302  10323
 10340  10347  10407  10432  10451  10469  10490  10499
 10515  10522  10533  10573  10591  10678  10679  10683
 10783  10784  10790  10812  10815  10922  10929  10931
 10991  11058  11121  11152  11172  11192  11192  11219
 11220  11233  11332  11343  11388  11417  11437  11455

Good Luck !!!

Negative Base Number System

2009-07-06T09:16:00.008+07:00

Negative-base systems can accommodate all the same numbers as standard place-value systems; but both positive and negative numbers are represented without the use of a minus sign (or, in computer representation, a sign bit); this advantage is countered by an increased complexity of arithmetic operations. The need to store the "information" normally contained by a negative sign often results in a negative-base number being one digit longer than its positive-base equivalent.

The common names for negative-base positional numeral systems are formed by prefixing nega- to the name of the corresponding positive-base system; for example, negadecimal (base -10) corresponds to decimal (base 10), negaternary (base -3) to ternary (base 3), and negabinary (base -2) to binary (base 2).

Denoting the base as − r, every integer a can be written uniquely as:

where each digit

d k

is an integer from 0 to

r - 1

and the leading digit

d n

> 0

(unless

n =0

). The base

- r

expansion of

a

is then given by the string d_nd_n-1.....d₁d₀.

Calculation:

The base

- r

expansion of a number can be found by repeated division by

- r

, recording the non-negative remainders of 0,1,2,.........,r-1; and concatenating those remainders, starting with the last. Note that if

a / b = c

, remainder

d

, then

b c + d = a

. For example, 146 in negaternary:



146 / -3 = -48; reminder = 2
-48 / -3 =  16; reminder = 0
 16 / -3 =  -5; reminder = 1
 -5 / -3 =   2; reminder = 1
  2 / -3 =   0; reminder = 2

Therefore, the negaternary expansion of 146 is 21102.

Note that in most programming languages, the result (in integer arithmetic) of dividing a negative number by a negative number is rounded towards 0, usually leaving a negative remainder; to get the correct result in such case, computer implementations of the above algorithm should add 1 and

r

to the quotient and remainder respectively.

The numbers -15 to 15 with their expansions in a number of positive and corresponding negative bases are:

Decimal	Negadecimal	Binary	Negabinary	Ternary	Negaternary
-15	25	-1111	110001	-120	1220
-14	26	-1110	110110	-112	1221
-13	27	-1101	110111	-111	1222
-12	28	-1100	110100	-110	1210
-11	29	-1011	110101	-102	1211
-10	10	-1010	1010	-101	1212
-9	11	-1001	1011	-100	1200
-8	12	-1000	1000	-22	1201
-7	13	-111	1001	-21	1202
-6	14	-110	1110	-20	20
-5	15	-101	1111	-12	21
-4	16	-100	1100	-11	22
-3	17	-11	1101	-10	10
-2	18	-10	10	-2	11
-1	19	-1	11	-1	12
0	0	0	0	0	0
1	1	1	1	1	1
2	2	10	110	2	2
3	3	11	111	10	120
4	4	100	100	11	121
5	5	101	101	12	122
6	6	110	11010	20	110
7	7	111	11011	21	111
8	8	1000	11000	22	112
9	9	1001	11001	100	100
10	190	1010	11110	101	101
11	191	1011	11111	102	102
12	192	1100	11100	110	220
13	193	1101	11101	111	221
14	194	1110	10010	112	222
15	195	1111	10011	120	210

Note that the base $- r$ expansions of negative integers have an even number of digits, while the base $- r$ expansions of the non-negative integers have an odd number of digits.

Program for calculating Negabinary

In python:


def negabinary(i):
    digits = []  
    while i != 0:
        i, remainder = divmod(i, -2)
        if remainder < 0:
            i, remainder = i + 1, remainder + 2
        digits.insert(0, str(remainder))
    return ''.join(digits)

In C++:


string negabinary(int i)
{
    int reminder;
    string digits;
    while(i != 0)
    {
        reminder = i % -2;
        i /= -2;
        if(reminder < 0)
        {
            i++;
            reminder += 2;
        }
        digits.push_back(reminder+'0');
    }
    reverse(digits.begin(),digits.end());
    return digits;
}

The same procedure it to be followed for calculating other negative number system.

Source: Wikipedia

0.99999999................... = 1

2009-07-06T03:00:00.008+07:00

Wanna see the proof? Check it out....

Let's assume,


Let, x = 0.99999999999999............................
=> 10x = 9.99999999999999............................
=> 10x = 9 + 0.99999999999999............................
=> 10x = 9 + x
=>  9x = 9
=>   x = 1
So, 0.99999999999999............................ = 1

Is anything going wrong here?

Matrix A	Matrix B
\| g(n) \| \| g(n-1) \| \| f(n+1) \| \| f(n) \|	\| g(n+1) \| \| g(n) \| \| f(n+2) \| \| f(n+1) \|

I, ME AND MYSELF !!!

Character Device Driver

Linux Kernel Programming: Writing a simple character device driver

Writing My Own 'ls'

Beginning Kernel Programming

Writing My Own Shell

DP @ UVa

C++ log() and log10()

3D to 2D vector?

A C++ Mistake

Huffman's Code

Pollard's Rho in Java

Java Access Modifiers

Overview:

Public

Protected

Default or no modifier

Private

More on "protected"

Summery of the above

Blogger Spacing Problem

Spacing problems in blogger blogs

Story of Centipede

SPOJ - POSTERS

138. Election Posters

CSE 202 Pseudo Codes 2

Insert ans Delete operation on a Singly Linked List

Insert Procedure

Delete Procedure

CSE 202 Pseudo Codes 1

Iterative Tree Traversal

Preorder

Inorder

Postorder

Facebook Like on Blogger

Add facebook "like" on every post of your blogger blog

About recent design changes

getch() & getche() in gcc/g++

SPOJ Problem Classifier

SPOJ - HORRIBLE

Problem 8002. Horrible Queries

Setup connector/j for JDBC

Setting up MySQL driver connector/j for JDBC in Windows

CRC - 32 (IEEE)

Matrix Exponentiation

Introduction:

Prerequisite:

Patterns:

Type 1:

Type 2:

Type 3:

Type 4:

Type 5:

Type 6:

Type 7:

Analysis:

Related problems:

Merge Sort Improvement?

Threaded Merge Sort

What?

How threading helps:

A simple implementation:

Merge Sort

Introduction:

Algorithm:

Analysis:

C++ Implementation:

Reference:

Simple Take Away Game

Take Away Game :

Another Example from SPOJ :

Analysis :

Stress on Optimal Play :

Binary Tree -- N Nodes & H Height

The problem:

Analysis:

Solution:

Sample program:

Similar problem:

BrainF**k & C++