Sorting and Efficiency

During the last few weeks we learned about varies sorting methods and their running time. The methods that are new to me are count sort, quick sort and merge sort.I learned that the idea about quick sort is to choose pivots, and so the list is divided into two parts. Then use quick sort to move the objects smaller than pivot recursively to the left of the pivot, and larger object to the right. The run time of quick sort is O(n log n).

Merge sort keeps dividing the list by two and obtains n sublists, each contains one element. And it keeps merge the values into new sublists. Merge sort is one of the O(n log n) sorting algorithm and has a worst case run time of O(n logn). It's faster than quick sort's O（n^2). But it takes more space than quick sort. 

In the lab this week, we compared these two algorithms with selection sort, bubble sort, insertion sort and python's built in sort(tim sort). It turns out that those O(n log n) algorithms(quick sort, merge sort and python's built in sort) are significantly faster than other algorithms when dealing with large inputs. Quick sort is fast for best case and normal case, but is slower than the merge sort for the worst case. Python's built-in sort is the fastest in most of the tests.

First Part of A2

In discussion of A2 me and my partner had some split in opinions. He thinks that the children should be a list containing two regexes or strings. And I think that there should be children1 and children2, both as inputs. After that we checked several questions on piazza and decided to use my partner's idea. We found examples extremely helpful. It's hard to come up with examples but after that everything is pretty easy. So we will finished that today and hopefully there's no more problems.
Well what I also found hard:

• to understand what the program __repr__ returns is kind of difficult for us. We have to check the piazza to decide whether or not to let it return exactly same thing with the input value.
• to use property to make the symbol and children read-only.
• to use format to write the __repr__ method. it turns out to be easier to write but harder to think.
• to communicate with partner--- actually more important than come up or writing down codes.

Recursion

I think I misunderstand the topic of the second week so I changed it into recursion. The original one is about the process of how we did a1 but I'm really sorry that I didn't see the topic clear.

Recursion:

I found it really helpful to think from the really basic examples. I'll use the function nested_depth(L) as a example. The basic example is a non-list object and the function should return 0. Then the second basic example is a non-nested list. The function should return 1. And then the more complecated example, nested-depth one list. We should recurse function nested_depth on the inner- list and add that number to the outer-list and got 2.

Examples that provided on the slide:

    >>> nested_depth(3)
    0
    >>> nested_depth([1, 2, 3])
    1
    >>> nested_depth([1, [2, 3], 4])
    2

Since there might be one or more inner-lists and their nested-depth might be different, the method max should be used.

So we got:

def nested_depth(L):
    """
    Return nested depth of list L.
    """
    return (1 + max([nested_depth(x) for x in L] + [0])
            if isinstance(L, list) else 0)

So what really important is the examination of the basic cases and some of the special cases. And as moving on to the more completecated cases, it would be clearer that how and where to use recursion.

code sorce:http://www.cdf.toronto.edu/~heap/148/W14/Lectures/danny/W4/nesting.py



OOP and class design

In the study in CSC 148, one important concept is object-oriented program. This method is more significant in programming than other methods and save much more time. In the learning process of OOP, I found class designing important and made the code shorter.
What I've learned:

• property(attributes)
• How to write exceptions
• How to write type contract and parameters together
• Sub-classes (inheritance)
• recursion 

What I found hard:

• exceptions
• inheritance
• recursion

Hope I can understand more about my weakness. I already found the lab and tutorial very useful. I've learned and understand how to design a class completely in it. And hope I can make more friends who can teach me on this! XD