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.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
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!
No comments:
Post a Comment