Week 11: Sorting and Efficiency

During week 10 and week 11, we analyzed some sorting method and their efficiency combined with the knowledge that is learned in CSC165 course, which is the big-oh notation.
The sorting methods include tim sort, which is the python build-in sorting method, insertion sort, selection sort, merge sort, bubble sort and quick sort as well.
In csc108, we focus on bubble sort, insertion sort and selection sort. Bubble sort, as the name shows, simply compare each adjacent pair in the list that is wait to be sorted and shift the largest item so far to the position with index -1. Its runtime belongs to O(N^2), which shows that its run time grows quadratically when the input size doubles.  As for insertion sort, we choose each of the item in the list that is wait to be sorted and insert the item to the correct position in the sorted part. The difference between insertion sort and bubble sort is that the sorted part of the bubble sort appears at the end of the list but the sorted part of insertion sorted is located at the front of the list. The same as the bubble sort, the runtime of insertion sort also grows quadratically but it's more efficient compared with the bubble sort when the length of the list that is wait to be sorted are very large. The last sorting method that is discussed in the csc108 course and it’s also mentioned in the csc148 course is selection sort. Selection sort focus on each of the item in the list and exchange the item and the smallest item in the remaining part that has not been sorted yet. The runtime of selection sort also grows quadratically with runtime n belongs to O(n^2).
Now move on to the new knowledge that is learned in the csc148 course. Quick sort, which is a new sorting method to me, chooses the pivot item and  find the items in the list that are smaller than the pivot item and the items that are less than the pivot item, and the rearrange the order of the items in the list. Finally, apply the same sorting method recursively. Here is some code for this recursive idea:
quick([x for x in L if x < L[i]])  + [L[i]]  + quick([x for x in (L[0:i] + L[i+1:]) if x >= L[i]])
Where L[i] is at its final position of the list and the former part and the later part are waited to be sorted. The base case for this sorting method is that when the length of the list is smaller than 2, there is no need to sort the list and therefore we can just return the list when this condition satisfies. And here is the example:
if len(L) < 2:
        return L[:]
Even though I understand how quick sort runs, I do not understand why the runtime for quick sort can belong to O(n log n), is that simply because the use of recursion?
To find the reason for it, I did some research on the internet and it shows that for each of the partitioning operation of the sorting method, it will take O(n) iterations and the number of the partition is logn, so after combining them together, the final result becomes O(n logn). Unfortunately, I was not fully understand this idea when doing the test, and failed to answer the question.

As for the merge sort, it consists two part, one of them can be treated as a helper function and It is named merge(), which takes two parameter and each of them is a list.  For this helper function, a new empty list is created and them compare the first items in the two given list and append the smaller one to the new empty list. And this step continues until one of the list becomes empty, then combine the list together as the following shows:
return L + L1[i1:] + L2[i2:]
Since one of L1[i1:] and L2[i2:] is already empty, we do not need to worry too much and L is the already sorted part.
The idea of the main function of the merge sort is that we split the given list to two equal pieces and apply the helper function to them:
merge(merge_sort(L[:len(L)//2]), merge_sort(L[len(L)//2:]))
Where the base case is the same as the base case in the quick sort since when the length of the given list is less that 2, there is no need for us to sort the list again. And the worst case performance is O(n log n) since it also involves dividing the list to two pieces and the number of iterations of the helper function grows linearly.

To talk about the test this week, I did not do quite well during the test since I do not understand the sorting methods at that moment and therefore fail to explain the reason why it is O(n log n) and I soon understand the concept after the test:(.

Good luck for the final exam :)

Week 7: Recursion

At first, I do not quite understand the definition of recursion, and after doing exercises, I gradually find that recursion is a new method to write a function and it mainly focus on the function that call itself again and again. For example, in order to find the factorial of 3, we can find the factorial of (3-1) = 2 and then times 3 to get the value of 3!. When repeating this process again and again, finally we need to find the factorial of 1 and then times 2 and 3. It is easily to see that the exact same process occurs in order to get the factorial of 3 therefore we can call the function we defined to find the factorial of the next number. Suppose the function we defined to find the factorial of n is factorial(n), then this process can be expressed as n * factorial(n - 1) for each n > 1, however, when n = 1, the factorial of n exactly equals to 1, therefore at this circumstances, we do not need to call the function factorial(n) to find the factorial of 1 and we just need to return the number 1. After considering this, the final code of finding n! is something like this:

def factorial(n):

    if n < 1:

        return 1

   else:

       return n * factorial(n - 1)

After doing more examples of the recursion, I find that the basic steps of writing the recursive function is that we need to find the way that the function works at the beginning and then try to write down more examples by assigning different values of the parameter(s) to avoid making mistakes. Although recursive functions repeatedly call themselves, a base case is needed to be the stepstone of the whole function, otherwise the function cannot work, which means that we need to find the most basic step that each of the other steps relies on such as when finding the factorial of n!, we need to write down the factorial of 1 is exactly the value 1 and this value is used when we try to find every value n's factorial.

An important point to notice is that, recursive functions are very difficult to trace since hundreds of steps may be produced when simply calling a single recursive function. In fact, we do not need to trace each of the steps of the recursive functions but we need to try our best to understand the way how the function works instead. Furthermore, we need to write the return statement when writing the base case of the function. A classic example to illustrate this idea is the code for tower of hanoi, which occurs in the first assignment. And the code is like this:

        move_cheeses(n - 1, source, destination, intermediate)

        move_cheeses(1, source, intermediate, destination)

        move_cheeses(n -1, intermediate, source, destination)

The steps of the code are very complicated and impossible to trace them all. However, the easiest way to understand this code is just to treat the first parameter as the number of cheeses we want to move and the second parameter is the original stool, the second parameter is the intermediate stool and the last parameter is the destination stool. Before running this function, we just need to assign value to each corresponding parameter and we do not need to worry too much about how the function works at each steps exactly.

It is hard to believe that I find it magic and interesting to find the recursive way that the function runs. Sometimes it is unbelievable that a complicated function can be expressed as a single line of code and the process to find the way of writing the recursive function is a lot interesting to me.

Now, move on to the topic we discuss during the week 7, this week we are working on the linked list which is another kind of tree that has only one children. It is somehow the same as the binary tree that is introduced in previous week therefore is quite easy to understand and to be accepted. However, some of the codes that professor provided is hard to think about and if I am asked to write the code independently, I cannot rewire the codes the same as the one professor provided. Such as the method called decapitate, the codes in the else clause:

else:

            self.empty = True

            del(self.head)

            del(self.rest)

is hard to think about because I am not sure about how to deal with each of the circumstances exactly.

This week’s lab is about the super class, and it asks us to rewrite the code we finished writing in a previous lab. Things went well when doing the lab exercise except sometimes I cannot understand what we are asked to do even if we have read the instructions.

Assignment 2 is also coming this week and I finished it very quickly since the content is just to design a three different types of trees, including dot root tree, bar root tree and star root tree. I am still working on the problem of how many and what kinds of methods are needed in order to finish the tree classes.

Recursion and Binary trees

This week, the definition of tree is introduced in class, which includes the definition of several terms such as leaf(node with no children), internal node, subtree, height of a tree and so on. Then, the three kinds of orders to read a tree are also introduced, including the preorder, postorder and inorder.
In order to present the value of each node with the given order, some recursion methods are used to reduce the work load, such as preorder can be represented as [tl[0]] + preorder(tl[1]) + preorder(tl[2]), which can be find out by listing several examples based on the given tree. 
Moreover, the way to present inorder is inorder(tl[1]) + [tl[0]] + inorder(tl[2]) and postorder is postorder(tl[1]) + postorder(tl[2]) + [tl[0]]. For each of the tree, a list with either int value or list can be used to present trees, such as [5, [4, None, None], [3, [2, None, None], [1, None, None]]], where None represents no children for the nodes with value that is in the position index 0.
Since the tree is also a kind of ADT, we can create several methods such as check whether a value is contained in the tree by creating a method __contain__ and so on.
One thing that needs to pay attention is that when writing the codes with comprehension, sometimes we need to write "()" and sometimes a list is needed. To provide an example, when using the function sum to find the sum of the given numbers, we need to write sum([numbers]) instead of sum(numbers) since it can sum up the numbers in the list but not the single numbers. Furthermore, writing a square bracket is also necessary when the comprehension is complicated.

-Flora

Nested functions and recursion

This week we discussed about the nested function and more example about recursion. And the Hanoi tower of three stools is introduced as new knowledge.
The code is like this:
       three_stool(model, number_of_cheeses - 1, origin, middle1, destination)
       model.move(origin, destination)
       three_stool(model, number_of_cheeses - 1, middle1, destination, origin)

When I try to trace the code above, I find the total steps are nearly 300, which is impossible to think how each step works. However, when thinking it by using another way, it becomes pretty easy. We can just treat the function three_stool as a move method and put the original stool, intermediate stool and the destination stool without thinking anything else.

Also, I got an idea about how nested function works, which shows that it only works inside the function we defined previously and we cannot use it independently by calling a(), where a represents a nested function inside another function.
The new idea about recursion is that we do not really to trace the step one by one but try to understand what steps are repeated when running the function. As we trying to solve the problem, a base case is needed to develop the whole. Since the base case plays an important role in developing the whole recursion, it is very important to find a correct one and write the return statement in order to produce value in each of the step in the recursion function.
To talk about the assignment one, I used to find the value of i by using the recursion method but after trying some actual example, I find it difficult to find a base case for the recursion function. Therefore, I used for loop instead of the recursion method, which means use the function          
 temp_moves = 2 * best_moves[n - i] + 2 ** i - 1
to find out the i that produces the least number of moves.

Finally, good luck for the following week!

The forth week's report

This week we continue discussing the examples of recursion, which is an amazing and efficient way to solve problem. For example, we can use it to find the depth of a list with several codes and if using the normal way instead using recursion, it will be very annoying due to the 'huge' work. The turtle recursion that is discussed during class is also an example. After tracing the code in the example, my friend and I find we can hardly write the code without recursion, however, the way to write codes such like this takes some time to think about...maybe exercises help a lot.
Now move on to the assignment 1. I nearly finish it although at the beginning I find it really difficult and hard to understand the meaning of it. The fact is, we should try to read and understand the meaning of each function and each module that are provided. At first I think it is ridiculous that the headers are worth 50% percent of the total mark. But later on, it is proved that the headers are quite important and if you can write down all the correct headers, it means you understand nearly 80% of the assignment 1. I am trying my best to finish the last step as soon as possible and discuss the best solution with my partner as well as the bonus question.

- Flora

The third week of CSC148

The super class and IntStack subclass are quite easy to understand and it's the same as defining a new exception since there are somehow the same. However, how to raise the exceptions that are defined by ourselves make me confused. I am not quite sure about how to use "try:......" and "except......as......". So I am still trying to figure out these new stuff and it seems clear after I check the website related to the knowledge about exceptions that is posted on the CSC148's website.
The second lab really makes me feel excited because of my nice partner and we solve the lab exercise very quickly and efficiently. Honestly, the 2nd lab exercise is easier than the first one, but I stuck at the last question asking us to make the function runs more quickly after having done the previous parts. Luckily, we understand this question with TA's help.
Now I am doing the second exercise and it helps me a lot with apply the knowledge I learn during the lecture. At least, hope I can finish the assignment one, which is just posted on the website, with my partner as soon as possible and I'll try my best to make it wonderful.

- Flora