Sorting and Efficiency

There are many kinds of sorting algorithm. And what I want to talk here is about there efficiency and why it has such efficiency.

Firstly, among those sorting algorithms, there are two kind of sort. One is comparison sort and another is non-comparison sort. Comparison sort means that we have to compare the item we get with another item, then we can decide where to put this item in the list. However, as for efficiency aspect, the time complexity of the most efficient comparison sort must bigger than O(n). Because we have to access to every element in the list otherwise we can no compare it with others. So if we want to compare we have to get the item's value and then the time complexity must be bigger than O(n). Non-comparison sort can have O(n) time complexity but it will demand more space to store the data.

The most intuitive algorithms of sorting might be the insertion sort. Given 1 0 4 2 as the input list, the way we think is just the process of insertion sort. We first put 0 to the front of 1 and then we find 2 is smaller than 4 but bigger than 1 then we put 2 between these two numbers. We compare the number and we put it in the right place. The time complexity of insertion sort is O(n^2). Because we have to compare the item we get in our hand with each item in front of the current item.
Selection sort is quiet simple as well. It select the first smallest item in the list and put it on the first place in the list,(or the last one, depends on the list is descending or ascending). And then the second smallest one should be put on the second place in the list. The time complexity of this algorithm is O(n^2) as well, for we have to compare the item we got with all other items.
Then here we come the QuickSort and MergeSort. These two has really good sorting algorithms. The average runtimes are all O(nlogn). Both of them are recursive.
Why they have O(nlogn) time complexity?
We can solve this buy drawing a tree.
Take MergeSort for an example
n                ------ need n step to merge
n/2 n/2          ------ each item need n/2 to merge, sum is 2*n/2 = n
n/4 n/4 n/4 n/4  ------ each item need n/4 to merge, sum is 4*n/4 = n
.......
As we can see in the above tree, each depth of the tree need n step to complete its task. Then the sum of all is nlogn because depth of the tree we can have is at most logn.

The non-comparison sorts are really interesting. But I still don't understand many of them.

More Talk About Recursion!

From the beginning of the csc148 class, we have already been told the importance of recursion. Knowing recursion and analyzing recursion is a important step in programming. However, recursion in the most time is extremely hard to track all the stuff. And I want to show some ways to fully understand the recursion and my experience about learning the recursion.

First of all, one powerful tool to understand recursion is drawing the recursion tree. (Actually I learn this stuff from a book called Introduction of Algorithms,And this is an extremely good book that tells you everything you need about understanding algorithm) A recursion tree is just like the picture the professor draw during the lecture. Take the hanoi tower as an example, the top node is the root of the tree and also the first time we call the method. Then the tree will be constantly adding the left nodes until it meet the base case, which means there are only one cheese left and it will execute the first step.Then the left most node will quit and you will get into the right node of the previous left node. That's sort of how I figure out the recursion in a tree model.

Another tool I guess is the visualizer. And actually it will give you more understanding about how computer works. For example, after visualizing one simple recursion function, you may notice that the recursion is actually based on the stack ADT. That's why when we sometimes forget to write the base case for the recursion, we will get stack overflow error.

My advice about learning and understanding the recursion is that don't rush and work step by step. The recursion is actually simple and it is so similar to one proof method in math, which is the Proof by Induction. I find it helpful if you can completely understand the Induction first.

My experience in Assignment 1(About Recursion)

Assignment 1 is a typical Hanoi tower problem. Luckily, I learned some thing about it by myself. So I can easily write the recursion. However, when I was writing the recursion part, I found myself in trouble. The problem is that there is really something trouble me in the handout. In the handout, the recursion description is as follows:

1. Move n -i cheese rounds to an intermediate stool using all four stools.

2. Move i cheese rounds from the origin stool to the destination stool, using the (now) only three

available stools and her TOAH method.

3. Move the n-i smallest cheese rounds from the intermediate stool to the destination stool, using

all four stools

And my first reaction is WTF?!!?!

See the step3? "Move the n-i smallest cheese rounds", I thought it means move the n-i smallest cheese round, not plural. And that's why I got into trouble.

I really hope, that the instruction can be more specific. It can be just say the same stuff as the first statement.

Ok, now let's talk about the recursion. I actually google it. Ok, never mind, it's not cheating. I just want to know the recursion because of the trouble I got into from above. And in my words, I will describe the recursion as follows:

 1. we cut the whole bunch of cheese into two part. 

Part1(Down): k cheese. k is a integer between 1 and n(of course, n is the number of cheese!)

Part2(Up): n-k cheese. 

2. Ok then we move these n-k cheese to an intermediate stool.

3.Then we use the three cheese method, and move the  k cheese to the destination stool.

4 Then we move the n-k cheese from intermediate stool to the destination stool.

However, how to choose k?

I first think it should be related to n. And I try k = n//2

Which is not the best answer, but it is actually really close.

How to know the best answer?

You know the k should vary due to the n. But every n has a best answer.

Then I try to using the recursion function teacher give us to calculate the best answer. I find it really painful.

To calculate M(8) for example, we have to calculate M(7)M(6)M(5)M(4)M(3)...M(1).
And we choose the best answer for k=1-7 about M(8)
And we choose that k for this partition.
These are the best step for every n<10.
[[1, 1], [3, 1], [5, 2], [9, 2], [13, 2], [17, 3], [25, 3], [33, 3], [41, 3], [49, 4]]
The first element in that list inside the list is the step, second element is k.

I hope I can get good mark in A1...

Object-Oriented Programming

During the class, I learn some stuff about object-oriented programming. The professor is kinda disorganized and I did not fully understand what that means. And after viewing some pages about object-oriented programming, I think I get that what it means. Here's my understanding:

For example, if I want to create a game, then there should be some objects in the game, warriors or enemies. Let us just assume that all object are human being. Then first, there should be a human class that have all attributes of a human and some methods that a human can do. Warriors and enemies are subclass of the human class, which means they will inherits all the attributes of human and those methods as well. What are those attributes? Hp or mp might be a good idea. And something like speed, defense data, attack data should be good. Those are variables stored in the class and can be easily accessed by using a getter or setter method. What are those methods? Attack, defense, sleep, walk or any action that will affect the variables will be good. 

After creating a class, actually we just create some definition and we still have no object. Then we should create an instance of that class and we can modified the object by using some methods.

After all, I learned C before I learned Python. Although there is no class in C, C does have some data type that is really similar to class, structure. Actually, I think class is just a improved version of structure. Those are both neat way to keep track on every related variable.

Something about the property: I was really confused when I saw the function property. After reading the text on piazza, I finally understand what this means.
The variable stored in the class can be accessed by using getter or setter method. And what the property does is just overriding the default getter and setter method. Why we doing this is because python does not have other way to make the variable private. And by overriding the default getter and setter method, we can actually make them private.