CSE 202 Pseudo Codes 1

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

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

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

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.

SPOJ - HORRIBLE

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

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:

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!".