Week 11: Sorting and Efficiency

About Sorting and Efficiency
I have talked about some points for efficiency in last several articles, so I will select some important points this time. Their common feature is to reduce the unnecessary duplication. For example, in week 4:  recursion in nested list and turtle, I have mentioned a method from our reading to improve efficiency in recursion, which is to use a variable(usually dictionary) to record the result from every iteration in order to avoid the repetitive work.
Moreover, sorting algorithm is a great case in the discussion on efficiency.  For instance, the principal improvement of Selection Sort compared with Bubble Sort is to make only one exchange for every pass. In the worst case, both of them will make (n-x) comparisons in the x-th pass for n items in the lists. However, Bubble Sort will also make one exchange in every pass, whereas Selection Sort will just remember the maximum or minimum and make the exchange once, which can almost save half the time than Bubble Sort.  The drawback of Selection Sort is that it will still check every items in spite of average case or the best case while Bubble Sort not.(i.e. the time complexity will not change in either the worst case or the best case.) Then the creation of Insertion Sort solves this problem by combining the advantages of both Selection Sort and Bubble Sort. Insertion Sort will not make effort to find the maximum or minimum but the "proper" position for the item in every pass like what Bubble Sort does. In the meantime, it will not make exchange every time but record the position and make only one exchange after finding the proper position like what Selection does.
Nevertheless, the efficiency of Insertion Sort still can't satisfy the demand of our computer scientists. (lol!!!)  Grouping is a good method to increase efficiency in our real life. Applying grouping in computer science, we have more amazing algorithm such as Shell Sort, Quick Sort , Merge Sort and Timsort. Shell Sort divide the lists to sublists by a given "gap". After that, the most part of the list will have been sorted and the task of the last basic Insertion Sort would be simple. However, the time complexity in Shell Sort depends on the "gap" we choose.
Quik Sort is a similar version of Binary Search Tree. Choose a pivot value and then divide the list to the part of the values less than the pivot and greater than the pivot. The Merge Sort, which is my favourite algorithm, just needs nlogn time complexity in any case because we know that it needs logn times to divide a list in half (i.e n /2 /2 /2...=2 -> 2 * 2 * 2 ... = n, then the number of 2 in the equation is logn). In the merge process, every items just likely compare with each other once, so the operation in total is still n. Then we get nlogn time complexity for the Merge Sort. The defect of Merge Sort is in the best case, the time complexity is still nlogn which is larger than n for Bubble Sort and Insertion Sort as we just need to make (n - 1) comparisons in the best case for both of them. Timsort manages to remedy this by combining Merge Sort with Insertion Sort as I have discussed in the last blog post.
In addition, it seems that the improvement of the algorithm on time complexity sometimes can lead to the increase of space complexity such as Merge Sort, Quik Sort and Timsort. I find another algorithm - Heapsort which can balance them.

About Asymptotic Analysis
As what I have talked in the last post, this topic is a little bit overlapped with the content of CSC165. The difference is that while CSC165 focuses on how to find an formula to express the runtime complexity of a function and its corresponding asymptotic analysis (i.e. Big-oh, Big-Omega, Big-Theta), CSC148 pays more attention to the explanation  for the time complexity of some given sorting algorithm. Nevertheless, they are close related to each other. In the last paragraph, I have analyzed how to get the time complexity of Merge Sort --- nlogn from the degree of CSC148, but we still can't obtain O(nlogn) without a detailed proof. I will make a brief proof for sorting algorithm so as to be more logic. Let's take an example of Bubble Sort:

1
2
3
4
5
6
7
8
9
10
11
12










def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp
 
alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

Assume the runtime of this function is T(n) for n is the number of items in the list. In the function bubbleSort, we can see two "for" loops. And the inner loop also has a "if" judgement sentence. As we are talking about Big-oh, we assume this is in the worst case so that every sentence in the "if" sentence will be always operated in every loop. For every inner loop, we get 4 times operations. Then we have 4 * passnum in every outer loop. Also, in the outer loop,  passnum will respectively equal (n - 1, n - 2,..., 2, 1). Then we get T(n) equal to 4(n - 1 + n - 2 + ... + 2 + 1) = 4 * (n - 1)n / 2 = 2n^2 - 2n. Then we can simply find (2n^2 - 2n) <= 2n^2 for n >=0. Then we get T(n) in O(n^2) in the worst case.

Challenge
To some extent, Sorting Algorithm is a complex study for computer science. There are many various algorithms. Each of them has itself's features, advantages and shortages. It is difficult to memorize so many functions or principles of these algorithms, especially for those algorithms involving recursion, many loops and built-in helper functions. Furthermore, the computation and the proof of the Asymptotic Analysis is really a challenge because it needs many mathematic knowledge. In addition, I saw it says that "According to information theory, no comparison sort can perform better than  comparisons in the worst case." I am still wondering the reason...

Achievement
I think the topic about algorithm will be accompanying with me in my university study as I will choose many mathematics courses. In fact, I like logic analysis for many things so it is really interesting to dig some deeper theorems or applications about it. To my disappointment, CSC148 seems just to discuss a little about them as they were not included in any assignment and exercises. However, the last question of test 2 is a nice example which we could spend more time analyzing (one hour is not enough for a detailed one...) Anyway, they cannot stop my forward steps as they couldn't in the past, either! Come on! Final!

 wo

1

2

3

4

5

6

7

8

9

10

11

12

Linked List & Binary Search Tree & Sort

Since I missed several blogs, I will talk about all of these 3 topics in this article.
1st: Linked List
Linked list is very similar with built-in list type in Python. Both of them are orderly and we can track the items by some "index". We can also easily implement some method in Linked list just like in built-list, such as "append", "remove", "+", etc. However, linked list is more like a listed list which only has two items, one of which is an object and the other is a listed list. In built-in list, the relationship between every item is parallel even if they are ordered, whereas in Linked list, the preceding item has a higher level than its following items. Therefore, I think that the most significant characteristic of linked list is its efficiency. In the week 2 lab, we found that the runtime for a similar tasks such as "enqueue" and "dequeue"  in a queue which uses list is much longer than that in a stack. The reason we analyzed is that in built-in list we need to move every item forward or backward by 1 step if we dequeue or enqueue 1 item in it since they are parallel, while in linked list, we just assign "self.next" to "self" in "dequeue" or assign "self" to "self.next" and the new item to  "self.cargo" in "enqueue". We consider the every item as a whole --- a node except the item that we delete or add in. For example, in our reading text, it has a paragraph talking about "The fundamental ambiguity theorem". It points out that there is often an ambiguity between a node and a list. The node of a linked list can be considered as a single item, whereas the concept of list is a collection of many items, as the text says "These roles are not part of the program; they are in the mind of the programmer." 

Challenge
Well, I don't think it is very hard to understand and implement a linked list since it is actually a simplified version of a tree except some abstract concepts such as the difference between a node and a list. It is important to avoid a loop in the linked list.


2nd: Binary Search Tree
Binary Search Tree is a strictly logic data structure. In mathematics, the relationship between any two real numbers is just equal to, greater than or less than. Binary Search Tree takes advantage of this fundamental theorem to increase the data search efficiency. Furthermore, in the logic analysis, as the every logic judgement has only two results --- "True" or "False", the he method of Binary Search Tree is very similar with a part of the content of our week 6 reading --- "The animal tree" Every node is a judgement just like " Is the input x greater or less than the given number y?" After we find the correct position for x, the program will learn a new judgement "Is the input z greater or less than z" just like what it does in the function "animal" in our reading.

Problem
I think there is a problem for Binary Search tree which is when we build a binary search tree from some lists with the same value but differently ordered items such as [1, 2, 3, 4] and [3, 1, 2, 4]. However, we will obtain the exactly same sorted list by Binary Search Tree with different data structures. Therefore, I prefer call this kind of tree as "a method" or "an algorithm" to construct data structure instead of a strict data sequence such as list and tuple or even linked list. Although the position of minimum and maximum values are relatively fixed (i.e. the leftmost and the rightmost), the positions of the other values such as the median varies from the tree to tree. 

Challenge
It is hard to combine the concepts of built-in lists, linked list and binary search tree, especially for the conversion among them(For instance, the Test 2...). In my view, the recursion is the only effective way to solve this problem. Otherwise, sometimes I have to use a loop (Of course!) and a built-in list as an immediate to cope with the conversion between linked list and binary search tree.

3rd: Sort

Sort is a large topic including many sorting algorithms. We have talked about Bubble sort, Insertion Sort and Selection Sort in CSC108. The new sorting algorithms (i.e. Quick Sort, Merge Sort, Shell Sort and Timsort) are really amazing ways. The differences among them are also obvious such as the how to split a list into sublist, how to compare the values and how to put them. For example, in Insertion Sort, we only have two parts --- the sorted part and the unsorted part. In every iteration, the item after the sorted part will be compared with every item in front of it until we find the correct position and insert it there. By contrast, Merge Sort has many sublists with only two items. It will compare each items in every sublist to put them in the correct position then merge every two sublists to a larger one successively and repeat the work. Every sorting algorithm has its characteristics and advantages. The invention of new algorithm is a great study. For instance, Timsort combines the strengths of Merge and Insertion Sort. The Minrun is just like the sorted part of Insertion Sort in Merge Sort.

About Asymptotic Analysis:
As I am learning CSC165, this conception is overlapped. The content in CSC165 about this is more difficult in fact because we need to find a function T(n) to represent the runtime based on the number of items n of the input and then implement a detailed proof to find its O(x) or Big-Omega or Big-Theta. Nevertheless, I don't think it is very complicated at least so far, perhaps for we are just the freshmen. Sometimes we can just draw a conclusion intuitively if it doesn't ask for a proof. Any way, it is very helpful to help us analyze the efficiency of a function or a sorting algorithm. 

Challenge
The memory of various sorting algorithm is a little bit hard, especially their respective python implementations. The  strict proof of asymptotic analysis is also challenging. However, I think these two topics are very important for my future study since I am going to study more about statistics and mathematics. I will spare no efforts to defeat them!

Week 7: Recursion

About recursion
We have been learning recursion for several weeks. Actually, I think it does show the strong power of the computer. In recursion, we need to trace the process from top to bottom(like popping the item from a stack) and then return the result back from bottom to top(like re-pushing the item to a stack). For us, it is an extremely tedious and error-prone process but for computers, it can be done in a short time.

The computer science version of "series"
I think it efficiently takes advantage of computers' characteristics. A computer can repeat and memorize the function call and its corresponding result or another function call through many unique addresses whatever the number of iteration is. For example, it is very hard to trace a complex series for us (we may make some mistakes in calculation or forget the results) but it would be just several-time iterations for only one function call(i.e. the formula) for the computer.

Loop & Recursion
Recursion is very similar with a loop. Both of them need to repeat one or several functions. However, I think there are several obvious differences between them. First, a loop needs a condition to judge whether it has finished(i.e. a boolean sentence in 'while' or a range in 'for'), whereas a recursion needs a bases case and could be done when the result can be obtained by computer itself. Second, for the recursion we need to conceive how to make sure the result from an iteration can be applied in the next iteration, whereas for the loop, the result of every iteration can be independent. Therefore, when we know a base case and how to apply the result in new iterations but don't know the condition to judge the process, we'd better use a recursion.

Challenge
In my view, recursion is a relatively abstract concept in programming. Sometimes it is like a "magic". For example, in the assignment 1, when we consider how to move n cheeses in 3 stools, we wrote a function and told the computer step1, step2 and step3(As in the lecture). For us, it is really difficult because the indexes which the"source", the "intermediate" and the "destination" stool refer to will be exchanged in every iteration and in the meantime we need to calculate and memorize the result of every combination. We tell the approach and the starting point then the computer shows us the result but we don't know what happened in the process.

Achievement
Although it is not easy, I think I have learned the crucial conception of recursion. Assignment 1, readings and labs and test( I just got the score of test1! lol!)  help me comprehend the recursion totally.  For instance, in the lab5, I learned some useful built-in functions in python such as filter, all and any. Then I can save much time and space in programming! Now, we have begun to learn tree and linked list. I hope I can successfully use the power of recursion to win in the following challenges!