Impression of Week 6

    This week, we met a new class - Tree. And we are implementing a huge amount of recursions inside this class. This class is basically nested-list inside nested-list but in the form of  nodes and children. So whatever we are going to de with the tree, we have to go over every node and its children and this is where recursion fits in.
    In the lecture, we did the function contains which is used to check if a number is in a tree.
    To implement contains, first we start with simple tree which is just a leaf with no children. We check if the root value is equal to the given value. And now we have the worst part of the function:
            def contains(t, v):
                  if len(t.children) == 0:
                      return t.children == v
                  else:
                        ...
    Now the question is what if the tree has children and its children have children? Recursion!
    The thought is, we have to check every node to see if its root value is v and check if v is in its children or children's children until we find all the leaves and check all of them. Checking a leaf needs the same code as in the if statement we just implemented checking a node needs the code to check its children and its own value. As the function will return a list of boolean outputs, if v is in the tree, at least one True should be in the list. Now we have the code:
                 else:
                       return t.value == v or True in [contains(c, v) for c in t.children]
    Also, we can make the function contains a special function __contains__. By doing so, running the function would be using 'in'.
           >>> t = Tree(3)
           >>> 3 in t
           True

    On Wednesday, we did a recursion called leaf_count which has basically the same idea. If the tree we are checking has no children then it is a leaves, so return 1. If not return nothing.
Here's the code:
             def leaf_count(t):
                   if t.children == []:
                        return 1
                   else:
                         return sum([leaf_count(c) for c in t.children])

Impression of Week 5

     This week, we learned more on recursion.
     It was snowing heavily on Monday and the TTC was delayed again. But I luckily made it to 148's lecture ;)
     On Monday, we did the quick sort using recursion first. The basic process is picking the first element and sort those greater than or equal to it to the right and those less than it to the left and repeat this process until all the elements are in the right position.
    Here's the code:

def quick_sort(L):
    ''' (list) -> list

    Return a list containing the same elements as L in ascending order.

    >>> quick_sort([])
    []
    >>> quick_sort([5])
    [5]
    >>> import random
    >>> L = [1, 2, 3, 4, 5, 6, 7]
    >>> random.shuffle(L)
    >>> quick_sort(L)
    [1, 2, 3, 4, 5, 6, 7]
    '''
    if len(L) < 2: # there's nothing to sort
        return L
    else:
        return (quick_sort([x for x in L if x < L[0]]) + 
                [L[0]] + 
                quick_sort([x for x in L[1:] if x >= L[0]]))

The recursion here is for those lists who have more than 1 element that is to say can be sorted. But in this code, we are not checking the order of the sequence but we keep sort things and dividing list up until the length of the list remains is 1.
      After that, we did the parenthesizetion using the ADT we coded before. Noticing that the computer can only see one character at a time, we are using Stack to store the parenthesis we see so far and check to see if they are in the correct position.
     Here's the code:

def balanced_delimiters(s):
    ''' (str) -> bool

    Return whether the brackets in string s are balanced.

    Assume: Only delimiters are brackets
    >>> balanced_delimiters('[({])}')
    False
    >>> balanced_delimiters('[({})]]')
    False
    >>> balanced_delimiters('[[]')
    False
    >>> balanced_delimiters('[(){}]')
    True
    '''
    st = stack.Stack()
    for c in s:
        if not c in '(){}[]':
            pass
        elif c in '({[':
            st.push(c)
        # now must have c in ')}]'
        elif not st.is_empty():
            c2 = st.pop()
            if ((c == ')' and not c2 == '(') or
                (c == '}' and not c2 == '{') or
                (c == ']' and not c2 == '[')):
                return False
        else: # prematurely empty stack!
            return False
    return st.is_empty() # better be empty at the end

Basically we are checking the type and the order at the same time, so using a stack which is a first in last out thing is reasonable as the first half of parenthesis should appear last in the application.

     Wednesday was the term test, so no lectures.

Impression of Week 4

    The forth week, we did recursion. It is a function but it's using itself in the function. Recursions are used to solve questions that requires unknown loops to check the nested-list inside the nested-list. For example:
 def rec_max(L):

    ''' (list or int) -> int

    Return L if it's an int, or the maximum int in L,
    a possibly nested list of numbers.

    Assume: L is an int or non-empty list

    >>> rec_max([17, 21, 0])
    21
    >>> rec_max([17, [21, 24], 0])
    24
    '''
    if isinstance(L, list):
        return max([rec_max(x) for x in L])
    else:
        return L

In this function, the function re_max is called again and again until we find the elements that are not lists and the loop stops.
We did a lot of tracing in the lecture and in the tutorial, starting with depth 0 and moved on to more complicated examples gradually. We can also find the docstring by calling and tracing examples, just like we did in the tutorial.
By calling non-lists or empty list, we get the special cases of the function. How I understand this is checking the 'else:' and checking the build-in method called in the recursion. Then we check examples with more depth, and we can conclude the docstring and the assumption.

The first term test is next week, wish everyone a good grade!