Introduction to Algorithms (An OpenCourseWare from MIT)

One of my friends (Manu Garg) told me about this course by MIT on Algorithms. Here are the links if you are interested:

Course Home | Course Download page | Video & Audio lectures of the course

I found a way to download these courses and also some other lectures of the prerequisites for this course by Googling. Yes, it's legal and it's from MIT's website.
One of the prerequisites for this course is "6.001 Structure and Interpretation of Computer Programs." The first version of this course's video lectures are available here for download.

Downloading 6.046J / 18.410J Introduction to Algorithms:

The URLs of the video lectures for Introduction to Algorithms have the following format:

http://mfile.akamai.com/7870/rm/mitstorage.download.akamai.com/7870/6/6.046j/f05/lecturenotes/ocw-6.046-07sep2005-220k.rm

If you'd like to download the entire file and play it, use the following URL:

http://ocw.mit.edu/ans7870/6/6.046j/f05/lecturenotes/ocw-6.046-07sep2005-220k.rm

The only change is the part in bold and red (i.e., till mitstorage.download.akamai.com/ in the first URL, the rest is the same.)

Extra, extra:

• Alternative Link for Video Lectures
• Scott Hanselman on Learning Algorithms
• Free Science Online has plenty of excellent links
  

More Extra:

Steve Skiena's, the author of the infamous Algorithm Design Manual, lectures are available for viewing from here. He also has videos of his discrete mathematics lectures here.

Java :: FindBugs :: Dead Store

I ran FindBugs on one of our projects and I had a warning on some code similar to this, let's see how the code was written. This is just a sample code to show an example, don't expect any logic here :-)

// DeadStoreExample.java
import java.util.ArrayList;
import java.util.List;

public class DeadStoreExample {
  public static void main(String[] args) {
    List list = new ArrayList(); // Dead Store here.
    list = getList();
    System.out.println(list);
  }

  private static List getList() {
    // Some intense operation and finally we return a java.util.List
    return new ArrayList();
  }
}

FindBugs reported me this problem: Dead store to list in DeadStoreExample.main(String[]). When I first saw it, I was like "What do you mean by Dead Store?" And when I looked into the code I saw a List object being created but not used. Instead, in the next line the reference variable is pointing to some other object in the heap. The object created on line number 6 is never used and hence it's a dead store.

So, what is a Dead Store? If we assign a value to a local variable, but the value is not read by any subsequent instruction, then it's called a Dead Store.

I love FindBugs, the thing that I like the most about FindBugs is that it tries to find all the lame bugs which many veteran programmers accidentally make. I always like to set my compiler warnings very high (even for my Javadoc comments). And now I have developed a habit of running FindBugs before I make a build or commit my code. It's one of those things like Unit Testing, you must try and get infected.

If a compiler or a tool can catch a bug, then I will always go for it. No one can write bug free code, at least I have not seen anyone till now. And I believe in automating anything that is possible so that we never have to do that manually again. That's why we have computers :-)

If you're not using FindBugs, I highly recommend that you to use it.

Python :: Calculate the Size of a MySQL Schema Approximately

Hi,

Recently I wanted to find out the total size of a schema in a MySQL database. I searched for it but can't really find it. So, I wrote something on my own, really simple which doesn't really bother about a lot of error conditions. But I think that's ok, I mean really this is not a project. I am posting my code here now, feel free to optimize it and tweak it to your own requirement and let me know if you have a better solution :-)

#!/usr/bin/python

"""Calculates the total size of a MySQL database schema approximately."""

import MySQLdb
import getpass

def main():
    db_host = raw_input('Host name: ')
    schema_name = raw_input('Schema name: ')
    user_name = raw_input('User name: ')
    password = getpass.getpass('DB Password: ')
    db_conn = MySQLdb.connect(host=db_host, user=user_name,
            passwd=password, db=schema_name)
    db_cursor = db_conn.cursor(MySQLdb.cursors.DictCursor)
    db_cursor.execute('show table status')
    rows = db_cursor.fetchall()
    total_size = 0
    for row in rows:
        data_length = row['Data_length']
        if data_length is None:
            data_length = 0
        index_length = row['Index_length']
        if index_length is None:
            index_length = 0
        total_size = total_size + data_length + index_length
    print '------------------------'
    print 'Total size: %s KB.' % str(total_size / 1024)
    db_conn.close()


if __name__ == '__main__':
    main()

I didn't add any exception handling code, I thought it would clutter the actual code I wanted to show.

Eclipse :: Configuring Eclipse Startup

If your eclipse is starting up a little slower or if it's running a little slower or if it gets an OutOfMemoryError, then just go through this checklist:-

• Is it using the latest and the fastest JRE?


• Is it having a good minimum and maximum memory?

And then follow this lovely blog:-
http://swem.wm.edu/blogs/waynegraham/index.cfm/2006/9/7/Tweaking-Eclipse

Let me know if the link doesn't work :-)

Java :: Constants Interface or Constants Class?

We all know about patterns and anti-patterns. One anti-pattern that has been hated by many people is the Constant Interface anti-pattern. Java doesn't support globals directly, but sometimes you will need to have a few things as global. Meaning, accessible to every class in your entire program.

In Java to get the platform independent new line character, we write the following code:

final String NEW_LINE = System.getProperty("line.separator");

But the new line character is something any class in our program may need and writing System.getProperty("line.separator") is not good for two reasons.

1. We may misspell the key 'line.separator' in which case we'll get a 'null' back, and
2. It's inefficient.
   

A better way is to get this new line character one time, store it in the memory and make it accessible to all the classes in our program. This kind of a situation led to the invention of the "Constant Interface" anti-pattern. People implemented this pattern like this:

public interface Constants {
  String NEW_LINE = System.getProperty("line.separator");
}

And the client of this 'Constants' interface started implementing this interface for convenience reasons. This is a bad idea because let's say this 'Constants' interface has 100 constants and a client class implements this interface for convenience reasons, all the 100 constants from the interface end up being a part of the public API of the client class. This breaks inheritance and you can by now imagine how the Javadoc will look like for this client class.

OK, we may ask all of our clients of this 'Constants' interface that they must not implement this interface and they should only see it as a place where global constants are stored, but what's the guarantee that they will NOT implement this interface?

Thankfully we have a better way of doing this, see the following code:

public class Constants {
  public static final String NEW_LINE = System.getProperty("line.separator");

  private Constants() {
    // Private constructor to enforce un-instantiability.
  }
}

The above 'Constants' class has the following benefits over the 'Constants' interface:

1. No client can instantiate, because the constructor is private
2. No client can extend, again for the same reason, the constructor is private
   

Having a class for constants and making it's constructor private is a much better approach than using an interface.

Java :: Static Inner Classes

We all know that Java supports the creation of inner classes. Some people intentionally avoid creating inner classes for many good reasons. And also, one should avoid creating non-static inner classes without a very solid reason. Till now I have never created a non-static inner class except for the anonymous inner classes that I created for event-listeners in GUI programming.

But recently I started using static-inner classes for various purposes and it has tremendously improved my code's readability. Currently I'm using it for two purposes.

1. Creating Private Utilities
2. Creating Private Implementations

Creating Private Utilities

What do I mean by "Private Utilities"? We have classes like SwingUtilities, Math, etc. They all contain only "public static" methods and they enforce non instantiability by means of a private constructor. These are public utility classes, but not all the utility classes we create must be public. There are times you will need to have them private. For example, you want to implement your own FileFilter but you don't want to make it public or even package-private. And you also don't want to create that implementation as an anonymous inner class because you think it may clutter the code.

This is a perfect reason for creating a "private static" inner class.

Creating Private Implementations

Just open the source code of java.util.Hashtable and you will see 2 private static inner classes: EmptyEnumerator, and EmptyIterator. When we invoke Hashtable.keys() method, it first checks if the Hashtable has any elements in it. If the number of elements in the Hashtable is 0, it returns an instance of EmptyEnumeration which is a private implementation of java.util.Enumeration interface for empty Hashtable.

These are only a very few applications of static inner classes. I see them as a tool that can make my code more readable, elegant and efficient.

Java :: Exceptions :: Nested Exceptions

There is a nice little thing that got introduced in Java 1.4, it's nested exceptions.

Consider the following piece of code:

class LowLevelException extends Exception {
  public LowLevelException(String message) {
    super(message);
  }
}

class HighLevelException extends Exception {
  public HighLevelException(String message, Throwable cause) {
    super(message, cause);
  }
}

public class TryNestedExceptions {
  public static void main(String[] args) {
    try {
      throw new LowLevelException("LowLevelException here.");
    } catch(LowLevelException e) {
      // While throwing a higher level exception, construct it with
      // the LowLevelException as the cause.
      try {
        throw new HighLevelException("HighLevelException here.", e);
      } catch (HighLevelException e1) {
        e1.printStackTrace();
      }
    }
  }
}

Let's see the stack trace of the above program:

HighLevelException: HighLevelException here.
at TryNestedExceptions.main(TryNestedExceptions.java:21)
Caused by: LowLevelException: LowLevelException here.
at TryNestedExceptions.main(TryNestedExceptions.java:16)

We also have stack trace of the LowLevelException in the "Caused by:" of HighLevelException's stack trace. This helps us to drill down to the root of the problem. I like the nested exception idea very much. We can nest as many exceptions as we want. For example, if the LowLevelException was caused due to some IOException then while throwing LowLevelException we can nest the IOException.

Naming :: Threads

I find it a good habit to name the threads that we create. For example, in Java the name of the Thread that executes the main method is called 'main'.

It's very useful while debugging or while viewing our log files when we have the thread namea in the log messages. It's especially useful in a multi-threaded application.

public class Main {
  public static void main(String[] args) {
    // Let's see the main thread's name.
    System.out.println("We are currently in: "
           + Thread.currentThread().getName());
  
    Thread thread = new Thread() {
      public void run() {
        String currentThreadName = Thread.currentThread().getName();
    
        for (int i = 0; i < 5; i++) {
          // Printing the user thread's name.
          System.out.println("We are currently in: "
              + currentThreadName);
        }
      }
    };
  
    // Setting a name for our user thread.
    thread.setName("MyUserThread");
    thread.start();
  
    // We're back in the main thread, let's check it.
    System.out.println("We are currently in: "
         + Thread.currentThread().getName());
  }
}

So, let's all give our Threads a meaningful name :-)

Naming :: Acronyms and Abbreviations

How often do we have to look into the code when a class name or a variable name contains acronyms or abbreviations in it. For example consider the following class name:

class MyCPPProgram {};

The class name, MyCPPProgram, is correct and fine except that it can be more readable if we declared the class like this:

class MyCppProgram {};

I find the 2nd one more readable than the 1st one. We can also see a similar naming pattern in Java. For example the HttpServlet class. It's not HTTPServlet.