Sorting and Efficiency

         From the primary course CSC165, I have learned the way to calculate efficiency of a function using Big-O. Furthermore, I learned and applied for using built-in sort in course CSC108. Also, I have known other three types of sort: the bubble sort, the selection sort and the insertion sort, especially their differences.

         In the course CSC148, I systematically learned more types sort included the kinds I learned before and efficiency.  Firstly, I would like to talk about what Sorting is. Sorting is the process that places the items into the given order by obvious characteristics. Then, I want to analyze several sorting techniques and their running time.

         The Bubble Sort takes n-1 passes through a list. In each pass, it compares the item starting at first one to the next item. If the previous one is bigger than the next, the two items exchange; otherwise, there is no exchange. Throughout the one pass, the last position can be determined, which the largest item in. The following pass will determine the second largest item. Thus, the first pass makes n-1 comparisons and the second pass makes n-2 comparison.  The sum of the first n-1 integers is 1/2n² – 1/2n, which is the total number of comparisons. The efficiency is O(n²). The best case is that the list is already sorted, while the worse case is that every comparison leads to the exchange.

         The Selection Sort makes the same number of comparisons with the Bubble Sort, but the number of exchange is apparently smaller than the number in the Bubble Sort because there is only one exchange in each pass, which exchange the largest item and the item in proper position. For instance, the second largest item in the list should swap with the second last item. Shortly, the Selection is also O(n²).

         The Insertion Sort determines exactly one item which follows the sublist to the sorted sublist that is in the lower positions of the list. Thus, the first pass makes only one comparison and last pass makes n-1 comparison. We can know that the Insertion Sort is still O(n²). 

         The Shell Sort is an improved technique of the Insertion Sort. It creates several sublists by using an increment i. It will have more sorted list through the passes and complete the insertion at the last step with few comparisons. Because it is more efficient than the Insertion Sort, the running time of the Shell Sort is between O(n) and O(n²), specifically, it is O(n^3/2).

         The Merge Sort is a recursive algorithm that splits a list in half until the list is empty or only one item(log n times). Sorting the base case first and combining them together each time when finishing the completed list. The total running time could be O(nlog n).

         The Quick Sort usually takes the first item as pivot value and divides the list by split point that is the position the pivot value belongs. Also it named quick sort, but the running time is O(n²), like others.

         I am more familiar with these several sorting process with their efficiencies during the study of this week. I know the best and worse case. I also know how to write the functions of these distinct techniques. All in all, these algorithms are important in studying Computer Science and I want to learn them well.  

Labs' Experiences

        This blog I want to talk about the labs’ experiences and changes through the weeks. As I said before, I felt difficult in dealing with the problems of labs in beginning weeks. I thought there are two reasons. The significant problem is that I was not familiar with context. I did not read the readings and review the slides with codes before the lab. The other problem is communication because I did not know how to communicate with the partner. Luckily, these two troubles are all solved through the weeks. I knew that I should read the readings and review the example codes for preparing. Also, this habit helps me catch up with the context we learn from the previous week. In addition, I made a good friend, who is also the partner with me for working labs’ problem. We can discuss the questions about CSC and prepare for the tests. All in all, the labs are valuable and I really learn from them.  

Assignment Two

For the assignment two, I work with new people. One of them is really good at coding and I never see someone who has that clear thought in planning code. The Part one is pretty easy because we only need to create __init__, __repr__, and __eq__. When we done the analyse, we done the part one.

Compare to part one, part two is complicated. However, honestly, it is much easier than assignment one for me. There are four main functions we need in regex_functions and we write some help functions. For instance, we test string s symbols and three types of forms separately in using four help functions. Then, we write in_regex to connect fours. The other example is writing function permutation to help all_regex_permutation.

        These good thoughts are all come from my excellent partner. I really want to learn from him and do well in CS.

Linked Lists

        These two weeks focus on linked list, a recursive date structure, which is consisted of nodes and each node have a reference to the next.

        From the picture below, we can see the linked list has two parts: head, the first element of the liked list and rest, another LinkedList that has the same structure. N the class LinkedList, we need to check whether head or rest is None. If both of heaf and rest are None, the self is empty. If not, we give the value of head to self.head. Then we assign the rest is an empty LinkedList if the rest is None; otherwise, we put self.rest = rest. In addition, method prepend is for adding new item to the front of its self and ,ethod decapitate is for deleting item from self by using del. The method __getitem__ clearly shows the recursion. Using ind = ind – 1 to get the item by going deep into the rest.

       The importance of this type list is collection. For instance, the first node in the list can refer to the whole list. 

Recursion

        This is the second time I write the blog that is about Recursion. Throughout the continuous learning according to this topic, I am more familiar with it. Besides knowing what it is, I learn how to use it now.

        A1 gives us the opportunity for practicing of using recursion. We need to solve the challenging problem by applying the structure of recursion. Also, it is very helpful to work with classmates. We can help each other on working it. 

        In addition, “Tree” is the good example. Form the structure of Tree, it is really like a family. There is a root, which is also the original parent and its children also have their children. In the methods of Tree, all returns are only one line owing to comprehensive and they clearly show the abstract solution. For example, count is the method for counting the nodes in the Tree. The function is “return 1 + sum([count(n) for n in t.children]). It counts all the parents and leafs. If the n is also the parents, it needs to call the function itself. Also, we could use the structure of Tree to do the calculation: preorder, inorder and postorder.

        Recursion is very important. The main benefits are these two: firstly, the program using recursion functions is obviously clearer, simpler, shorter, and easier to understand. Secondly, it directly reflects the algorithm. All in all, I prefer recursion to iteration.