Week Eleven - Sorting and Efficiency

Week Eleven -  Sorting and Efficiency

Efficiency has not really become a huge concern to me this term, but this is mainly because of the fact that the data we are dealing with right now is relatively small. However, in real world, this is definitely not the case. In real world, the data structures are often huge, and if the program is not efficient enough, it is can take more longer time to run and reproduce the result. Therefore, in my opinion to optimize the run-time should always be a goal to achieve for a good programmer. This week, we discussed several sorting algorithms,  some are more efficient than other, and I will talk about them below:

Selection Sort

Selection sort is very easy to code and understand, in selection sort you have an index 'i', which split the list into two parts, all the indices smaller than 'i' are the sorted part, and the indices equal or greater to 'i' are the unsorted part. You would first make 'i' equal to index 0 (which means the sorted part of the list is empty and the unsorted part is the whole list), and you would move 'i' to the end of the list. Each time you move i down by one, you can find the smallest item in the unsorted part and swap it with the object at 'i' (this can be done using tuple unpacking). There is no best, average, or worst case because no matter how you arrange list it will have the same number of operations with respect of the lengths of the list. The run-time is always in O(n^2) where n being the number of items in the list. (when i is 0, you will make n-1 comparisons, then n-2, n-3, n-4 and so on. so at the end when you sum up all the comparisons it will be O(n^2)).

Insertion Sort

Insertion sort is similar to selection sort in some ways. It has an index 'i' and a unsorted and sorted part of the list. But in insertion sort you would "insert" the item at index i to the correct place in the sorted part. (To do this you might have to shift some of the item in the sorted part in order to insert i). Different than selection sort, insertion sort actually have a best case and a worst case. The best case is when the list is already sorted, therefore no shift is required to make. However, the worst case is when the list is in exact reverse order, then you have have to shift every insert. In the worst case the run-time is also big O(n^2), similar logic with the selection sort can be applied here. 

Quick Sort

Quick Sort is a new algorithm we learned in this course, I personally really liked this sort because the algorithm is straight forward and the code is extremely easy to write. This sort shows how powerful recursion can be sometimes (also the merge sort below). In the quick sort, you can pick a pivot, then you compare all the other elements to the pivot. All the elements smaller than the pivot will be in one list and all the elements greater or equal to the pivot will be in another list. Then you call the quick sort on those two list separately. The worst case can occur when all the items are always greater or equal than the pivots or all smaller than the pivots (i.e. one sub-list is created). In that way the run-time is going to be in  O(n^2), the problem is however able to be avoid by using the random number generator to generate a new pivot each time, then the run-time is going to be O(nlog(n)) where n accounts for the comparison.

Merge Sort

Merge Sort is also uses recursion, the idea is that you keep cutting the list a half, then you sort the left side of the list and the right side of the list, then you would put them together. (kind of like binary search) There is not much difference between the worst and average case of merge sort. Similar to quick sort the run-time is O(nlog(n)), one thing to note is the worst case run-time of merge sort is actually the best/average run-time of quick sort.

Week Ten - Assignment 2

Week Ten -  Assignment 2

I have spent a relative long period of time on assignment two, especially part two, it was giving me a lot trouble. The first design part was quite easy and straightforward, you can write it in literally one day if you understand the features of the regex expression pretty well. However, I did not my design, I created a class to classify leaf and a class to have one children and one class to have two children. This way works, but I don't think the relationship between different regex expression was characterized well using this approach. On the other hand, the instructor created several inheritance relationship to link the classes. I think this approach is much more clearer than what I did. 

However, part two was the challenge part in this assignment, I did this part twice. When I first did it, I did not look at the hint on piazza. So I break on the regex expression on brackets to produce a nested list. And use the nested list to check validity of the expression. This approach worked, however it only works on valid strings. So an exception can raise if you try to check something like this ")2.(1|1))", since the order of the brackets is incorrect, the method that converts string to list will go out of bound. Moreover the runtime was extremely slow on the function all_regex_permutations when the length of the string get larger. It actually resulted in a OutOfMemoryrError when the length get to greater than 6, I think there are just too many recursions for the computer to handle and eventually caused it use up all the memory. So, I decide to try a different approach for the assignment (it is really hard to give the nested list approach up, because I spent so long to figure it out). The second time, I used the way instructor assignments. I have to say the hint was so useful for the assignments, it kind of give the solution away already. If I were to figure this algorithm out by myself, I think it will take a long time to do so. I think I really need to improve on those type of skills, but that is computer science really about. I used the approach where I look at each individual bar or dot, see whether it split into two valid regex expressions. If all of them doesn't, return false. This approach did not cause any exceptions, and it was much much quicker for the all_regex_permutations methods. Regex_match is little hard to deal with, but in my point of view, if you really understand the algorithm the instructor was talking about in class, it is actually not that band. I think the way to break a string into two parts to check for ‘*‘ is such a smart idea. If I were to do it, I probably will choose to do a loop on it or something.

Week Nine - Binary Search Tree and Big O

Week Nine -  Binary Search Tree and Big O 

This week I started to work on assignment two, part two with my partner. Although we have worked out a solution for all_regex_permutations, it was very inefficient as the size of the string grows larger. It can take upto minutes to run the method. I think to improve that method will be my main goal in CSC148 this week.

Speaking of efficiency, we also talked a little about efficiency, runtime and Big O in the lecture. The process time of an algorithm can be described using big O notation. For example, if an algorithms has a linear running time with respect to the size of the input, we can express this as O(n). (we normally would consider a very large input size to observe the runtime. Because in real-world problems, input size are normally fairly big. That is also the constant and breakpoint in the big O definition considered for). An example of the O(n) algorithm can be a linear search algorithm. There are other types of running time, for example, the following will be an example of having O(n^2)
for i in len(L):
     for j in len(L):
          a  = i * j
Or binary search, which will be an example of O(lg n). However, in some recursive functions the running time can increase exponentially or even factorially. (you really want to avoid this for larger input. I used several recursion method to do the all_regex_permutations, that is why it tooks so long to calculate). We looked at selection sort this week, I am really excited to more efficient sorting algorithm like merge sort this week. 

We also talked about binary search tree this week. We even did a lab on it to enhance the understanding. I personally found the lab pretty easy and straight forward. In some method, it is possible to use the characteristics of a binary search tree to make the method more efficient. Because in binary search trees, the first children contains all the object smaller than the root while the second children contains all the object larger than the root. Using this characteristics, many unnecessary comparison can be avoided.

Week Eight - LinkedList

Week Eight - LinkedList

We have been talking about linked list in the past two weeks of class. Two ways of implementing linked list is discussed and they both have a recursive structure. In the first way of implementing linked list, it contains a head (called item in the lab) and a rest. A head is a object (a value) and head is "linked" to rest which is either another linked list or None. The "rest" part makes this class a recursive structure, and we need to write some of the functions using recursion. I personally find this way of implement a bit confusing, it took me some time to fully understand this class and write functions for it. (recursion is required in some functions, which makes it harder and less straightforward to implement.) However, this data structure does have some advantages: i.e. in the lab we did last week, we re-implemented the Queue class using this structure, and some functions in Queue implemented this way turns out to be more effective than implementing using the list Object.

The second way of implementing Linked List is to use nodes, each nodes has a value and the reference to another node or None. This way of implementing is a way of using a wrapper class. I am still a bit confused about the structure of linked list this way. In my opinion, I think the class implemented in such a way that it is using the class LListNode to store all the informations. One thing I really like about this implement is that it keeps track of the size of the list. So, instead of writing a method and call it to compute the size, the size is automatically recorded, which save a lot work than compute it every time.

I found the lab this week is easier than last week, probably due to the fact that I am more familiar with LinkedList now. When I finished the lab this week I was able to go back and rework on the lab last week.