我的征尘是星辰大海。。。
The
dirt and dust from my pilgrimage forms oceans of stars...
-------当记忆的篇章变得零碎，当追忆的图片变得模糊，我们只能求助于数字存储的永恒的回忆，
作者:黄教授
上一个世纪的最后的日子里。。。无痕的岁月。。。 以前的杂记
Here comes the personal notes of English version. The purpose I write both English and Chinese version of my day dreaming gossip is that for some idea, it is more natural for me to write it in English. Of course, there are some percentage of showing off as I stated in the original purpose of establishing this website, however it seems to me that knowledge is accumulated from generation by generation. If everyone is so selfish that he didn't share what he thought, we might never have our prosperous civilization today. Then why don't you show off your idea if you think it is worthwhile? It is nothing shameless to share with others.
14/7/04
I am supposed to write something here, am I? In my Chinese main page, I write down my diary and every month I have to move the last fourth month diary to my backup page as the diary becomes so long.
I like to see the
LHS or left-hand-side-column grows longer than RHS or
right-hand-side-column even it means imbalance. It gives me
some phoney proud as usually LHS lists all my work during my study.
However, the RHS usually records my meaningless solo. I think for
most of time, I am simply talk to myself and those "ambiguous,
blurred, chaotic words" are only functioning as a reminder for
myself when I try to read them later. Should I also write these kinds
of garbage in English? Why not?
12/7/04
The reason for me to look into "code breaking" is the strong belief that problem solving is a process of code breaking. Here, code in a more general sense is representation of phenomenon of objective world. We are not solve problems on problem itself, rather at bottom of our hearts, more precisely in our brains. Therefore, a isomorphic mapping must be established between the object world and its pattern in our brains. This is exactly the meaning of code. The code is created either by others or more probably by nature itself. What we need to do is to "break" it, or to "understand" it. The way of code-breaking is described like some activities of creation of arts because it requires wild imagination. Let me quote the preface in the book "battle of wits": "It is not necessary to be crazy to be a cryptanalyst. But it always helps." ----Joseph Rochefort.
14/7/04
The "code contest" for me is always a defeat of self-confidence. I cannot even finish the very simple first problem within three hours.
18/7/04
I have a quarrel with my friend Mr. Zhu over distribution of blood type of human kind. I decided to write a little program to test my argument: O type has the smallest chances to be inherited. The only reason of majority of O type in the world must be due to the fact that O type is originally only blood type of human. All other type are developed from O type after many years. I give this trivial program a star only because it proves me correct, at least its running result does.
A second check revealed a small stupid mistake in displaying---I swapped the result of type O and type AB. In order to save face and save space, I decide to modify it without creating a new version.
And I show the probability by the most stupid way.
20/7/04
I am not in slightest mood to add more sentences into my little imaginary dialog between HAL9000 and Dave in "2001: A Space Odyssey".
The second test program proved to be great difference from previous one.
21/7/04
I want to achieve the variable number of parameter like those in function "printf()". But the template class doesn't work. I guess maybe the passing convention of either template class, or virtual function is different from c convention.
26/7/04
It is my greatest honour to receive such encouragement from respectable professor Mr. Cliff Shaffer!
27/7/04
I think the approach is beyond the ability of compiler.
29/7/04
I found the way to remove comparison class!!!.
10/8/04
I always want to write Huffman code as it is such a famous and fundamental algorithm. However, compressing file is still not very easy as you need to operate on bits instead of bytes since all file manipulating functions deal with bytes as far as I know. Then aligning Huffman code to series bytes is a tedious job. So, I give up.
11/8/04
It is a good evening to take a walk around with some stupid idea in mind such as recursion. You know, it puzzles me when I think over this stupid question. Every computer science student understands recursion. However, I always regard there exists two kinds of recursions: recursive structure and recursive algorithm. For the first one, we can find an example in definition of set. And I think usually the concept of recursion refers to the second one---recursive algorithm. Is there any connection between two kinds of recursions? Ironically, before asking this vague question, I begin to wonder if there really EXISTS recursive structure in real world! Can you imagine that you could find an exact same box inside a box in 3D world? Mathematically, we can define a recursive structure like a set, but we even find it difficult to realize it in as abstract way as in computer language. Just remember your first experience to define a linked list in C++, the recursion is done by a pointer instead the structure itself. Considering pointer is of no size at all comparing with structure. Does it imply that the recursive structure doesn't exist in real world at all? If this is true, then why do we have this concept of recursive structure? Or maybe we are confusing the two concepts? Or more probably, it is me who invents this stupid concept?
15/8/04
Today I played basketball with my good friend Mr. Zhu and we talked about philosophy of life a little bit. He told me that he realized he is a common person and he felt a kind of relief. I told him I felt similarly. However, as I said before, I am just a common person with a common wish to try to look like uncommon. In contrast, he is an uncommon person with an uncommon wish to try to look like common.
I tried to use two simple grammar example to indicate how to use SLR(1) grammar to detect context-free-grammar ambiguity. Of course, I cannot prove it at all and I highly suspect it is a good one, or a reliable at all.
16/8/04
Two naughty boys play a little game with you. As they are both genius of math, you can only beat them if you are a computer science student or a programmer.
I don't think many people would make such stupid mistake like I did for so many times. It is purely a shame since I just read MSDN without understanding anything! There is a long-time naive thought in my mind about "files", that file is similar to "null-terminated" string that has some special terminating character to indicate end of file. This impression maybe come from the shape of function "feof". I continually trace the run-time of VC6.0 and it is Mr. Zhu's comment that reminded me: the length of file is recorded in file descriptor. And I was told this from so many courses, comp229, comp346 etc. However, they seems to have no effect on my mind when I deal with practical problem! Indeed, Mr. Zhu has a stronger logic mind as he declared!
22/8/04
So, everybody who already has taken computer architecture course knows that the average latency time for disk arm to move to the target track is 1/3 of time it moves across all tracks. But how to calculate this? Honestly I don't know. I write a simple program to simulate and convince myself. However, there is one pre-condition for all kinds of "average waiting time" problems no matter whether the waiting elements are processes or tasks or threads or whatever. The length of queue must be stable otherwise there is no average waiting time at all. Just imagine the queue is continuing to increase as the output is much slower than input. Can you predict the average waiting time? Increasing to infinite? That is why I write the second version to test under different the incoming rate. The result is exactly 1/3 if the tasks are sparse and few.
After lunch I visit Mr. Zhu and understand the way of integral. The "latency" has nothing to do with "waiting time". They are completely different things!!! Latency is simply the time needed to reach the point by moving disk head. We simply don't have to consider the waiting time for each task.
In fact, it is a rather simple calculus problem.
25/8/04
A simple problem! But why should I use such complicated way to solve? Maybe I just want to show the application of "radix sort" which is said to be the way used by IBM in World War II for American secret service to help breaking Japanese code: how to find repeated string in enciphered code?
29/8/04
Today I understand a little problem of my code: You cannot passing expression as parameter to a "macro"! I distinctly remembered this problem when I took "compiler design" when I always took for granted that I CAN always passing an expression as parameter as long as the types are in consistent. During that course, I realized how much work has to be done to achieve such seemingly-easy functionality. You know, the preprocessor mechanically replace the "macro" and at that time, parser even has not started job, then how can precedence and meaning of operator be able to be translated by parser?
i.e. #define ABS(x) (x>=0?x:-x)
If you want to use it like this: ABS(--x), then what is the truth value of
"--x>=0"? There should be some unpredictable problems.
30/8/04
It is rather strange that when I try to define a function in "dll" by using "__stdcall" which is said to be the "windows API" calling convention my calling function pointer cannot correctly find the exported procedure address by using "GetProcAddress()" call after I load library with "LoadLibrary()" call. It is OK if I define the exported function by using "extern "C"" and my calling function is also defined as "__cdecl". But why cannot I use "stdcall"? Is that because I am using VC++ which is now compiling into C++ name decoration?
2/9/04
The last summer sunshine in my eyes. I am in my last sunshine. The last sunshine in my heart.
6/9/04
I should read these books, I wish, at least this is what I thought. Thanks.
15/9/04
I decide to take AI in winter. In order to memorize the basic operation of vector, I write an extremely trivial little program for practicing. The point worth mentioning is the argument of "..." which I believe very few programmer would like to use it.
18/9/04
And I post my FTPServer. But please don't copy all of them, otherwise we will all get zero marks.
21/9/04
Sometimes, I just wish I have the chance to study more about mathematics.
I am hesitating on if I should post my ultimate version.
22/9/04
It is probably the footstep of those hackers. And I wish I have time to write a simple program to monitor all ports of my computer to alert me if there is some unusual activity at certain port. I am sure there is finished tools with this functionality, but it is fun to write by myself, if I have time, of course.
24/9/04
03/10/04
Yesterday I spent one dollar to watch two big movies: "I, robot" and "King Arthur". However, I was soaked in the rain.
"Winzip" is said to use "Lempel-Ziv" compression algorithm. I finished the simple compression before going to cinema. The de-compression should be finished in next edition.
11/10/04
My thanks-giving is a hard-working day, at least I only eat two instant noodle to prove that I am working very hard. The UDP turns out to be complicated than I expected. This is ridiculous.
15/10/04
I found some problems in linear algebra. It quite upset me that when I told all my friends that the idea of linear transformation is very profound and almost always their reactions were not what I expected. Maybe my mind is becoming slower and slower recently.
15/10/04
Are we proving they are linearly independent or not?
19/10/04
20/10/04
02/11/04
I like the quotes in my networking textbook very much:
Data is not information; Information is not knowledge; Knowledge is not understanding; Understanding is not wisdom;
If you forgive me, I would like to add one more from my own: Wisdom is not originality;
10/11/04
Maybe my mind is more and more like a machine because I found I have difficulty in justifying a simple problem without help of compiler of C++.
11/11/04
It takes me five paper to write down my proof.
12/11/04
I add a binary search for monotone array. The program is trivial, but the analysis by Master Theorem is a bit of fun. At least I try to understand the practical usage of this theorem.
14/11/04
I finished "gobackN" with some kind of hard-working since there is some confusing part you cannot predict until you write a program. This is what I said often to my friends: Unless you are 100% of clear about what you are going to write, you are surely going to make some mistakes. There are several issues worth of clearing up before you begin coding:
1) Should receiver send NAK for each out of order packet? Or is NAK necessary?
2) Should sender resend all outstanding packets in window whenever it receives a ACK for some packet? Or should sender be wiser to wait if last packet window is ACKED before timeout?
3) Should the last EOF packet be included in last window to be sent out with other packet? Or does it help to send the EOF before all data packet are ACKED?
4) Is it a kind of advantage for receiver to ACK each well-ordered packet?
5) How to solve the last packet dilemma?
16/11/04
I am not convinced by your proof.
17/11/04
Indeed dynamic-programming is rather shallow intellectually as it is said in lecture. However, when we do programming, should we add a bit flavor of dynamical instead of statical? I mean, is it wise to calculate all sub-problem even the user's request is obviously impossible? In this case recursive call is more efficient because it only touches those sub-cases that it needs. On the hand, recursion might repeatedly call those cases it solved. In order to combine the both advantage of "dynamic-programming" and "usual recursion", I just add one line of code to check the stored records of calculated cases before recursive call. So shallow intellectually, albeit quite useful. It saves tens of hundreds of wasted executions.
Is dynamic programming as powerful as you imagined? It is a mixed answer. On one hand the total calls for single base LCS(1,1) is far less than expected. The total repeated call of all repeated recursion calls is still very big. From this trivial experiment of LCS, I want to prove my suspect of the claimed upper-bound.
20/11/04
The tutor should have warned me that small modulo number won't work for go-backN under condition of "delay"! It only until the demo time that I discover this problem. The reason is similar to "stop-and-wait" when delay happens. However, I am stubborn to modulo sequence number since it has no upper limit for size of file to be transferred and it saves the size of header of packet. The compromise is to use a comparatively large modulo than window size. In my case it is 32 because there is only 5 bits left in the first byte of my packet.
28/11/04
I try to save the most important things I learned in lab project of comp451. And also I saved some naive understanding of NP-complete problem for my future review. It is always help to clear my mind when I try to write down what I am thinking and what I think I understand. Quite often they turn out to be a contradiction or conflict.
This morning the news program in CBC is discussing some moral value of anti-terrorism war. It is said, "Sometimes what is right doesn't work; Sometimes what works isn't right"; I have to compromise with my ideal to this realistic world.
29/11/04
I don't like to do those kind of numb-minded-mechanical job. So, I write a simple program to calculate the Bellman-Ford routing algorithm. It is a rather intuitive, straight-forward algorithm. And I am too lazy to write a matrix-reading function. So, I borrow a simplified "matrix" from my old code.
30/11/04
I wandered in library and found a book which talked about implementing graph and combinatorial algorithms. But it is a pity that they used a high-level language called "mathematik". Maybe I should write little by little by myself with c++.
Whenever I told my Chinese classmates that I was taking "linear algebra". They would always tell me that is an easy one. And I would always try very hard to evaluate my IQ to see if it was below 100 then. Why should they regard it is an easy one? To me it is such profound theory such that you can use vector to explain so many issues. Is matrix a naturally a part of linear algebra? I always suspect it. To me, matrix is nothing but a perfect tool to represent pair-wise relationship among elements of a set. And linear algebra is perfect to describe the relationship between all subsets in a superset. Why? Have you asked yourself that is it by coincidence or by consequence that a matrix of MxN has dimension of MxN and the collection of all linear mappings from vector space V to vector space U whose dimension is M and N respectively also forms a vector space of dimension of MxN. Or in mathematics language:
dim(Matrix of m x n) = m x n
A={ f | f: V-->U , dim(V)=n; dim(U)=m and f is linear transmission}
dim(A) = m x n
(If matrix has not the same dimension, we cannot expect it to represent all transmissions.)
02/12/04
In DBMS, there is almost everything you can find in OS. I want to write a simulation for scheduler in DBMS which use time-stamp to ensure valid concurrency. However, it takes me a whole day to start with the environment. What is a task? What is a transaction? What is a task item? What is a scheduler? It becomes quite messy after I create this environment!
A little improvement of Bellman-Ford algorithm. Now, it update more entries within one loop, therefore it saves some time.
04/12/04
I finished the second version of scheduler with two basic operations: read, write at the price of forgetting my breakfast. After a hot shower, I am in a rather sad mood in listening to some classic music.
Actually in the afternoon I tried very hard to finish the "abort" and "commit". As a reward, I think I found a big loophole in the scheduling protocol of textbook. In the reading request, the book asks to check database element's committed status. And only grant read unless it is true. But if the read request is from the same transaction of previous write, there should be no need for checking. Otherwise it is a deadlock since committed status will always be set false if it writes.
The code becomes quite complicated to me. And I highly suspect anybody can easily understand what I am writing. I often hear somebody boasts that he has been learning C++ for XX years. However, it seems to me that he is saying that he learned C++ XX years ago since he may not be using it so often, or in worst case, not at all. How many hours have I been coding since I learned C++ two years ago? I roughly estimate it should be more than 1000 hours. It is just like those elite pilots compared with each other with flying hours per year. Otherwise, the question of how many year you have learned C++ becomes quite meaningless.
14/12/04
A personal understanding of similarity of two matrix.
27/12/04
My mind is in a chaos state for several days after my finals because I am continually playing the most silly PC game day and night. Then I excused myself for finishing a simple extensible hashing for more than two days. There is some tiny details about disk hashing that I don't understand clearly, especially how to expand, split bucket. It once more proved that you cannot write a program to implement an algorithm if there is any double, ambiguity about it.
04/01/05
The first lecture of a course is often misleading. i.e. Comp326 makes me feel I am entering a wrong classroom. Sometimes I am thinking I am playing "Age of Empire" because the slides show the development of human architecture and it is quite similar to the game from Microsoft. Sometimes I am thinking I am taking a market course because I get the impression that a design engineer of chip company has to take market factor into consideration. I wonder why this should happen. I mean, as an engineer, I just do my best job to optimize the output based on limited input. That's it and just leave the salesman to take care of other issues.
07/01/05
I have been hesitating for my bit-matrix for several days. On one hand, I think it is still very simple and need more implementation, especially for an approximate approach for calculating "clique" problem. On the other hand, I clearly know that for all this kinds of "mission impossible" adventure, it is futile to spend more time and energy. Honestly I do think it is possible to find a polynomial algorithm for problem of clique because when the "k" of "clique(G, k)" is a certain concrete number, it is not NP-complete problem. It is only when k is somewhat related with size of G, say k=n/2, it becomes NP-complete problem. But I am definitely not the genius to find any algorithm.
Oracle pointed to the porch behind Neo and said, "it is Latin, means 'know thyself'." -------<The Matrix>
The question is how to know yourself? In my opinion, if you want to prove x=k for some number k, you have to prove that both x>=k and x<=k are true. Then logically you have to find out both your upper bound and lower bound. The closer you find your both upper limit and your lower limit, the more accurate you know yourself. In my case, I found my upper limit in comp465 of "analysis and design of algorithm". I know I am not The One. However, it makes me feel better just like Neo took the cookie Oracle gave to him.
In <The Matrix>, I particularly like the Agent Smith, the guardian of the Matrix. In his solo with Morphius, he shared with us his philosophy. He found out that human beings is not even a kind of mammal because all mammals in this planet would achieve an equilibrium with nature. However, human beings moves to every area they can find and multiply infinitely until all natural resources are consumed. Then they have to spread to another area to survive. Agent Smith found out that there is only another organism in this planet shares the same pattern. It is virus. Therefore Agent Smith thinks human beings are a disease, a plague and the Matrix is the cure.
Another interesting point from Agent Smith is that human beings defines their reality as misery and suffering therefore no one would like to stay in the perfect dreaming world of the Matrix. Or coincidentally as I quoted ancient Chinese saying that "people would die in safe and slackness." In North America, people lead a almost perfect life that so many people continually ask why the world is like this. So, they ask themselves who I am and where I am from. As a joke Mr. Bean (Rowan Atkinson) in my favourite series "The Thin Blue Line" answered perfectly, "they should look it up in their passport or ask their parents." Haha, I like so much about the puns and jokes in the British humour even though it is very difficult even for a native English-speaker in North America. I just watch it over and over.
Some say that language is the shell of thought. And logically it implies that language is only a tool or carrier of idea. However, the carrier and passenger are in such close relation that you cannot imagine chemists talk to each other without referring to formula and elements and compounds and musicians communicate with each other without actually playing the instruments. Similarly without thought there is no need for developing language. Then in this sense language is a part of idea, or gut of thought to some extent. In China, there is an overwhelming popular tendency that people educate their kids by learning English without developing corresponding minds. I think I am one of the victim in my university education in China. That is why I feel mind shock when I took Eng207 in Concordia. During the English lecture my teacher emphasize more logic and idea even than most of my computer science and math courses.
10/01/05
I am surprised and grateful to professor's detailed explanation. I feel lucky to take a right course with a right professor plus the right tutor!
14/01/05
Practicing programming under UNIX.
14/01/05
Have you ever realized that "copy file" is not a basic system call in any usual operating system? And at beginning I was worrying about the relative path and absolute path, then I realized that "lstat" is not system call and can do a little "parsing" job to ease programmer's pain.
18/01/05
My memory is as bad as that! I even call the algorithm as "Euclid Algorithm"! What a joke!
20/01/05
I update my "weblog"(I learn this term from Dr. Grogono one year after I have been updating my weblog the way that the term defines. It gives me a sense that there are many, many people who are thinking in the similar ways. ) in a real time mode, so, I am acting like real time system? It is a bad joke.
21/01/05
I cannot observe the strange behaviour of "readlink" again.
23/01/05
temporarily backup my first part of lab1.
24/01/05
It is quite a painful job to debug under GDB of Linux as it takes me almost two hours to find a simple pointer error. And there is some subtle difference in function pointer between C++ and C. Also the "constant" in C is treated almost like variable and I have to change it to be "#define variable value" instead of "const int variable=value;"
I add a dynamic array in my lab1 which is written by me at least more than three times. It is always fun for me to write those old simple subjects. But the debugging of pointers in GDB under Linux is a real pain.
30/01/05
Miss Sunny supplied an interesting algorithm to minimize DFA. If I have time, I would do it. However, I am struggling with my comp444.
03/02/05
08/02/05
How to convince myself that the parent and child process are sharing the same file status table?
09/02/05
If someone would ever ask me the question: what is the major characteristic of Canadian film, I would tell him/her without any hesitation by two words, nudity and horror. The theme is always similar. A blood-lust parasite or epidemic, vampire-like or zombie-like, Montreal or Toronto...It seems the imagination of Canadian directors are restricted within horrors happened inside Condos.
14/02/05
For the number of blocks in each block group, a formula was given in lecture: block# in partition / (8x number of bytes in each block). I think it over and over and understand that file system in Linux must use one block to hold all block group as bitmap. This maybe explained in lecture, but as far as I can recall, I have no impression. During the lecture of comp326, the instructor found precious lecture time is so difficult to waste that he deliberate allowed students to give out various comments publicly which usually had nothing to do with technical stuff. Some students complained about ambiguity of questions in both comp228 and comp229 which I totally disagree. In Concordia, comp229 is one of the unique course which needs student's double efforts to understand it thoroughly. As for me, I gave it triple efforts in the sense that I actually listen to lecture for THREE times. By my personal opinion, usually those who are doomed to be the level of application programmer will definitely find system programming boring. Those who are destined to be system programmer will inevitably find application programming fascinating and application programmer farce.
I collect those useful questions and answers of which I highly appreciate.
And for personal review purpose, I store my second assignment here because by experience if I don't posted here I may never find them in future.
23/02/05
Can you predict how many signal do I receive?
27/02/05
A personal reminder of sigsuspend().
At the nick of blade...(Signal handling programming is tricky and time-consuming in the sense that you cannot trace them properly since they are definitely multi-task programming. Is there any good reason to use signal within one process except you implement thread by yourself?) It is a hard job than I expected and I am really happy when my program can generate 2000 child processes and play in a tournament of 1000 games, even though the joy is a slightly less than playing "Koukai4" for more than 16 hours a day.
03/03/05
05/03/05
SIGPIPE is only available for good-habited programmer.
09/03/05
Today there is a demonstration in Concordia and some students want to go on strike. I read the bio of my professor and it is really interesting. His life is not so straight forward. It reminds myself which I also think is not so straight. And what's more, I learned a perfect word to describe myself--hyperbole.
10/03/05
Thread test1. The name of novel I have forgotten for long is "Martin Eden" by Jack London. I dimly find the same shape in the bio of my professor. The other day I saw DVD <A.I.> is on sale for 11.99 and I was attempted to buy it. However, I recalled that it is one of the few films that makes me shed tears. So, I persuaded myself not to buy it.
14/03/05
This is just a personal reminder: To solve the circular softlink puzzle, i.e. A--> B, B-->A, you need to cautiously call "lstat" first to be sure if it is a softlink. If yes, then call "readlink" to retrieve the contents of softlink. Then repeat previous step until you reach regular file or directory.
There is one and only one mode in C, passing-by-value, nothing more and nothing less.
18/03/05
I really don't want to treat this synchronization-revisit as some new work for me.
25/03/05
The puzzle of sleeping thread...
27/03/05
This is a naive approach and it is some kind of stupid try like my previous try on "clique" problem. It is only to satisfy myself. And I even don't want to explain that. Just keep the page full.
30/03/05
Why should I specify "O_RDWR" instead of "O_WRONLY"?
A program for enjoying myself. This kind of programming makes me feel real good. It is purely for fun. It is a minishell.
02/04/05
Wild, wild, test. These are just mindless tests.
05/04/05
05/04/05
The major lesson I learned from this lab4.
09/04/05
12/04/05
signal is essentially bitmap and counting won't guarantee for all children's SIGCHLD signal
15/04/05
Grammar is just a pattern，and compilers in most cases are "predictable-pattern-processor". What if the pattern is unpredictable and we need to add newly-discovered pattern dynamically into old compiler? A dynamic compiler?
19/04/05
22/04/05
I spent 7 hours a day to finish this little program and began to worry about my coding ability.
25/04/05
My book collections. Generally I don't like to buy those copied ones since I have the belief that only if I treat those books seriously enough can I be treated seriously enough by those books. Most men would like make friends with a real girl instead of a replica of human. So, I don't like reading a copied one.
Is it semantically reasonable?
24/05/05
China has become a crazy world! Can you imagine that millions of kids stay in internet bars for day and night? Can you imagine that one internet game has more than 80 million regular players? Can you imagine that countless kids are paying nearly 2000 Canadian dollars for one weapon in web games and that amount money is almost several months' salary for a common person in China? And can you imagine that some teenage dealers for stolen account/password can earn ten thousand Canadian dollars per month? Isn't it crazy?
For record purpose, I just post two small trivial project which were finished before my travel to Guangzhou. Half-finished big-number and inexact-match with DFS.
16/06/05
The only thing in my mind about Shakespeare is "Denmark is rotten." Now I should say "China is rotten!"
18/06/05
23/07/05
I always consider template is a key to many issues in my heart and they are also often puzzles in my mind. Once I read a message in Chinese BBS which discusses the connection and conflict of template and inheritance. It is said these are two different approaches for a common purpose. But it seems to me that template has more unexplainable profound meaning.
For quite a long time, I am searching for ways to handle pointer of member functions of a class. It seems there is way to handle them. And after the little test, I reconsidered the significance and realized that it could be considered as a demo of implementation mechanism of late binding and vtable.
This is also a remarkable event. I discovered a new way of passing callback function pointer to a template class. Usually I will define the function pointer type and declare the variable which points to the implementation function. Then declare the template class variable by passing the function pointer variable to constructor of class. However, this new way is demoed in a famous book <Generic Programming and the STL>, that it declare a struct which overloads the operator(). Then you just pass the "struct" to the "type" parameter of template class. Please note that we DON'T pass struct variable to constructor. My own explanation is that the struct's overloaded operator() is like a static method of an abstract class which will be called by constructor. (This is purely my guessing.)
23/07/05
After I wrote down those notes in yesterday, I bought a Chinese version of <The C++ Standard Library> which is translated by the same writer who is from Taiwan. In this book, everything is described so clearly and many my long-time puzzles are explained thoroughly. And I also found many "my" discoveries which are treated so ordinarily that I felt very disappointed because these are so common to those masters of C++. i.e. Once I noticed there exists an overloading of operator "void*" by "iostream" and I thought it is quite remarkable and now I understand the reason. You also overload operator "!" for "iostream" and this is a test for errors which already happened. And operator "void*" tests errors just happened now. i.e. if (cin>>myInt) which just calls operator "void*" and if (!cin) calls operator "!" to test errors happened already.
17/08/05
Yesterday midnight I came back by last flight from Guangzhou to Xiamen and ended my nearly one-month wandering in China. There are the traces of my footprints during wandering.
07/09/05
Today it is the first class of AI and there comes the old famous question: Is "DeepBlue" intelligent? As always I think we need to define our question very clearly before attempting to give an answer: What on earth is intelligence? Decision-making, problem-solving, learning etc maybe your answer. Then under the chess-playing environment, DeepBlue is indeed doing very well in decision-making, problem-solving, even learning on the senses of known environment. Why don't we call brute-force-searching intelligence? Probably those who ask this question consider that simple intelligence is not really intelligence. But without the first floor, how can you come up to the top of building?
Another thing I attempted to exclaim in the class is that I come up with my own little definition of A.I.: I want to switch the AI to IA which stands for "Intelligence Automation". If this definition can be accepted, then there will be no such questions like above because automated intelligence are all part of IA no matter how simple or complex it might be.
08/09/05
Is definition itself able to be defined? Can algorithms itself be described in the format of an algorithm? In other words, algorithm will be manipulated as common data.
A set is a domain or a context such that elements inside it can be referred in a denotation system, i.e. names. Maybe scope is its alias in this sense.
set ->stack -> list -> vector is a sequence of denotation system such that information needed to describe the system is decreasing. i.e. In set, you have no other way to denote each element except enumerate them one by one. Stack gives you a single direction of enumeration while list may provide double direction. Vector is a well ordered form which can be accessed randomly which means that you can use minimum information to book keep a system.
Knowledge is a system of compression. Knowledge is an evolution of encryption or encoding. Learning is a process of decryption. Memorization is the simplest way of decryption and it costs most. Whatever way to help decreasing amount of information is considered as a progress in civilization.
I am recovering bit by bit from difference both of time zone and culture. Hopefully isolation can play a good role in this process because no internet connection at home is becoming such a luxury that you can ponder on whatever is worth thinking about such as Scheme, OpenGL etc.
To mount a CD in Linux, just type mount /dev/cdrom /mnt/cdrom.
15/09/05
Today I found a few things in lab regarding
OpenGL:
1. I defined glOrtho2D(). Therefore my view volume is just
a plane which means the solid-sphere cannot be displayed properly. It
won't be a solid sphere.
2. Secondly the co-ordinate I chose for
the above function decides the position of object I drew. It won't be
in middle of clip until you define xmin=-WinSize and xmax=WinSize;
...
3. In order to draw a moveable object, one of my tutors
introduced "PushMatrix" method. But Ram said that it is too
expensive and should be avoided. The lesson here is that there is
always many ways to go to your destination.
4. The problem Ram and
I cannot solve is that I tried to define a function pointer array of
a series of OpenGL function so that I can call them in future by
their indexes.But I always get a compilation error, or more
accurately "linking error". I suspect that the definition
of function must be available for linker to link because I test with
some static function and it works. Therefore my theory is that OpenGL
function are all defined
in "dll" file and can only be
linked dynamically. Ram suspected that it is due to function
signature or those calling convention key words in MS VC++. And he
suggested that I tried it in Linux.
16/09/05
The problem is due to calling convention.
17/09/05
I have internet at home again and I can continue to update my blog. I added a new column for "scheme"--a dialect of LISP. It is rather trivial for experienced programmer. However, it is really hard for any beginner in functional programming. At least I think it is my case.
20/09/05
It took me four hours to figure out a permutation of list. But combination only took me less than five minutes.
12/10/05
I spent almost three days including Thanks-giving Day to try to establish an object-oriented model for those primitives and commonly-used model in OpenGL. However, the result is very disappointing. At some point, I have to stop this futile exploration as deadline of assignment is approaching. Then I realized one of the major reason why this way is not so popular. It is efficiency. When talking about efficiency, there are two aspect regarding it. One is the performance efficiency and the other is the coding efficiency. Students from Engineering department can enumerate various reasons against OOP when performance is highly required. Even students want to argue that OOP helps improving coding efficiency, they have to realize that OpenGL transformation must be done at a proper order and sometimes lack of flexibility in OOP will eliminate all those benefits brought by class model.
The idea of my small project is straight forward and it is different from Dr. Grogono who tries to wrap those basic primitives in OpenGL which is handy and sound. My design concentrate on all higher level object developed by programmer and try to find out all the common property and method of them. Then define a base class which will be inherited by all models and also define most commonly operations of them. i.e. Every model object has a property of coordinate, color, direction which is the axis of the object, occupying dimension which is the enclosing cube created by scaling on three dimensional direction. And all objects have to implement an abstract method display which will be called by a global callback. However, within this function programmer doesn't have to think about rotation, translate, scaling operations because base class already take care of that with the property of derived classes such as coordinate, direction, dimension volume etc. Only the most basic simple standard drawing function need to be defined by programmer. And an object manager class handles all creation, storage, viewing jobs of all objects. This sounds quite nice to me and one immediate benefit to this system is that I can used it in my project design by creating a script system that art user can create their 3D world by script file which will be read by my glut Object manager class. However, some viewing problem puzzled me for quite some time and I stopped there. Just in case I need them again, I store a half-finished version here.
After four-month of wandering, I feel quite embarrassed to post such a trivial program. Maybe the days of no-programming means blank days to me. To ease my pain in heart, let me post a few Scheme which is quite awkward. Tower of Hanoi. CNF_convertion.
13/10/05
In "wesnoth", for some units, at some time, the best defence is offence and for some other units, at some other time, the best offence is defence.
My vision comes from my passion; My passion comes from my mission; My mission is to cross star ocean;
15/10/05
The more I use VC++6.0, the more I feel hopeless. When I started using VC++ almost three years ago, I felt it was almost perfect. However, day after day I have an feeling that sooner or later there would be a day when I realized it is not perfect at all. Maybe the day is approaching. Besides the gigantic amount of bugs in templates, there are also many so-called "nuisance" within the class operators overloading. I heard this evaluation against VC++ from Dr. Grogono when I tried to explain to him one bizarre behaviour in compiling his graphic library. (Maybe it is due to my wild-guessing explanation, however, the behaviour is unusual and it is almost a certain thing when you try to compile code in both windows and Linux.) There are so many illogical design in class model, if I can say so. Taking the example given in comp348 by Professor, class Account has a member function which takes a parameter of an object of class Account, void modify( Account& another), and it is possible for different Account object modify another Account object. You may attribute this to bad design. But you cannot deny this is a kind of flaw in class model since objects from same class has similar code denies the independence of each object.
Today I encounter something similar to above. I want to overload the operator * for my Vector class which takes a "double" parameter and return another Vector object: Vector operator*(double d); However, when applying, I need pass Vector object as constant reference as parameter in some function, then I have no way to use this operator.
void Matrix::rotate(const Vector& vect, double degree)
{ //now you cannot use this vect to operate.
Vector temp; temp=vect*degree;//this would be wrong since my operator overloading is not for "reference".
What I have to do is to define a global operator* overloading which takes LHS parameter as Vector&, and RHS parameter as double. Is it insane?
(When I finished above babbling, I get a second thought that I forget to overload operator* as a const function so that compiler refused to apply the operator* to const Vector&vect. This is explains everything and restores a little confidence for me in VC6. And it is a good lesson even though I have met such problem before several times. But why do I repeatedly forget such basic problem? Maybe by writing down can I start learning from my lessons!)
To describe a system with dimension of N, we usually need N+1 dimension space to describe it. Can this wild guess be a theorem? Recall in theoretical computation, there is a famous example that a program can not calculate the result of another program, since the program which is running only has two degree of freedom. Of course this is all my wild guessing.
In order to free myself from matrix calculation, I write a trivial tool to calculate the transformation matrix in graphic.
22/10/05
Sad day it is today! Even though I have anticipated this situation as long as two years ago, still I cannot accept this simple fact---I cannot code under pressure and my mind just stop working in that excitement. Programming competition is never a place for me because of the simple reason: I am too old for this sprint. Maybe I am a good marathon player. There is absolute reason for people to realize something which is absolutely painful! And that is it.
23/10/05
Failure in competition maybe a good thing for me to concentrate on preparing midterm of AI.
I write down this simple argument for proving evaluation function is monotonely non-decreasing for A* algorithm. And I also suspect there is a flaw in proof of textbook on monotonicity implying A* algorithms.
And here comes the cnf-sat. I spent almost a whole week fighting for this project and as a reward to my efforts, our group finally use my code. Even though it is a team work, sometimes you will find it is quite difficult to balance both job, functions and relations. So, I often prefer to do it all by myself as long as I can manage it because I discover that I have a big trouble to understand code of others.
25/10/05
LL sends a birthday card and then I realized that I am passing on another meaningful day after another meaningless year. It is said by ancient Chinese poet that 80-90% of wishes of one man are unfulfilled. Maybe I still belong to the lucky class. Suddenly I recalled ten years ago when I first visited Montreal as a member of business delegation. At that time, I cannot expect I have the chance to live in this beautiful city. Even though the small island across Pacific is also a beautiful city, here I enjoy more peacefulness.
26/10/05
The process of pattern-recognition is the process of repetition-discovery. The process of learning is the process of wrapping repetition with high-order functions. What is high-order function? I don't know and can only get a glimpse when I encounter linear transformation in graphic where 3D space linear transformation is unified by 4-dimension matrix transformation. And programmer always understand that if you want to write some clear-cut code, you need to wrap all repetition in another function and call them in a generic method. This is what I mean high-order function.
Something cannot be solved by scientists can sometimes be solved by engineers. Maybe I should try to become an engineer?
Generating all possible partition pattern takes me a quite some efforts! I even failed long time ago which is one month ago. And it takes me more than three hours to figure out my stupid mistake. This also proves that partition is a much complicated operation compared with combination and permutation. So, there are more "relation constraints" in generating a partition.
27/10/05
Our great leader and poet Chairman Mao taught us that: "Theory comes from practice and must serve practice." Indeed it must be like so. When I thought DFS,BFS,Backtrack,Best-First-Search,A* algorithm are trivial, I proved myself to be an idiot once again. The very first trivial discovery traced back the small puzzle when I read algorithm of Best-First search. I was about to write to ask why there is no path returned like DFS or BFS, then I hesitated because it is meaningless to let professor realize I am the most insane idiot in Concordia by asking such trivial question. The hesitation seems to be correct because under Best-First search algorithm, it is hard to track a path when you always choose the best node to proceed from open-list where both ancestors and descendants are mixed. I then try to use a internal link list to link each node with its parent when suddenly I realized that the "standard library" in C++ is passing by values for those "deque, list, map etc." and since those data structure are stored internally sorted from time to time, I have no way to pinpoint a pointer! This is purely implementation details since I am using c++ standard template library, however, it may have more profound meaning behind.
If I don't try to do it myself for those algorithm in textbook, it would be impossible for me to discover that problem, or worse, to realize there exists some problems. I am late for graphic tutorial now.
28/10/05
I didn't expect this trivial 8-puzzle debugging takes me so long and I even didn't finish it after 2am. However, when I wakeup I find a better way to recover the transition path. That is using the original start state instead of goal state which is obvious. The optimal path of 8puzzle is 57 step and I am still waiting the outcome of 15puzzle which is probably hundreds of steps. I write two versions, one without heuristic, the other is best-first search with A* compatible heuristic where heuristic is as simple as summation of offset distance of all nodes. Also I understand one thing, just like Dijkstra algorithm which can tell you the minimal distance without telling you the path. It is possible that these kinds of "greedy algorithm" won't be able give path unless you design your way to track it.
By the way, I forget to keep a version of newest "glutobject" which I continually updating for new objects and improvement. Yesterday I realized one thing I didn't expect. For non-symmetric objects, you need at least two vector to represent directions. I cheated by using a "lastDraw" to remit this flaw which only works for special cases. However, this is always the dilemma of design and application. It is hard to balance flexibility and robustness. One design can never satisfy all demands. Instead of modifying framework repeatedly, I decide to choose to ignore these issues.
I am only half-convinced about the explanation of DY because I highly suspect there can be as big mistake as this one for a well-known textbook of fourth edition. However, I am too stupid to see any obvious reason there is no decent explanation of using two principally different concepts without any notion. Maybe I should stop here and keep it in mind.
30/10/05
How do you make birds fly? How do you make flowers blossom? Actually I don't know the answer. Neither do I know how I should proceed on with my "glutobject"!
31/10/05
Can you call that programming? I mean, sometimes people regard parameter setting up as programming or coding. And this helicopter is the case. It takes me just a couple of hours to do the coding, or parameter setup including a little naive scene construction. The movement is quite straight forward. However, I do notice the weird phenomenon mentioned by my classmates in class about the pitch. I guess it is due to the similar reason when you rotate around 3-axis even though I cannot solve it.
I did very bad in AI which is quite easy to be predicted when I hardly read either book or slides. What else can you expect? However, honestly speaking, some questions are beyond my reach even I did read book. This is a bit unfair because I am no genius and how can I know something I never learned?
This month I did programming a lot and this comforts me a little bit. You know, I did absolutely nothing in this summer vacation in China. This makes me feel guilty.
01/11/05
I am lucky today to find another flaw in vc6 that when I include <cstring> instead of <string>, I will get wrong answer for operations of string, like +=, append etc. But this seems to be the convention to enable my program portable to Linux by changing <string> to <cstring> in include statement. Why? I also find a good toy of overloading operator "," so that you can pass infinite parameter to a statement, but you cannot do it easily in function as compiler would check number of parameter before invoking operator ",". Anyway it would be handy to call like this way: cout<<(Proposition1, Proposition2,Proposition3)<<endl; Isn't nice?
Hopefully I can finish my proposition translation from logic to c++ within today.
02/11/05
I give up the proposition simply because it is too trivial. But predicate is just too complicated for C++ to define it. And alpha-beta pruning is not so simple to implement. Just to output a tree takes me couple of hours to figure out. Hopefully I will finish pruning tomorrow morning.
Here is my puzzle: At beginning, I thought that I couldn't implement an algorithm if I didn't understand every detail of it. Later I realized that even if I understood (at least I thought I did.) every detail of an algorithm, still I might not be able to implement it. But in some cases, even I implement an algorithm, there is still big chances that I don't understand every detail of it because sometimes implementation of algorithm by following pseudo code in text is like a copy-paste. Alpha-beta pruning is of this case because the algorithm in text book is not very clear. Or I don't quite understand. It seems that I need another day to finish it.
I guess most students would consider this algorithm is trivial since there is only a comparatively less paragraph to cover it. However, I suddenly realized that without explicitly setup a concept of depths or levels of search it would be extremely difficult for you to implement it. As far as I know, it is a DFS with bounded depth for a MinMax tree which is generated ONLY when your DFS reaches a node. And it only ignore certain branches unless you already have some information, like heuristic value of leaf nodes. However, most of us are misguided by its "already-generated" minimax tree. (This is explained quite clear in a Chinese text book I bought this summer. It proves that not all Chinese textbooks are useless copies.)
This morning I went to attend a seminar of title of "Privacy Compliance of email" which was given by a post-doc from Uni. of Ottawa. This is a rather academic experimental approach to prevent carelessness of people who accidentally send out sensitive, private information. The hardcore of system is heavily depended on a rather poor parser which tries very hard to detect those key words in contents of emails by an extremely simple grammar rule sets. I personally estimate that it is very simple because: 1.It is impossible for a mail server to do heavy parsing job which will significantly reduce performance. 2. It is not worthwhile to do such job because the style of email is more flexible than formal article and natural language process is done no good on it. Therefore I highly suspect this baby toy can have any practical application except for academics research unless they find a better way for NLP. You see their statistic shows that the precision is very poor when the so-called "semantic-tagging" procedure does a poor job. Any good thing about it? I think it mentions a formal language developed by IBM for security rules which is quite interesting style. The name is EPAL. Maybe I can use this seminar for my comp495 report since it is academically shallow and is quite open for naive ideas such as their next stage goal: detecting attached files etc.
I bought a packet of frozen shrimp a few days ago and decided not to cook until I finished my alpha-beta pruning. You see I am training myself to write program in some similarity of training a monkey to do math. No matter how dump I am, as long as I continue to learn I would become smarter than most of those who stopped learning after they graduated. Let me try a new English saying I learned today. If there is learning, there is hope. It suits exactly for the case of AI because beyond all else learning is the most important part to solve. Although the more practical question is what to learn before how to learn. Or more essentially what is learning?
What happened to those monkeys which stopped learning millions of years ago? They become fossils of ice age. Then what would happen to those who stopped learning after grownup? I don't know. Maybe compu-archaeologists in far distant future would find out when computers become lord and master of earth.
04/11/05
The picture of alpha-beta pruning is becoming clear when I try to answer these questions: 1. Can alpha prune and beta prune be executed at same time for a certain period? No. 2. When is alpha-beta prune invoked and which nodes are affected? Alpha-prune affects alpha nodes, and beta prune affect beta prune. For all other nodes, you still have to obey rule of MinMax game. 3. Is alpha-beta executed in DFS style? Yes. Do I take care of depth issues? No, no need to worry of depth because prune function returns a heuristic value. According to Chinese textbook, by pruning redundant node, you can return parent node function call with current node value. And since pruning only happens for descendant nodes, you don't have to worry about sibling's descendant nodes.
This refinement of algorithm proves one thing: I simply don't get what is written in text. Those English sentences must sound as meaningless as those meaningless articles in the book listed in my English book report. It is written by an American feminist and I hate her historical exaggeration of social problems as a columnist in <New York Times>. I simply don't believe USA has so many serious social problems!
It takes me another five hours to finish this seemingly trivial experimental program---alpha-beta-prune. Once again I should say it is almost impossible to write correct code unless you really understand each word of algorithm. At least it is the case of me. Some notes might be worth memorizing since I learned these after a couple of days! Dull may I be, I am learning.
05/11/05
In order to run job in background in
"alpha.cs.concordia.ca" which is solaris, you need do like
this: try running "./puzzle.exe >& result.txt
&"
the ">&" sends both stdout and
stderr to the file and the last
"&" puts it in the
backgroup. This is a bit strange compared with Linux command "&
yourprogram > outputfile". It seems that solaris is using a
stack for parameter parsing.
I modified a little bit of alpha-beta pruning by hand-coding the tree of assignment. And I add a small star to this little program as an encouragement to me because there has been no star program for almost half year.
For a time, I have an impulse to call "visual studio" as
"virtual stupid". And if I found a way to solve my problem,
I can shout "I have a visual, I have a visual" instead of
"Erika".
08/11/05
Spend almost whole morning to write a logic tester for zebra puzzle. A couple of years ago, when I was naive as a c++ beginning learner, I wrote several version of program to solve this puzzle by DFS. Now it becomes my assignment in AI, however, I am a little reluctant to write a similar version in Scheme. Anyway to implement the propositional logic tester may be more appropriate.
13/11/05
A question that every student who is learning graphic will ask.
I write a simple brute-force searching program for "zebra puzzle". The first edition is finished so fast that I suspect there is no brain activity in my head because I realized there are a little bit too many permutations only after I finished the coding. Then I quickly fixed a serious bug of tester and did a little cheating with given knowledge. I hope this version can generate some results.
14/11/05
Out of context, out of mind. What would you choose to be if you are only given two choices? One is zombie, and the other is fish. Both of them don't need too much sleeping.
15/11/05
Finally I understand how to do "while loop" in scheme. What a shame!
17/11/05
Is it correct to say that real programmer only uses C/C++ and only super programmer may also use Scheme occasionally? For a while I am not sure if I am restarting to write in assembly language because I am doing something similar with Scheme. That is, I am re-implementing some basic I/O operations.
When should I fix the bug of alpha-beta-prune?
21/11/05
During the meeting of yesterday, Alex helped me to solve the mysterious vector reference problem which I regarded as a bug of Gambit implementation of Scheme. I will post it lately today because I need sleep now. The origin of problem is, I believe, from so-called "premature optimization" which shouldn't be done unless you are out of the stack frame of function you are calling to. I learned this phrase from some Chinese forum of C/C++ who worship those masters and authors of C/C++ bibles.
Last Saturday we have a dinner after Mr. Zhu successfully moved out for the sixth time within one year. Mr. Zhang explained to me the puzzle of word "transparent" which I have read for so many times. It is simple. If something is transparent, you cannot see it as if it doesn't exist. Before that I got a mistaken interpretation of myself as "something you can see through it and ???." It doesn't make much sense and I now realized that probably it is due to the reason that in China I seldom saw any high quality glass window in my childhood that "you can see through it without sense of its existence". You see, the so-called common sense is not so "common".
24/11/05
Today I attended the seminar about "Golomb Ruler problem". The only thing I understand is that it is a problem of well-ordered set of a binary relation of a set.
If science is a severe master then computer science must be a cruel master. I don't know why I am always feeling so hungry.
Today I attended a thesis defense about so-called "cascaded refactoring ...". It really sounds to me like foreign language. However, it presents me a fundamental question: what is equal? Because one professor questioned about the consistency during refactoring even though you have defined a one-to-one mapping. Maybe we should also map the dependency relation to its model. I also borrowed the book <automated theorem proof> by Dr. Newborn. Actually I borrowed this book two years ago, now it is time for me to be able to read it. There is a rather difficult way to define "equality" because this is the most basic concept even before "true" and "false".
28/11/05
Shortest-Path maybe the most complicated function I have ever written. And I think it is really a powerful one. However, the problem of "reference" in Scheme may not be able to be solved as I expected before. It is a problem like this.
I like to deal with computers rather than with human because they seem to be like bloody idiots who can never cheat you. However, as they are bloody idiots, you can never cheat them because they only believe in the simple truth, nothing but truth.
In AI class, the professor introduced an idea of machine learning like this: y=f(x) where x is the input and y is the output. It says that whatever you learn can be generalized like an output for an input. I personally disagree with this "seemingly-beautiful" simplification because it seems to me more like "recognition" which is only one of important processes of machine learning. To me the more important and difficult part is "induction" which generates hypothesis and "deduction" which proves and disproves the hypothesis. And between these two processes, "induction" is much more difficult than "deduction" because the processes of generalization and abstraction is far beyond "first-order logic" if my guessing is correct. And if this guess is true, I should have a very good reason to doubt if current programming language is capable to do "induction" because it seems to me all programming languages are just expressions of first-order logics. Should we invent new programming languages? Or is it possible to mimic higher order logic with this first-order logic? The answer maybe yes because almost all current science and technique are based on previous establishment which means we never really invent something completely new, instead we create by morphing current, mutating previous. The question is how?
30/11/05
Decision tree is purely intuitive which I mean as common as me can come up this idea one year ago. The difference is that some people in MIT or Stanford were born many years ago and spent some time to make an algorithms and theory. It is just a way to discover logic. Why do we need logic? Logic is a pattern. Why do we need pattern? Pattern saves us memory? How? Because all our current sciences and techniques in every area is on earth a kind of information compression technique which try to help us to know those things without memorize all states in a scenario or even help us to know something even we haven't encountered before PERSONALLY. You see the math symbols, physics formulas, chemical equations..., but these are all abstraction of clustered information or behaviours which are predictable. Prediction or deterministic is our pursuit.
However, genetic algorithms seems only to be speculations even it guesses with reasons, still I dislike this desperately, hopelessly, last measure for those lazy experimentalists. It may work for those seemingly unconquerable questions and at this moment, nothing harms by guessing.
I must have lost most of my memorizing ability because when I read my diary today I am surprised to see I even tried a naive way to solve 3CNF before by randomizing algorithms. What a surprise! I cleanly forget I have done this about half year ago! However, I do remember yesterday my classmate explained a little about pattern recognition. He told me that they have a large database and by comparing previous pattern in database with sample, you can recognize it. This sounds OK, but do we human recognize things always by memory? No, there are two kinds of recognition: comparing sample with memory in brain, and reconstruct sample by imagination. Or we can call them two stage of one process. Taking alphabetic and numbers on picture, do we compare them with memory or just use our imagination to reconstruct?
01/12/05
I got an idea this morning and I am 99.99...% sure it won't work as usual because it is another wild idea to try to solve CNF. Observe:
(!AvBvC)^(Av!B)^(Av!C)^(AvBvC)^(!Av!B)^(!Av!C)
is not as symmetric as (!Av!B)^(AvB)^(!AvB)^(Av!B)
By the way, I need to keep an edition of "hex game" which allows human vs. computer now.
02/12/05
Everyday I forget what I have thought about yesterday. Therefore everyday I think I have some new idea even they are more or less the same of what I had yesterday. It is very good when you watch an old movie from time to time because you think you are always watching a new movie. That is why I like to collect old movies. I write down my understanding of neural network in case I would think I find something new tomorrow.
The way ahead. When I read my "puzzles" two years ago when I have no idea of difference between proposition and predicate, it does seem naively brave to write an email to professor about these questions. Now I understand a bit that the best way to deal with a learner with puzzle is just let him/it to think/search. Maybe in future I would also design such a machine to let him think/search. Anyway reading my email of before sometimes is fun.
03/12/05
If a job can be done with hand within half hour, would you like to do it by programming with three hours? Probably nobody except me would do such meaningless thing. ID3 is just a simple but effective algorithm in AI and I just cannot help writing a simulating program to test it.
04/12/05
And gradually I realize that knowledge is just compression and intelligence is simply encoding/decoding. Time is universal marker for total ordered set while probability is a measure of binary relationship of a set. This is my view of world.
06/12/05
Philosophy is the biggest heuristic of computer scientists.
07/12/05
Finally I am in the mood to fix the bug in alpha-beta-prune.
16/12/05
...
10/01/06
There is a trend in development of AI such that pure mimic is regarded as a possible way to birth of true intelligence. In my opinion, it is a pure illusion because these activities are far below the conscience of human. For example, a language translation program based on bi-text training using probabilistic algorithms can never understand the meaning of the translated language. (maybe this "never" is a little too absolute, they may use bi-semantic training after the program evolves to proficiency.) (Only one second after I finished above assert, I began to suspect myself. Why not? A understanding of a language is simply a kind of mapping words to semantic representing objects. If we can manage the mapping from English-->French, and why cannot we manage to establish the mapping of French-->Semantic-Object based on already-established English-->Semantic-Object? )
I think my mind is always in such a mess that only after one second I overthrow whatever I have established because during that very second another new idea rushed into my mind. If I stick to my belief about knowledge which is simply a well-defined compression of data, then the method above-mentioned has to automatically find the suitable encryption method for compressing data acquired. I think people call this process as induction. That is, data-->abstraction.
There is another puzzle in my mind about induction and deduction. Which one is more important? Which one comes first? Is this another example of egg-and-chicken? Without the basic deduction, no induction can be made. But can deduction be generated by itself without accumulated induction? Obviously not. (Is it true? Can coincidence create the basic deduction system millions of years ago?)
I wrote to my professor once to say that I wish life is like an automaton for me such that I don't have to pick up choices. Then quite soon I run out of choices. No choice become my only choice. Surely it is the best choice because there is no other choice at all. It is somewhat like the little thing in "combinatorial algorithms" where I happen to notice that it is only true when m=2 that "n mod m = -n mod m". Maybe this is the origin of "reflected binary representation of Grey Code". Or maybe it is the nature of "two's complement representation of binary integer". And I also remember about the so-called "buddy's algorithm" in data structure. All of this comes from "the order of minimal change in set" which is such a beautiful creature by Lord. Maybe recognition of similarity should be defined as finding the minimum distance between two objects. Perhaps Eigenvalue is a hash function of such distance. Who knows? God knows.
16/01/06
I did a trivial test in backtrack of latin square. The only thing I want to make a note is that I am thinking a way to check if a vector is a valid permutation of elements from a set. For example, (1,2,3) is a valid permutation while (1,1,3} is not. But how do you quickly check? I am thinking about to map these n elements to the first n prime numbers so that by checking the product of them I know if there is repetition. Anyway I didn't use this idea in my test as I am too lazy to write it.
20/01/06
Unique factorial representation.
30/01/06
I want to give my first java program one star and I think nobody will object this. The question answered by tutor is more helpful than the program. Originally I want to write some bits and bytes about the surprising things for C++ programmer who tried to learn java for the first time. However, after I write down some pieces in Chinese, I lost the impulse to rewrite them in English. I mean will this be a joke or useful to anybody? Will a programmer in C++ ever have need to "learn" how to program java? What for?
My classmate called me and ask about the mutual exclusive testing. I told her it is very hard to design a testing case since RMI is implemented by TCP which cannot run properly after a large number of calls, say 3000 calls in a loop. The tutor suggests to design some special cases instead of such random testing. This implies of using thread which is something I don't want to write. However, her request did motivate me to write such a test cases. I used a fancy java synchronization object "CyclicBarrier" to let all threads to be barriered before running. The idea is simple. To create equal number of threads to either deposit or withdraw same amount into same account. If the server is not properly synchronized, the balance will not be able to remain the same as before testing.
06/02/06
Aks showed me the artwork of professional CG artists. These are modern artists. Mouse and keyboards are their brushes and palettes. Those masterpieces have the same breath-taking effect as real arts.
MPI deadlock can be detected by OS? Because when I tried the example in book by using two big array as sending parameter to let two nodes to send them to each other and MPI immediately return error.
In Java, the Semaphore is initialized by the parameter "permit" which gives you the first available number of tokens. I made a mistake on that. Another stupid thing is that "main" function always expect a "String argv[]" argument. In MPI, the tag is mandatory for classifying message class. And if you use MPI_Recv, you might get stuck if you are expecting wrong tag. Professor said that the multi-thread in RMI is implemented by creating multi-instance of server object. However, I tried to use a "static" Semaphore and still my synchronization is not working properly. Tutor suspected problem might arising from file operations and suggested using memory for testing. Anyway, I will try to use file lock instead because I am running out of time.
In STL, I am still making low level mistakes. The "Prev" parameter for "set" is a function object and I overload the "bool operator()(const Key_t& x, const Key_t& y)". However, I am making low level logical mistakes. This operator requires a "total order" effect that "==" is achieved by "both comp(x,y) and comp(y,x) are false". Therefore, for two different key, I must return either true or false. But for same key, I must return false in all means.(Tricky or sticky in mind?)
Another low level mistake I am making is actually affected by using java recently. It lowers my IQ greatly. You see, in java, int[] can be treat as a type and you can even define like "int[] array;". In C/C++, I typedef int Array_t[16]; However, if you pass this type into STL as parameter, there might be problem. I am not sure if "set<Array_t>" is intelligent enough to copy contents for you or just copy the pointer. Probably it will only copy "const int*" which is Array_t for you because the "16" here is only used for compiler to check type instead of allocate memory in code generation. Usually I think it will treat "int[]" as "const int*" and ignore the size of array. So, the correct way is to define a struct which holds "int puz[16];" and pass struct as an element type in "set" constuctor, set<Array_struct, Array_Comp>.
13/02/06
Did I re-discovered a well-known vector space?
If somebody claims to have some talent in computer science, then he should try combinatorial algorithms. For me, I dare not touch the topic. However, I do understand this area is the kernel of kernel, heart of heart of all computer science. If discrete mathematics is the foundation of computer science then combinatorial algorithms is body of computer science. I think I am not exaggerating.
14/02/06
I was confused by the so-called lexicographic order in text because it uses a so-called characteristic vector to represent subset where the index of vector starts from right to left, starting from 0 to n-1 and the element denoted by the bit is starting from left to right, starting from 1 to n. So, a subset {2,3,6} from base set {1,2,3,4,5,6,7,8} is denoted in vector as [01100100] and the index referred to each element accordingly is 6,5,2 where you need subtract the element by n which is 8 in this case. In other word, if an element is i (starting from 1) then its index is n-i starting from right to left. What an awkward denotation system! The author must be very comfortable with pseudo code only! And at beginning I was bewildered looking at the sequence of {},{3},{2},{2,3},{1},{1,3},{1,2},{1,2,3}. Is this called lexicographic order? Later I understood that the order is depended on the "characteristic vector". It is quite confusing that later the author indeed uses elements to define lexicographic order when discussing k-element subset. i.e. {1,2,3},{1,2,4},{2,3,4} of 3-set of base set {1,2,3,4}.
About "write through" policy, I have been forgotten its definition again and again. Let's write it down. The policy of "write through" is compared with "write back" which is lazy writing. That is to say, write through always updates memory when it writes to cache while write back only updates when cache is replaced. Hope I wouldn't need to refer to text in future.
In Gray code, when its rank is even number, its order is also even number.
22/02/06
After almost one week struggle, I finished my work on CORBA which I think quite good in view of its thread-safe and robust in deadlock-free. I really learned a lot except there is some regrets in "NamingContext". Apart from using file lock, you have to use mutex for synchronization and socket for TCP communication. Of course the CORBA technique is very complicated.
25/02/06
I really hate reading. Just as one of my classmate mentioned that
I have no patience in reading. However, at a glimpse of "logical
timestamp", I realized that it essentially had the same idea of
theory of relativity of Einstein in which the essence is that
transmission of message costs time even if by light. In world of
digital communication, network transmission is never free of time.
Whatever you observe in one end has a logical simultaneous moment at
other end until your message is able to reach destination. That is to
say a communication connection setup and synchronization of clock
begins. So, it is that people in different coordinate may observe
same event with a different timestamp with respect to different time
coordinate. That is it and no more reading is needed.
26/02/06
I only half-finished this and I want to give it a star.
01/03/06
Yesterday I finally found the bug of my assignment 1 which is not correctly synchronized. It is all due to my misunderstanding of java syntax of "finally" and I doubled the release count of semaphore which invalidate the using of semaphore for synchronization.
03/03/06
In shell, use "exec" and >command& is similar to nice command. ps -A = top. In VC long =int and __int64 is real 64bit integer. In Linux, use long long. In VC, use size_t and use typedef unsigned int size_t; in Linux. When calculating (n,k), be careful integer division divisor in decreasing order.
04/03/06
Yesterday I struggled for whole day for this "revolving door" algorithms. One reason is that I underestimate the difficulty and the major reason is that I planned to port it to MPI. Therefore I used an unusual algorithm---unrank. The small mistake of size of groundset cost me more than two hours debugging which is terrible. You see, I have to pin down the loop among (72,8) which turn out to be overflow of integer. This is exactly why I called myself a idiot because before starting programming I already calculated that even for the largest size of 48, a integer with 64 bit won't overflow. However, I messed up with the length of vector with ground set size of subset. It should be (36,8) which will not overflow. The MPI version is just a demo of my belief: if given a rank function for a computation job, we can divide this sequential job into parts and distribute them among different nodes. This can also be done along with another paradigm which divide the problem context into different parts which basically create a set of problem with smaller size. And it seems to me these are two different divide and conquer. Yesterday I also meet Mr. R who gives me many information of graphic. It is a revolutionary method in my view.
14/03/06
The interesting thing of yesterday is that I spent some time in trying to define a "recursive callback". And finally I realized that this is impossible in current language. For example, I want to define a callback such that it takes an integer parameter and another callback function pointer which also takes an integer parameter and a callback function pointer which also takes an integer as parameter and a callback function pointer which ... Can you do that? Usually a solution to this recursion is a forward declaration, but how can I do it for a callback type?
I hesitate in posting the slightly modified version of minimal-weight because 1. it is not worth another web page for my misunderstanding;2. the result is not available for test7. So, maybe I should overwrite it. Anyway in order to keep it as it is, just give it another page.
A recursion version of permutation generation in order of minimal change.
15/03/06
The big truth I learned these two days.
Sometimes the discussion is more interested than a simple program itself.
16/03/06
For a while I thought there were full of idiots in "sun.com" because many of its tutorials are unbelievably wrong. For example, when I take a first glance at its many repeated "hello-world-like-tutorial" in namingcontext, I thought I must have jumped to conclusion too fast because it is such an obvious mistake in "bind_new_context". And the guy who copy-paste tutorial must have no idea what he is doing because it reveals that he has no sense of tree or whatever data structure. Then I tested and convinced myself that in the countless examples in sun.com, there are many work done by those idiots in this seemingly-impressive company which I considered to be a advertisement-successive-only type. It wasted me nearly one hour to test his ignorance.
23/03/06
In area of comb. algo., there are only two types of players: genius or ingenious ones. As for Knuth, I really don't know which type of player he belongs to. I remember a trendy saying in China which I heard a few years ago when I just began to study computer science. It is said that programming is just coding and it is the lowest type of work in computer science. However, if those who holds such kind of belief would spend some time reading the notes of Knuth, surely they may change their view. Basically there are different types of programming in real life just like cooking in real life. A house wife goes to supermarket and shops a half-finished dinner. She follows exactly the step in a recipe written down from a popular TV-cuisine program. So, such a Saturday-evening-dinner is cooked in a way similar to those described as programming by following well-written algorithms. What a boring assignment.
In order to prove to myself later that I am alive these days, I posted these boring assignments.
And this max clique problem.
27/03/06
Long long ago, SD told me that I was a normal man only when I was working. Now I feel I am only living like a normal man when I am programming. By exaggerating a little bit, I should say I am programming. So, I am.
Sometimes I am proud that I have more than half energy than those who has less half of my ages. However, when I read Knuth's notes and program, I feel depressed because I am sure I don't have more than twice energy than Knuth who probably only has less than twice ages than I have.
"Blade Runner" probably is one of the best science fiction film in the world. I think everyone will be deeply impressed by its breath-taking image and imagination. Do you know the same director also directed "Alien" which is another mile stone in science fiction film. Many people believe that "Zergling" from "StarCraft" is inspired by this film.
05/04/06
In textbook, it says that Gray Code problem is actually a Hamilton-Circle problem which is quite difficult to understand. I try to explain to myself like this: If it is a minimal-change-order or in Gray Code, then the xor of two consecutive subsets will have order of one. In other words, there is only one element different between two consecutive subsets. Let's take an example of base-set of three. There are only three subsets with order of one: A=001,B=010,C=100. Now let's find all possible pairs whose xor is one of them.
X={000+001, 010+011,100+101,110+111} has xor of A
Y={000+010,001+011,100+110,101+111} has xor of B
Z={000+100,001+101,010+110,011+111} has xor of C
Observe: 1) If consider each subset as an vertex in a graph and edges are all vertices between "+" in above, finding a minimal change order is just finding a Hamilton circle among these vertices. 2) Although we can start from any vertex in Hamilton circle, however it is easy to see starting from 000 and ending at 000 is the easiest way because it is our convention that a code starts from empty set or zero. 3) If starting from 000, we must four different Hamilton circle. Let me enumerate one of them. (000,001,101,111,011,010,110,100,000). This one is not Gray Code, but it has an extra property which I consider better than Gray Code. Just observe that the result of xor of consecutive two subsets is A,C,B,C,A,C,B which is a little bit more balanced than Gray Code which is A,B,A,C,A,B,A.
06/04/06
13/04/06
14/04/06
Do you know dancinglink? If you want to understand it, read knuth's paper.
16/04/06
19/04/06
Let me write down what I understand about virutal synchrony after visiting professor.
After I write down what I think, I have new ideas about virtual synchrony and it is more convincing.
11/05/06
Do you know how to make birds fly? Do you know how to make flowers blossom? Now I know! After more than half year I know why my OpenGL library doesn't work and now it works. From now on, students from comp471 would be happy to do no coding at all in assignment! This might be a bad news for professors. I just change one number in one line! To set near plane to be 0.5 instead of 0.0. That is it and I don't know why!
12/05/06
I think I figure out the setup of wmpi2. First of all, you must reboot after updating licence key and this is known for anybody except me. Secondly, WMPI2 is stupid because it needs you to setup identical executable file in all nodes. I mean why WMPI itself copy this executable to all nodes like lan-mpi which is easy to do!!! The third thing is that wmpi cannot pass firewall and I have to turn it off. The fourth thing is that run it from "mpiexec" and setup wmpi.clusterconf file and "program name".pg2 file properly. There are corresponding environment variable to setup the path of these files. And the executable copy job can be done by a batch file with shared file folders in each nodes.
13/05/06
Talking with RG over phone for one hour and really getting a lot of help. First, I don't need that glew32.dll because the extension of OpenGL I am querying is not located in it. The extension implementation is within hardware driver, i.e. display driver. The "glew" only helps easing querying job and this is not absolutely necessary as long as I have those extensions declared within "glext.h". (I should say this header file is continuously updating by manufacturers.) Second, RG tells some idea of his code and it saves me a lot of time to understand them. I find out it is always difficult to understand other people's code, including my own code. View frustum culling is implemented already and occlusion culling is not. (I need to read papers about this.) Third is that the "glQueryXXX" is no good according to RG. What else? A lot of bits and bytes which may seem trivial but they may puzzle you for quite long time. For example, his color of texture mapping is set in those shading language file and that is why I cannot find them in code. Those shading language is written in ARB assembly language. Scanner generates separate "texture file" for color of points. And he suggests me to dump all collected result into disk for the time being. And first of all, try to get dirty with my hands of coding otherwise I may never realize there are countless problems awaiting ahead. It proves my "road map" report is a good idea to write down what I understand to get confirmation from professor. Then what am I waiting for?
18/05/06
I don't know how many students have ever given a thought of why OpenGL chooses to use column array as transformation matrix instead of usual row array in C/C++. After a few seconds of pondering, I think I got it. It maybe due to the possibility of hardware. For example, some powerful graphic cards have special "vector register" which is similar to those "super scalar" architecture of super computers. By using column array, it will be very natural for the vector register to load operand in consecutive memory access.
|c[0] c[4] c[8] c[12] | |v[0]
|
|c[1] c[5] c[9] c[13] | |v[1]
|
|c[2] c[6] c[10] c[14] | x |v[2] |
|c[3]
c[7] c[11] c[15] | |v[3] |
is equivalent to [(c[0],c[1],c[2],c[3])* v[0], (c[4],c[5],c[6],c[7])*v[1], ...]
Please note that c[0],c[1],c[2],c[3] is just a vector in consecutive memory address, and it is usually the requirement for vector-computer to access one vector of data in one access. Otherwise the performance gained by vector register operation will be defeated by multiply memory access.
19/05/06
Finally I think RG is correct with the matrix multiplication and I am wrong. This is a typical lesson which I have learned from time to time. That is, don't jump to conclusion too quickly! Please note, no matter what kind of matrix representation OpenGL is using, still we must follow the basic way of matrix multiplication or linear transformation rule. That is, transformation matrix is at LHS and vertex or coordinate vector is at RHS. Then each row vector multiplies the "transposed" vector to get a new vector. (Isn't this too trivial? However, I just get confused to which one should be transposed, the matrix or the vector.) Even though OpenGL matrix is using column-major matrix for optimization of vector-register operation, still we need to follow this basic rule. That is to say, suppose we have a C-array matrix C=(v0,v1,v2,v3) in row based 16 float array such that v0=(C[0], C[1],C[2],c[3]), v1=(C[4],C[5],C[6],C[7]), v2=(C[8],C[9],C[10],C[11]),v3=(C[12],C[13],C[14],C[15]). Also assume the coordinate vector of vertex is v. Then what OpenGL is doing is to use the transposed matrix of C (without actually doing the transpose, it is logic! And this is where I get confused.) to do the multiplication. Let's say T=transpose(C) = (u0,u1,u2,u3) where u0=(C[0], C[4],C[8],C[12]), u1=(C[1],C[5],C[9],C[13]), u2=(C[2],C[6],C[10],C[14]), u3=(C[3],C[7],C[11],C[15]).
Then, the actually result of transformation is equivalent to
T*v = u0*v+u1*v+u2*v+u3*v
And please note that the total 16 multiplication + 12 addition operation becomes 4 vector multiplication + 3 vector addition. In those super computer or special CPU like some powerful GPU, vector operation takes roughly the same time as common operation in common CPU. So, this is what we learned about parallel in comp326.
Finally just keep in mind, if you are calculating youself matrix transformation in "geometry" sense, and you want to call "glLoadMatrix" to overwrite OpenGL matrix, you have to transpose it first.
Actually I learned this fact in comp471 and I even have used in my library. Still I get confused when I read RG's code. Sigh...
24/05/06
Made a small tutorial slides for synchronization. This actually makes previous one easier to be understood. And there is some crazy tips for C++ programmer who uses java for the first time.
27/05/06
I should say VBO is really a tricky part and the tutorial code I read in web is not trustworthy. Let's always concentrate on official OpenGL doc's only!
31/05/06
I think I really feel happy by teaching or helping others with whatever I have learned.
20/07/06
To prove I am still alive, you can check those simple quick tips on project. Compared with this project, my current research project is much more touch in the sense that you never know if it works or not. So, the most frequent word I am using is "clueless".
01/08/06
One of a good thing as a marker is that you can learn from what you marked. Even though I dislike java language very much, I have to admit that some flexible syntax is a bit intriguing. For example, I now know that you can create a thread either by inheriting from class Thread or by extending Runnable interface. Of course this is trivial in OOP. However, the surprise is that some student declare their "so-called main class" as an implementation of Runnable. At first glance, I thought it was impossible because "main" function is the only entrance point of program and the "main" function will automatically become the "main" thread. Then how can you make it a multi-threaded? After a couple of minutes rendering, it becomes so simple. You see, the "main" function is just a static method which has nothing to do with the "enclosing" class. i.e. It happens to reside there. Within the static "main" function, you can "new" an object of your "main" class. As for the "starting" thread issue, it depends whether you want your class to be inherited from "Thread" or not. If your class is "extended" from "Thread", you can call the "start" method at its constructor or after your "new". Or you can simply "implements" the "Runnable" interface and pass your class object as parameter for "new Thread(myClass, "start Thread");"
Actually everything is so trivial and the only difficulty comes from my C-syntax because it never occurs to me that I can "start" a thread within itself which is impossible conceptually. You see, if you create a thread with "CREATE_SUSPENDED", then you can only "ResumeThread" from other thread. However, in java treating thread as a class, the part of constructor will always be executed even though the thread hasn't been ready to run. And it is there we can call "this.start()".
09/08/06
I must have made a fool of myself! The compression algorithm used for fax or T4 is using one byte for color and the other byte for length. And I take for granted to combine the two bytes as one byte. That is to use first four bits as color and the rest four bits for length. Do you know what happens? The compression rate is extremely low! You see, the idea is to use more bits to represent a longer length. And using one byte to represent a few different color is a little bit inefficient. However, the most important thing is to use more bits for a bigger number to represent longer length!
14/08/06
10% of luck, 15% of skill, 20% of concentrated power, 5% of pleasure, 50% of pain, 100% reason to remember the name.
That is the lyric of "PLU" for "starcraft" and it also suits for programming.
30/08/06
They called it "HowEasy" and I didn't make it right.
07/09/06
To be blocking or not to be blocking, this is a problem and it is a problem of deadlock or not. I spent almost a whole day to change communication mode to be non-blocking. However, there is some limits because it is like the "logic time" in distributed system. Some events must go before some other events. Therefore some asynchronized communication have to be synchronized at some stages. It seems that I am practicing the "distributed system design" in my real life.
30/10/06
How many lines of code do I make every month recently? I don't know. Maybe less than before and definitely they are all unpublished here. First, I am doing the big project of parallel computation which is not suitable to be posted here. And it is keeping updating. Secondly when you write one big program instead of a series of small program, the situation is different. That is to say, the difficulty of coding lines is different. Surely I am learning. Today I learned how to wakeup a remote computer which is in hibernating or sleeping. It is called "remote-wakeup" or "wake on LAN". I guess this program may be the simplest program I have ever posted here, but the hardware configuration makes it worth posting for memorandums.
08/11/06
When I looked at it, I didn't see it; When it was removed, I felt its existence; When it was brought in, I realized its significance; Finally I carve its figure in my heart and then I get a visual; This is called recognition.
From time to time, I was bothered by a simple question. Which way is easier for us to notify? To add a small tree into a forest or to remove a small tree from a forest? If this is considered as a meaningless question, then how about this one? To add a tree in a grassland where no tree is there at all or to remove the single tree from grassland so there is no tree in grassland. Which way is easier to notice? Probably same and most people would say that.
If the above questions are all nonsense, then how about this question. In a structured system, say an AVL tree which means a balanced binary search tree. Does it cost same when you either add one element into the tree or remove one element from the tree? Not exactly same because it depends how we implement the structure of AVL tree. In some data structure, maybe removing is easier. So, back the above question, it depends. It depends on how you construct your knowledge system to represent what you see and how you implement a "fast-recognition" algorithm.
Of course the above comments are all garbage which I don't believe myself. I finished the "regular-sampling-quick-sorting" of MPI.
14/11/06
Yesterday Dr. Hopcroft came to make a lecture and here is some inspiration from his lecture. Or precisely it is simply what I remembered.
24/12/06
I guess the origin of AI is from vision because it is the most intuitive method to observe and recognize pattern. Maybe all high-level concepts need to be first transferred into visual image before comparison and recognition are done.
4/01/07
Convex Hull is a typical algorithm that the definition gives out the clue of construction itself! See, the definition says that any edge of the two vertices in the convex polygon will leave all other vertices in its right-hand-side. And the algorithm takes advantage of this. After the lecture I spent about one and half hour to finish a simple implementation of this algorithm. When I finished, I noticed the name of algorithm is "Graham's Scan-type". I am happy because it proves I am still capable of coding after so many months. Even though I am doing the MPI programming which is far more hard than these kind of single-machine programming.
14/01/07
99% of Chinese ancient philosophy is purely mysticism which is practically useless except for fortune-telling. Their dirty trick is to use as many as ambiguous terms, words, concepts, expressions etc. to express something so ambiguous such that they can always explain themselves if you are foolish enough to give the truth before asking for prediction. Most defenders of so-called Chinese traditions feel so blindly proud for this kind of useless philosophy and claim it to be unique. Let me quote President Bush to comment on this: Shame on you and a fool cannot be fooled again. (These are so popular in "youtube" and surely you will find it by searching "Bush") However, there is something I also feel like to note down and it is one of my favorite. For those who consider themselves as guru of programming and experts of AI, this might be interesting. "Expressions themselves cannot be expressed; Names themselves cannot be named." This is the very first sentence from <DaoDeJing> which is one of most famous ancient Chinese philosophy. And maybe it touches the most profound and most basic topics of language and origin of intelligence.
01/02/07
It is said that I think, so I live. In order to prove I am alive, I write a simple algorithm to generate simple polygon from a set of points because I only think when I do coding. Thus I live when I am programming. The trivial algorithm is inspired by assignment from comp6711.
09/02/07
Professor C's lecture must be interesting. However, it is really a headache for me to understand those proofs' of Erdos. I guess I never have talents for math because I simply have difficulty understanding all those stuff related with continuity. Even for discrete math I learn them more from intuition. Anyway I enjoyed myself by reading those stories about mathematicians'. Women may be natural enemy of math. So, math may be natural enemy of women because enemy is a kind of relation of symmetric. And it must be very rare for a woman mathematician married with a man mathematician who coincided with related theorem of same problem for which Erdos called it "Happy End Theorem". And what's more interesting is that Canadian mathematicians were said to be Maoist in 70's because they talked about "Reactionary Math" and "Revolutionary Math" in the sense how easy they can be understood by layman. Like the "Friendship Theorem" which is expressed such as in a group of persons each of them has exactly one common friend and there exists a politician who is friends of everybody. And these are all math I can understand. :)
Another old story is about number which I sometimes find very unfamiliar after long time rendering about. What exactly is number? Maybe from perspective of computer, they are infinite statically predefined variable names such that can be dynamically used as helper of counting or memorization. I mean we simply take for granted that we know how to calculate difference between numbers which I think is purely depended on encoding. For example, binary or hexadecimal would be a completely different story of calculating the difference of two numbers compared with decimals. When we discuss about computation complexity, we naturally ignore the computation complexity difference between different number encodings. This maybe the only thing I learned from "design and analysis of algorithm" in which we describe the size of problem in its encoding length. Therefore the different number encoding will play an important role in size of problem. Say a number is represented in binary format must be much bigger than decimal and then the calculation of time complexity of algorithm maybe much different. And perhaps if we human can find an as easy way to store and calculate vector as natural numbers then our math will be completely different.
10/02/07
In the era of Cold War, almost all extremists like to label themselves as communists. Nowadays they like to expose themselves as terrorists.
The "hibernate" program is really an irony for myself. The original intension of it is simply to schedule a timed shutdown of my computer to force myself sleep early instead of watching the internet TV till very late in night. However, coding of such a simple program simply took away my sleep of the night because it is first time for me to handle the windows privilege accessing rights which is a bit messy. It seems to me that Linux tends to store these rights in data while windows tends to associate these rights with operations. Both approaches have its limit and disadvantages. The password file is a dilemma for Linux because it belongs to everybody and cannot be accessed by everybody. Operations or methods can be distinguished with privileged or not. However, the methods maybe the most dynamic part in software engineering. Thus maintaining is practically difficult.
Today I think my mind is becoming clear about the depth-buffer algorithm after I was pushed to give a clear definition of input and output. Indeed, let's note down this: "Well defined, well designed".
Suddenly I see the essence of "sweeping line" algorithm. It is used to do a kind of sorting job when the searched and the searching objects share a same "well-order" property. The status structure is a currently "working window". The event queue is as its name indicated, the trigger of our handling operation. The size of event queue decides the size of problem. The size of status structure decides how efficient our algorithm is. The event handler is the key of algorithm.
02/03/07
What is incomputable question? You setup a communication protocol with your receiver such that she will reply Yes when the message is correct, No when the message is incorrect and Don't Know when she doesn't know how to answer. However, what if she doesn't reply? The problem is exactly the example of incomputable problem.
The word "voronoi diagram" sounds to me like paranoid which is a total chaos. For the whole lecture I was almost in lost.
09/03/07
There is a nice design of WOW, the parental control, which can constraint the playing time. And I made my mind to restrict my playing time to only two hours per day and at the same time trying my best to forget the password of parental control. If worst case happens, I can send the password to my friend and ask him to change the password to prevent myself from modifying the schedule. It is the only way of starting my project.
12/03/07
It is said that in this world only two kinds of people are unable to read properly. One kind is blind people. The other one is those who refuse to read or believe what they read. I am the second kind. The "ply" header reads clearly it is big-endian, but I just refused to believe it. Sick and silly.
18/03/07
Zealot yells: I long for combat!
It is such an exciting moment to face challenge! When the going gets tough, the tough gets going!
30/03/07
Coding work requires you to have cold blood because your brain needs to be cooled down. Coding work requires you to have hot blood because your heart needs to be warmed up. So, you become a cold-blooded, warm-hearted, passionate, emotionless hybrid.
When I was twinkling with DCEL, I got an "Internal Compiler Error (C1001)" which didn't make me slightest panic at all because I know there must be somebody else running into it long time ago. Let me hold it on for an hour before checking Google.
Do you like ICE? I don't, because it is really an annoying thing. What is ICE? It is "Internal Compiler Error". They said it is compiler bugs and some guys give a simple example to indicate such kind of errors. It is like a kind of pseudo C++ syntax. For example, declare a class within a function and pass the parameter of function to member function of nested class. Is it valid. No, but compiler doesn't give an error when do syntax parsing or P2 or 2nd pass. And when compiler needs to generate code and finds out the error. LOL, and my case is a little bit similar. I declare a static data member which is a type of struct such that it has another static data member which also has static data member which is struct. Am I crazy? Or do I make compiler crazy? Maybe both. Anyway I must finish DCEL today! This morning I have wasted a lot of time to fix my last bug of "out of core rendering" which I really hope is the last bug. I re-calculate the size of leaf octree node such that it won't waste too much file storage. Also I fixed the single "break" bug which "inflates" data file by many times.
31/03/07
I must be a fool! Such a simple algorithm of triangulation takes me half day of tracing!!! What a simple rule! You just count the internal convex hull vertices and also count the internal convex hull vertices. Is that too difficult for me to figure out? Why do I use a combined counter for both internal and external convex hull? You know, you cannot cross the limit, don't you? I was doomed to be starving to death. What a shame!!! Now I am completely behind schedule!!! Can I finish rule of "TrianGO" tonight? I must finish it! Otherwise I will have no time for assignment 3 and quiz on Tuesday! But...
04/04/07
TrianGO go go go!
06/04/07
Excuse 1: I am a weathered hunter who has been hunting vicious beasts in jungle for years and suddenly I am ordered to kill an innocent bunny which I stop killing since my childhood. My mind is a blank for any skills I learned long time ago. Is it a good excuse? The hunting skill should be no different from killing a tiger or killing a rabbit. Yeah... I have no excuse.
Excuse 2: It is like a fever. It makes me sleepless a whole night. I hardly eat. I cannot concentrate my mind. My heart beats 30% faster than usual for day and night. My mind is totally a blank. Does that mean you cannot work under pressure. Yeah... a kind of...No, that is not true. I have no excuse.
Excuse 3: From bottom of my heart, I know it is not mine. I am not ready. It is not ready. Better to let this finish early before my ego inflates to uncontrolled extent. So, beat it. I don't need it. Does that sound like sour grape? Yeah...I know. I have no excuse.
However, my heart beat reduces to only 10% faster than usual and I feel much better after that. Last night I dreamed about the life in CAIEC again. That old business man from Pakistan comes again. My life becomes again the hopeless struggle for those meaningless coins. Before this dream, the other dream is that I found big bugs just before my demo and tried to solved desperately. Compared with the hopeless past, I feel much released. After all I now live with honor and shame.
The data file may not be correct. Let me check from scratch.
I feel much better now. This is a simple example how to make Linux device driver accessible by multiple user.
Dude, call of honour! Go to lab!
There is a time when a victory created a victim; There is a time when a defeat constructed a hero! So, let me finish a rendering engine tomorrow before we plunge myself into debugging.
09/04/07
Dude! Don't underestimate your potentials! You are invincible! Here goes my Out-Of-Core-Rendering project.
Here is the forgotten assignment of GPU programming. It is good that I now recall and post it. Otherwise it might be buried in my computer forever. I don't like this GPU programming cause I think it is a kind of easy if you know the algorithm and I lost interest so soon that I almost forget to keep a copy.
Because of this out-of-core-rendering project, I dig out a long-forgotten project. The pilot control system is what I am borrow and modified in outOfCore rendering. To download full source and data report, you need to go to here.
10/04/07
Finally the demo finished with some success and I am happy that my work is recognized. Dr.M is absolutely right about the "error-checking" idea. I should have this sense before. Let's make a note here. By linearly checking all leaf nodes and compare with the dataset collected by my "flooding algorithm" we will know the error rate. I think the "neighbourhood recursion" algorithm fails to advance when there is some gap between near nodes and far node. How to solve it? Maybe try parent nodes which has less chances of "holes" or "gaps" in space. Another thing is "GlobalMemoryStatusEx" API. Let me use this at beginning and "exhausts" user's memory for my performance! hahahaha...
17/04/07
My most respected Chinese writer has a famous saying about literature. It is like this. Either you play with literature or you are played by literature. Replacing literature with program suits perfectly with my idea.
18/04/07
Comrade Stalin in <Red Alert> says: Killing one person is killing; Killing one million of people is just a number. Yes, indeed in USA killing a person becomes a news. And in China it is just a number. It is said at the same day exact same number of coal miners were killed in an accident. That number happens to be 33.
25/04/07
Passion must be a kind of chemical energy which drives you forward even though you are starved and exhausted. And I am starved and exhausted with IJG library. Using pure C library which aimed to be portable in all platform, various compilers, multiple purpose is a nightmare. I think the only possible error of linking I got maybe comes from the type of function pointer which acts as a parameter in those functions declared in library. Otherwise I will surrender by giving it up after almost three days futile tracing. I am really hungry now, with hands shaking when typing. Sometimes I really suspect computer science is the most cruel master whom you have ever served because it makes you feel like an idiot all the time.
01/05/07
01/05/07
"Without brain the body cannot live." Morphius told Neo. <The Matrix>
07/05/07
09/05/07
The price of loyalty must be much, much bigger than the price of freedom.
15/06/07
Totally clueless! To be better to deal with insane world, should you be more insane or more sane? MPI sometimes is a puzzle.
If someone considers about finding brain teaser, this is not a good one because it will only cost you ten minutes of brain exercise provided you know what algorithms is instead of how algorithms spells because as a computer science student you should know what complexity of an algorithm like this can be.
28/06/07
I long for combat! It took me 12 hours in lab to finish debugging of my Linux-version! It finally works!
Again the Great Mokhov figures out the riddle even faster than I can imagine!
30/06/07
The marvelous comment from <Yes, Prime Minister> about British press by Prime Minister.
07/07/07
I seldom understand man page and this time I find more convenient to write the simple "find" for myself. Then I find the strange thing that command line parameter cannot have "*" as wild char.
10/07/07
Actually the "simple find" has at least two big bug in linux version. Do you find it?
02/08/07
A day of chaos! First I found another problem of windows API--GetTempFileName. The programmer must be very naive to believe that any program at most only uses 65535 temp files cause he simply uses a short int to increment without checking it reaches 0xFFFF. Linux version of mkstemp is much better because it uses 6 wild char to make unique file name and opens with "exl" to make sure no one open it before. Say 26^6 is much reasonable compared with 65535. (However, indeed my requirement is weird. Just imagine how many programmer will use temp file to pass parameter in order to save memory usage in stack? Can I blame MS windows?) Although I highly suspect it might help by running more processes than number of nodes, still I have to give it a try and various weird things come out. HP MPI allocates ranks not in usual "modulo" policy. i.e. 14 process for 7nodes, node0 got rank0 and 1. And in other MPI, node0 gets rank 0 and 7. So, it is like this: mpirun -srun -n 14 ./myprogram.exe. But be noted that you must make sure "master" runs on display node. But again, program crashes after a few seconds which never happens before. Clueless!!!
11/08/07
To compile with __stdcall, use /GZ in compiler option. To compile with __cdecl, use /Gd. And they are before function name after return type. OK, finally I give up the efforts to make it a real dll because it is said the file pointer cannot be shared between dll and caller. It is reasonable because "file library" is simply a library and the FILE struct is definitely a local struct unless you use file HANDLE which is OS-wise. So, let me keep a handy version here.
21/08/07
Nobody claims he/she likes my tool!
06/09/07
Suddenly I can see ...
10/09/07
So, this is second edition of jpeg editor. The only big difference is that I am using Intel Jpeg Library which allow you to decompress jpg to memory. Here is the Intel Jpeg library.
26/09/07
It is a joke, but a good joke. This is the a performance comparison between conditional wait and naive mutex. The result is really stunning!
27/09/07
It is a simulation of a scenario of my project. And I think it is not a trivial problem. This is the only one I feel a bit satisfied because the previous jpeg tool is simply a modification of ijg which can be considered a bit trivial. Sometimes I even feel shameful to mention it at all. I happen to see an old project of my predecessor in his computer which also uses the code from "game tutorial" and the code is very similar to what I am doing. So, it is a bit trivial which means common people would do the common thing. That is what I mean trivial.
16/10/07
Here is my project that I have been working for more than one year!
18/10/07
HPMPI does support multiple threads who are making MPI calls. You only need to link with "thread-compliant library" by "-libmtmpi". And in SVA_conf, there is a specific node lists of "compute" nodes which are in LSF. So, I can use it if I want and if my "compute" nodes don't require X-window. But the problem is "sva_remote" may require x-window to be setup??(Let me try and see!)
<MPI: The Complete Reference> is really a great book and I begin to understand it after one year when I borrowed it from library a second time. It not only addresses users but also discusses with implementers in many interesting subjects. i.e. Generally speaking, the sending buffer will not be altered by MPI, but it is not recommended to be accessed before completion of sending. The author gives an argument that maybe implementation involves DMA moving data from buffer and the reading may not be coherent with cache. Even I am not fully aware of the exact meaning, still I am convinced with the point. MPI_Waitany is an interesting thing and I will use it in my code because I am stupid to think that it returns an array of indexes. The "short-protocol" and "long-protocol" in non-blocking communication is really like a "two-phase-transaction" and "three-phase-transaction". And it aims to solve the possible "starvation problem" when large message blocks for progress of other message sending.
"P-completeness" is interesting. "Bandersnatch": A fleet, furious, fuming, fabulous creature, of dangerous propensities, immune to bribery and too fast to flee from. Lewis Carroll, Through the Looking Glass, 1871.
19/10/07
No strategy is the best strategy!
21/10/07
Even as stupid as Forest Gump can figure out he is stupid. You see, you don't have to be smart to realize your algorithm is shabby. Isn't this important for an Intelligent Automation system to have such a simple algorithm to figure out if it is a good or bad algorithm no matter however complicity that one might be. It should be essential for a generic evolutionary program.
Mama told Forest that he must make the best of what God gives him. And his life is like a box of chocolate that he never knows what is inside the box. Now the question is like this. Is it an optimization problem or decision problem to make the best of what God gives him. When we say decision problem you only have to answer yes or no to a statement like whether Forest can become a good soldier or not, or whether Forest can become CEO of Apple corporation. However, when we say optimization problem you not only have to answer the yes or no for that statement, but you have to give a detailed way how to fulfill that claim like what exactly Forest needs to do to become CEO of Bubb Shrimp Corporation. So, this is really a difficult question. Suppose it is a simple decision problem, then Forest might have to try various career in his whole life to figure out what he can make the best of what God gives him. Common people simply don't have that damn luck to try out so many roles of life, war hero, ping pong player, shrimp boat captain, owner of Apple corporation etc. I tried once in my life and it takes more than ten years to find only one negative answer. How many should I try?
22/10/07
This winter there seems to be two good news for Canada. One is the loonie is soaring like a loony. For the first time, I think, one Canadian dollar is even more valuable than one US dollar. Is it good? It depends. Another thing is that it seems this winter will turn out to be a warm one. It is very warm today and it is almost end of October. Isn't good? It depends. As if it is a consequence of global warming, then it may not be a good news for many people on this planet. Actually what is good news? It is said no news is a good news. CNN news host is a kind of aggressive. Religion issue is used as a political signature, at least for potential voting behaviour. And there is one interesting thing they mentioned about Islamic. It is said its expansion is, quote "by reproduction"; Whilst Christen is expanding not only by reproduction but also by conversion. What an interesting pattern of religion! If you were born in a Islamic family there is huge chance you will become an Islamist. Most people argue that every religion should be treated equally, just like people from different region or racial origin. But is it true? People are born unequally and we want to ignore their difference intentionally.
23/10/07
When Hugh Grant asks Julia Roberts that if she always say "No" to everything, she hesitates and say, "No".
27/10/07
Do you know or do you not know?
25/11/07
I always consider NP-complete problem as a kind of dirty trick of encoding. They play with concept of problem size over the time complexity of algorithm. Just imagine that if you consider Travel-Salesman-Problem has a problem size of O(N!) then why do you still consider we haven't found a faster algorithm. You are presented with N! choices and without scrutinizing all of them can you be sure enough to see the best solution? I still remember clearly the counter-example given by professor to illustrate the trick of encoding when considering the time-complexity of algorithm. Say you are given a decimal number and you have an algorithm for finding all prime number smaller than it. How would you calculate the time-complexity of your algorithm? based on size of encoding of decimal number or based on size of encoding of binary number? Turing machine can only do a linear probing and modern computer can access memory randomly. Do these factors change the time complexity of an algorithm? Suppose you are using super-scalar machine to do matrix calculation, do you consider you are advancing in algorithm efficiency? What kind of advantage do we borrow from our familiar natural number system? Say by establishing an isomorphic mapping between actual problem with a consecutive sequence of natural number, we actually are able do a binary search instead of linear probing. However, the procedure of establishment of this mapping is not always successful. It requires the problem to be of equivalence class which has reflexive, symmetric and transitive property. What if our natural naive concept of number system also includes logarithms or trigonometrics?
29/11/07
I heard some "magic" algorithm from my friends and they are the killer of one's confidence. So, don't read them if you want to be happy.
07/12/07
If I have time I will add a small improvement such that the octree leaf nodes will be assigned to the render nodes to which they were assigned in previous frame. This will reduce the file-mapping overhead when viewer moves its view point.
11/12/07
The seminar is brain-shocking! Professor claims that there is a misconception regarding TSP: the problem size is not the source of its difficulty! What an amazing statement! But I have to admit he is right and I once again being wrong. Even he himself admits that he doesn't know what makes the TSP so difficult. Maybe it is the nature of all problems.
10/01/08
To bypass nfs setup in linux, you need to login as single. It is "kernel" plus single. To setup printer in Linux, you go to printing, new "printhost-um" which is a "samber" service by adding printer name as "shared". Then choose "postscript".
15/01/08
The thing scaring me very much is that I try to break the dependency to achieve parallel computation by redundant computation in parallel. However, what if the nature of dependency is such that whenever you "intentionally" create redundant work to try to break the dependency you might suffer more than you gain. Or in other words, dependency is the impossible leap you want to make. You pay the price to buy something and the price is only a result after you get what you want. But you don't just pretend you pay your money and expect what you want "automatically" comes to your hand, isn't it? This is something I feel frightful. Parallel computation seems to me is more and more like a perfect way of wasting our "precious" computation resources. People in 60-70's worries about memory usage so much that they might want to share same constant value between code and data. Whatever algorithms which makes extensive usage of memory might be regarded as dumb one. Nowadays nobody really cares about memory cause it will someday become as cheap as disk. Maybe only when cluster nodes are becoming common equipment of every family then some of our parallel computation idea may look like feasible.
