Monday, July 25, 2011

Character Device Driver

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

#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_AUTHOR("Zobayer Hasan");
MODULE_DESCRIPTION("A simple character device driver.");

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 *);


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;
    buff_rptr = buff_wptr = device_buffer;
    return 0;

static int device_release(struct inode *nd, struct file *fp) {
    if(device_opend) device_opend--;
    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
    make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) modules
    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!

Saturday, July 2, 2011

Writing My Own 'ls'

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.

Friday, July 1, 2011

Beginning Kernel Programming

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
    make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) modules
    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 :)

Tuesday, May 17, 2011

Writing My Own Shell

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 :)

Saturday, March 19, 2011

DP @ UVa

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

Friday, March 11, 2011

C++ log() and log10()

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 logba, 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?

Thursday, March 3, 2011

3D to 2D vector?

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:
α[x1, y1, z1] + β[x2, y2, z2] = [γ1, γ2, γ3] ... (2)

Now if we apply the transformation from (1), we get a system of 2D vectors as follows:
α[y1-x1, z1-x1] + β[y2-x2, z2-x2] = [γ21, γ31] ... (3)

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

From (2), we get 3 equations:
αx1 + βx2 = γ1 ... (I)
αy1 + βy2 = γ2 ... (II)
αz1 + βz2 = γ3 ... (III)

Similarly from (3) we get 2 equations:
α(y1-x1) + β(y2-x2) = γ21
α(z1-x1) + β(z2-x2) = γ31

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:
α1[x1, y1, z1] + α2[x2, y2, z2] + ... ... + αn[xn, yn, zn] = [γ1, γ2, γ3]

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 γ1 = γ2 = γ3 = γ 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!

Sunday, January 23, 2011

A C++ Mistake

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.

Saturday, January 22, 2011

Huffman's Code

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 {
Node *left, *right;
int weight, ch;
Node() {}
Node(int _w, int _c) : weight(_w), ch(_c) { left = right = NULL; }
~Node() {}

class comp {
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));
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.pop();
Node *b = new Node;
*b =; Q.pop();
Node c(a->weight + b->weight, 0);
c.left = a, c.right = b;

// traverse tree to generate code
generate(&, 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

Thursday, January 13, 2011

Pollard's Rho in Java

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.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)) {

BigInteger divisor = rho(N);

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

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

while(null != (string = reader.readLine())) {
BigInteger N = new BigInteger(string);
for(int i = 0; i < v.size(); i++) System.out.println(v.get(i));
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...

Thursday, January 6, 2011

Java Access Modifiers


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

  1. Public

  2. Protected

  3. Default or no modifier

  4. 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:


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.


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.


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

publicprotectedno modifierprivate
Same classYesYesYesYes
Same package subclassYesYesYesNo
Same package non-subclassYesYesYesNo
Different package subclassYesYesNoNo
Different package non-subclassYesNoNoNo

I think these are the cases.

Tuesday, January 4, 2011

Blogger Spacing Problem

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; }

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 -->

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



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

Monday, January 3, 2011

Story of Centipede

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.


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:

1 4
2 6
8 10
3 4
7 10

The states of the set are shown after each input:

1 4
first entry

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

8 10
no conflict

3 4
conflicts with (2,6) (left and right both)

7 10
conflicts with (8,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

Sunday, January 2, 2011

CSE 202 Pseudo Codes 2

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;
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;

Delete Procedure

Delete ( head, n )
if head = null then return;
if n = 1 then
temp := head, head := Next[head];
free temp;
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;

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