How to Solve a Polynomial Number Sequence

Given a polynomial sequence (e.g. 1, 2, 4, 7, 11), how can we easily find the next number in that sequence?

http://digg.com/programming/How_to_Solve_a_Polynomial_Number_Sequence

First of all, each of the numbers in a polynomial sequence is a result of a polynomial function on n (where n = 1, 2, 3, ...). In other words, f(n) = amnm + am-1nm-1 + am-2nm-2 + ... + a2m2 + a1m + a0. The example above (1, 2, 4, 7, 11) can be represented by the polynomial function f(n) = 0.5n2 - 0.5n + 1.

Checking,
f(1) = 0.5(1)2 - 0.5(1) + 1 = 1
f(2) = 0.5(2)2 - 0.5(2) + 1 = 2
f(3) = 0.5(3)2 - 0.5(3) + 1 = 4
f(4) = 0.5(4)2 - 0.5(4) + 1 = 7
f(5) = 0.5(5)2 - 0.5(5) + 1 = 11

Hence, the next number in the sequence is
f(6) = 0.5(6)2 - 0.5(6) + 1 = 16

With this knowledge, how can we find the next number in a given polynomial sequence? Initially, i tried to find a0, a1, ..., am in the function f(n) = amnm + am-1nm-1 + am-2nm-2 + ... + a2m2 + a1m + a0 and work on from there. That would work, but for sure it was very tedious, especially if we have a high-degree polynomial function.

I then did a search for other methods to do this, and came across this page: http://www.everything2.com/index.pl?node_id=1026695. The first idea (by ariels) on that page is a simple and powerful method for solving polynomial sequences without having to solve for the coefficients of the function itself. You can read up on the method by visiting the link itself; my contribution here would be a Java programme which makes use of the algorithm described by that method:

import java.util.ArrayList;
import java.util.List;

public class Main
{
    public static final void main(String[] args)
    {
        int numInput = args.length;

        List<int[]> sequencesList = new ArrayList<int[]>(100);

        int currentSeqLen = numInput;
        int[] currentSequence = new int[currentSeqLen + 1];
        boolean constantFound = true;

        for (int i = 0; i < currentSeqLen; i++)
        {
            currentSequence[i] = Integer.parseInt(args[i]);

            if (constantFound
                    && (i > 0)
                    && (currentSequence[i] != currentSequence[i - 1]))
            {
                constantFound = false;
            }
        }

        sequencesList.add(currentSequence);

        while (!constantFound)
        {
            int[] prevSequence = currentSequence;

            currentSeqLen--;
            currentSequence = new int[currentSeqLen + 1];
            constantFound = true;

            for (int i = 0; i < currentSeqLen; i++)
            {
                currentSequence[i]
                        = prevSequence[i + 1] - prevSequence[i];

                if (constantFound
                        && (i > 0)
                        && (currentSequence[i] != currentSequence[i - 1]))
                {
                    constantFound = false;
                }
            }

            sequencesList.add(currentSequence);
        }

        for (int i = currentSeqLen; i < (currentSeqLen + 1); i++)
        {
            currentSequence[i] = currentSequence[i - 1];
        }

        for (int i = (sequencesList.size() - 2); i >= 0; i--)
        {
            int[] prevSequence = currentSequence;

            currentSeqLen++;
            currentSequence = sequencesList.get(i);

            for (int j = currentSeqLen; j < (currentSeqLen + 1); j++)
            {
                currentSequence[j]
                        = currentSequence[j - 1] + prevSequence[j - 1];
            }
        }

        System.out.println(currentSequence[numInput]);
    }
}

This programme takes in a sequence of numbers as arguments, and outputs the next number of that polynomial sequence.

E.g.
Input: java Main 1 2 4 7 11
Output: 16

Ubuntu 6.10 - How to Have a Minimal Graphical Desktop

The desktop installation of Ubuntu is touted as a complete Linux-based operating system, and includes many of the major applications. Indeed, Firefox, OpenOffice.org, Gaim, GIMP, and the Totem Movie Player are just some of the applications that come pre-installed if you used the desktop CD.

http://digg.com/linux_unix/Ubuntu_6_10_How_to_Have_a_Minimal_Graphical_Desktop

The downside of this is that if you have an older system with limited resources (memory, hard disk space, etc.), you may not want to have all of those applications pre-installed. One way around this is to manually un-install those applications that you do not want. However, that can be quite a pain if you intend to remove more than a few of them, and if you are really THAT low on hard disk space, you will not be able to get the desktop installation done in the first place.

The alternative is to start with a minimal graphical desktop and almost none of the applications installed. You then have the flexibility to add an application only as and when you need it. We will explore the two steps needed to achieve this.

1. Download the server install CD (instead of the desktop CD), and install from that.

One thing to note is that the server install CD functions differently from the desktop CD. The server install CD does not function as a live CD, so do not expect to boot to a graphical desktop to do the installation. The installation procedure is purely text-based, but otherwise, it is quite straightforward and should take a much shorter time than installing with the desktop CD (less packages to install).

2. Install the packages necessary for a graphical GNOME desktop.

When you boot into the system after you complete step one, all you will get is a text-based system. If you are used to the graphical desktop, this may be a little disconcerting, but do hang in there! The next step is to use apt-get to install the packages necessary for a graphical GNOME desktop.

The packages that you will need are:

• gdm
• gnome-applets
• gnome-control-center
• gnome-icon-theme
• gnome-menus
• gnome-panel
• gnome-session
• gnome-terminal
• menu
• metacity
• nautilus
• synaptic
• x-window-system-core

The packages listed here are related to the X window system and the GNOME desktop environment, with the exception of nautilus, which is a graphical file manager, and synaptic, which is an application that makes it easier for you to install other applications and packages in future (sort of like a graphical front-end to apt-get).

In a nutshell, the two commands you will have to run from the command line (either as root, or using sudo) are

apt-get update

and

apt-get install gdm gnome-applets gnome-control-center gnome-icon-theme gnome-menus gnome-panel gnome-session gnome-terminal menu metacity nautilus synaptic x-window-system-core

Once that is done, reboot, and you should get a graphical log in prompt this time.

There you have it. A graphical desktop installation for Ubuntu without all the heavy applications.

Reference:
Ubuntu Web Forum: What Packages Needed for Basic Installation + GNOME

5 Pitfalls Involving Java Exceptions

After looking at a fair number of application source codes written by others, i have noticed that these are some of the most common pitfalls involving exceptions. i must admit that i have committed them at one time or another as well -- earlier, due to ignorance, and later on, due to convenience (but only in trivial, run-once-and-throw utilities). i am sure there are other common mistakes and bad habits in this area, but these few i have come across most often.

1. Catching an exception, then doing absolutely nothing.

try
{
    FileReader in = new FileReader("MyFile.txt");
}
catch (FileNotFoundException ex) {}

This, in my humble opinion, is the single worst thing to do with an exception. Should the exception occur, the offending application continues to run in an indeterminate state. At best, another exception (usually a NullPointerException) will terminate the application a few lines later. At worst, it just continues to inexplicably (to the programmer) churn out erroneous results.

There is a, well, exception to this though. When we clean up resources in finally blocks (e.g. closing connections, streams, etc.), We typically enclose those statements in try-catch blocks to allow the finally block to run to completion.

InputStream in = null;

try
{
    // Do Stuffs Here
}
finally
{
    if (in != null)
    {
        try
        {
            in.close();
        }
        catch (IOException ignore)
        {
            // Ignore
        }
    }
}

http://www.digg.com/programming/5_Pitfalls_Involving_Java_Exceptions

In such cases, it is "forgiveable" to ignore the exception. The failure to close a resource usually does not prevent an application from continuing to run correctly, and there is also little corrective action that can be done about it. However, it is still better to log the exception (perhaps with a lower priority), so that if indeed a resource leakage is detected later on (and resource leakages are usually not obvious right away), the cause of the leakage can be traced.

2. Allowing an exception to manifest itself to the user, and terminating the application.

For desktop applications, this means throwing exceptions out of the main method.

public static void main (String[] args)
        throws IOException, FileNotFoundException
{
    // Do Stuffs
}

This is bad because usually, the user cannot do anything about the exception that just showed up, and in most cases, the stack trace would not even make any sense to him. In the worst case, the user could be halfway through a critical piece of work when the application crashed on him.

3. Not ensuring that the finally block completes normally.

As mentioned above, an important practice is to make use of finally blocks to clean up resources before they are garbage-collected, and these cleaning-up statements are wrapped in try-catch blocks, but sometimes, it is not done correctly.

FileInputStream in = null;
OutputStream out = null;

try
{
    // Do Stuffs
}
finally
{
    try
    {
        in.close();
        out.close();
    }
    catch (IOException ignore)
    {
        // Log Exception
    }
}

The problem here is that, if the in.close() statement throws an exception, the out.close() statement will not even be attempted, and the output stream will be left open. In more serious cases, this could lead to resource leakages. The more correct way to do this, would be to wrap each clean-up statement individually in its own try-catch block.

FileInputStream in = null;
OutputStream out = null;

try
{
    // Do Stuffs Here
}
finally
{
    if (in != null)
    {
        try
        {
            in.close();
        }
        catch (IOException ignore)
        {
            // Log Exception
        }
    }

    if (out != null)
    {
        try
        {
            out.close();
        }
        catch (IOException ignore)
        {
            // Log Exception
        }
    }
}

4. Throwing ExceptionS.

Throwing exceptions in general is not a big issue, it is the throwing of an instance of the Exception class (as opposed to a specific sub-class) that sometimes causes a loss of clarity in the code.

private String readFromFile(String filename) throws Exception
{
    FileInputStream in = null;

    try
    {
        in = new FileInputStream(in);

        // Do Stuffs
    }
    finally
    {
        if (in != null)
        {
            try
            {
                in.close();
            }
            catch (IOException ignore)
            {
                // Log Exception
            }
        }
    }
}

In the readFromFile method above, there are possibly FileNotFoundExceptionS and IOExceptionS that need to be handled. One way to handle them would be to catch them within the method itself (and appropriately handling them). Declaring throws FileNotFoundException, IOException in the method header is fine too, but declaring an all-purpose throws Exception is not a good practice, and there are a couple of reasons to this.

Firstly, the throws clause in a method header is considered to be part of the interface contract. Following the principles of abstraction and encapsulation, declaring specific exceptions (and providing the corresponding Javadoc comment) would allow a programmer to understand how this method could potentially fail without having to delve into the implementation details. Declaring a generic throws Exception simply tells the programmer that, well, this method could potentially fail.

Secondly, declaring specific thrown exceptions would allow the calling method to handle each exception separately in different catch blocks. In the example above, the calling method would have to handle the exception in a generic manner. Should it be more appropriate for the calling method to throw the exception instead of handling it, it would also have to declare a generic throws Exception.

5. Throwing the wrong exception.

private void setValue(String s) throws ClassNotFoundException
{
    if (s == null)
    {
        throw new ClassNotFoundException();
    }

    this.value = s;
}

This is a rather contrived example. The next example is a more common sighting, but it is not much more better off either.

private void setValue(String s) throws Exception
{
    if (s == null)
    {
        throw new Exception();
    }

    this.value = s;
}

This sort of follows the argument in the previous point about the importance of the declared exception. Always throw the appropriate exception type. If an appropriate exception is not available, by all means create a new sub-class of Exception. In the examples above, the most appropriate exception to throw would perhaps be the IllegalArgumentException.