Week #11: Sorting and efficiency

Over the last serveral weeks, we learned about the sorting and efficiency from the lecture, reading resource, and lab practicing. Sorting is a method which can collect the elements in a specific order in computer science. However, there are many different kinds of sorting method in python, such as bubble sort, selection sort, etc. Based on my comprehension, we are not going to learn about how to write the sorting function instead of learning that which sorting method is more efficiency and why this method is more efficiency than other. This is the purpose of what we learned about in this week.

When I studied the sorting and efficiency, I would like to realize the process of executing firstly in the bubble sort, the selection sort, the insertion sort, the merge sort and the quick sort. In this week's lab exercise, we did a experiment about the sorting efficiency and abserved the change of result in different condition. When we know about the execution of different sorting method, we will understand the experimental result more easily. 

In the lab, after we collected the data of sorting time, we made some graph in excel for observing the change of the result and discuss with my partner. We found that, the data just changed slightly and the selection sort is the most efficiency in this condition.

After finishing the lab and lecture, I found that the most important reason of sorting efficiency is that if the sorting function is more complex, it will spend more time. Also, the input will affect the running time. We can do the exercise of big-oh for improve the knowledge of sorting efficiency.

week #8 --- Tree

This week, we learned about the Tree class. Based on this class, there were many methods and it extended some knowledge points. For example, recursion and subclass.

The tree list must have three element. The first element is root and the rest are their leaves. The leaves can be a new tree list and also can be None. Basically, we can do a lot of exercise about tree by ourselves. It seems like our exercise 3. We know the preorder and inorder tree list, and return the original tree list. After that, we wrote one more function about count the sum of deepest leaves from root for the tree list. For this kind of exercise, we can understand and apply recursion and writing the helper function inside the main function deeply.

For the computer science, every day we learn the different knowledge and every day we think the different methods for the function. We need to keep practicing everyday and improve our knowledge well. 

Week #7 --- Recursion

In the last few weeks, we learn about the recursion deeply from lectures, reading materials, labs and assignment 1. Base on my comprehension, recursion means we call the function inside itself for solving the subproblem easily. The recursion makes the function always run and stop until finding the result of subproblem.

When I knew recursion in the lecture first time, I had no ideas for this term, because it seemed very abstract and hard to understand. After reading the material from the course website, though I knew what is the recursion, I still did not know how to apply recursion in python so that I felt difficult to finish the lab exercise in the lab. Talking about the lab, I was really appreciated to my partner since he helped me lot. He told me a method for understanding recursion easily. When I get a question, I will seperate the question into two parts. The first part is basecase which means the normal case. The second part is recusion case. I want to use an example to explain what is basecase and recursion case.

For example(This is an example from the week 5's lecture):
def rec_max(L: list) -> float:
    """Return the max number in possibly nested list of numbers.

    >>> rec_max([17, 21 0])
    21
    >>> rec_max([17, [21, 24], 0])
    24
    >>> rec_max([17, [21, 24], [18, 37, 16], 0])
    37
    """

    return max([rec_max(x) if isinstance(x, list) else x for x in L])

In this case, the basecase is when L is a normal case and L do not contain any nested list. The rec_max function will only run once time. Therefore "else x" is basecase. When L contains some nested list, we need to run rec_max function in the nested list . This case is recursion case. Therefore, we write the recursion case "rec_max(x) if isinstance (x, list)". When x is nested list, we need to call the rec_max function again. This is what recursion means. However, "for x in L" is the condition of the function which can make the function stop when every element in L executed. This method is my partner teaching me which is a good method for me to solve the recursion problem. 

In the assignment 1, we did a good application of recursion. We use recursion to finish the 4-stools hanoi tower game. This is the first assignment of CSC148. I think the most difficult part is part 5 --- calculate the minimum moves of 4-stools cheeses. This is a kind of recursion problem. I spent almost two days finishing part 5 of this assignment with my partners. We discussed together, search some reading source from internet. We seperated the problem into two small parts. First, we though about the minimum of cheeses move in 4-stools. Then, we write the code for the number of moves. Finally, we combined two small parts in the main code. During the process, we got a lot of error. We modified the code continuously until we pass the testcase. When we finished the recursion of part 5, we were screaming at that moment. We were excited we can overcome the challenge. After I finished the assignment 1, my biggest experience is that the most difficult part is recursion and we achieve a good application of recursion this time. 

Although we practiced a lot about recursion in the lab, assignment 1 and term test 1. I think we still need to practice more different recursion problem for comprehencing recursion more deeply in the further study.