[ o,r,S,n,g,i,t]--->Sorting and Efficiency

Sorting reminds me of the last two week’s lectures. Sorting and efficiency are things we spend a long time to talk about in this period of time. I would like to begin form ask myself, what actually the sorting is and how can a sorting algorithm said to be efficient.

This is the definition of sorting on Wikipedia.

Sorting is any process of arranging items according to a certain sequence or in different sets, and therefore, it has two common, yet distinct meanings:   

1. ordering: arranging items of the same kind, class or nature, in some ordered sequence, 

2.categorizing: grouping and labeling items with similar properties together (by sorts).

To make it clear. Using my picture as an example of sorting.

You can see that my photos are listed in random and now I want to sort them into the order by age.

The result shown as follow

For example, we can sort a list of integer from great to small or from small to great or sort some apples form big size to small size. Those actions are all sorting objects. Like we can call the python built-in method sort() to sort number and letters.

>>>a = [3,4,6,1,8,0]

>>>a.sort()

>>>a

[0, 1, 3, 4, 6, 8]

>>>b = ['g','e','w','s']

>>> b.sort()

>>>b

['e', 'g', 's', 'w']

However, u can see that is method is only can sort specific things in specific order. Therefore, we need other method and algorithm to help us sort things we want in orders we want. Like selection sort, insertion sort and bubble sort and so on. Each sorting algorithm has their own way to sort objects and they may run different times to sort same object. Some algorithms good at sorting specific objects. 

For example, to sort [54,26,93,17,77,31,44,55,20] 

merge sort uses 297 steps

insertion sort uses 106 steps

gapinsertion sort uses 181 steps

selection sort uses 132 steps

bubble sort use 154 steps

Therefore, you can find there is a such big difference between those sorting algorithms for their efficiency.

Yes, EFFICIENCY. Now I would like to talk about that. For us, to decide using an algorithm to sort different objects depends on the efficiency. In that case, we need to know, when there are more and more objects contained in the list we sort, how the runtime grows according to the way each sorting method use to sort. To analysis the growing of runtime, we introduce Big-oh.

What is big O?

Big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.Big O notation is used to classify algorithms by how they respond to changes in input size.

For example, for 1<a<b, n^a in O(n^b), or a^n in O(a^b). These are sample examples.

To see a little bit complex example.Lets say that the function is T(n)

max=0                              1

for i in range(0,n):               2

    for j in range(i,n):           3

        sum = 0                    4

        for k in range(i,j):       5

            sum = sum+L[k]         6

        if sum > max:              7

            sum = max              8

We can say that T(n) is O(n^3)

The reasons are listed as follow.

Line 6 takes 1 step

The loop on lines 5-6 iterates at most n times, because i is from 0 to n-1 and j is from i to n-1, so the number of steps is less than n

Lines 4-8 add at most 4 steps.

However, the loop on 3-8 iterates at most n times and 2-8 iterates exactly n times.

line 1 add 1 step.

Therefore, the number of steps is <=2n^3+1 <=2n^3+n^3 <=3n^3 for n greater than 1

In the lab, we also ran some different functions and changed the size of input and then filled the chart to get the graph of the growing of each function. Next compared them to get the result in order to observe the change of the runtimes.

Sorting and Efficiency are really important in computer science. Not only because they can help us to solve problems easily, but also because they can help us to improve the efficiency of our program and function.

These are my understanding of Sorting and Efficiency. Hope I can learn more about it and have better understanding of it compare to now I have.  

Working on term test!!!

Hey, there is a term test THIS WEEK!!! In three days!!!

Unbelievable???

But you have to prepare for that!

Hence, in this slog, I want to talk about my preparation on my term test 2.
My result for term test1 is really really bad. That makes me fell upset for a long time. Therefore, I have to try my best at this time.

First, I reviewed all the slides to check that whether I already understand all the things we learned in the lectures.

Second, I plan to read the code I wrote during the lab because that is the things we put the idea into practice. 

Third, I need to rewrite the exercise, cuz you know, sometimes people can forget things they did before by their own.

And then, after those preparations, I can do some past tests to check if I can solve all the problems on it.

Finally, it is better for me to write something bother me or something confuse me, and something need to spend lots of time to remember. Also, something easy for me to forget when I am nervous.


OK~~~I m going to work on the test. Good luck to you guys and me ~~~

Another typical week.(Talk about exercise)

In this week, I think one of the challenges on computer science for me is the exercise 3. In previous weeks' lecture, we've learned a lot of things about the traversal of tree.
There are three ways for us to traverse the trees.
1.Pre-order
2.In-order
3.Post-order

As you can see, the order or the way for these three algorithm to traverse trees are different with each others.

Pre-order

Visit the root.

Traverse the left subtree.

Traverse the right subtree.

In-order 

Traverse the left subtree.

Visit root.

Traverse the right subtree.

Post-order

Traverse the left subtree.

Traverse the right subtree.

Visit the root.

For me, I can easily traverse a tree with these algorithms. However, what make me confusing is to build a tree with given pre-order and in-order.

To solve this problem,I use the given example form the handout to draw picture and find the way to solve that.Let me explain.

[10, 6, 8, 12, 11, 15] (pre-order) 

[8, 6, 12, 10, 11, 15] (in-order)

As we already know, the order for pre-order to traverse is root-->left--->right(which shown above). Therefore, the first item(pre-order[0]) must be the root for the tree which is 10.

Then, the order for in-order to traverse is left-->root-->right. Therefore, items before 10 is the left subtree and items after 10 is the right subtree.

After that, things all become clear. 6 must be the root for the left subtree and use 6 into in-order list to split the left subtree and right subtree for the left subtree.Using this idea to keep traverse in recursive way. Finally we can get the result.

The tree will be:

[10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]

_______________________________________________________________________

Just post my code here after the due day to let everyone see my slog can have an idea about this exercise if you did not do well on it.

def make_tree(preorder, inorder):
    """
    >>> make_tree([10, 6, 8, 12, 11, 15], [8, 6, 12, 10, 11, 15])
    [10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]
    """
    
    if not preorder or not inorder:
        return None
    root = preorder[0]
    in_left = inorder[:inorder.index(root)]
    in_right = inorder[inorder.index(root) + 1:]
    pre_left = preorder[1:len(in_left) + 1]
    pre_right = preorder[len(in_left) + 1:]
    left_sub = make_tree(pre_left, in_left)
    right_sub = make_tree(pre_right, in_right)
    return [root, left_sub, right_sub]







See you in the next slog soon~~~~

Typical week. (talk about assignment2 and lab)

This is a typical week for studying computer science. In this week, we learned something about linked lists and do the work across the same topic in the lab. However, what I want to talk more in this week’s slog is my assignment two.

 

I just finished my assignment two with my partner this weekend. This assignment is about the tree. At first, we designed to use only one class that contains all the requirements in the handout. The reason for this is that we can write less code. In other aspect, in some way one class does meet the requirement. Therefore, this weekend, I and my partner met up and changed our one class to many classes. Those classes including star tree class, bar tree class and so on. It is not hard to fix, but we think our solution works will still and uploaded our first solution with our new solution with many sub-classes. And in this assignment, I also learned how to set common property. That is really helps a lot.

In this week’s lab, I find that in lots of questions, it will be much easier to use list comprehension than the for loop. I am really not good at using list comprehension. Hence I need more practice during the lab and by myself in free time.

 

Recursion,[Re,[cu,r],[[s],ion]

This is the fifth week that I have known the recursion. I am getting more and more familiar with recursion. However, I am on the way to understand and to use it still.

 

First of all, I want to talk about my own opinion of recursion. The most straightforward way to explain recursion is that calling a function inside itself. 

 

This is a picture about recursion on wikipedia.
A visual form of recursion known as the Dorste effect. The woman in this image holds an object that contains a smaller image of her holding an identical object, which in turn contains a smaller image of herself holding an identical object, and so forth.

More precisely, recursion is a process of repeating objects in a self-similar way and stop repeating when it achieve its goal. 

 

In csc148, we often use recursion to solve the problem of nested lists because the process of dealing with the lists inside the big list is same as the process of dealing with the whole list.

 

Here is an example.

Def sum_list(L):

Lis=[]

For item in L:

If is instance(item, list):  # (*)

Lis.append(sum_list(item))   #where recursion happended

Else:

Lis.append(item)

Return sum(lis)

 

Lets create a nested list.

>>>[1,3,[4,2],[[4],7]]

 23

 

At (*), the function check whether the item is a list or not, if it is a list, this item will turn back and loop again until the elements inside  the item are all integers. This process makes a new list which contains all the integers in L without sublist or inner list inside it. Therefore, we are allowed to call sum to get the result.

 

 

Recursion really helps a lot when I was working on the assignment one. In Step.5 in assignment one, we were asked to solve four stool instances of Anna Hoy's cheese moving problem. When we try to move the cheeses, we need to determine if the cheese we plan to move is bigger than the top cheese on the destination stool., but if the destination stool is empty, we move the cheese without any judgments.  Hence the process for every move is the same. Using recursion here becomes a very good idea.

Here is my functions.

 

def tour_of_four_stools(model: TOAHModel, delay_btw_moves: float=0.5,
                        console_animate: bool=False):
    """Move a tower of cheeses from the first stool in model to the fourth.

       model - a TOAHModel with a tower of cheese on the first stool
                and three other empty stools
       console_animate - whether to animate the tour in the console
       delay_btw_moves - time delay between moves in seconds IF
                         console_animate == True
                         no effect if console_animate == False
    """
    helper = Helper(model, delay_btw_moves, console_animate)
    n = model.number_of_cheeses
   
    def move_cheeses_3stool(n: int, source: int, inter: int, dest: int):       
        if n == 1:
            model.move(source, dest)
            helper.pri()
        elif n > 1:
            move_cheeses_3stool(n - 1, source, dest, inter) #
            move_cheeses_3stool(1, source, inter, dest) #
            move_cheeses_3stool(n - 1, inter, source, dest)#
   
    def move_cheeses_4stool(n: int, source: int, int1: int, int2: int, dest: int):
        i = n // 2
        if n == 1:
            model.move(source, dest)
            helper.pri()
        elif n > 1:
            move_cheeses_4stool(n - i, source, int2, dest, int1)#
            move_cheeses_3stool(i, source, int2, dest)#
            helper.pri()
            move_cheeses_4stool(n - i, int1, source, int2, dest)#
           
    move_cheeses_4stool(n, 0, 1, 2, 3)

 

You can see that the line with # are where the recursion was being used.

Recursion is really interesting and useful. I like it and wish to know more about it. For programmers, it is really important to learn to be lazy which means that avoiding write repeating code. Recursion helps us achieve that.

 

Finally, using my picture as an example of recursion~~ lol~

 

 

Talk about cs learning experience in midterm week.

This is a busy week. Although have to finish many tests and assignments this week, I paid my attention to computer science as usual. 

 

In this week, our lectures also focus on recursion. This week’s lecture really helps me understand recursion much better. The Tower of Hanoi is a very good example which shows how we can useful recursion is and how we can use recursion to solve problems in daily life. Another topic we discussed in our lecture this week is scope. Python looks or goes through the code in order. It is very important for us to know which order it is because this order can influence the efficiency of code. More importantly, it helps us know how our functions run which lets us know how to arrange the code properly and figure out the mistakes easily. By the way, we can clearly see the order which python looks with the online visualizer. 

 

 

Here, I want to talk about the assignment 1. I did not started it before yesterday because of my midterm tests. After I read the handout of assignment 1, I think that it is really interesting. When I was a child, I often play this game on my game boy! 

 

 

This game is harder than 星のカービィ (Kirby) which is more popular in our school. As a girl, I really like playing video games. I played games like Metal Slug with boys in our class and my little cousin when I was a primary school student. I think that is why I choose computer science. Computer is a really amazing invention. People can use it to do almost everything! I want to know it , to get familiar with it. All the things we can do are all build up on millions lines of code. This assignment reminds me of my first inspiration of computer. 

 

I will talk more about the assignment next week after I finish it.

 

 

 

 

 

Finding and fixing problems

In this week, working on computer science becomes more and more interesting. Our lectures, exercises and labs all improve my programming skills and let me understand well. 

 

First of all, I want to talk about my exercise2 which help me to practice using the ‘Exception’. In my opinion, ‘Exception’ is that we can except when something happens, the function will raise a error to help you figure out what kind of error your function makes. In the exercise2, I fixed a mistake for long time. I raise a ValueError when x cannot be convert to a integer with int(x) if x is a str. But actually we do not need to raise that because python can raise that error itself. Therefore, next time, I really need to read the handout carefully. And the next thing is the order of our exceptions. Before the exercise, I think the order of the if loop cannot influence the result. However, I fail a test in my e2b but my function has only one difference with others who pass the test. I did not find my error, but my partner helped me find that. He tested if the order can influence the result, and it worded. Therefore, I fixed this problem. I also think that let other people help you figure out your mistake is a good choice. Because sometimes people cannot see the error in their own works. 

 

Secondly, for my lab, it really goes on well. This is the first time I try to use unittest to test our function by ourselves. I and my partner at first thought our works are perfect. After testing it, we caught many error in it. Hence it is very important for us to learn to test by ourselves before someone else help you to find the mistakes. 

 

The most important thing I learned this week is that finding and fixing the problems. I think it really helps me in my computer science study.