Old Days

我的征尘是星辰大海。。。
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.

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?
　

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.

The "code contest" for me is always a defeat of self-confidence. I cannot even finish the very simple first problem within three hours.

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.

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.

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.

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?

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 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!

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.

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?

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?

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?

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.

And I post my FTPServer. But please don't copy all of them, otherwise we will all get zero marks.

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.

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.

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.

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.

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;

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++.

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.

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:

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?

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.

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.

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.

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.

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:

(If matrix has not the same dimension, we cannot expect it to represent all transmissions.)

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.

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.

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.

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.

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.

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!

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.

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.

Miss Sunny supplied an interesting algorithm to minimize DFA. If I have time, I would do it. However, I am struggling with my comp444.

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.

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.

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.

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.