Breadth-First-Search & Depth-First-Search

1. Breadth-First-Search
BFS(G){
for (each vertex u in V[G] - {s}) {
color[u] = WHITE;
d[u] = ∞;
Pi[u] = NULL;
}
color[s] = GRAY;
d[s] = 0;
Pi[s] = NULL;
ENQUEUE(Q, s);

While (!Q.empty()){
u = DEQUEUE(Q);
for (each vertex v in adj[u]){
color[v] = GRAY;
Pi[v] = u;
d[v] = d[u] + 1;
ENQUEUE(Q, v);
}
color[u] = BLACK;
}
}

2. Depth-First-Search
DFS(G){
for (each vertex u in V[G]){
color[u] = WHITE;
Pi[u] = NULL;
}
time = 0;
for (each vertex u in V[G]){
if (color[u] == WHITE)
DFS-VISIT(u);
}
}

DFS-VISIT(u){
color[u] = GRAY;
time ++;
d[u] = time;
for (each vertex v in adj[u]){
if (color[v] == WHITE){
Pi[v] = u;
DFS-VISIT(v);
}
}
time++;
f[u] = time;
color[u] = BLACK;
}

B-Tree

1. Find key k in Tree T:
B-TREE-SEARCH(x, k){
int i = 1;
while (i <= n[x] && k > keyi[x] )
i++;
if (i <= n[x] && k == keyi[x]) return (x, i); else{ if (leaf[x])
return NIL;
else
return (ci[x], k);
}
}

2. Insert a node in Tree T;
3. Delete a node in Tree T;

Binary Search Tree

1. Search an element in Tree T:
1)Recursive Method:
TREE-SEARCH(root[T], k){
x = root[T];
if (x == NIL || key[x] == k)
return x;
else{
if (k < key[x])
return TREE-SEARCH(left[x], k);
else
return TREE-SEARCH(right[x], k);
}
}
2)Iterative Method:
ITERATIVE-TREE-SEARCH(root[T], k){
x = root[T];
while (x != NIL && key[x] != k){
if (k < key[x])
x = left[x];
else
x = right[x];
}
return x;
}

2. Find the minimal element in Tree T:
TREE-MINIMUM(root[T]){
x = root[T];
while ( left[x] != NIL)
x = left[x];
return x;
}

3. Find the maximal element in Tree T:
TREE-MAXIMAL(root[T]){
x = root[T];
while (right[x] != NIL)
x = right[x];
return x;
}

4. Find the successor of element x in Tree T:
TREE-SUCCESSOR(x){
if (right[x] != NIL)
return TREE-MINMIAL(right[x]);
else{
y = p[x];
while (y != NIL && x = right[y]){
x = y;
y = p[y];
}
return y;
}
}

Team radio transmissions

zz from bbc

In the interest of transparency, full transcripts of the Team radio comms from the Chinese GP have now been made available. Selected quotes.

BMW: "Robert, can you get a close look at that Toyota diffuser?"
Kubica: "How about I bring some of it back with me?"

Kimi: "How many Hamiltons are there? That's the fourth one that's gone past me!"

Williams: "Kazuki. Be careful, the track's really wet now."
Nakajima: "It's okay, I'm not using the track!"

BMW: "Robert, there seems to be a problem with your nose."
Kubica: "Why does everyone have to talk about my nose?"

Ferrari: "Well, as we're not running KERS, at least we won't have any electrical problems!"
Massa: "&$%!!*$!"

McLaren: "Lewis, we're not sure about that last overtaking manoeuvre ... let Kimi past ... let Kimi past!"
Hamilton: "I already have ... several times!"

QUICK-SORT

Input: A(p, r)

QUICK-SORT(A, p, r){
if (p < r){
q = PARTITION(A, p, r);
QUICK-SORT(A, p, q-1);
QUICK-SORT(A, q+1, r);
}
}

Subroutine:
PARTITION(A, p, r){
i = p -1;
x = A[r];
for (j = p; j <= r-1; j++){
if (A[j] <= x){
i++;
exchange(A[i], A[j]);
}
}
exchange(A[i+1], A[r]);
return i+1;
}

Features:
1. T(n) = O(nlgn) ~ O(n2)
2. Sort in place

HEAP-SORT

Input: A[]

Main Algorithm:
HEAP-SORt(A)
{
BUILD-MAX-HEAP(A);
for (int i = length[A]; i >=1; i--)
{
exchange(A[1], A[i]);
heap-size[A]--;
MAX-HEAPIFY(A, 1);
}
}

Subroutines:
BUILD-MAX-HEAP(A)
{
heap-size[A] = length[A];
for (int i = [heap-size[A]/2]; i >= 0; i--)
MAX-HEAPIFY(A, i);
}

MAX-HEAPIFY(A, i)
{
l = 2i;
r = 2i +1;
if (l <= heap-size[A] && A[l] > A[i])
largest = l;
else
largest = i;
if (r <= heap-size[A] && A[r] > A[largest])
largest = r;
if (largest != r)
{
exchange(A[i], A[largest]);
MAX-HEAPIFY(A, largest);
}
}

Bubble Sort

Input: A[]

for (i = 1; i <= length[A]; i++)
    {
         for (j = length[A]; j >=i; j--)
           {
              if (A[j] < A[j-1])
                   Exchange (A[j], A[j -1]);
           }
     }

Features:
1. Stable

Merge Sort

Input: A[], p, r, where p < r.

Merge-Sort(A, p, r)
{
if ( p < r )
{
q = [(p + r)/2];
Merge-Sort(A, p, q);
Merge-Sort(A, q, r);
Merge(A, p, q, r);
}
}

Megre(A, p, q, r)
{
n1 = q - p + 1;
n2 = r - q;
for (i = 0; i <= n1; i++)
L[i] = A [p+i];
for (j = 0; j <= n2; j++)
R[j] = A[q+j];
L[n1 +1] = Sentinel;
R[n2 +1] = Sentinel;
i = j = 0;
for (k = p; k <= r; k++)
{
if (L[i] <= R[j])
{
A[k] = L[i];
i++;
}
else
{
A[k] = R[j];
j++;
}
}
}

Features:
1. loop invariant
2. stable
3. T(n) = O(nlgn)

Insertion Sort

Input: A[1..N], length[A]

for (j=2; j <= length[A]; j++)
{
key = A[j];
i = j-1;
while (A[i] > key && i > 0)
{
A[i+1] = A[i];
i--;
}
A[i+1] = key;
}

Features:
1. sort in place;
2. loop invariant;
3. stable sort;

Long time no update

I went home on 17th last month. Today, on 16th this month, I'm sitting in chair, working. One-month-time is quite easy to elapse before we catch its evanescent character.

This year will be a busy one, especially under current economic situation all over the world. In coming July, I will start to hunt for a job. There're merely four months left for me to get ready. These 120 days may be even shorter than spring vacation passed yet.

This period is paramount due to three reasons. The first is that job pressure requires me to acquire various knowledge on algorithms, cooperating, experiences in projects, to name just a few. The second stress comes from dissertation, including paper and master dissertation, which determine the Niubility extent of universities who give me offers. The third unsaid factor may influence my life time -- Delia. I have been being with her only for three days -- at my sister's wedding. Do you call this kind of encounter the predestined relationship? Maybe. She is now getting a driver's license at her hometown, but after that her parents will help her seek a job in Beijing, where I stay. I have known little about her habits, interests, temper, wants and likes, not even the color she favors. After she comes to my place, I will make more contacts with her and seriously consider whether asking her to be my GF or not.

From this week, from today, from current second, minute, hour, I am forced to work hard for my dreams, no matter how lazy I was. It seems a long time since I determined to do meaningful things. I have lost my passion, and now I am going to get it back.

Bless My Sister

Bad news, though the symptom is relatively minor.

The old saying always works: Body is the most important factor.

All of us should live a  healthy lifestyle which contributes more and more to our physical bodies as we are walking towards the aged steadily.

* * * *   * * * *

I should focus on my researches and paper, instead of checking msgs all the time. It is a bad habit for my success, and I know it exactly. Snior students in my lab told me that they felt it is extremely difficult to find an ideal job within a short time. They are now quite regretful of their wasting time before. Shouldn't I learn some lessons from their experiences? From now on, I will not run im softwares during work time. I swear.

Happy Single Day~

Next month will be a critical period for me. By the end of this weekend, I will submit all online applications and mail all supplemental materials, if time allows.

Just now, my collegue said that we would go on a biz travel to a province which hasn't been affirmed. The task is to deploy a report project. I would be happy to go if only I were in my undergraduate. Nevertheless, I am extremly boring to go now.

I cannot change this situation. The mere thing I can do now is to accept it and try to focus on my own researches.

It's a war!

It definitely is.

SOP, CV, References, Transcripts, to name just a few, are all demanding, pushing things.

I surely like to study in first-class graduate schools, as anyone else does, but it seems quite difficult.

Thanks for everyone's help. I am really appreciated. I will not make you disappointed.

Topic 5

5. A company has announced that it wishes to build a large factory near your community. Discuss the advantages and disadvantages of this new influence on your community. Do you support or oppose the factory? Explain your position.

I SUPPORT THE FACTORY PLAN

Building a large factory will bring about both benefits and harmful impacts on my community. In my opinion, advantages of a new factory outweigh disadvantages. Therefore, I definitely support the new factory plan in my community.

As a threshold matter, there will be numerous benefits of constructing a new factory in my community. For instance, the new factory will surely offers considerable opportunities of jobs -- such as cleaners, workers, managers, and so forth, which may ease the pressure of job market. A lot of folks may find their ideal positions in this factory. Besides, tax revenue from the factory will also supplement local government's income. As a result, statesmen would have more money to budget their financial plans. For instance, education system of our community will be the right beneficiary of the factory, because tax revenue from the factory can be spent in ameliorating facilities of community colleges and providing positions with high salary which may enslave quantity of outstanding professors to work in local colleges. Furthermore, the factory will certainly arouse other businesses appear in my community -- for example, hospitals, restaurants, plazas, and so forth, which will boom economy of my community.

Nevertheless, certain disadvantages of constructing a new factory do exist. Especially, some of them may be extremely devastating. Take potential pollution. As a common sense, a factory releases large quantities of wastes, such as polluted water, poisonous gases, and etc, as by-products while it produces merchandises. These wastes may induce towards severe disasters in my community. Polluted water may cause intestinal diseases and stomach cancer; poisonous gases will lead to respiratory diseases which makes quality of life decrease. Moreover, the factory generates loud noises as well, which is especially intolerable during night. Residents' sleep may be disturbed and they do not have enough energy to face daylight work.

When it comes to make a decision about whether to support or oppose the factory, I would like to support the factory plan. There are several reasons to name. Firstly, the factory will bring a excellent opportunity to economy of our community. Local folks will benefit from the plan from the long run time. Secondly, since technology today has developed to a quite high level, I deeply believe that political leaders and managers of the factory will find right ways to solve potential problems caused by the factory. For instance, they may adopt new waste disposing methods to reduce harmful effects of wasted water to the lowest point. Gases will also be carefully cleaned before releasing into the air. Thus, advantages far outweigh disadvantages of the factory.

In summary, there are both benefits and harmful effects that the factory will bring about. In my view, the factory will contribute a lot to our community in future time. Then, it the final analysis, I support the factory plan.

Smoking, Integrated Writing, Test 2, Kaplan

In the article, the author tries to demonstrate that smoking isn't as harmful as supposed to be in three aspects. However, the speaker of the lecture opposes this opinion and contrasts each point stated in the passages.

In the first place, the author of the article writes that smoking ban doesn't work and limit the freedom of people who smoke, which is debated by the speaker. According to the speaker, smoker could still smoke as they want. Those persons who smoke can still smoke at home or other personal places. Moreover, in the speaker's opinion, smoking bans help smokers quit smoking, because they reduce places where smoking takes place. Furthermore, the speaker says smoking ban can help those addicted out of smoking.

In the second place, the author of the article holds that several stores and businesses have to close due to decreasing number of patronage of people who smoke. Nevertheless, the speaker definitely opposes this point. In effect, the speaker points out that though a few bars close down, new ones open and survive. Moreover, business can be prosperous by attracting nonsmokers.

Finally, the speaker of the lecture doubts the mortality rate of smoking as well. In the article, it is said that secondhand smoke doesn't cause severe problems because it takes longer than a lifetime to develop cancer. However, the speaker disagrees with this point of view and says that lung cancer isn't the only disease caused by smoking. Further more, the speaker also expresses uncertainty on tax contributed by smokers. The speaker believes that smokers do not pay significant tax, which is directly contrary to what is stated in the article.

Topic 35

35. Do you agree or disagree with the following statement? Attending a live performance (for example, a play, concert, or sporting event) is more enjoyable than watching the same event on television. Use specific reasons and examples to support your opinion.

ATTENDING A LIVE PERFORMANCE GIVES MORE THAN TELEVISION

In my opinion, I strongly agree with the statement that attending live performances is quite more enjoyable and exciting than watching the same events on television or listening through radio. There are numerous advantages of going to a live performance, while watching television cannot offer us things equal to those special benefits.

As a threshold matter, attending a live performance gives me a peculiar feeling which I cannot get when I watch television. For instance, I attended the opening ceremony of the 29th Olympic Games which was held last month. When I was sitting in the national stadium -- Bird's Nest, where the ceremony was celebrated, the whole vehement atmosphere created by numerous people screaming together completely shocked me. At that time, I sang together with other people and kept swaying national flag in my hand. I even didn't feel a little tired at all. Furthermore, when the torch was lit at the last moment, I felt that hearts of all athletes from every country are linked together. However, when I reviewed the opening ceremony next day at home by watching television, that feelings didn't come into my mind.

Secondly, when going to a live performance, spectators will not be restricted by perspectives of cameras, which is a main shortcoming of watching television at home. For instance, take the most recent show in theater. The singer was chanting at the center of the circle and person around me were singing together with the star. This scenario was made up of a whole cubic surrounding, which could only be experienced by attending it. I could see and hear anything I want to. For instance, I know how excited and ardent of persons in my neighbor seats. Nevertheless, if watching live concert at home or other personal places, these feelings would surely be over us.

Thirdly, attending to live performance could offer good opportunities to contact with our stars within a short distance. For instance, if I could go to Michael Jackson's live performance, I might be extremely fortunate to be chosen as a lucky person and have the chance to communicate with Jackson face to face, which is impossible if I watch the same live rendering at home. As a result, I would be better able to understand what kind of person my idol really is. Moreover, only taking a photo with Jackson would make me sleepless over several days. Nevertheless, watching television far from the venue where concerts are held merely makes me jealous towards the person who would be me.

In summary, there are a myriad of benefits of going to a live performance, such as vehement feeling, opportunities of getting a signature of popular stars, and so forth. To the contrary, watching television or hearing on radio could not offer such beautiful things.

Core Curricula, Integrated Writing, Test 1, Kaplan

In the article, the author explains what core curricula are and then demonstrates that both universities and students gain a lot from this system. However, the speaker of the lecture casts doubt on the author's opinion and cites several reasons to support his standpoint.

In the first place, according to the speaker, some courses of core curricula are too easy for students to learn. Moreover, some other courses are totally irrelevant to students' majors. The speaker also mentions that some obligatory courses of core curricula are just outside students' primary interests. As a result, students couldn't learn much from these courses. All these three points are contrary to what are expressed in the article which writes that core curricula give students a broader perspective on life.

In the second place, the speaker of the lecture says that a few curricula in core ones are too big for students to study as well. In the speaker's opinion, those courses' size is too large and students couldn't do well in these classes. This is in conflict with what is said in the article. The speaker also mentions that guidance should give students some advices on how to get well in core curricula. Furthermore, the speaker holds that core curricula ought to offer creative ways to satisfy students' need. According to the speaker, guidance should also provide opportunities of internship to help students with their careers.

However, if we could solve all the problems mentioned above, students surely are the very beneficiaries. First, universities would increase enrollment of high-quality students and thus ameliorate public profile. Secondly, students would learn the most paramount courses in core curricula and don't have to learn too easy, or rigid curricula they don't like. As a result, students would have careers of promising prospect.

Topic 45

45. Some people prefer to get up early in the morning and start the day's work. Others prefer to get up later in the day and work until late at night. Which do you prefer? Use specific reasons and examples to support your choice.

GETTING UP EARLY HELPS A LOT

Personally, I am prone to get up early in the morning and begin my work. In my opinion, going to bed early in the night and getting up early in the morning will certainly benefit me in numerous ways. Generally speaking, I will be in good health and filled with energy under this pattern of life.

In the first place, going to bed early in the night and getting up early in the morning guarantees that I have a good sleep and don't feel tired after getting up. This pattern of sleep can provide me with enough rest of high quality, which is crucial for daylight work. In my experiences, I would feel difficult to get asleep and extremely dreary when I get up next morning, if I go to bed late at night on the first day. For instance, once a friend of mine invited me to take part in his birthday party. Many people played happily and didn't go home until two o'clock in the morning. However, when I got back to my bed, I couldn't stop thinking what took place just now and was vehement. At that day, I was asleep at about five o'clock in the morning and woke up late in the afternoon, which was a terrible feeling.

In the second place, going to bed too late at night over a long period definitely harm my health. According to medical lectures held in my community, in the span from 10 to 12 p.m. everyday, our bodies begin to tone and secret certain hormones to keep bodies clean. After that, our bodies are tired and need deep sleep, which aims to recover after a day's hard work. However, if we are still awake and tacking thorny problems, our bodies will receive harmful effects -- for example, imbalanced secretion, insomnia and high blood pressure. Of course, each of these phenomena deserves our careful attention.

Thirdly, if I get up early in the morning, I can do a lot of meaningful things which would help me with health, and mental status. For instance, I could do morning exercises, such as running, pushups, and so forth, on condition that I get up at 7 o'clock everyday. These activities help me improve status of my body and mentality. After morning exercises, I always feel quite relaxed and free of anything constricted, therefore I can face the rest time of the day. Needless to say, my working efficiency surely is much higher than it of getting up late in the morning without any physical exercise.

In summary, going to bed early at night can maintain balance of my body's circulation, which is beneficial and positive for my physical health; getting up early in the morning offers me enough time to do exercises, which tones my body and makes me relaxed and energetic. Then, in the final analysis, I would definitely choose to this healthy routine of life.

Origin of Life, Integrated Writing, Test 6, Barron

In the article, the author primarily talks about the experiment which aimed to discover the origin of life on Earth. However, the speaker casts doubt on the correctness of the experiment and cites several scientists' critiques towards that experiment done several years ago.

In the first place, the speaker of the lecture confirms that the experiment was grand at that time. Nevertheless, the speaker also points out that the electrical problem with the experiment. The author of the article writes that, in laboratory environment, flasks are charged with electricity continuously. But, according to the speaker, though there were frequent electrical storms in early atmosphere of Earth, there was no continuous electricity, which is certainly a flaw of that experiment.

In the second place, in the article, the author mentions that oxygen is reduced in experiment. According to the speaker, this is another flaw as well. The speaker of the lecture says that the premise that there was not considerable oxygen in atmosphere of early Earth cannot be proved anyway. Perhaps that hypothesis is totally wrong, which would undermine the correctness of the experiment.

Finally, the speaker also mentions meteorites as evidence to disprove the conclusion of the experiment in the article. The speaker says that scientists have found that there is amino acid in meteorites, which would demonstrate that this kind of acid could survive under severe conditions. This conclusion means, according to what the speaker says, that the acid was on early Earth which contained asteroids. Moreover, the speaker also points out that we just don't know or unsure about the truth that how life in Earth originated from simple organs into large buildings. There are more work before we make clear.

Messed Up

iBT
Personally, I would have to say that ETS deserves thousands of people's aversion and antipathy.
I got up early to take test of iBT held in BFSU last Saturday, which turned out to be a farce.

There were about three or four students when Maggie and I arrived at library where certifications were supposed to check. We finished privacy provision and then deposited our sacks. Before we were about to stand in a line, Maggie received a call from a friend in America, which aimed to tell her jj of that day in North America. Of course, we were excited, in respect that we "had" known the independent part of speaking section, integrated part and independent part of writing section, which made us more despondent later.

We started to line up in the entrance of library at about 9:20.

We were still lined up, agitatedly, and didn't inch a little towards the door of library at 10:00.

We came to realize that something was definitely wrong. Indeed it was. Invigilators told us technicians couldn't access servers in America. We had to wait.

Then time lapsed second by second. It was over 12:00.

All of students there appeared to be worn out. In effect, we were out of status and would definitely render a bad performance if servers were available right then. We just didn't know how long we had to wait. Several persons kept making and receiving calls.

At 13:00, teachers told us that we were not allowed to check in after one o'clock and we had to choose one option from reexamination or refund. Thanks god. The farce eventually ended.

Flu
The positive thing of the farce is the fact that I have been in flu for two weeks. However, I have more time to recover from disease and may have a good score in speaking section. Recently, it is obvious that I am in sub healthy status. I decide to exercise after test. After all, health should be put in the first place.

American Teleplay
Now I am in season 03 of Friends. No subtitle. Flamboyant? Huh... No, I can only interpret approximate 60 percent of the content, which doesn't prevent me from understanding what is ongoing between Rachel and Ross, Chandler and Joey, Monica and Phoebe. Lesbian wife, Italian guys, Julie, Janice ... and you surely know what I'm talking about.

The Book Thief
Well, I'm regretful that I fail to keep trace of Leisel and Rudy -- the idiot. I have finished 70 percent of that book and will finish the rest parts in the coming vacation of National Day. Whether to go home or not to go depends on which day I take iBT.