Sorting and Efficiency

    In week ten, we are introduced to some sorting algorithms. Sorting is very important in computer science because it is related to efficiency which, to be more exact, is a huge number of items being selected and processed  as quickly as possible. For example, sorting algorithm who deal with a large collection of items and has a less running time is more efficient than those who have more running time. During the lecture and through the given reading posted on the website we have learnt many sorting algorithms such as bubble sort, selection sort, insertion sort, merge sort, quick sort and so on.
Since there are so many sorting algorithms so I will only talk about some of them.

       Bubble sort. In bubble sort, assume there are n items will be sorted and there is a key pointing to the first item, which also can say that bubble sort starts from the first item, then the first item will compare to the first item behind it which is second item to see which one is bigger. If the value of front item is greater than  the latter item, swap them. Then the key will move and point to the second item and compare the value of first item behind it to see whether first one is greater. If so, swap them...Bubble sort will keep repeating these steps until the key points at the last item. Then the item that has the maximum value will be bubbled up and putted in the end of all the items. (see picture below, the picture is from the website)

That is the first pass and only the largest value is in place. There are still n-1items left and waiting to be sorted. Then the key will point to the first item again and repeating the steps above until all the items are in the right place. I think Bubble sort is not that efficient because there are so many exchange and compare steps. 

      Selection sort. In selection sort, first find the largest item and put it at the end of all the items then find the largest the item in the rest of the items and put in before the largest item which is just sorted.(see the picture below, the picture is from the website)

And the selection sort will keep doing these until all the items is in the right place. Compare to the Bubble sort, I think selection sort greatly reduce the running time and improve the efficiency since it requires less number of exchanges.

      Merge sort. In merge sort, the concept of divide and conquer strategy is really important. In my comprehension, merge sort will split the list in half and each of the half is already sorted. Then create the new empty list and set two keys to point at the first item of both two half lists. Compare the items pointed by key in both half lists and put the smaller item in front of the bigger one in the new empty list. Then the key will move to the second item in both half lists and do the comparison again until the key is out of one of the half list. Then put the rest of the items from other half list into the end of the created list. How to find those two half sorted list is also very essential in merge sort. Basically, we have to do the recursion, merge sort will recursively split the list into half until there are only  two or one item left, then sort them by definition (called the base case). Then do the way mentioned above to  combine two half list to one single list until there is only one single list left. This step also requires recursion.

      Making a Comparison Of different Sorting algorithms. This week's lab, we are asked to compare the running time of different sorting algorithms of different number of items. Basically, the build-in function is the quickest way to sort and when the number of items become larger and larger, bubble sort will have the largest running time which seems like it has the lowest efficiency.

      Overall, sorting algorithms are not as easy as I thought because it needs us totally understand the concept and the way each sorting algorithm has. For me,  merge sort and quick sort are the most difficult sorting algorithms to understand and they take me quit a bit of time to figure out how they work and even if there are prof's code examples help me , it is still really hard for me to translate these two algorithms into python codes. And I think I still have some question about them and I will keep practicing and figuring them out in the future.

Tree

     In week six, we have been introduced a new type of data structure which is called Tree and our lecture is mainly focus on Binary Tree. Binary Tree is a tree-like data structure which has a root and at most two children. It contains some internal nodes as well,whose number also has to be less and equal to two.The overview of Binary Tree is like this

2 is the root of this Binary tree. 7, 5, 6, 9 are internal nodes and 2, 5, 11, 4 are children.

      Moreover, we have been introduced 3 different types of traversal, pre-order traversal, in-order traversal and post-order traversal. For pre-order traversal, root will be visited first then the left subtree finally the right subtree. In-order traversal is left subtree first, root second and right subtree at last. Post-order is left(first)and right(second) tree will be visited respectively and root is the last one to be visit. 

      Understand this three traversals graphically is easy but when I try to write it as codes, it becomes hard for me.But the slides of week six help me a lot.At least I understand how to implement codes for those three traversals using recursion. Honestly, the concept is really easy. If the input is None, we have to return None.Else we have to use recursion.

     Take a pre-order traversal as an example, since we have to visit root first so if the input is not None, we have to return t[0] first which  represent the root then we return t[1] afterwards as it represents the left of the subtree and finally t[2] which represent the right tree. Because there may have more internal nodes in both left and right subtree and each internal nodes with its children or other internal nodes can be seen as another new binary tree so the t[1] and t[2] can be nested lists, which requires us using recursion. And that is the point of implementing traversals' codes.

Recursion

Up to now, we have been introduced some knowledge about recursion so this week, I want to write something about it. First of all, writing a function using recursion is really hard for me, in the assignment one , my partner and me are stucked on that recursion part for a long time. What I have learnt about recursion is when you write a function, the codes for that function could be the function call itself, which means we can call the function inside itself. During the lecture ,we have been showed lots of examples about how to use recursion to solve some problems and I think recursion really simplify our codes.But even if I understand the concept of recursion, it is still really hard for me to implement it into my function such as the function in assignment one. So I need to do more practices until I can use it without difficulty.

exception and subclass

    This week we did E2 which is about exception. I know how to create a exception to prevent our program from crashing because of some certain code. The format of creating an exception is try...except clause. Below the try: clause, write the code possibly will crash when run the program and below the except: clause, write the result we want to produce or the way we want to fix those exceptions. Also, I have learnt how to raise exception defined by our ourselves and how to create a subclass. But there is still something I don't get about exception and subclass and I will try to figure out in the next few days. There is one more thing I have no idea. During the lab this week, both my partner and I don't know how write the  unittest and maybe we should do a little bit works on it because unittest is the content we have already been introduced in last semester in CSC108 so we are supposed to understand and apply it to our program.

Object-oriented programming

    This semester, I am taking computer science 148. During these first three weeks, we have been introduced to some concepts and given some examples about Object-oriented programming(OOP) and abstract  data types(ADTs). There are something, written below, I have gotten so far about Object-oriented programming(OPP).

    Basically, OOP is a programming paradigm and the object of OOP is usually known as instances of classes. Actually, I have already learned something about class in computer science 108 last semester, which helps me a lot to understand OOP but I am still a little bit confused about it. What I have already gotten in CSC108 and CSC148 during the lectures of the first three weeks is that we can create different classes and define plenty of methods in class.Also, different classes can be called and used in other classes.And class has Inheritance, which means when different classes are called in other classes, they inherit the properties from their original classes. Hope I can learn more in the later lectures.