Wednesday, December 29, 2010

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!

Friday, December 24, 2010

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:
`<iframeallowTransparency='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!

Monday, December 20, 2010

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.

Friday, December 10, 2010

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

As sometimes, we use the header "conio.h" in windows (although deprecated), 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, and 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 error 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

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.

Thursday, December 9, 2010

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.

Saturday, December 4, 2010

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

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:
1. 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".
2. 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!".