conclusion

This shall be the last blog for cmpt376w, and it is also the conclusion for my blog.

In the first one, I wish I would write 3 blogs per week. However, the result is one blog for average except recently I wrote one blog per day to catch up.

Having a habit to write regularly is not easy. For my new resolution, I hope I could keep this blog, and post at least one blog per week. It is reasonable and I really do not want to give up.

other disadvantages of ray tracing

Except the slow speed of ray tracing algorithm, other drawbacks are in some case it could not show the “realistic image”

one of it is the dull-looking (non-reflective) objects. Because they do not reflect, the reflected ray (the perfect reflection of eye to object) part is 0. And, in real world, its real color is contributed by lights directly(Phong Shading) and other part of environment (ray tracing does not computer this part).

Another example is that mirror. Ray tracing could see what is in mirror perfectly. However, if a light ray irradiates a mirror, the light ray should perfect reflection to some place. When ray tracing to treat this place, it will not count this part of lights.

In conclusion, ray tracing is still a simplified algorithm to simulate the “real world”. The drawbacks above could be handled by another algorithm for rendering - “radiosity”. However, radiosity usually is more expensive than ray tracing.

Exterminator – C/C++ exterminator

At yesterday's cmpt383 class, Ted talked about a (new?) tool for debugging: exterminator. It could correct (or degrade) some bugs automatically. When a program run on exterminator environment and trigger a bug, exterminator could detect and correct it.

First kind of bugs is “overflow”. when exterminator detect this kind of bug, it will allocated more space to array. Second kind of bugs is “released pointers”. Exterminator will cancel former release and , then, release the pointer after the use of “released” pointer.

It is kind of magic because this two type of bugs are most common and cause security issues. If we can avoid them by using exterminator technology, it will save much time for C/C++ programmers.

How to choose class to take

It is time to enroll classes, and many friends are asking which classes are easy to get a high score? Maybe it is not a right way to choose class.

This semester, after I enrolled cmpt361 – computer graphics, one friend persuaded me to drop it because cmpt361 is very difficult: too many contents and labs cost too much time. When I was work on the labs, I had to say that my friend was right. However, after finishing my labs, I felt this course is interesting.

It is a kind of dilemma, we want to get high score, and we also want to learn more knowledge. On the other hand, if a course cost too much time, there will be less time left for other courses. I really do not know what to say if other people ask my opinion if cmpt361 is a good class to take.

More on ray tracing

When we play a PC game, we usually feel that the scenes are not real because now real-time picture system can not simulate nature environment very well. Ray tracing is a simply way to make picture “real”, but it need more calculations and now it can not generate real-time images on commodity computers.

However, there are some experiment system try to use ray tracing in real time system. Intel did a lot of works on it. Intel demonstrate “Quake Wars: Ray Traced” on a 16core cpu system with larrabee hardware, a separate video card system Intel planned. Intel also has a “Wolfenstein ray traced” project shows fantabulous real time image powered by 4 servers. (http://www.youtube.com/watch?v=XVZDH15TRro)

It looks we might play a PC game with ray tracing algorithms within 2 – 3 years. I hope.

My ray tracing project

When I finished about 80% of this project, I have to submit it. It is not because the time is due, but I have to do other more important things.

First, I have to finish the cmpt376's writing, assignment 3 rough version. I almost did not leave enough time for it; Second, tomorrow there is a cmpt454 quiz, which is 20% score for that course. The decision of just finishing 80% in ray tracing project will leave me enough time for writing and preparation for database quiz.

The decision is difficult since I already have a beautiful ray tracing framework, and add more functions are just time-consuming thing.

Sometimes people have to give up, right?

car problem

My car had problem about 10 days ago. When turning sharply, its steering wheel might be stuck. Obviously, it is not safe for driving. I drove it to dealer for repairing immediately. I thought fixing might need 2-3 days, and I did not ask for rental car from dealer. Next day, dealer called me and said they found the problem: one part were damaged and need to replace. They didn't have this part in stock and they are not sure when the part would be there. I still thought it is OK for me without car for a week. But last Thursday, They were still waiting. I had to ask they for a rental car. I got rental car yesterday, and still do not know when my car would be fixed.

My lesson is when repairing a car, ask a rental car immediately.

More advantages of ray-tracing

Ray tracing algorithms have some advantages and disadvantages. Because ray tracing follow the path of THIS ray, it is some kind of independent to other rays. this features is controversial. The biggest drawback of this is that it is very expensive (costs too much time), and its benefit is that it makes ray tracing algorithms very easy to be parallelized. This is very important for modern computers framework since nowadays main stream CPUs have over 4 cores.

I hope I could see PC game using ray tracing algorithms in near furture.

Ray tracing

Recently, I'm working on the ray tracing assignment of cmpt361. Ray tracing is a very interesting algorithms for rendering; it does not need 3D transformation. Instead, it uses each ray from a camera ( or a eye ) to calculate each pixel. Another feature is that it recursively calculates specular reflection, and then get more realistic picture.

One big drawback of ray tracing algorithms is that it can not be used in real-time render because it need too much time. Otherwise, quality of computer games will be much better.

Busy time is coming

This Friday, I need to hand in a draft writing. Next Monday, a project, building a ray tracing system, is due. Also, there is a 20% test of database II in next Tuesday. Finally, final is coming next next week. Moreover, the final of cmpt361 is Dec 8, and cmpt454 is Dec 9. Oh, man, give me a break.

The different between vector and arrayList in Java

In Java, vector and arrayList are very easy to be confused. Both arrayList and vector are dynamic array. what are they different?
1.vector is synchronized. Therefore, it is safe to use in multithread programs. On the other hand,arrayList is not synchronized, it need to call a function to synchronize. Therefore, it is faster than vector.
2.Vector is build on old framework, it does not need to indicate a type of this vector, for example:
Vector v = new Vector();
arrayList, on the other hand, need to indicate the type of this array.
ArrayList myArr = new ArrayList();

Vector and arrayList in C# is very similar to Java. However,vector in C++ is more like arrayList, not vector in Java.

“Inception” and programming

I heard a very interesting point of view about the movie “Inception”, and it says that “Inception” is a movie about computer programming. We could see those concepts: recursion, concurrency, exception handle, share memory, thread (process), system fail-over, global variables, local variables, etc..

In “Inception”, dreams are a child processes (or function? Recursion?). Therefore, characters could go down next layer, a dream in another dream. If a child process did not return properly (Cobb in beginning), system may interact to help him to end the dream (fail-over). Or, child process may be stack in limbo forever (zombie in OS).

A person in another person's dream looks like a process communicates with another, having shared memory (the same scene).

And, also, we could get different interpretations from “Inception”. In my point of view, its director must be a programmer. Is Christopher Nolan a programmer?

QQ vs 360

QQ is the most popular IM in China, and it has been installed in almost every computers in China . 360 is a free anti-virus software having only Chinese Version.

Recently, 360 claimed QQ scan user's personal data, and send back to QQ's server. Then, 360 published a software “QQ guard” to prevent scan user's privacy data from QQ.

Now, QQ announce that QQ will not run on computers if 360 installed.

In my point of view, QQ is using its monopoly in IM market to eliminate a potential market adversary. On other word, if Microsoft said Windows will not operate if Chrome is installed, the result is that MS will be fined by court, and enforce MS to cancel its decision.

What is the final result of QQ vs 360? I'm waiting...

My computer was stoned

After I installed an application downloaded from Internet, I felt my computer had some virus symptoms. I had AVG free version in my laptop, and it gave some alerts. SFU wireless network also alert me that my laptop was stoned and cut my lapton's connection to SFU network. Then, I installed McAfee and full scaned my laptop. But SFU network still warned me that having virus on my laptop.

Finally, I uninstalled McAfee, and try MS essential. This free antivirus software really give me a surprise, it found a Trojan:WinNT/Bubnix.gen!A on my system\driver\, and show "Trojan:WinNT/Bubnix.gen!A is a generic detection for a kernel-mode driver installed by other malware that hides its presence on an affected computer by blocking registry and file access to itself."

It looks MS still has backdoors that other antivirus companies do not know. Therefore, after the virus in system, McAfee can not find it, but MS can.

A thought about Russell Williams

I have to see the news about Russell Williams shocked everybody, especially recently released crimal details by court. CTV’s news called it shocking news every time. I really don’t know how to critizice him, or I should call it.

First, he is a senior office in Canadian Aire Force, commandor of an air base; second, the released details about his crimal are unbelievable crude, how cans a human being did those things?

Although, generally, death penalty may be not humane, I really can not find any reason to not treat this kind of criminal with it.

Binary search

In cmpt454 quiz, a problem is related to binary search. But I though it is binary search tree. Now, I need clarify these two topics.

Binary search is an “algorithm” for search an item in a sorted array.
Binary search tree is a data structure, or called ordered search tree. It left subtree is smaller than the node, and right subtree is bigger than the node. When we traverse it in in-order, its elements are retrieved by order.

The similar point is that for search an item, both running time are in O(log(n)).

Database II and modern CPU architechture

I take Database II (cmpt454) this semester, and feel the way to speed up database is very similar to modern CPU.

One of the most important issues for implementing database is that the read/write speed of disk is too slow comparing to memory read/write. Therefore, algorithms, such as B+ tree,hash index and clustered record, are solutions for disk’s tardiness.

Now we have 3 layers of cpu cache, and each layer is faster than layer, and, also, CPU caches are more speedy than memory . When we use a listed list, the efficiency is not good because it does not take the advantage of CPU cache. On the other hand, if we use an array to hold data, it should be better than listed list because array is stored in sequential block, and CPU could pre-fetch elements of array to cache.

In my point of view, algorithms for implementing database will be more popular in general software development.

Constant and pointers

Recently, I reviewed some basic C++ knowledge. one is qualifier CONSTANT, and another one is POINTER.

CONSTANT is a useful qualifier in team project because it will reduce the mistakes when using another’s methods, but I seldom used it in my project. I should use CONSTANT more often because it makes reuse them easier.

Using “constant” and “pointer” together make it more complicated.

1.Constant variable
2.A pointer points to a constant varaible
3.A constant pointer points to variable.
4.A constant pointer points to a contant variable

Confused? Follow is an example:

const double pi = 3.14159;
const double *const pi_ptr = π

In this case, pi_ptr is a const pointer and points to a const object.

Reading SGI STL source code

Reading source code is fun and very useful for programmer. SGI STL is the original STL implementation, and also it is considered to be a paradigm for C++ templateprogramming. By comparison with Linux source code, SGI STL is very small, and sould be very easy to understand.

However, when I start to do it, I really have not ideal where to start. Fortunately, I got a book that explains how to read its code. After a few hourse reading the book, I know some basic of SGI STL, and found its entry.

Although there are some comments on SGI source code, I thought it’s still a challenge for a computing science student if didn’t have help.

New ideas

In cmpt431, distributed system, professor asked us to discuss “new ideas” about “cloud computing”. Although I thought very hard, there were no NEW ideas appear. Also, others classmates’ ” new ideas” were not actually new.

Recently, when I review the hash table, I really though I got a new idea about collision. Traditionally, we use a linked list, ordered or unordered, to store collided elements. In worst case, its perfermance would degrade to O(n), it is very bad. What I thought is uses a balanced tree, such as red-black tree to store collided elements. In worst case, its perfermance would still keep in O(log(n)).

After I read “hast table” in wikipedia, I found that it is not a NEW idea. In wiki, there is detailed discussion on its advantage and disadvantage. However, I thought it might be a good sign because it means I’m on the right track of thinking about data structure.

RTFSC

[ Read The F***ing Source Code – allegedly from a very famous IT guy ]

When I wanted to find out how the “map”, which is an associative container, is implemented in C++ STL, things were not going well. I got some information from Internet that map is implemented by red-black tree, but none of wikipedia, Microsoft or www.cplusplus.com confirms it. They just said that “map” is a sorted associative array.

After I did some research on this topic, I confirmed that all informations are right. C++ STL did not define the implementation of “map”. Therefore, C++ compilers and C++ libraries could have their own implementations. In general, all balanced trees are satisified to implement “map”.

After going through the SGI STL source code (http://www.sgi.com/tech/stl/), one thing is sure: “map” in SGI STL is implemented by redblack tree.

Confusing of “map” (data structure)

According to wikipedia, a map is an associative array, and “an associative array (also associative container, map, mapping, dictionary, finite map, and in query-processing an index or index file) is an abstract data type composed of a collection of unique keys and a collection of values, where each key is associated with one value (or set of values).” we could simply see a map as a colletion of <key, value > pairs. This definition does not define the detail of its implementation.

However, in C++ STL, map is a sorted associative array, and is implemented by red-black tree. Therefore, more precisely, in C++, a map is a container that implemented by red-black tree, and nodes are pairs.

In java, a map is an interface that “maps keys to values.” The abstractmap class implemented map interface. Under the “abstractmap” class, there are hashmap and treemap. Obviously, a hashmap is implemented by hash table, and a treemap is implemented by red-black tree.

Therefore, when we talk about “map”, we have to know the context. However, saying “a hash table” is a map is always not right.

Hash table (1)

Half year ago, I got a co-op opportunity in SAP. Once our group, 6 software developers, had lunch together, and the lead talk about a new grad he interviewed that morning, and said that girl did not answer well a question about hash table. Then, he asked me the same question: what is a hash table? I said: simply speaking, hash table is an array, plus listed list. Supprisely, our lead said: no, hash table is a map, and suggest me to get a newer data structure text book about.

After that, I did search new text books and online resource for hash table. And the result is still a little bit confusing. When developers use hash talbe containers, specally in perl, it really looks like a map, which contains [key, value] pairs. However, how is it implemented in low level? It’s still an array + linked list + hash function.

Hash table is not a standard contain in C++ STL now, but gcc and VC++ have already implemented it, and it will be in next version of STL standard (C++ TR1).

To make things more complicated, now people call it different name in different language. In STL, it has been call hash_map or unordered_map. In C#, Microsoft calls it “dicationary” container.

For most software developers, maybe they really don’t need to know the low-level different between hash table and map. But, if developers readlly want to make their program elegant and efficient, know more about the implementation is much helpful.

Resolution of this semester

It is a restart for my blog. I planed to write blog routinely for recording some interesting things and improving my writing long time ago, but can not insist on it.

Now, it is an assignment for CMPT376W, and I hope that I will be accustomed to write blog regularly.

Except classes I take this semester, I will spend more time on find a job because this term is my final term in SFU, and I alread applied for graduation.

Therefore, my blog will focus on data structure and algorithm, the core part to find a job in computing science field. Plus, I hope I could write 3 blogs per week.