Week 11

This is the last topic of CSC148 --- sort and efficiency.  The sorting methods we are looking at put a list of items in an ascending order.  We've done different kinds of sorting methods in CSC108, including bubble sort, selection sort and insertion sort.  But in CSC148, we are digging more into the sorting algorithms and learning to analyze their efficiency on different sizes of lists, with the addition of some new sorting algorithms (including quick sort, merge sort, count sort, built-in/tim sort).  In order to do the running-time analysis, the 'big-oh', O(g), is being introduced.  The 'big-oh' describes the algorithm's behaviour over a large input of size n.  I haven't heard of the 'big-oh' before so the idea was a little bit vague to me.  But after Professor Heap explained it, it becomes much clearer to me.

There are two very important, new sorting algorithms introduced.  One is quick sort, the other is merge sort.

1) Quick sort picks a pivot and puts values greater than the pivot value to the right of the pivot and values less than the pivot value to the left of the pivot.  After doing that, the pivot value is at the right position.  It continues to pick pivots on sublists and quick sort the sublists.

2) Merge sort splits the list into halves recursively, sort each half and merge them together.  

In the average case, both sorting algorithms are O(nlogn).  This is more efficient than the sorting methods we learnt before.  To fully understand and get familiar with these sorting algorithms, I practiced writing their codes on my own.  And then I get to understand their 'big-oh's as well.  For quick sort, it chooses the pivot logn times and for merge sort, it divides the list into halves logn times.  And each partition has O(n) complexity.  Therefore, the overall complexity is O(nlogn).

However, it is not always the case.  For example, in the worst case of quick sort, the complexity is O(n^2).  So we need to analyze best, average and worst cases of sorting algorithms respectively.  In the last lab, we tested three situations for each sort: 1) random list  2) sorted list  3) sorted and reversed list.  After we transform the data into graph, the graph gave us a very clear image on how different sorting algorithms perform.  Moreover, the performance also depends on how the codes are written.  I discussed a lot with my partner to figure out why different codes result in better/worse efficiency. 

In addition, we looked at count sort which sorts consecutive integers.  And there is the very efficient built-in sort (i.e. tim-sort).  By testing it in the lab, we found it much faster than any other sorting algorithms.  But it seems like it is also more complex comparing to the other ones.  Even though I studied the above sorting algorithms, it was still quite challenging for me to analyze the ones in the test.  I still have to practice more about the 'big-oh'.

Week 10

This week we finished assignment 2 part II.  In the first 'is_regex' function, we have revised so many times since there are a lot of cases needed to be considered.  It is also tightly related to the 'build_regex_tree' function.  Their codes are quite similar to each other.  As each regex type has very different form, it is difficult to put them together.  The hardest part I found was to check long regex with parentheses, since it takes a long time to figure out how to separate BarRegex and DotRegex into two parts to check if each part is a regex.  

I didn't expect myself to finish writing 'all_regex_permutations' so quickly.  When I first read the instruction, I thought it was really hard to do it.  But it turns out that it is quite a short function to write.  I think it is probably because I've got better with recursion.  

This week's lab is really tough.  I understood the instruction and our TA helped us a lot and gave us some hint.  However, we still didn't manage to find a way to write the function.  I found it is especially challenging to do recursion on linked list node and binary tree node classes.  I need much more practice on that.  

Week 9

The topic we are working on is binary search tree for this week.  Basically, binary search tree presents the nodes in a very orderly way.  Nodes greater than the root value is in the right tree and nodes smaller than the root value is in the left tree.  Based on this special property of binary search tree, it is much more efficient to implement methods, such as finding a node.  If the item is bigger than the root value, it is certain that it is in the right subtree; if the item is smaller, it is certain that it is in the left subtree, and so on.

In the insertion and deletion function, we need to assign a new variable to the original BTNode.  After some tracing, I realized that the new variable makes an alias with the original one, so that when we change the original node's left or right subtree, the new variable is being changed as well.  That's why we can return the new variable in the end.

Based on this property, functions can be written recursively by calling recursion on either the left tree or the right tree.  In the lab, we practiced different ways of writing the same function.  

We also did Exercise 3 this week.  It is the hardest exercise I've ever done.  The sum_to_deepest function took me quite a long time.  I didn't think of using recursion involving decreasing the index over each recursion at first.  The make_tree function was not so hard to figure out at first, but the auto-marking reported minor mistakes for several times.  There are some cases that I didn't consider.  Also, even though I checked the docstring using pep8, there was still one more error reporting.  Luckily, the due date has been extended so I could fix those small problems.

Week 8

We are dealing with the 'LinkedList' now.  It is quite different from other classes we've learnt before.  It links a LinkedList object with another LinkedList object, one after another.  The class itself is harder to understand, so are the functions.  Adding or deleting an item from the LinkedList isn't so hard to figure out because it simply involves assignment of the attributes to the new values.  I found the 'reverse' function very confusing.  I couldn't even manage to trace that function.  It starts to get more and more confusing with recursion and things like 'self.nxt' or 'self.nxt.nxt'.  Also, there are two different ways of building a LinkedList.  One is that an item points to another LinkedList with all the remaining items.  The other one is an item points to another one (and another and another....) so that we need a 'node' class.  Overall, this class seems a lot more complicated than the ones we did before. 

Moreover, I found this week's lab quite challenging for me.  I have not fully understood how to manage linked list yet.  The functions all require some recursion in them.  It is not easy for me to figure out the recursion inside LinkedList.  I had to spend time working on this lab again.