Happy New Year 2007

Today is the December 31st, the 365th day of 2006.

T.S.U.L was set up in June 2006

apache axis and tomcat

Apache Axis and Tomcat are popular tools on a Java based server.

However, apache, axis and tomcat are not something good.

Solaris and Sun Studio

First,

Desktop computers older than 4 years old may not be able to run it.
Notebook computers older than 2 years old may not be able to run it.

so, my testing platform is P4 512MB.

Before inserting the dvd (I got the auto installation version), free enough disk (32G in my installation) space for solaris. Some suggests that the minimum is 6G or 8G.

Then insert the dvd. (You might have to set the boot order in the bios).

Should the dvd rom eject if everything works fine. (Well, this is an auto-installation :P). Remove the disk and reboot.

Then gdm starts and everything is easy.

BTW. If you can't find Sun Studio (probably not in the start menu. Did bill create such a menu?). Try type sunstudio with an enter in the console. (Oh.. please. the console is the terminal in linux.)

To be continued...

Next, we are supposed to discuss something about comiplation and start a little program in Sun Studio. Many tools are powerful, but what a pity that we do not even know their names. :D

Social networks, Wikis, Communication tools, and Folksonomies

That is web 2.0, or the next generation of network.

Folksonomy, or tagging, could not deal with certain cases such that the sequence order of the words (tags) matters. [Example]

Further more, tagging could not understand. The system could find all pictures with triangle tags or circle tags, but it can't tell the difference between triangles and circles. The system could not learn to distinguish a triangle from circles by tags, even one hundred times.

Is tagging a solution? If we would like to find something by tags: First, we must speak the same languages (at least, could be translated). So a bird is not likely to find what it wants with human being's tags. Second, we have to specify enough tags. The word "mathematics" is not likely to help you find what you want. Although this might not be a problem. Third, precise tags. Certain groups of people would use different words to describe the same thing, or would they refer to different things with the same words. This could lead to some difficulties in finding information efficiently. Especially when certain group is very powerful, other smaller groups would submerge.

Above Three Four and Five

Have you ever noticed the three punctations above 3,4,5 on a standard US keyboard?

Yes, they are #(sharp), $(dollar), and %(percent).

You will notice that on a US keyboard, shift-4 is "$", which is the bash variable expansion character. On the keyboard, immediately to the left of "$" is "#". So, you can see that "#" is "at the beginning" of "$", and thus (according to our mnemonic), "#" removes characters from the beginning of the string. You may wonder how we remove characters from the end of the string. If you guessed that we use the character immediately to the right of "$" on the US keyboard ("%"), you're right!

So, #, which is before $, will remove characters from the beginning, and %, which is after $, will remove characters from the end of the string.

"${1##*.}"

"${1%.*}"

The bash is funny, easy while powerful. ;)

For more infomation about bash, click here.

Cygwin is not linux at all

Cygwin behaves strangely.

Gnome can not run.

Althought X works.

Collision with mingw.

Java Reference

Java passes parameters by reference which brings convinience as well as strange errors. For example:

import java.util.*;

public class Test {
	public static void main(String[] args) {
		Vector v = new Vector();
		int [] a = new int[5];
		for(int i=0;i<10;i++) {
			for(int j=0;j<5;j++) a[j] = i*j;
			v.add(new Obj(a)); // this won't work!
		}
		for(Iterator it=v.iterator();it.hasNext();) {
			it.next().dump();
		}
	}
}

class Obj {
	int [] a;
	Obj(int [] a) {
		this.a = a;
	}
	void dump() {
		for(int i=0;i		System.out.println();
	}
}

Well, the line

v.add(new Obj(a));

won't work as expected. Instead all arrays 'a' in 'Obj' are the same.

Change it to

v.add(new Obj(a.clone()));

so that every time a new array is passed.

Unexpected Error

printf("%d %d", 1ll, 1ll);

This will not output the expected result. A 64-bit integer will not cooperate with a %d argument.

So, instead

printf("%d %d", (int)1ll, (int)1ll);

or

printf("%I64d %I64d", 1ll, 1ll);

or

printf("%lld %lld", 1ll, 1ll);

should be used.

Strongly Connected Components

//Graph
//Strongly Connected Components

//call DFS(G) to compute finishing times f[u] for each vertex u
//compute GT, the transpose of G
//call DFS(GT), but in the main loop of DFS, consider the vertices
// in order of decreasing f[u] (as computed in line 1)
//output the vertices of each tree in the depth-first forest formed in line 3 as
// a separate strongly connect component

First Unscheduled System Down

We experienced the first unscheduled system down today. The reason is that the server of our service provider met some unforeseen problem.

Now, problems are fixed and data seems not affected.

Generalized Euclidean Algorithm

Generalized Euclidean Algorithm, or Integer Relation:

A set of real numbers x_1, x_2, ..., x_n is said to possess integer relation if there exist integers a_i such that
a_1x_1+a_2x_2+...+a_nx_n==0
with not all a_i==0.

Image Search or Color Search?

I tried several so-called "image search" engine, but found nothing that interests me.

Generally, there are two ways to search for a image or picture.

• By text


• By image

Implements of searching by text is easy and efficient. There are many search engines of this kind, among which google image search is a nice one.

However, search by text is not what people expected, and is not that user-friendly. Have you ever imagined a scene that could hardly be described? Or do you have less famous paintings whose name and author are not known?

Then you would draw your imaginations or take pictures of your favourite paintings and search for them. Of course, you can not search by text, because you do not have any idea of the text description of your targets.

But, up till now, there is no such engine that could search images worldwide effectively and efficiently. (Suggestions are appreciated ;))

Instead, according to my experience, image search engines behave in this way. They scan your uploaded image or picture, calculate color distributions with certain functions, match the colors with what are in their database, and finally send the results back to users.

So, you are expected to find those pictures with the same colors, do you?

If you search for a "white cat", you will probably find snow.

That's color search!

I think shape search is closer to the way of thinking of human being, though it could not be the same. But there are several difficulties for this not-so-perfect solution. First is how to distinguish shapes. Second, how to match shapes? How to define a regulation to match certain shapes? And this is also based on how to define shapes, especially complex shapes. Third, huge calculations. A compressed picture of ordinary size could be 100K. Finding shapes and storing them are time consuming, and could require more than 10 times of spaces. It's not just slow. It could be unsolvable because of high space complexities.

We, human beings, could easily distinguish a smile face from faces with a glance. :) However, distinguishing a smile face in black-white is hard enough for computers. :( Why? Because computers do not have eyes and brains. They only have scanners and CPUs. After defining many complicated regulations, it is possible for computers to find a smile face that meets the requirements of human beings. But implementations would be hard and bugs would be everywhere. This (;)) is a smile or not?

[]

Javascript is NOT Java at all

Although more and more people have realized that Javascript is not Java, I still want to state that:

• Javascript is now the most popular script language used in webpages all over the world.


• Javascript is now supported by most browser (I guess all browsers you have tried :P).


• Javascript is an object-oriented language, although you could not define a class with the keyword class explicitly.


• Javascript is young.


• Javascript is created by Netscape (currently Mozilla), not Sun (well, not the sun ;)).


• Javascript is NOT Java at all.

If you are interested in Javascript, please visit developer.mozilla.com. The documents might be of use.

Java IO

BufferedReader saves your memory!

In Java, input with Scanner (1.5) is very slow, and requires more memory. Scanner tries to read all data when initialized. However, Scanner is a convenient with methods like nextInt, and self defined delimiters.

BufferedReader is not as convenient but more efficient. Use StringTokenizer to extract numbers from a line if needed.

Generally speaking, Java IO is slower and requires more memory than other common languages.

Some tips on Java IO

• Scanner is suitable to read input data for the most of problems, but it is very slow. You should use it to read small input data only.



• BufferedReader provides quite fast read operations for almost all problems. But this class may be used to read single characters and lines only. To read tokens and numbers you should use StringTokenizer or StreamTokenizer.



• PrintWriter is preferred in all cases and works rather fast. But its method printf is too slow as well as calls like println(a + " " + b). You should output variables one-by-one to reach the highest performance.

Distance between Skew Lines

I assume that you are familiar with vector and cross product in three dimension.

A line is defined by two points x_1, x_2:

x==x_1+(x_2-x_1)*s

where s is a variable.

The normal vector of skew lines l_1 (x_1,x_2) and l_2 (x_3,x_4) is the cross product of vectors (x_2-x_1) and (x_4-x_3)

N==(x_2-x_1)x(x_4-x_3)

and normalize it, we get

n==(x_2-x_1)x(x_4-x_3)/|(x_2-x_1)x(x_4-x_3)|

so the distance between line l_1 and line l_2 is

d==n.(x_3-x_1)

Easy? For more informations about vector and geometry, please refer to
http://mathworld.wolfram.com/topics/Geometry.html

Poor sound quality on Debian (settled)

Did you ever meet the same problem? When playing music or cds, there is a backgroud noise and the sound quality is quite bad.

Set your PCM to about 80% rather than 100%

Pulse code modulation (PCM) is a standard method of encoding analog audio signals in digital form.

So it seems that debian is not dealing well with sound encoding and decoding currently.

Element Uniqueness

Element Uniqueness

I was reading on the topics reductions and lower bounds (Combinatorial Algorithms) when met the problem again.

Definition: Given a list of n numbers x_1,x_2,...,x_n, whether any two of them are equal.

Artificial Intelligence

We are stepping from floor one to floor two. To reach floor 3, there is a long way to go.

AI

Gcc does not support unicode

Gcc will not compile souce files in unicode

Of All The

From Peanuts

Of all the Charlie Browns in this world, he's the Charlie Brownest.

:)

so dark the con oF man

Madonna of the Rocks, with a more popular name The Virgin of the Rocks, refers to two different paintings with almost identical compositions. One is in the National Gallery, London, and another is in the Louvre.

SODARKTHECONOFMAN
vs.
MADONNAOFTHEROCKS

Humorous Words

• There are 10 kinds of people in the world. One knows binary, while the other don't.
• 
  
• 世界上总共有 10 种人，一种懂得什么是二进制 ，一种不懂。

Style today is simple

So who has brought us the style?

Obviously.

Vista, Office 2007, InfoCard

This afternoon, I attended, together with SV, a so-called meeting held by Microsoft on topics related to Vista, Office 2007 and InfoCard.

Well, it was actually not a meeting for us. However, we did get something, a small foot-like clock (it is cute ;)) and some ideas about the corporation. Two out of three lecturer (so called) demonstrated on Vista and the other used XP.

First topic was Vista. What is Vista? What could Vista do? What to benifit from Vista. Most are demonstrations, few about technologies. One demo was 3D virtual Olympic arena. Another was clipping of anything, pictures, videos, vectors or bitmaps. They were somewhat interesting, though not equally useful.

Algorithm related Book List

Combinatorial Algorithms

Computer Graphics

Design and Analysis of Algorithms

Computational Optimization

Computational Geometry: Methods and Applications

Introduction to Algorithms (2nd edition)

Advanced Topics in Graph Algorithms

Graph-Theoretic Algorithms

Fundamental Problems in Algorithmic Algebra

Algorithmic Information Theory

Algorithms and Complexity

Combinatorics of Words

Fast Algorithms for Sorting and Searching Strings

Computation Complexity

Theoretical Foundations for Greedy Methods

RollRotor beta Now Available

RollRotor is a 3D animation demonstrator of rotors.

The beta version now is available at

sourceforge.net/projects/rollrotor

Before you download, make sure you know what 'beta version' means.

Thanks for your interests.

Live Archives

It's great, isn't it?

New Project on Sourceforge.net

Recently, I created a project on sourceforge.net. The project is about visualization and animation. Now it is under alpha test, and the beta version will be soon available.

Thanks for your interests.

btw, subversion on sourceforge seems not available.

Why in English

reasons:

1. Widely used! The most important


2. ACM/ICPC official language


3. Personal preference

Floyd-Warshall All-Pairs Shortest Path

Time complexity: O(n^3)
Space complexity: O(n^3), O(n^2)

In computer science, the Floyd-Warshall algorithm (sometimes known as the Roy-Floyd algorithm or Warshall's algorithm) is an algorithm for solving the all-pairs shortest path problem on weighted, directed graphs in cubic time.

关于网络的一些想法

从writely说起, 它大概是最早提供在线word的,而现在google又出了spreadsheet, 也就是ms的excel (受ms影响太深了~~) 随后我猜想(或者已经存在)会有ppt, dreamweaver (其实page creator就是的, 虽然太简陋了), photoshop (这个比较有挑战, image的数据量不是一般text可以比的), 然后我希望会有visual c++(或者换个好听点儿的名字), java bean, eclipse, ultraEdit.

切入正题, 我想说的是google, writely等正在逐步改变microsoft所创立的windows植入用户大脑的根深蒂固的概念或观念. 简单的说, 网络时代才刚刚开始.

我们可以没有硬盘,内存,cpu,甚至显示器,键盘,鼠标等等. 我们不需要电脑或者说pc! 我们需要的仅仅是一个接口,或者说交互的终端(terminals), 但不一定是显示器和键盘, 它也许是三维投影仪(个人设想;)

那么, 我们的数据在哪儿?

上个世纪, 也许你可以把金砖藏在自家的地下室里, 现在, 你更愿意把他们放在银行(虽然不是每个银行都像瑞士银行). 所以, 现在你把你的(数字化的)宝贵资料都放在自己的电脑里, 将来也许应该有一个类似银行的机构(当然不是存放现金), 或许银行以后也开办这样的业务~~ 或者有个新名词~

安全问题

最重要的问题便是安全问题, 大多数人都很关心这个问题, 特别是关于敏感信息, 个人隐私等等. 那么, 首先的问题是放在个人电脑上够安全吗?

对于大多数人来说答案是否定的. 很多电脑上没有密码或者密码很弱, 绝大多数硬盘上的数据没有经过加密, 换言之取得那些数据根本不需要密码,操作系统的登陆密码是一个极为脆弱的保护(什么级别不记得了, 大概C).

另外一个问题是, 你有备份吗? 或许有人有很好的习惯, 把数据备份到移动硬盘上, 那么这是很值得称赞的, 但是, 请问你的移动硬盘跟你的硬盘的物理直线距离是多少? 10米还是10公里? 还是更远?

No Evil

cvs, subversion. spreadsheets, writely.

Mnemonic

Mnemonic, pronounced nee'monikos, is "A device, such as a formula or rhyme, used as an aid in remembering."

Examples of Mnemonics:

PI

Poe, E.: Near a Raven. Midnights so dreary, tired and weary.

Silently pondering volumes extolling all by-now obsolete lore.

During my rather long nap-the weirdest tap!

An ominous vibrating sound disturbing my chamber's antedoor.

'This,' I whispered quietly, 'I ignore.'

Perfectly, the intellect remembers: the ghostly fires, a glittering ember.

Inflamed by lightning's outbursts, windows cast penumbras upon this floor.

Sorrowful, as one mistreated, unhappy thoughts I heeded:

That inimitable lesson in elegance--Lenore--

Is delighting, exciting... nevermore.

Algorithm related Abbreviations

dsu - disjoint set union

dp - dynamic programming

dfs - depth first search

bfs - broad first search

FFT - Fast Fourier Transform

NP - nondeterministic polynomial

KM -

LIS - Longest Increasing Subsequence

LCP - Longest Common Prefix

SA - Suffix Array

KMP - Knuth-Morris-Pratt

Any More?

Looking for Numb3rs

Season One

Uncertainty Principle

Maximum Flow

Time Complexity: O(n*m^2)
Ford Fulkerson Algorithm

Play with it

Algorithms

Ready

Settings, catelogs, plugins, sidebars, widgets, etc..

First things first :)

Thanks for your interests.

This is the very beginning...

And there is a long way to go...

Tsul Problem Hints coming soon.

:)