Sorting and Efficiency

Sorting is a method that change the sequence of a list in the order that we want to. For example, we can sort a list of numbers: [5,2,7,8,4,9,6,3,1] by calling the python build-in method '.sort()' to arrange it in to [1,2,3,4,5,6,7,8,9]. This method also can be applied in a list of letters. However, python build-in methods have some limits. It can only sort particular things that has a certain order. Therefore, we must other methods to finish that. It remains that in CSC108 we have already experienced some methods of sorts such as selection sort, bubble sort and insertion sort. Those sorts have their own way. The way the compare items is different with each other. So there's another problem emerged-- Efficiency. The step of those sort method is different. For example, in merge sort, the idea is to divide the list in half and then merge sort the halves then merge the sorted results. There is two variables, times of splitting the list and the steps that each time we split. Less steps means less time to run it then it is more efficient. To be accurate, let's take look on some data.

This is what we did in this week's lab. It is obvious to see that the different method has different runtime when they have a some list. Form this table, we can tell that the python build-in method sort() is the most efficient method.
Meanwhile, we just compare this table vertically. We also can compare it horizontally. With the increasing of length, the time of all of methods increased. But they increased at different rate.
Some are increasing exponentially. Some are increasing linearly. This is what we learnt the Big O.
It is like the Big O in CSC165. It talks about the runtime at worstcase. g∈O(f) means “g grows no faster than f” (or equivalently, “f is an upper bound for g”).

hard assignment2 p2

This week is the due week for assignment 2 part 2. This assignment is really hard. The case is so difficult. At the start, I thought the bar and the dot is the hard case. However, after I study more. The hard case is the star. This week's lab is also hard for me.

preorder&inorder

This week, we were doing this preorder and inorder for a TreeList. It is very interesting topic. I am very happy that I understand everything during the lecture. The way it works is very attractive and I enjoy those steps. I think this week's lab is quite hard. Compared with lecture, the lab is difficult for me to do. My partner and me cannot finish half of handout. But it is a good practise. Some recursion function and Treelist makes the 2 hour lab interesting.

linkedlist

This week, we learnt more about linkedlist. It is very new for me and I do not understand too much during the lecture. However, the lab helped me a lot. The exercise let me understand much more about how this linkedlist work, how the ids going, how to add a new thing to 'prepend' to the list. I am very interested in the part of changing value at the index in the list. At the start, i thought that was a list. Then I realise that it is not a list. It is more complex then a list. So the step of changing value becomes hard. I really enjoy this lab exercise. I can ask questions and practice.

Recursion

    This week, we almost finished recursion. I really enjoy thinking about questions during the lecture. It let me feel that I am following with professor. I did learn a lot of things about how recursion works. This is a new topic for me and it is quite challenged. For example, the tower of Hanoi taught me a lot about recursion. Function can run by calling itself. Before 148, I never meet this kind of things. At the start, it confused me a lot because I thought the function will run over and over. It never stopped. However, I am wrong. It would never stop if there was no conditions or limits for the function. After I study more about the question of tower of Hanoi, I realized that there is always some situations that make the function stopped. Another thing that makes me confused is the return thing. Specifically, if I do ‘return min([nested_list[x]]) if isinstance(x, list) else x for x in L, L = [1,2,[3,[4,5]]]’, I thought it will just return ‘1’ because the first one is ‘1’ and then it will end this function. However, after I trace the function it shows me this. The first one is ‘1’, it is not a list so it will return ‘1’. Then return means to remember this ‘1’ will be store in a list. This is an easy example. After I did the example of winter 2013 term test Q4. I understand more about it. This question is like this:

def rec_len(L):

"""(nested list) -> int

Return the total number of non-list elements within nested list L.

For example, rec_len([1, 'two', [[], [[3]]]]) == 3.

"""

I did this:

       result = 0

       for x in L:

              if isinstance(x, list):

                     result += rec_len(x)

              else:

                     result += 1

       return result

    Every time the ‘return’ remembers the number of the non-list elements. If it is a list, the number of non-list elements will be stored in the result and then count the next one and so on. This makes clear for me that how recursion works. I mean the assignment 1 and tower of Hanoi for me is like a practice of imitating the same pattern. I did understand those examples in lecture and try to do the same way but I did not understand it in my own way. After those examples, I learnt more things which belong to me. However, more things emerged: how could I know if a function is recursive. I can do it by feeling. In another words, Guess! Yes, assume it is recursive and try to do it see if I could do it in recursion or not. Some question is obviously recursive such as nested lists. But maybe some are not; hard to say. I felt ok with recursion. I mean I can face to the problem and solve it by myself. I just need time to think about it.

    Four stools tower of Hanoi is a really good assignment that related to some internet source. I searched some websites that solve the problem of four stools. Some people gives the mathematical function of four stools, some people gives the data of i that in minimum moves, number of cheeses, and minimum number of moves and some people do it in java or other programs. I cannot understand that mathematical function completely nor the java codes but I understand some of the explanation. But I did not use it, it is just some hints that help me to consider my recursion function.

    The biggest achievement that I had is that I can do some questions by myself in a few changes. The python shell is a good way to test myself. I wrote the code then I test it by setting me some testcases. Some edge cases were also included.

    This week’s tutorial was going good. Learning new things and sharing ideas with partners. I mean at the start I was talking with the tutorial group mates about the test. I did not finish all the questions in the handout. And I also realized that this Linklist is very important so I try to finish this at home. Good news is I finish it. Bad news: I get some questions. I will ask those questions in office hour or to my friend.

Q: how can we stop a recursion function?

A: setting a condition, when it satisfies this condition, it will stop. 

awesome assignment 1

This week,I was using my entire week to do A1. It is a really challenge assignment. It is not only an assignment but also a practice. I need to practice more on this course. I always feel like I understand everything on a course. But I cannot do well on exam. Every time I finished an exam, I always found something wrong with my answer when I went out of exam room.

I like tutorial and lab exercise. I can ask question during that time and TA is very patient to answer the question. 

The Exception and recursion

The Exception function gives me lots of fun. This is new for me to write in python. I enjoyed thinking about small details during the class. The thinking of how python behaves is different from when we writing it. For example, this week's exercises told me that the int(x) does not need to raise. When I think to write it in my brain, I do called the function with a if statement. However, when I write it, I just called the int(x) directly. For this week, I think the recursion challenged me. I just don't quite understand the procedure of how it works. I do pay my time to read notes and do some exercises to understand it. Now I am confident with it. I mean I can face it and know how to start with it. This week's tutorial is great. The exercise is good and I finished most of parts. If I had time, I could do it all.