Sorts and Efficiency (SLOG topic for Nov. 28th)

During the week of Nov.4^th, we had already come to the conclusion that the python built-in sort is the most efficient. Then it is quick sort and merge sort (with O(nlog n)), while selection sort being the least efficient (with O(n²)). Also during lab09, we were asked to run each different sort and record the time each sort took to sort a list with 1000, 2000, 3000, 4000, 5000, and 6000 items. We also repeated the same steps for sorted list as well as reverse sorted list. The results did match the race we did in class during the week of Nov. 4^th.

During the second half of the Wednesday class, we revisited the quick sort algorithm. Professor Heap pointed out that if we run quick sort on an already sorted list (reversed or not), it would take a longer time (the worst case scenario). In this case, instead of O(nlog n), quick sort would be O(n²). Normally, quick sort works by picking the first item as a pivot, arrange all the items with value lower than the pivot in one list, and all the value higher than the pivot in another list. Then it would call quick sort on the two separate lists. The main problem is that the algorithm always takes the first item as the pivot. If the list is already sorted, then one of the lists would be empty. Thus the divide-and-conquer method would not apply. In addition, python has a limit on the number of function calls. If the input is a sorted list with 10000 items, then quick sort would call upon itself 10000 times, which would probably exceed the call limit. In order to solve this problem, we modify the code such that it takes an arbitrary item as the pivot (by using the random module). When the size of the input is large, the probability of the pivot being the smallest or the largest is very small, thus it can solve the problem of sorting sorted list.

Name, Trace, and Efficiency (Week of Nov. 25th)

We learned about name and tracing on Monday. In python, every name contains a value, and every value refers to the address of the object. Also when python is searching for name, it goes in the order of local, nonlocal, global, and then built-in names. Professor also showed us an example of local, nonlocal, and global variable. Prior to this example, I never really understood what global does and I have never encounter nonlocal before. I found the python visualizer really helpful when going through the example, because it list what the variable is assigned to in different frame (eg. In global frame, spam is assigned to “global spam”, while in scope_test frame, spam is assigned to “nonlocal spam”).

After finishing the python memory model, Professor Heap started the topic of tracing method. I found tracing not too complicated for most of the function, as most of the functions are pretty straightforward. Determining the output of a function would not be very hard as long as you understood what the function is supposed to return. However, when tracing recursion function, Professor suggested that we should not trace too far. We should first trace the simplest non-recursive case. Then we should trace the next most complicate case, and plug in the results obtained from the simplest case, and repeat the previous steps.

On Wednesday, Professor Heap started off looking at the Fibonacci recursive function. Professor Heap pointed out that the function made a lot of redundant calls when computing the nth number in the Fibonacci sequence, especially when n is very large. However, if we could record each number in the sequence into a table, then the efficiency would be improved. Of course a lot of programmer had already realized this solution, and they called it memorization. Memorization records value into a table (dictionary usually), and when it is called, it would look up the corresponding value in the table. The original function is only run when the input is not in the table. After computing the output, it would be recorded into the table to prevent redundant calls. In this way, the efficiency can be improved by a lot; thus looking for large Fibonacci number would take as long anymore!

Mid-Term 2 Results , Property, and MapReduce (Week of Nov. 18th)

The TA’s for this course marked really quickly! It only had been a week and Professor Heap had already returned the Mid-Term back to us. I did generally well on this Mid-Term, and I believed the results truly reflects my knowledge on recursive tree structure (including binary tree as well as binary search tree). For question 1, it asked us to return a tuple containing the number of interior nodes and the number of leaves in the tree. Since I was not really familiar with tuple, I decided to write two helper functions within the count_node function: one function would count the number of interior node while the other would count the number of leaves. count_node would then call upon the two help methods and return the intended result as a tuple. For question 2, it asked us to return the number of nodes with value that was even. This question was pretty straightforward; the code for this function was very similar to the function that counts the number of nodes in a whole tree, just with a slight modification. As for question 3, it asked us to build a linked list of the path from root to minimum element. It was really similar to the question we did in lab08, where we had to use linked list structure to represent inorder traversal of a recursive tree. However, I for some reason checked for right child of the BST when I was writing my answer. Consequently, I got 2 marks off question 3 (and the whole Mid-term). Nonetheless, I am still very satisfied with the result!

This week we learned about the Property function as well as MapReduce, in which both functions were very new to me. One of the functions of Property is that it can restrict the attributes of an object. Property takes in four arguments: function that get the attribute, function that set the attribute, function that delete the attribute, and a docstring. They are all None by default. Professor Heap only went through the first two function arguments (get and set). At first, I was really confused in class, I have no idea when the program would invoke the get or set function. However, after reading the background material posted on the CSC148 website, I was more comfortable with Property as I got to see different examples on the internet. Similar to Property, MapReduce is very new to me, especially the Reduce part. I did not know how reduce work at first, so I decided to ask my friend to explain it to me. Now I understand that reduce combines elements of iterable into a single reduced value. I believe by reading background material and consulting friends in computer science, I have a better grasp on how to use Property and MapReduce.