Monday, December 04, 2006

Good Hash Discussion

Friday, December 01, 2006

Timers in C#

private void CreateTimer()
System.Timers.Timer Timer1 = new System.Timers.Timer();
Timer1.Enabled = true;
Timer1.Interval = 5000;
Timer1.Elapsed +=
new System.Timers.ElapsedEventHandler(Timer1_Elapsed);

private void Timer1_Elapsed(object sender,
System.Timers.ElapsedEventArgs e)
"Timer Event Raised!");

Tuesday, November 28, 2006

Berkeley DB

From :
1. Berkeley DB is an embedded database that supports fairly simple data access with a rich set of data management services

Data access in this context means
a) insert b)update c)search d)delete
Data management in this context means that
a)Concurrency b)Transactions c)Recovery

Thursday, November 02, 2006

Unix Ports

From Google groups

netstat -lp

It will tell you which task is listening on the port.

fuser -v -n tcp 32768

Will tell you which task is listening on the specified port and under
which account it's running.

Monday, October 30, 2006

IE6 duh?

urns out, IE doesn't like the script tags if they are using element minimization. I got the page rendering just as I intended by changing the tag to look like this:

Doing some research, I came across this post in theList by Eric Vitiello which clarifies this more. Apparently the DTD declaration for the script tag says , and the XHTML specs says (under Appendix C. 3):

Given an empty instance of an element whose content model is not EMPTY (for example, an empty title or paragraph) do not use the minimized form (e.g. use

and not


So, I guess this isn't really a bug in IE. I'd think instead, that this is a bug in the DTD itself. The script tag doesn't have to contain #PCDATA (in fact, I consider it graceful if it doesn't), and forcing it is, well, stupid.

For now, I am explicitly closing the script tag with a seperate closing tag, and everything seems to be working well. Does anyone have any idea about handling this better, preferably with minimized element closures

stolen from

Monday, October 23, 2006

When do you need a pointer to a reference?

From C++ groups
> Why/when would someone need a pointer to a reference?

Never. A reference is another name for a real thing. A pointer can only
point to a real thing - it can't point to a name for a real thing.

References are often implemented as secret pointers, but it breaks the
language if you try to get a handle on this secret pointer - it is an
implementation detail.

If you meant a reference to a pointer, use this when you need something to
grab your pointer, point it to something else, and give the result back to
you. Consider a parser that reads statements written by the user:

WORD_TYPE getWord (char *&statement);

Each time you call this function it finds a word, returns its type, and
points the pointer off the end of the word.

Friday, October 20, 2006

VIM split

Vim viewport keybinding quick reference

:sp will split the Vim window horizontally. Can be written out entirely as :split .

:vsp will split the Vim window vertically. Can be written out as :vsplit .

Ctrl-w Ctrl-w moves between Vim viewports.

Ctrl-w j moves one viewport down.

Ctrl-w k moves one viewport up.

Ctrl-w h moves one viewport to the left.

Ctrl-w l moves one viewport to the right.

Ctrl-w = tells Vim to resize viewports to be of equal size.

Ctrl-w - reduce active viewport by one line.

Ctrl-w + increase active viewport by one line.

Ctrl-w q will close the active window.

Ctrl-w r will rotate windows to the right.

Ctrl-w R will rotate windows to the left.


Thursday, October 19, 2006


Monday, September 25, 2006


minute hour dom month dow user cmd

minute This controls what minute of the hour the command will run on,
and is between '0' and '59'
hour This controls what hour the command will run on, and is specified in
the 24 hour clock, values must be between 0 and 23 (0 is midnight)
dom This is the Day of Month, that you want the command run on, e.g. to
run a command on the 19th of each month, the dom would be 19.
month This is the month a specified command will run on, it may be specified
numerically (0-12), or as the name of the month (e.g. May)
dow This is the Day of Week that you want a command to be run on, it can
also be numeric (0-7) or as the name of the day (e.g. sun).
user This is the user who runs the command.
cmd This is the command that you want run. This field may contain
multiple words or spaces.

Thursday, September 21, 2006

AJAX the Diagram

Monday, August 21, 2006


#pragma warning(disable: 4786)


using namespace std;

int main() {
map ass_array;

// Assign keys and values

ass_array["fat"] = 0;
ass_array["sodium"] = 45;
ass_array["totalcarb"] = 46;
ass_array["protien"] = 0;

// Insert Value

ass_array.insert( map::value_type( "potassium", 25 ) );

// Print value of sodium

cout << ass_array["sodium"] << endl;
cout << "The map has " << ass_array.size() << " entries.\n";

// Iterator used to hold position in the map

map::iterator loc;

// Returns same value as ass_array.end() if not find.

loc = ass_array.find("sugar");

if(loc != ass_array.end())
cout << "Sugar found!\n";
cout << "No Sugar\n";

return 0;



#include // Include algorithms
using namespace std;

vector vec;
vec.push_back (10);
vec.push_back (3);
vec.push_back (7);

sort(vec.begin(), vec.end()); // Sort the vector

// The vector now contains: 3, 7, 10

STL: find

list nums;
list::iterator nums_iter;

nums.push_back (3);
nums.push_back (7);
nums.push_front (10);

nums_iter = find(nums.begin(), nums.end(), 3); // Search the list.
if (nums_iter != nums.end())
cout << "Number " << (*nums_iter) << " found." << endl; // 3
cout << "Number not found." << endl;

Tuesday, August 15, 2006

Sharing mouse and keyboard between two computers with different operating system


Running Synergy

Synergy lets you use one keyboard and mouse across multiple computers. To do so it requires that all the computers are connected to each other via TCP/IP networking. Most systems come with this installed.

Step 1 - Choose a server

The first step is to pick which keyboard and mouse you want to share. The computer with that keyboard and mouse is called the "primary screen" and it runs the synergy server. All of the other computers are "secondary screens" and run the synergy client.

Step 2 - Install the software

Second, you install the software. Choose the appropriate package and install it. For example, on Windows you would run SynergyInstaller. You must install the software on all the computers that will share the mouse and keyboard (clients and server). On OS X you'll just have a folder with some documentation and two programs. You can put this folder anywhere.

Step 3 - Configure and start the server

Next you configure the server. You'll tell synergy the name of the primary and secondary screens, which screens are next to which, and choose desired options. On Windows there's a dialog box for setting the configuration. On other systems you'll create a simple text file.

Note that when you tell synergy that screen A is to the left of screen B this does not imply that B is to the right of A. You must explicitly indicate both relations. If you don't do both then when you're running synergy you'll find you're unable to leave one of the screens.

On Windows run synergy by double clicking on the synergy file. This brings up a dialog. Configure the server:

* Click the Share this computer's keyboard and mouse (server) radio button
* Click the Screens & Links Configure... button
* Click the + button to add the server to the Screens list
o Enter the name of server (the computer's name is the recommended name)
o Optionally enter other names the server is known by
o Click OK
* Use the + button to add your other computers
o Using a computer's name as its screen name is recommended
o Choose desired screen options on the Add Screen dialog
* Use the controls under Links to link screens together
o Click (once) on the server's name in the Screens list
o Choose the screen to the left of the server; use --- if there is no screen to the left of the server
o Choose the screens to the right, above and below the server
o Repeat the above steps for all the other screens
* Click OK to close the Screens & Links dialog
* Use Options... to set desired options
* If the server's screen name is not the server's computer name:
o Click Advanced...
o Enter the server's screen name next to Screen Name
o Click OK

Now click Test. The server will start and you'll see a console window with log messages telling you about synergy's progress. If an error occurs you'll get one or more dialog boxes telling you what the errors are; read the errors to determine the problem then correct them and try Test again. See Step 5 for typical errors.

Unix or Mac OS X
Create a text file named synergy.conf with the following:

section: screens
section: links
right = screen2
left = screen1

Replace each occurrence of screen1 with the host name of the primary screen computer (as reported by the hostname program) and screen2 with the host name of a secondary screen computer. In the above example, screen2 is to the right of screen1 and screen1 is to the left of screen2. If necessary you should replace right and left with left, right, up, or down. If you have more than two computers you can add those too: add each computer's host name in the screens section and add the appropriate links. See the configuration guide for more configuration possibilities.

Now start the server. Normally synergy wants to run "in the background." It detaches from the terminal and doesn't have a visible window, effectively disappearing from view. Until you're sure your configuration works, you should start synergy "in the foreground" using the -f command line option.

On unix type the command below in a shell. If synergys is not in your PATH then use the full pathname.

synergys -f --config synergy.conf

On OS X open Terminal in the Utilities folder in the Applications folder. Drag the synergys program from the synergy folder onto the Terminal window. The path to the synergys program will appear. Add the following to the same line, type a space at the end of the line but don't press enter:

-f --config

Now drag the synergy.conf file onto the Terminal window and press enter. Check the reported messages for errors. Use ctrl+c to stop synergy if it didn't stop automatically, correct any problems, and start it again.

Step 4 - Start the clients

Next you start the client on each computer that will share the server's keyboard and mouse.

On Windows run synergy by double clicking on the synergy file. This brings up a dialog. Configure the client:

* Click the Use another computer's shared keyboard and mouse (client) radio button
* Enter the server's computer name next to Other Computer's Host Name
o This is not the server's screen name, unless you made that the server's host name as recommended
* If the client's screen name is not the client's computer name:
o Click Advanced...
o Enter the client's screen name next to Screen Name
o Click OK

Now click Test.

Unix or Mac OS X
To start a client on unix, enter the following:

synergyc -f server-host-name

where server-host-name is replaced by the host name of the computer running the synergy server. If synergyc is not in your PATH then use the full pathname.

On OS X open Terminal in the Utilities folder in the Applications folder. Drag the synergyc program from the synergy folder onto the Terminal window. The path to the synergys program will appear. Add the following to the same line and press enter:

-f server-host-name

When you added the client to the server's configuration you chose a name for the client. If that name was not client's host name then you must tell the client the name you used. Instead of the above command use this instead:

synergyc -f --name name server-host-name

where name is the name for the client in the server's configuration. (On OS X drag the synergyc program to the Terminal window rather than typing synergyc.)

Step 5 - Test

Clients should immediately report a successful connection or one or more error messages. Some typical problems and possible solutions are below. See the troubleshooting and the FAQ pages for more help.

* failed to open screen (X11 only)

Check permission to open the X display;
check that the DISPLAY environment variable is set
use the --display command line option.

* address already in use

Another program (maybe another copy of synergy) is using the synergy port; stop the other program or choose a different port in the Advanced... dialog. If you change the port you must make the same change on all of the clients, too.

* connection forcefully rejected

The synergy client successfully contacted the server but synergy wasn't running or it's running on a different port. You may also see this if there's a firewall blocking the host or port. Make sure synergy is running on the server and check for a firewall.

* already connected

Check that the synergy client isn't already running.

* refused client

Add the client to the server's configuration file.

* connection timed out

Check that server-host-name is correct.
Check that you don't have a firewall blocking the server or synergy port.

* connection failed

Check that server-host-name is correct.

If you get the error "Xlib: No protocol specified" you're probably running synergy as root while logged in as another user. X11 may prevent this for security reasons. Either run synergy as the same user that's logged in or (not recommended) use "xhost +" to allow anyone to connect to the display.

When successful you should be able to move the mouse off the appropriate edges of your server's screen and have it appear on a client screen. Try to move the mouse to each screen and check all the configured links. Check the mouse buttons and wheel and try the keyboard on each client. You can also cut-and-paste text, HTML, and images across computers (HTML and images are not supported on OS X yet).

Step 6 - Run

Once everything works correctly, stop all the clients then the server. Then start the server with the Start button on Windows and without the -f option on Unix and Mac OS X. Finally start the clients similarly. On Windows before clicking Start you may want to set the Logging Level to Warning so the logging window doesn't pop up (because you currently can't close it, just minimize it).

You can also configure synergy to start automatically when your computer starts or when you log in. See the autostart guide for more information.

Command Line Options Guide

Common Command Line Options
The following options are supported by synergys and synergyc.
-d, --debug level use debugging level level
--daemon run as a daemon (Unix) or background (Windows)
-f, --no-daemon run in the foreground
--display display connect to X server at display (X11 only)
-n, --name name use name instead of the hostname
--restart automatically restart on failures
-1, --no-restart do not restart on failure
-h, --help print help and exit
--version print version information and exit

Debug levels are from highest to lowest: FATAL, ERROR, WARNING, NOTE, INFO, DEBUG, DEBUG1, and DEBUG2. Only messages at or above the given level are logged. Messages are logged to a terminal window when running in the foreground. Unix logs messages to syslog when running as a daemon. The Windows NT family logs messages to the event log when running as a service. The Windows 95 family shows FATAL log messages in a message box and others in a terminal window when running as a service.

The --name option lets the client or server use a name other than its hostname for its screen. This name is used when checking the configuration.

Neither the client nor server will automatically restart if an error occurs that is sure to happen every time. For example, the server will exit immediately if it can't find itself in the configuration. On X11 both the client and server will also terminate if the connection to the X server is lost (usually because it died).

Server Command Line Options

synergys [options]

The server accepts the common options and:

-a, --address address listen for connections on address address
-c, --config pathname read configuration from pathname

address has one of the following forms:


hostname is a hostname or IP address of a network interface on the server system (e.g. somehost or port is a port number from 1 to 65535. hostname defaults to the system's hostname and port defaults to 24800.

Client Command Line Options

synergyc [options] address[:port]

address is the hostname or IP address of the server and port is the optional netw

Monday, August 14, 2006

Explicit in C++

Using Explicit in C++

In C++ it is possible to declare constructors for a class, taking a single parameter, and use those constructors for doing type conversion. For example:

class A {

void f(A) {}

void g()
A a1 = 37;

A a2 = A(47);

A a3(57);

a1 = 67;


A declaration like:

A a1 = 37;

says to call the A(int) constructor to create an A object from the integer value. Such a constructor is called a "converting constructor".

However, this type of implicit conversion can be confusing, and there is a way of disabling it, using a new keyword "explicit" in the constructor declaration:

class A {
explicit A(int);

void f(A) {}

void g()
A a1 = 37; // illegal

A a2 = A(47); // OK

A a3(57); // OK

a1 = 67; // illegal

f(77); // illegal

Using the explicit keyword, a constructor is declared to be
"nonconverting", and explicit constructor syntax is required:

class A {
explicit A(int);

void f(A) {}

void g()
A a1 = A(37);

A a2 = A(47);

A a3(57);

a1 = A(67);


Note that an expression such as:


is closely related to function-style casts supported by C++. For example:

double d = 12.34;

int i = int(d);

Our Services

Back to Home Page

Tuesday, July 25, 2006

5 PHP Design Patterns

Five common PHP design patterns

Tuesday, July 18, 2006

Writing your own newsreader
XML feeds are the way today to keep a tab on what's happening in the blogosphere as well as to know about site updates and new additions. I had heard about two popular open source feature-rich Java APIs to deal with the feeds, ROME and Informa but could never really savor them.

For one of my own sites where I, sort of hand-built the aggregator as Myjavaserevr does not allow deploying external JARs or Taglibs I did not get any chance to play with these APIs. So when I got some opportunity it was imperative that I tried them.

The following is a very elementary example of using the two news aggregation libraries that imitates a newsreader. The examples, as I said, are pretty basic and they would make a hit to the specified Feed URL every time you call the JSPs. The code snippets are not meant to demonstrate good coding practice.

Both the libraries support almost all versions of RSS, RDF and Atom and features such as dynamic discovery of feed format. Feature wise probably Informa has an upper hand (it supports OPML, recognizes the Enclosure element making it suitable to comprehend Podcast feeds and can be configured to use a persistence mechanism built over Hibernate) but what it lacks is availability of documents. There are no primers at the site and the code is very poorly commented making the Javadocs difficult to come to pace quickly. The two articles that I could, Google have been outdated, as I used the 0.6.5 version of the library.

ROME, on the other hand, has very nice documentation available at its site, complete with code examples. Many desirable features are unfortunately still on the TODO list. For comprehending the "Enclosure" element ROME needs a separate plugin module (that also supports iTunes extensions). While I have not investigated them, there are a number of sub-projects based on both ROME and Informa, for example: there is a JSP Tag library based on Informa. There is a short review of various libraries here but I guess much stuff on Informa is not relevant now since its latest release.

I am not mincing my words when I say that each API has its own strengths, Informa library is pretty bulky but supports OPML while Rome has a wider support for all kind of XML feeds and has a pluggable architecture. The good thing about these APIs is that they pretty much offer you everything that you may want to do with feeds, reading, generating your own, and creating a digest from multiple feeds and so on.

To run these JSPs, needless to say, you would need to download Informa and ROME libraries. I ran these on jakarta-tomcat-5.0.28 / j2sdk1.4.2_06 and the only dependency I was missing was the JDOM jar that ROME needs.

Concurrent Prograaming Good Reference

Concept and Notations in Concurrent Programming By Andrews and Schneider

Monday, July 17, 2006

Saturday, July 15, 2006

Sunday, July 09, 2006

Concept Drift

Concept Drift

On the Business Delegate Pattern

J2EE pattern langugae


Tuesday, July 04, 2006

What is business logic?

The part of an application program that performs the required data processing of the business. It refers to the routines that perform the data entry, update, query and report processing, and more specifically to the processing that takes place behind the scenes rather than the presentation logic required to display the data on the screen (GUI processing). Client applications are made up of a user interface and business logic. Server applications are mostly business logic.

Both client and server applications also require communications links, but the network infrastructure, like the user interface, is not part of the business logic

Design Patterns: Visual

Monday, June 26, 2006

Berkeley DB: Part Three

Message Handler

package db.GettingStarted;
import com.sleepycat.db.Environment;
import com.sleepycat.db.MessageHandler;

public class MyMessageHandler implements MessageHandler
// Our constructor does nothing
public MyMessageHandler() {}
public void message(Environment dbenv, String message)
// Put your special message handling code here

Set the databaseconfig to use this messagehandler
package db.GettingStarted;
import com.sleepycat.db.DatabaseConfig;
DatabaseConfig myDbConfig = new DatabaseConfig();
MyMessageHandler mmh = new MyMessageHandler();

Chimney Bluff State Park

Visited this on 06/25/06

Friday, June 23, 2006

Berkeley DB:Part Two

1. Code for exception handing


catch (DatabaseException e)

2. Errno values, if the errno values are greater than zero then a system error occurred. Special error values like the key and the data being searched is not found results in a error withe negative value.

3. Key and Data of records managed by DatabaseEntry class.

DatabaseConfig class allows setting the properties of the database,
package db.GettingStarted;
import com.sleepycat.db.Database;
import com.sleepycat.db.DatabaseConfig;
import com.sleepycat.db.DatabaseException;
import com.sleepycat.db.DatabaseType;
Database myDatabase = null;
try {
DatabaseConfig dbConfig = new DatabaseConfig();
myDatabase = new Database("sampleDatabase.db",

if (myDatabase != null)

} catch (DatabaseException dbe) {
// Exception handling goes here.
} catch (FileNotFoundException fnfe) {
// Exception handling goes here

Berkeley DB: Part one

Berkely DB concepts

1.DB databases contains records
2. A record contains a key and value.
3. key/data of a record , the data cen be complex.
4. DB database similar like a table in a relation
5. DB applications could use more than one DB databases ( more than 1 tables)
6. The DB database containing records have an assoicated access methods to them
a) Btree
b) Hash
c) Queue
7. Typical DB applications will using many DB databases.
8. Retrieving the records = get()
Putting the records = put()
9. If the databases does not support duplicate records , the next time you insert the data records with existing key, this key replaces the old key.

10. In addition to handles, cursors could be used to insert/retrieve data. Cursors could be used to seek to the data
11. DB provides secondary database which serves as an index to the primary database. Cursors are iterators over the records on the database.
12. Btree access method the most popular method to retrieve data.
13. RecNo , logical records numbers as keys.

Arbitrary Data (strings) Btree or Hash
logical records number (integer) Queue or Recno.

14. Small working datasets no difference between RecNo.

Thursday, June 22, 2006

My laptop crash

So what I did not want has finally happened. My laptop crashed yesterday and even though I think I managed to backup some data before that, but now I am in a precarious position.

First I have suse 9.2 and windows on my laptop. And i had a spyware problem with my PC and I tried to remove it with tools in the market. And since I have rebooted nothing shows up on my screen, not even the BIOS screen. I tried to boot from my recovery drive disk in the CD-ROM drive but nothing seems to happen on my computer screen.

I am trying to boot through the SUSE bootable CD and see what happens.

Wednesday, June 21, 2006

Talk with Werner Vogels and Jim Gray in ACM queue

Saturday, May 13, 2006

Java Caching System

Friday, May 12, 2006

AWK one liners

Taken from

# Print the length of the longest input line:
awk '{ if (length($0) > max) max = length($0) } END { print max }' data

# Print every line that is longer than 80 characters:
awk 'length($0) > 80' data

# Print the length of the longest line in data:
expand data | awk '{ if (x < length()) x = length() }
END { print "maximum line length is " x }'

# Print seven random numbers from 0 to 100, inclusive:
awk 'BEGIN { for (i = 1; i <= 7; i++) print int(101 * rand()) }

# Print the total number of bytes used by files:
ls -l files | awk '{ x += $5 }
END { print "total bytes: " x }'

# Print the even-numbered lines in the data file:
awk 'NR % 2 == 0' data

# Print first two fields in opposite order:
awk '{ print $2, $1 }' file

# Print lines longer than 72 characters:
awk 'length > 72' file

# Print length of string in 2nd column
awk '{print length($2)}' file

# Add up first column, print sum and average:
{ s += $1 }
END { print "sum is", s, " average is", s/NR }
# Print fields in reverse order:
awk '{ for (i = NF; i > 0; --i) print $i }' file

# Print the last line
awk '{line = $0} END {print line}' file

# Print the total number of lines that contain the word Pat
awk '/Pat/ {nlines = nlines + 1}
END {print nlines}' file

# Print all lines between start/stop pairs:
awk '/start/, /stop/' file

# Print all lines whose first field is different from previous one:
awk '$1 != prev { print; prev = $1 }' file

# Print column 3 if column 1 > column 2:
awk '$1 > $2 {print $3}' file

# Print line if column 3 > column 2:
awk '$3 > $2' file

# Count number of lines where col 3 > col 1
awk '$3 > $1 {print i + "1"; i++}' file

# Print sequence number and then column 1 of file:
awk '{print NR, $1}' file

# Print every line after erasing the 2nd field
awk '{$2 = ""; print}' file

# Print hi 28 times
yes | head -28 | awk '{ print "hi" }'

# Print hi.0010 to hi.0099 (NOTE IRAF USERS!)
yes | head -90 | awk '{printf("hi00%2.0 f \n", NR+9)}'

# Find maximum and minimum values present in column 1
NR == 1 {m=$1 ; p=$1}
$1 >= m {m = $1}
$1 <= p {p = $1}
END { print "Max = " m, " Min = " p }

# Example of using substrings
# substr($2,9,7) picks out characters 9 thru 15 of column 2
{print "imarith", substr($2,1,7) " - " $3, "out."substr($2,5, 3)}
{print "imarith", substr($2,9,7) " - " $3, "out."substr($2,13 ,3)}
{print "imarith", substr($2,17,7) " - " $3, "out."substr($2,21 ,3)}
{print "imarith", substr($2,25,7) " - " $3, "out."substr($2,29 ,3)}

# Single space to Double space
awk '{print ; print ""}' infile > outfile

Data Normalization in Weka


Normalizes all numeric values in the given dataset. The resulting
* values are in [0,1] for the data used to compute the normalization
* intervals.


The command to print the first attribute from a file with attribute values as

attr1, attr2, attr3 ..

awk -F, '{print $1}' filename

Wednesday, May 03, 2006

Upper Triangular Matrix

For allocating upper triangular matrix, we use the following technique

(Num) * ( Num -1 ) >> 1 + Num

where num is the number of dimensions of the matrix, what essentially this formulae does is m multiplying ( Num *Num -1 is always divisible by 2 and adding num gives the upper traingular matrix)

Nice trick for allocation of upper triangular matrix.


Sunday, April 23, 2006

Types of Join

Types of join

Occasionally there is a post on a forum asking what a certain type of join is all about, so I thought it would probably be good to have a stock explanation to refer people to so that I don't re-write near enough the same response each time the question arises.

First lets consider these two tables.


Key         Data
----------- ----------
1 a
2 b


Key         Data
----------- ----------
1 c
3 d
We can see that the only match is where Key is 1.


In an INNER JOIN that will be the only thing returned. If we use the query

SELECT A.[Key] AS aKey, A.Data AS aData, B.[Key] AS bKey, b.Data AS bData
INNER JOIN B ON a.[Key] = b.[Key]
the returned set will be
aKey        aData      bKey        bData
----------- ---------- ----------- ----------
1 a 1 c

In the case of the various outer joins non-matches will be returned also.


In a LEFT OUTER JOIN everything on the left side will be returned. Any matches on the right side will be returned also, but if there is no match on the right side then nulls are returned instead.

The query

SELECT A.[Key] AS aKey, A.Data AS aData, B.[Key] AS bKey, b.Data AS bData
LEFT OUTER JOIN B ON a.[Key] = b.[Key]
aKey        aData      bKey        bData
----------- ---------- ----------- ----------
1 a 1 c


The RIGHT OUTER JOIN is very similar to the LEFT OUTER JOIN, except that, of course, the matching is reversed. Everything on the right side is returned, and only matches on the left side are returned. Any non-matches will be filled with nulls on the left side.

The query

SELECT A.[Key] AS aKey, A.Data AS aData, B.[Key] AS bKey, b.Data AS bData
RIGHT OUTER JOIN B ON a.[Key] = b.[Key]
aKey        aData      bKey        bData
----------- ---------- ----------- ----------
1 a 1 c


A FULL OUTER JOIN returns a set containing all rows from either side, matched if possible, but nulls put in place if not.

The query

SELECT A.[Key] AS aKey, A.Data AS aData, B.[Key] AS bKey, b.Data AS bData
FULL OUTER JOIN B ON a.[Key] = b.[Key]
aKey        aData      bKey        bData
----------- ---------- ----------- ----------
1 a 1 c


The CROSS JOIN doesn't obey the same set of rules as the other joins. This is because it doesn't care about matching rows from either side, so there is no ON qualifier within the join clause. This is a simple join that joins all rows on the left side to all rows on the right side. Where the other joins cannot return more rows than exist in the most populous of the source tables, the CROSS JOIN will return the product of rows from each side. If you have 5 rows in Table A, and 6 rows in Table B it will return a set containing 30 rows.

The query

SELECT A.[Key] AS aKey, A.Data AS aData, B.[Key] AS bKey, b.Data AS bData
aKey        aData      bKey        bData
----------- ---------- ----------- ----------
1 a 1 c
2 b 1 c
1 a 3 d
2 b 3 d


Friday, April 21, 2006

Thursday, April 20, 2006

SED oneliners

Handy one-liners for SED

HANDY ONE-LINERS FOR SED (Unix stream editor)               Mar. 23, 2001
compiled by Eric Pement version 5.1
Latest version of this file is usually at:
This file is also available in Portuguese at:


# double space a file
sed G

# double space a file which already has blank lines in it. Output file
# should contain no more than one blank line between lines of text.
sed '/^$/d;G'

# triple space a file
sed 'G;G'

# undo double-spacing (assumes even-numbered lines are always blank)
sed 'n;d'


# number each line of a file (simple left alignment). Using a tab (see
# note on '\t' at end of file) instead of space will preserve margins.
sed = filename | sed 'N;s/\n/\t/'

# number each line of a file (number on left, right-aligned)
sed = filename | sed 'N; s/^/ /; s/ *\(.\{6,\}\)\n/\1 /'

# number each line of file, but only print numbers if line is not blank
sed '/./=' filename | sed '/./N; s/\n/ /'

# count lines (emulates "wc -l")
sed -n '$='


# IN UNIX ENVIRONMENT: convert DOS newlines (CR/LF) to Unix format
sed 's/.$//' # assumes that all lines end with CR/LF
sed 's/^M$//' # in bash/tcsh, press Ctrl-V then Ctrl-M
sed 's/\x0D$//' # gsed 3.02.80, but top script is easier

# IN UNIX ENVIRONMENT: convert Unix newlines (LF) to DOS format
sed "s/$/`echo -e \\\r`/" # command line under ksh
sed 's/$'"/`echo \\\r`/" # command line under bash
sed "s/$/`echo \\\r`/" # command line under zsh
sed 's/$/\r/' # gsed 3.02.80

# IN DOS ENVIRONMENT: convert Unix newlines (LF) to DOS format
sed "s/$//" # method 1
sed -n p # method 2

# IN DOS ENVIRONMENT: convert DOS newlines (CR/LF) to Unix format
# Cannot be done with DOS versions of sed. Use "tr" instead.
tr -d \r outfile # GNU tr version 1.22 or higher

# delete leading whitespace (spaces, tabs) from front of each line
# aligns all text flush left
sed 's/^[ \t]*//' # see note on '\t' at end of file

# delete trailing whitespace (spaces, tabs) from end of each line
sed 's/[ \t]*$//' # see note on '\t' at end of file

# delete BOTH leading and trailing whitespace from each line
sed 's/^[ \t]*//;s/[ \t]*$//'

# insert 5 blank spaces at beginning of each line (make page offset)
sed 's/^/ /'

# align all text flush right on a 79-column width
sed -e :a -e 's/^.\{1,78\}$/ &/;ta' # set at 78 plus 1 space

# center all text in the middle of 79-column width. In method 1,
# spaces at the beginning of the line are significant, and trailing
# spaces are appended at the end of the line. In method 2, spaces at
# the beginning of the line are discarded in centering the line, and
# no trailing spaces appear at the end of lines.
sed -e :a -e 's/^.\{1,77\}$/ & /;ta' # method 1
sed -e :a -e 's/^.\{1,77\}$/ &/;ta' -e 's/\( *\)\1/\1/' # method 2

# substitute (find and replace) "foo" with "bar" on each line
sed 's/foo/bar/' # replaces only 1st instance in a line
sed 's/foo/bar/4' # replaces only 4th instance in a line
sed 's/foo/bar/g' # replaces ALL instances in a line
sed 's/\(.*\)foo\(.*foo\)/\1bar\2/' # replace the next-to-last case
sed 's/\(.*\)foo/\1bar/' # replace only the last case

# substitute "foo" with "bar" ONLY for lines which contain "baz"
sed '/baz/s/foo/bar/g'

# substitute "foo" with "bar" EXCEPT for lines which contain "baz"
sed '/baz/!s/foo/bar/g'

# change "scarlet" or "ruby" or "puce" to "red"
sed 's/scarlet/red/g;s/ruby/red/g;s/puce/red/g' # most seds
gsed 's/scarlet\|ruby\|puce/red/g' # GNU sed only

# reverse order of lines (emulates "tac")
# bug/feature in HHsed v1.5 causes blank lines to be deleted
sed '1!G;h;$!d' # method 1
sed -n '1!G;h;$p' # method 2

# reverse each character on the line (emulates "rev")
sed '/\n/!G;s/\(.\)\(.*\n\)/&\2\1/;//D;s/.//'

# join pairs of lines side-by-side (like "paste")
sed '$!N;s/\n/ /'

# if a line ends with a backslash, append the next line to it
sed -e :a -e '/\\$/N; s/\\\n//; ta'

# if a line begins with an equal sign, append it to the previous line
# and replace the "=" with a single space
sed -e :a -e '$!N;s/\n=/ /;ta' -e 'P;D'

# add commas to numeric strings, changing "1234567" to "1,234,567"
gsed ':a;s/\B[0-9]\{3\}\>/,&/;ta' # GNU sed
sed -e :a -e 's/\(.*[0-9]\)\([0-9]\{3\}\)/\1,\2/;ta' # other seds

# add commas to numbers with decimal points and minus signs (GNU sed)
gsed ':a;s/\(^\|[^0-9.]\)\([0-9]\+\)\([0-9]\{3\}\)/\1\2,\3/g;ta'

# add a blank line every 5 lines (after lines 5, 10, 15, 20, etc.)
gsed '0~5G' # GNU sed only
sed 'n;n;n;n;G;' # other seds


# print first 10 lines of file (emulates behavior of "head")
sed 10q

# print first line of file (emulates "head -1")
sed q

# print the last 10 lines of a file (emulates "tail")
sed -e :a -e '$q;N;11,$D;ba'

# print the last 2 lines of a file (emulates "tail -2")
sed '$!N;$!D'

# print the last line of a file (emulates "tail -1")
sed '$!d' # method 1
sed -n '$p' # method 2

# print only lines which match regular expression (emulates "grep")
sed -n '/regexp/p' # method 1
sed '/regexp/!d' # method 2

# print only lines which do NOT match regexp (emulates "grep -v")
sed -n '/regexp/!p' # method 1, corresponds to above
sed '/regexp/d' # method 2, simpler syntax

# print the line immediately before a regexp, but not the line
# containing the regexp
sed -n '/regexp/{g;1!p;};h'

# print the line immediately after a regexp, but not the line
# containing the regexp
sed -n '/regexp/{n;p;}'

# print 1 line of context before and after regexp, with line number
# indicating where the regexp occurred (similar to "grep -A1 -B1")
sed -n -e '/regexp/{=;x;1!p;g;$!N;p;D;}' -e h

# grep for AAA and BBB and CCC (in any order)
sed '/AAA/!d; /BBB/!d; /CCC/!d'

# grep for AAA and BBB and CCC (in that order)
sed '/AAA.*BBB.*CCC/!d'

# grep for AAA or BBB or CCC (emulates "egrep")
sed -e '/AAA/b' -e '/BBB/b' -e '/CCC/b' -e d # most seds
gsed '/AAA\|BBB\|CCC/!d' # GNU sed only

# print paragraph if it contains AAA (blank lines separate paragraphs)
# HHsed v1.5 must insert a 'G;' after 'x;' in the next 3 scripts below
sed -e '/./{H;$!d;}' -e 'x;/AAA/!d;'

# print paragraph if it contains AAA and BBB and CCC (in any order)
sed -e '/./{H;$!d;}' -e 'x;/AAA/!d;/BBB/!d;/CCC/!d'

# print paragraph if it contains AAA or BBB or CCC
sed -e '/./{H;$!d;}' -e 'x;/AAA/b' -e '/BBB/b' -e '/CCC/b' -e d
gsed '/./{H;$!d;};x;/AAA\|BBB\|CCC/b;d' # GNU sed only

# print only lines of 65 characters or longer
sed -n '/^.\{65\}/p'

# print only lines of less than 65 characters
sed -n '/^.\{65\}/!p' # method 1, corresponds to above
sed '/^.\{65\}/d' # method 2, simpler syntax

# print section of file from regular expression to end of file
sed -n '/regexp/,$p'

# print section of file based on line numbers (lines 8-12, inclusive)
sed -n '8,12p' # method 1
sed '8,12!d' # method 2

# print line number 52
sed -n '52p' # method 1
sed '52!d' # method 2
sed '52q;d' # method 3, efficient on large files

# beginning at line 3, print every 7th line
gsed -n '3~7p' # GNU sed only
sed -n '3,${p;n;n;n;n;n;n;}' # other seds

# print section of file between two regular expressions (inclusive)
sed -n '/Iowa/,/Montana/p' # case sensitive


# print all of file EXCEPT section between 2 regular expressions
sed '/Iowa/,/Montana/d'

# delete duplicate, consecutive lines from a file (emulates "uniq").
# First line in a set of duplicate lines is kept, rest are deleted.
sed '$!N; /^\(.*\)\n\1$/!P; D'

# delete duplicate, nonconsecutive lines from a file. Beware not to
# overflow the buffer size of the hold space, or else use GNU sed.
sed -n 'G; s/\n/&&/; /^\([ -~]*\n\).*\n\1/d; s/\n//; h; P'

# delete the first 10 lines of a file
sed '1,10d'

# delete the last line of a file
sed '$d'

# delete the last 2 lines of a file
sed 'N;$!P;$!D;$d'

# delete the last 10 lines of a file
sed -e :a -e '$d;N;2,10ba' -e 'P;D' # method 1
sed -n -e :a -e '1,10!{P;N;D;};N;ba' # method 2

# delete every 8th line
gsed '0~8d' # GNU sed only
sed 'n;n;n;n;n;n;n;d;' # other seds

# delete ALL blank lines from a file (same as "grep '.' ")
sed '/^$/d' # method 1
sed '/./!d' # method 2

# delete all CONSECUTIVE blank lines from file except the first; also
# deletes all blank lines from top and end of file (emulates "cat -s")
sed '/./,/^$/!d' # method 1, allows 0 blanks at top, 1 at EOF
sed '/^$/N;/\n$/D' # method 2, allows 1 blank at top, 0 at EOF

# delete all CONSECUTIVE blank lines from file except the first 2:
sed '/^$/N;/\n$/N;//D'

# delete all leading blank lines at top of file
sed '/./,$!d'

# delete all trailing blank lines at end of file
sed -e :a -e '/^\n*$/{$d;N;ba' -e '}' # works on all seds
sed -e :a -e '/^\n*$/N;/\n$/ba' # ditto, except for gsed 3.02*

# delete the last line of each paragraph
sed -n '/^$/{p;h;};/./{x;/./p;}'


# remove nroff overstrikes (char, backspace) from man pages. The 'echo'
# command may need an -e switch if you use Unix System V or bash shell.
sed "s/.`echo \\\b`//g" # double quotes required for Unix environment
sed 's/.^H//g' # in bash/tcsh, press Ctrl-V and then Ctrl-H
sed 's/.\x08//g' # hex expression for sed v1.5

# get Usenet/e-mail message header
sed '/^$/q' # deletes everything after first blank line

# get Usenet/e-mail message body
sed '1,/^$/d' # deletes everything up to first blank line

# get Subject header, but remove initial "Subject: " portion
sed '/^Subject: */!d; s///;q'

# get return address header
sed '/^Reply-To:/q; /^From:/h; /./d;g;q'

# parse out the address proper. Pulls out the e-mail address by itself
# from the 1-line return address header (see preceding script)
sed 's/ *(.*)//; s/>.*//; s/.*[:<] *//'

# add a leading angle bracket and space to each line (quote a message)
sed 's/^/> /'

# delete leading angle bracket & space from each line (unquote a message)
sed 's/^> //'

# remove most HTML tags (accommodates multiple-line tags)
sed -e :a -e 's/<[^>]*>//g;/
# extract multi-part uuencoded binaries, removing extraneous header
# info, so that only the uuencoded portion remains. Files passed to
# sed must be passed in the proper order. Version 1 can be entered
# from the command line; version 2 can be made into an executable
# Unix shell script. (Modified from a script by Rahul Dhesi.)
sed '/^end/,/^begin/d' file1 file2 ... fileX | uudecode # vers. 1
sed '/^end/,/^begin/d' "$@" | uudecode # vers. 2

# zip up each .TXT file individually, deleting the source file and
# setting the name of each .ZIP file to the basename of the .TXT file
# (under DOS: the "dir /b" switch returns bare filenames in all caps).
echo @echo off >zipup.bat
dir /b *.txt | sed "s/^\(.*\)\.TXT/pkzip -mo \1 \1.TXT/" >>zipup.bat

TYPICAL USE: Sed takes one or more editing commands and applies all of
them, in sequence, to each line of input. After all the commands have
been applied to the first input line, that line is output and a second
input line is taken for processing, and the cycle repeats. The
preceding examples assume that input comes from the standard input
device (i.e, the console, normally this will be piped input). One or
more filenames can be appended to the command line if the input does
not come from stdin. Output is sent to stdout (the screen). Thus:

cat filename | sed '10q' # uses piped input
sed '10q' filename # same effect, avoids a useless "cat"
sed '10q' filename > newfile # redirects output to disk

For additional syntax instructions, including the way to apply editing
commands from a disk file instead of the command line, consult "sed &
awk, 2nd Edition," by Dale Dougherty and Arnold Robbins (O'Reilly,
1997;, "UNIX Text Processing," by Dale Dougherty
and Tim O'Reilly (Hayden Books, 1987) or the tutorials by Mike Arst
distributed in U-SEDIT2.ZIP (many sites). To fully exploit the power
of sed, one must understand "regular expressions." For this, see
"Mastering Regular Expressions" by Jeffrey Friedl (O'Reilly, 1997).
The manual ("man") pages on Unix systems may be helpful (try "man
sed", "man regexp", or the subsection on regular expressions in "man
ed"), but man pages are notoriously difficult. They are not written to
teach sed use or regexps to first-time users, but as a reference text
for those already acquainted with these tools.

QUOTING SYNTAX: The preceding examples use single quotes ('...')
instead of double quotes ("...") to enclose editing commands, since
sed is typically used on a Unix platform. Single quotes prevent the
Unix shell from intrepreting the dollar sign ($) and backquotes
(`...`), which are expanded by the shell if they are enclosed in
double quotes. Users of the "csh" shell and derivatives will also need
to quote the exclamation mark (!) with the backslash (i.e., \!) to
properly run the examples listed above, even within single quotes.
Versions of sed written for DOS invariably require double quotes
("...") instead of single quotes to enclose editing commands.

USE OF '\t' IN SED SCRIPTS: For clarity in documentation, we have used
the expression '\t' to indicate a tab character (0x09) in the scripts.
However, most versions of sed do not recognize the '\t' abbreviation,
so when typing these scripts from the command line, you should press
the TAB key instead. '\t' is supported as a regular expression
metacharacter in awk, perl, and HHsed, sedmod, and GNU sed v3.02.80.

VERSIONS OF SED: Versions of sed do differ, and some slight syntax
variation is to be expected. In particular, most do not support the
use of labels (:name) or branch instructions (b,t) within editing
commands, except at the end of those commands. We have used the syntax
which will be portable to most users of sed, even though the popular
GNU versions of sed allow a more succinct syntax. When the reader sees
a fairly long command such as this:

sed -e '/AAA/b' -e '/BBB/b' -e '/CCC/b' -e d

it is heartening to know that GNU sed will let you reduce it to:

sed '/AAA/b;/BBB/b;/CCC/b;d' # or even
sed '/AAA\|BBB\|CCC/b;d'

In addition, remember that while many versions of sed accept a command
like "/one/ s/RE1/RE2/", some do NOT allow "/one/! s/RE1/RE2/", which
contains space before the 's'. Omit the space when typing the command.

OPTIMIZING FOR SPEED: If execution speed needs to be increased (due to
large input files or slow processors or hard disks), substitution will
be executed more quickly if the "find" expression is specified before
giving the "s/.../.../" instruction. Thus:

sed 's/foo/bar/g' filename # standard replace command
sed '/foo/ s/foo/bar/g' filename # executes more quickly
sed '/foo/ s//bar/g' filename # shorthand sed syntax

On line selection or deletion in which you only need to output lines
from the first part of the file, a "quit" command (q) in the script
will drastically reduce processing time for large files. Thus:

sed -n '45,50p' filename # print line nos. 45-50 of a file
sed -n '51q;45,50p' filename # same, but executes much faster

If you have any additional scripts to contribute or if you find errors
in this document, please send e-mail to the compiler. Indicate the
version of sed you used, the operating system it was compiled for, and
the nature of the problem. Various scripts in this file were written
or contributed by:

Al Aab # "seders" list moderator
Edgar Allen # various
Yiorgos Adamopoulos
Dale Dougherty # author of "sed & awk"
Carlos Duarte # author of "do it with sed"
Eric Pement # author of this document
Ken Pizzini # author of GNU sed v3.02
S.G. Ravenhall # great de-html script
Greg Ubben # many contributions & much help

Tuesday, April 18, 2006

Elevator Design Problem

UML By Examples



    Table of Contents

    0. Introduction

    The aim of this tutorial is to show how to use UML in "real" software development environment.
    1. Elevator Problem

    A product is to be installed to control elevators in a building with m floors. The problem concerns the logic required to move elevators between floors according to the following constraints:

    • Each elevator has a set of m buttons, one for each floor. These illuminate when pressed and cause the elevator to visit the corresponding floor. The illumination is canceled when the elevator visits the corresponding floor.
    • Each floor, except the first floor and top floor has two buttons, one to request and up-elevator and one to request a down-elevator. These buttons illuminate when pressed. The illumination is canceled when an elevator visits the floor and then moves in the desired direction.
    • When an elevator has no requests, it remains at its current floor with its doors closed.

    2. Unified Modeling Language

    UML is a modeling language that only specifies semantics and notation but no process is currently defined. Thus, we decided to do the analysis as follows;

    • Use Case Diagram
    • Class Diagram
    • Sequence Diagram
    • Collabration Diagram
    • State Diagram
    3. Analysis

    3.1. Use case diagram

    Use case description:

    • A generalized description of how a system will be used.
    • Provides an overview of the intended functionality of the system.
    • Understandable by laymen as well as professionals.
    Use Case Diagram:

    Elevator basic scenario that can be extracted from Use Case Diagram:

    • Passenger pressed floor button
    • Elevator system detects floor button pressed
    • Elevator moves to the floor
    • Elevator doors open
    • Passenger gets in and presses elevator button
    • Elevator doors closes
    • Elevator moves to required floor
    • Elevator doors open
    • Passenger gets out
    • Elevator doors closes

    3.2. Class Diagram

    Class diagrams show the static structure of the object, their internal structure, and their relationships.

    Class diagram:

    3.3. State diagram

    A state diagram shows the sequences of states an object goes through during it's life cycle in response to stimuli, together with its responses and actions.

    4. Design

    The design phase should produce the detailed class diagrams, collaboration diagrams, sequence diagrams, state diagrams, and activity diagram. However, the elevator problem is too simple for an activity diagram. Thus, we are not using an activity diagram for the elevator problem.

    4.1. Sequence Diagram

    A sequence diagram and collaboration diagram conveys similar information but expressed in different ways. A Sequence diagram shows the explicit sequence of messages suitable for modeling a real-time system, whereas a collobration diagram shows the relationships between objects.

    Sequence Diagrams:

    Sequence Diagram for Serving Elevator Button

    Sequence Diagram for Serving Door Button

    4.2. Collaboration diagram
    • Describes the set of interactions between classes or types
    • Shows the relationships among objects
    Collabration diagrams:
    Collabration Digaram for Serving Elevator Button
    Collabration Digaram for Serving Door Button

    5. Detail Design

    5.1. Detail Class Diagram

    5.2. Detail Operation Description

      Module Name Elevator_Control::Elevator_control_loop
      Module Type Method
      Input Argument None
      Output Argument None
      Error Message None
      File Access None
      File Change None
      Method Invoke button::illuminate, button::cancel_illumination,
      door::open, door::close, elevator::move, elevator::stop

    5.3. Pseudo-Code
      void elevator_control (void)
      while a button has been pressed
      if button not on
      update request list;
      else if elevator is moving up
      if there is no request to stop at floor f
      Elevator::move one floor up;


      6. Acknowledgement

      This example was developed for topic in software engineering in Vanderbilt University by myself and my best friends:

Monday, April 17, 2006

What is Windows Collation

Windows collations define rules for storing character data based on an associated Windows locale.

Sunday, April 16, 2006

Semaphore and Mutex

What's the difference between semaphore and mutex?

A: Rules of thumb:

- By semaphore we actually mean counting semaphore. By mutex we actually mean mutex semaphore. A mutex is essentially a binary semaphore. You can replace any Mutex with a Semaphore of MaxCount 1.

- Mutexes are usually more efficient than binary semaphores.

- Mutex has an owner concept: unlocking a mutex can be only done by the thread that locked (or, equivalently, "owns") the mutex.

- However, though I don't think it's a real issue in this particular case either, mutex can do fancy things with the thread that has locked the mutex (mutex owner thread), like raising its priority to the highest one of the threads waiting for the mutex to prevent so called priority inversion. (huican ping notion, not in the original version)

Saturday, April 15, 2006


Thursday, April 13, 2006

Algorithms in Latex

Preditive Accuracy

Several possible criteria for evaluating a learning algorithm:
  • Predictive accuracy of classifier
  • Speed of learner
  • Speed of classifier
  • Space requirements

Most common criterion is predictive accuracy

Wednesday, April 12, 2006



Maximum Likelihood Estimation (MLE)


Now we are in a position to introduce the concept of likelihood. If the probability of an event X dependent on model parameters p is written
   P ( X | p )

then we would talk about the likelihood
   L ( p | X )

that is, the likelihood of the parameters given the data. For most sensible models, we will find that certain data are more probable than other data. The aim of maximum likelihood estimation is to find the parameter value(s) that makes the observed data most likely. This is because the likelihood of the parameters given the data is defined to be equal to the probability of the data given the parameters (nb. technically, they are proportional to each other, but this does not affect the principle). If we were in the business of making predictions based on a set of solid assumptions, then we would be interested in probabilities - the probability of certain outcomes occurring or not occurring. However, in the case of data analysis, we have already observed all the data: once they have been observed they are fixed, there is no 'probabilistic' part to them anymore (the word data comes from the Latin word meaning 'given'). We are much more interested in the likelihood of the model parameters that underly the fixed data.
Knowing parameters -> Prediction of outcome

Observation of data -> Estimation of parameters

A simple example of MLE

To re-iterate, the simple principle of maximum likelihood parameter estimation is this: find the parameter values that make the observed data most likely. How would we go about this in a simple coin toss experiment? That is, rather than assume that p is a certain value (0.5) we might wish to find the maximum likelihood estimate (MLE) of p, given a specific dataset. Beyond parameter estimation, the likelihood framework allows us to make tests of parameter values. For example, we might want to ask whether or not the estimated p differs significantly from 0.5 or not. This test is essentially asking: is there evidence that the coin is biased? We will see how such tests can be performed when we introduce the concept of a likelihood ratio test below. Say we toss a coin 100 times and observe 56 heads and 44 tails. Instead of assuming that p is 0.5, we want to find the MLE for p. Then we want to ask whether or not this value differs significantly from 0.50. How do we do this? We find the value for p that makes the observed data most likely. As mentioned, the observed data are now fixed. They will be constants that are plugged into our binomial probability model :-
  • n = 100 (total number of tosses)
  • h = 56 (total number of heads)
Imagine that p was 0.5. Plugging this value into our probability model as follows :-
But what if p was 0.52 instead?
So from this we can conclude that p is more likely to be 0.52 than 0.5. We can tabulate the likelihood for different parameter values to find the maximum likelihood estimate of p:
                  p       L
0.48 0.0222
0.50 0.0389
0.52 0.0581
0.54 0.0739
0.56 0.0801
0.58 0.0738
0.60 0.0576
0.62 0.0378
If we graph these data across the full range of possible values for p we see the following likelihood surface.
We see that the maximum likelihood estimate for p seems to be around 0.56. In fact, it is exactly 0.56, and it is easy to see why this makes sense in this trivial example. The best estimate for p from any one sample is clearly going to be the proportion of heads observed in that sample. (In a similar way, the best estimate for the population mean will always be the sample mean.) So why did we waste our time with the maximum likelihood method? In such a simple case as this, nobody would use maximum likelihood estimation to evaluate p. But not all problems are this simple! As we shall see, the more complex the model and the greater the number of parameters, it often becomes very difficult to make even reasonable guesses at the MLEs. The likelihood framework conceptually takes all of this in its stride, however, and this is what makes it the work-horse of many modern statistical methods.

Return to front page

Site created by S.Purcell, last updated 21.09.2000

Monday, April 10, 2006

Normal Forms Again II

  • The First Normal Form (1NF) addresses the structure of an isolated table.
  • The Second (2NF), Third (3NF), and Boyce-Codd (BCNF) Normal Forms address one-to-one and one-to-many relationships.
  • The Fourth (4NF) and Fifth (5NF) Normal Forms deal with many-to-many relationships.

Good implementations in C

Thursday, April 06, 2006

Expectation Maximization Theory

Monday, April 03, 2006

Database Design Relationships

  • 1-1:

    • In order to create the relationship between two relations with a 1-1 relationship - post the primary key of one table into the other table, it doesn't matter which way around.

    • The key placed into the other relation is called a foreign key.

    • MP{name, dob, party, constituencyName*}

    • Constituency{name, size}

  • 1-Many:

    • To create the relationship - the primary key of the 1 side is posted to the many side as a foreign key.

    • LibraryBook{id_no, name}

    • Reader{membership_no, name, book_id*}

    • Imagine if the many side was posted to the one side instead.

  • Many-Many (M-N):

    • To create the relationship we can't add a foreign key, because will result in repeted data.

    • Instead, create an extra link table between the two relations, which has as its primary key the foreign keys from the two relations.

    • Actor{id_no, name}

    • Film{id_no, title}

    • Cast{actor_no*, film_no*}

    • The foreign keys from the original tables form a compound primary key in the link table.

    • The link table has a 1-many relationship with both the original tables.

    • This method prevents duplications of the relationship - actors could not be entered for the same film twice because the foreign keys are the primary key.

    • A link table can have its own attributes, if it is appropriate for the relationship to have attributes.

    • E.g. the Cast table could have an attribute 'time_spent_on_set'

Thursday, March 30, 2006

sed and awk

Wednesday, March 29, 2006


Stolen from site

CSE2305 - Object-Oriented Software Engineering
Week 5

Topic 10: C++ Polymorphism


Pointers, references¤ and inheritance

  • Recall that public inheritance¤ implies an "is a" relationship from child to parent
    class Vehicle
    Vehicle(char* regnum)
    : myRegNum(strdup(regnum))

    { delete[] myRegNum; }

    void Describe(void)
    cout << "Unknown vehicle, registration "
    << myRegNum << endl;

    char* myRegNum;

    class Car : public Vehicle
    Car(char* make, char* regnum)
    : Vehicle(regnum), myMake( strdup(make) )

    { delete[] myMake; }

    void Describe(void)
    cout << "Car (" << myMake
    << "), registration "
    << myRegNum << endl;

    char* myMake;
  • One consequence of that relationship is that a base-class¤ pointer can point at a derived object without needing a cast
    Vehicle* vp1 = new Vehicle ("SGI 987");
    Vehicle* vp2 = new Car ("Jaguar","XJS 012");

    vp1->Describe(); // PRINTS "Unknown vehicle....."
    vp2->Describe(); // PRINTS "Unknown vehicle....."
  • Likewise, a base-class¤ reference¤ can refer to a derived object without a cast
    Vehicle v1 ("SGI 987");
    Car c1 ("Jaguar","XJS 012");

    Vehicle& vr1 = v1;
    Vehicle& vr2 = c1;

    vr1.Describe(); // PRINTS "Unknown vehicle....."
    vr2.Describe(); // PRINTS "Unknown vehicle....."
  • The problem is that when the compiler is working out which Describe() member¤ function to call, it selects according to the type of the pointer (Vehicle* or Vehicle& in both cases), rather than the type of the object being pointed at or referred to (Vehicle or Car)
  • So all the above calls to a Describe() member¤ are dispatched to Vehicle::Describe(), even when the pointer of reference¤ actually points to a Car object!
  • What we need here is polymorphism¤

Polymorphism¤ in C++

  • C++ provides a simple mechanism for class¤-based polymorphism¤
  • Member¤ functions can be marked as polymorphic using the virtual keyword
  • Calls to such functions then get dispatched according to the actual type of the object which owns them, rather than the apparent type of the pointer (or reference¤) through which they are invoked

Virtual functions¤

  • A member¤ function which is declared with the virtual keyword is called a virtual function¤
  • Once a function is declared virtual, it may be redefined in derived classes¤¤ (and is virtual in those classes¤ too)
  • When the compiler sees a call to a virtual function¤ via a pointer or reference¤, it calls the correct version for the object in question (rather than the version indicated by the type of the pointer or reference¤)

An example

class Vehicle
Vehicle(char* regnum)
: myRegNum(strdup(regnum))

{ delete[] myRegNum; }

virtual void Describe(void)
cout << "Unknown vehicle, registration "
<< myRegNum << endl;

char* myRegNum;

class Car : public Vehicle
Car(char* make, char* regnum)
: Vehicle(regnum), myMake( strdup(make) )

{ delete[] myMake; }

virtual void Describe(void)
cout << "Car (" << myMake
<< "), registration "
<< myRegNum << endl;

char* myMake;

Vehicle* vp1 = new Car ("Jaguar","XJS 012");
Vehicle* vp2 = new Vehicle ("SGI 987");
Vehicle* vp3 = new Vehicle ("ABC 123");

vp1->Describe(); // PRINTS "Car (Jaguar)....."
vp2->Describe(); // PRINTS "Unknown vehicle....."
vp3->Describe(); // PRINTS "Unknown vehicle....."

How virtual functions¤ work

  • Normally when the compiler sees a member¤ function call it simply inserts instructions calling the appropriate subroutine (as determined by the type of the pointer or reference¤)
  • However, if the function is virtual a member¤ function call such as vp1->Describe() is replaced with following:
  • The expression vp1->_vtab locates a special "secret" data member ¤¤ of the object pointed to by vp1. This data member¤¤ is automatically present in all objects with at least one virtual function¤. It points to a class¤-specific table of function pointers (known as the classe's vtable)
  • The expression (vp1->_vtab)[0] locates the first element of the object's class¤'s vtable (the one corresponding to the first virtual function¤ - Describe()). That element is a function pointer to the appropriate Describe() member¤ function.
  • Finally, the expression (*((vp1->_vtab)[0]))() dereferences¤ the function pointer and calls the function
  • We can visualize the set-up for vp1, vp2, and vp3 as follows:

        [Diagram showing the pointers vp1, vp2, and vp3, all pointing to objects          containing vtable pointers.  These pointers point at separate          class-specific vtables (one for Vehicle, one for Car).  The first          element of each vtable points at the corresponding Describe() member          function.]

Virtual destructors¤¤

  • The same problem that occurred with the non-virtual version of Vehicle::Describe() also occurs with the Vehicle::~Vehicle() destructor¤
  • That is, the following code doesn't call the Car::~Car() destructor¤, and so the memory allocated to the myMake data member¤¤ leaks ¤:
    Vehicle* vp4 = new Car ("Aston Martin", "JB 007");

    // AND LATER...

    delete vp4;
  • Why doesn't delete call the correct destructor¤?
  • We can force delete to call the destructor¤ corresponding to the type of the object (not that of the pointer), by declaring the Vehicle::~Vehicle() destructor¤ virtual:
    class Vehicle
    Vehicle(char* regnum)
    : myRegNum(strdup(regnum))

    virtual ~Vehicle(void)
    { delete[] myRegNum; }

    virtual void Describe(void)
    cout << "Unknown vehicle, registration "
    << myRegNum << endl;

    char* myRegNum;

    class Car : public Vehicle
    Car(char* make, char* regnum)
    : Vehicle(regnum), myMake( strdup(make) )

    virtual ~Car(void)
    { delete[] myMake; }

    virtual void Describe(void)
    { cout << "Car (" << myMake
    << "), registration "
    << myRegNum << endl;

    char* myMake;

    Vehicle* vp4 = new Car ("Jaguar","XJS 012");

    delete vp4; // CALLS Car::~Car()
    // (WHICH THEN CALLS Vehicle::~Vehicle())


  • Lippman & Lajoie
  • New: Chapter 17.

  • Stroustrup
  • New: Chapter 12.

This material is part of the CSE2305 - Object-Oriented Software Engineering course.
Copyright © Jon McCormack & Damian Conway, 1998–2005. All rights reserved.