Regular Entry Dec 1 2013

This week's material is rather interesting due to the fact that it concerns a little bit on the hardware part of computer science. First, We have learned MapReduce, which is the practically the essence of the different sorting algorithms we have learned so far. As I have said in the assigned topics, the essence of O(n*logn) algorithms lies in the fact that they employ a recursive structure. This allows the partition of the domain of a particular function and then simultaneously perform computation to different partitions. The net result will be assembled together and the final result will be returned.

What I have described above is practically a mini version of MapReduce. MapReduce is a frame work for computing parallelizable problems across a large number of CPUs. The entire frame work consist of two steps. The Map step uses the master node and takes in the input data. The input problem is then split into sub problems and assigned to different sub nodes. The worker node may perform another separation and so on. The second step is the reducing step. This step consists of the collection of answers from different sub nodes and the combination of these answers to these outputs which will eventually yield the answer to the problem it originally intended to solve. The general theme of this framework is clearly very important in computer science due to the fact that a large portion of this course is practically recursion. And recursion is essentially the same concept on a smaller scale. The beauty of this concept is that it allows distributed simple problems to be solved while they are altogether too complicated to solve. As we can see from the sorting algorithms, a method that splits the original input and recursively apply the function are usually more efficient.

Another thing which we have learned is memorization. This is completely a new concept to me since it is similar to caching. The whole idea is that it may improve all the recursive functions I have programed so far by making the programs not repeating the calculations which have been performed already. This can further save time in real time since no calculations will be repeated, which makes a recursive function even more efficient.