Sorting and Effiency

In CSC108, we were introduced to three kinds of sorting algorithms, insertion, bubble and selection sort. Again at the end of the CSC148 semester, we learned two more sorting algorithms, quick sort and merge sort. A sorting algorithm is an algorithms that puts elements of a list in a certain order. In the following, I am going to talk about various kinds of sorting algorithms and its efficiency. In addition, we usually use different big-oh notations to express the complexity of each algorithms. 

Quicksort is something new to me, but after compare the running timing for 1000 item list, it turns out that it is a very efficient sorting algorithms. By using quicksort, we usually find a good pivot so that we can compare the items after the pivot. If the item is larger, we put it in front of the pivot, and vice versa.
In most cases, we choose the first item of the list as a pivot, and repeat the quicksort until the list is sorted. This kind of algorithm is usually used for large size of data. Its best case complexity is o(nlogn), but worst cases is o(n^2).
Merge sort is different, it splits the list into half, sort the two halves, and merge the sorted list again. By using the recursion, we can sort the whole list using this technic. The whole process remains the same no matter what list is given so that its complexity is o(ologn) for all cases.

Insertion sort works by moving the next item to its proper position in the sorted part of the list at beginning. This sorting algorithm the most basic algorithms but not very efficiency. Its complexity is o(n^2) for worst cases.
Bubble sort works by going over the list and place each item to its final position. It compare each item to the whole list and swap the one after it so that after each iteration, the final item must at the right place. Despite its worst complexity is the same as insertion sort and selection sort, bubble sort is the most inefficient sorting algorithm according to lab10's analysis.

Binary tree sort is very similar to the merge sort algorithms, since the structure of a binary search tree provided a good path for sorting. In a BST( binary search tree) node, the left children must be less than the root, mean while, the right children must be larger than the root. Under this condition, to sort the list, we just need to compare half of the items in the list. Its worst complexity is o(nlogn) just as merge sort.

Selection sort selects the smallest remaining item repeatedly and puts it to the proper position it belongs. This algorithm have the worst complexity o(n^2) because for each item in a n size list, it has to go over the whole list to find its position as well as its best complexity. It is not very efficiency.

Regular Expression II

On the second part of the Assignment Two, we were required to write four module level functions. The first one is_regex, returns True if a given string s is a valid Regular Expression. When we first encountered the problem, we thought it was a piece of cake, until we realized that there were at least six different conditions we need to consider. The code was finished in about 80 lines, but it was a little bit messy. The second function is all_regex_permutations, returns a list of possible valid regular expressions that a given sting s and its permutations can be. The difficulty was mainly on part one since we already have some code from the Professor during the lecture that deal with string permutations. All we need to do is generating all the permutations and checking which of them are valid expressions. The third one is regex_match, which is also the hardest one to implement. It returns True if the given string s matches the given regular expression r. The intuition was similar to is_regex, however, there were some minor details that need to be noticed. The last one was to build a regex tree when giving a valid regular expression. It was not that hard if you can finish the first three.

Regular Expression I

Over the last couple weeks, we were working our ass off on the second assignment of the term, which is about the concept of regular expression. According to Wiki, regular expression is a sequence of characters that forms a search pattern, mainly for use in pattern matching with strings, or string matching operations. Our tasks were in two parts, the first one was simply straight. We were asked to write various classes for different combination of regular expressions. The simplest form of a regular expression is a single string of either 'e', '0', '1', '2'. Furthermore, we can add as many of '*' (stars) as we want at any of regular expression to form a new regular expression. Also, we can use '.' or '|' to combine two different valid regular expressions to form a new one. Basically, all we need to do is to write a parent class for the single regular expression, and inherit all the features to create children classes. The reason we can do this is that the regular expressions can be presented in the form of a tree structure. We did not run into any trouble when finishing the first part, but after seeing the second part, we realized it might be a big challenge. 

Recursion

Half way through the term and we are exposed to more and more recursive structure design in the course. Recursion is the process of repeating items in a self-similar way. A recursive function that we are talking about in python, is a function that executes the function itself repeatedly until a certain constrain is met. We have seen a few recursive structures so far such as 'stacks', 'nested list',  'linked list' and 'tree, those we usually called ADTs. Recursion is used widely in all these abstracted data types to get access from them.
The most obvious reason why recursive function works in such a data type like 'nested list' is that the list itself contains more lists, and each of them may contain more and so on. We can always use for loops and if statements to write functions on them, nevertheless, the use of recursion would be more wise. By using the recursive structure, all we need to consider is that the most simple senior and let the recursive function handle the rest by itself. When you using the recursion, not only your code becomes much clearer and simpler, but also it makes you looking like a pro!

List comprehensions, zip and filter.

In week 5 lab, we learned something new called list comprehensions, which can reduce your code whenever you have to loop over your list. Normally we use a for loop and an if statement within that for loop to modify the list. By using list comprehensions, we can easily use one simple line to do the job. For example, if we want to generate a new list of odd integers from 1 to 10, using for loops. First we need to create an empty list, then for each number in range from 1 to 10, we append only the odd number among all to the new list. By using list comprehensions, we can just write new_list = [ n for n in range(10) if n % 2]. Nevertheless, when the circumstance becomes too complicated, we prefer to use the for loops.
Zip is a bulit-in class in python, which helps a lot when we use list comprehensions. By defining a new class of  zip on two lists, it will return a list of tuples that containing each item in both lists. Of course one that uses zip() has to note that lists with different length have to be treated differently.
Filter is a bulit-in function in python that can be use in list comprehensions as well. When we generating a new list from the old one, we often set certain conditions on the item we want. The if statement usually does the job in a for loop. Here by using filter(function, iterable), it is equivalent to the generator expression [item for item in iterable if function(item)].

Hanoi Tower

In the first assignment of the term, we were introduced to a game called Hanoi Tower. This mathematical puzzle consists of three rods and different sizes of disks that can be moved onto any rod. Some rules apply to the game, that bigger disks can not be stack onto smaller ones. To win the game, someone has to move all the disks from the original rod to a destination rod within the least moves. The tricky part was that we had to deal with the more complex version.
Four rods were given, and we were required to find the most efficient solution on this task. Me and my partners followed the steps provided. None of us foresaw the difficulty of this assignment until step four which we had to write recursions for the solution. We suddenly realized that within four rods, the whole game changed.
Instead of three rods, using four rods gives us one more intermediate rod which makes the case more complicated. The strategy of playing this game is to choose a number between one and the number of total disks (call it n) in the game, call it i. We first move i disks onto either one the intermediate rods by using all four rods here. Then we move n-i disks onto the final destination rods using three rods that are available. Last, we move i disks onto destination rods using four rods. After a few rounds of moving, we realized that we could play the game by using recursion. Recall that recursion is a method that to run a function which contains this function itself. Here in this case, we have to use three recursion one after another. First, we use a recursive function of moving disks within four rods, then a recursive function of moving disks within three rods, and lastly another recursive function of moving disks within four rods.
The key to find the least moves is the choice of i. We discovered that within 10 disks, we chose i to be the middle number of the total n. However, when the disks increase to more than 10, we failed to find the most efficient way of solving the problem.

Inheritance

Can you believe that there are only 8 weeks until the semester ends? In the last week's lectures, we have been introduced a concept called 'Inheritance'. Inheritance is used to indicate that one class will get most or all of its features from a parent class. Another way to do the exact same thing is to define another class and modules. There are three ways that parent class and child class interacts: (1). Actions on the child imply an action on the parent; (2). Actions on the child override the action on the parent; (3). Actions on the child alter the action on the patent. In the lab of last week, we mainly practiced on how to apply the first two interactions. Also, we wrote some test code by using the unit test mode. During the lectures, a new concept called "Turtle" was introduced. I have not fully understand this whole new thing yet, and definite need to work on it more. After all, happy Chinese New Year to everyone, and wish you all the best!