Algorithm and Efficiency

      In the past couple of weeks, we learnt how efficiency verifies between different algorithms; a good algorithms can provide extremely high efficiency. In this case, it is pretty important to understand algorithms and learn how to evaluate the efficiency of functions.

      We have learnt several sorting algorithms in class: bubble, insertion, selection, merge, quick etc. They are using different method of sorting and, of course, their efficiency are different. However, through the study and the understanding of these algorithms, I find that we shouldn't choose algorithms only base on their efficiency on the worst case, since sometimes our function would be used in some kind of specific data, and that might be not in worst case. Consequently, when we are choosing algorithms, we should consider both the efficiency of the algorithms and the condition of our target data or what our function our be used for. In another word, this means that it is not enough to remember the efficiency but also understand the algorithm itself. For example, even both selection and insertion sort's efficiency are both O(n^2) in average, but we if we test it precisely, we can find that insertion sort is still faster than selection sort. The reason is that big-Oh notation only give us a rough idea of run-time, selection sort's run-time is always longer then insertion sort's.

Recursion makes coding easier

    Recursion is a kind of very computational programming style that is recalling the function itself. For example it is like dividing 10 by 3, and each digit is 3 because we are dividing 10 by 3 recursively. However, in a recursion there is a base case which  tells when the recursion should stop. Since we can use only one recursion function, which is always short, to deal with huge algorithm, recursion makes our coding easier. For example, the algorithm of Hanoi Tower is a typical recursion algorithm. Once we think it recursively, we can finish it in fewer lines of codes. Otherwise, I believe it should be several "for loop" with a LOT of if statements.
    To master recursion, I have two steps and one strategy. At first, you should always find out the base case. The base case does not only ensure the ending of the recursion, but also give you a primary understanding of the algorithm. After that, normally, you can just move one step up, and think about the situation which has only one recursive step. If you can deal with that, you are done with your recursion problem. The strategy I really love to use is list comprehension. I believe this is a very useful way to right the recursion function. For instance, when I come up with a recursion idea, I will describe it in  English. Since python is a pretty readable programming language, my description can always be easily transfer to a list comprehension format. For example,  my description is like do something when balabla, otherwise, I will do something else, for every item in the list.  SEE! This is almost a list comprehension format, and I am almost done with the recursion problem.
   

An useful example of OOP.

    After the study of object oriented programming, I came up with a idea that I want to write a review program for myself to cope with those courses with a lot of definitions. In this case, I decided to write all the definitions in a text file: one definition per line, and each phrase would be separated from its definition by a "*". I used ADT to store my definitions. Basically, it is a dictionary, each key is a phrase, and the corresponding value is its definition. All of these are finished in initialization. After that, i add several method to this class. Firstly, there is a  pop method, it means when I got the right definition, I don't need to review this phrase anymore. Moreover, there is a method called "get_question", which is a getting a random number in range(2). If it is 0, then the phrase will show,  i need to give definition, and  compare with the formal one. if it is 1, there would be a multiple choice.  Whenever I get the right answer of one question, the corresponding key would be pop from the dictionary. Also, there is a method to check if the dictionary is empty, and whether I would like to restore the definitions and begin a new round. I import this class to my main function, use some while and if statements to make it a loop, I am pretty sure it would be helpful for remembering both the definitions and the OOP programming in csc148.