Last Impression

      It's the last week of CSC148 and it's been a pleasure to be in this course.
      We did three assignments and two term tests this semester. All of them have been fine. We did classes at the beginning, did recursion after that and did big O as well.
       Classes include the use of subclass, the use of a function implemented in the general class but depends on subclasses. And that was what we did in A1, we implemented a game Subtract Square.
      Recursion is mainly calling itself in the function, and we did a lot exercises. In A2, we used that in Minimax.
      The big O thing was the last thing we talked about briefly. We kind of did that in 165, just finding the upper bound of a function which now means the function of the running of a method. It helps us to make the functions run faster. That's A3, perfecting Minimax.
      In general, this course went well, although the strike was kind of a disruption. But despite the cancelled lab, this course was running well and Danny and Diane were doing their best.

Impression of Week 10

      The key point this week was efficiency.
      I remember we did two things. How to check if an element is in the list efficiently? And how to sort a list efficiently.
      We all agreed that the efficient way to check an element in the list is sort of like checking a binary tree. If the value we are checking is greater than the middle value in the list, check the right half of the list, otherwise check the left. This is an recursive function, we are always checking the middle value in the right or left list until we find the value or reach the end. In this way, we reduce the path from linear to logistic which is a huge step considering a really large list.
      But that function mentioned above need a sorted list which leads to our second problem of sorting a list. We considered the sorting algorithm we already known, bobble, insertion and selection. Although they are slightly different in their running time, but they are all portion to the length of the list squared. So what we can do is to reduce one length of the list into the lg of the length. Here we introduce a function called quick sort.

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

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

    >>> L = []
    >>> quick_sort(L)
    []
    >>> L = [17]
    >>> quick_sort(L)
    [17]
    >>> L = [3, 1, 2]
    >>> quick_sort(L)
    [1, 2, 3]
    '''
    if len(L) < 2:
        # copy of L
        return L[:]
    else:
        return (quick_sort([i for i in L if i < L[0]]) +
                [L[0]] +
                quick_sort([i for i in L[1:] if i >= L[0]]))

      Tracing one example, in each step, this function divides the list into three parts, the first element in the list, the left with all the value less than the first and the right with all the value larger than the first. In each step, we go through all the value, so the number of iteration we are taking is portion to the length of the list. But the number of steps we are taking is nearly portion to lg(length). So the running time of the whole function is portion to length*lg(length). Considering a really large list, this function will save a lot time.

Revisit

      I looked over my Slogs this week and find out there's nothing much to talk about.
      I'll talk about the first slog about why geeks should write. That one was a five-minute work and I did not realize that this will be marked so strictly. I did not think about it very critically.
      Geeks write to record, to communicate. That's my claim in the first slog. And now I think I need one more, writing helps geeks think. I got that thought when I was doing my slog. Writing helps me clear my thoughts and gets me organized. While writing, I found out things I knew and thing I didn't know as I was going over everything in my mind. Writing about things I knew helps me review, writing about thing I don't know makes me learn.
      That's how I felt about my slog. During the strike, my slog was the only extra thing beside the lecture. I wrote about things happened in the lectures and I gained better understanding of the course.

Impression of Week 9

      We did some test on Minimax.
      We were given three SubtractSquareState and we wanted to know what outcome of our Minimax meant our function was more likely to be correct. For states with current value 9, 10 and 11, the outcomes are all win or all lose. From that we cannot conclude whether our Minimax is working or not, so we would want a state with less wins to test our code on. In the unit test for Minimax, Danny used a state whose current value is 25 and this state has only one move to win. If that winning move is returned, which is nearly impossible for a random strategy, our Minimax is very likely to be correct.
      Later in that week, we saw some other functions.

      N = 5
      M = 2

      def f(N):
          return M * g(N + 1)

      def g(N):
          return M * N

      def h(N):
          return f(g(N))

      What we learned from them was when the name of a variable is used more than one time, which one should we refer to. The rule is the nearest one is what we need.

Impression of Week 8

      We didn't do much during the lecture this week because this week is a test week. We had a test on Wednesday and that wasn't as bad as I thought it would be, it was actually pretty easy.
      On Monday's lecture, all we did was one function: deletion of data from BST from a certain node. In this function, we have several things to consider: if the node is None; using the BST characteristics  to avoid unnecessary iterations; is the node a leaf or a internal node; what should we return?
      So, when implementing the function, we should take all of these things into consideration. As Danny suggests, we should have a list of all the possible situations:

def delete(node, data):
    ''' (BTNode, data) -> BTNode

    Delete, if it exists, node with data and return resulting tree.

    >>> b = BTNode(8)
    >>> b = insert(b, 4)
    >>> b = insert(b, 2)
    >>> b = insert(b, 6)
    >>> b = insert(b, 12)
    >>> b = insert(b, 14)
    >>> b = insert(b, 10)
    >>> b = delete(b, 12)
    >>> print(b)
            14
        10
    8
            6
        4
            2
    <BLANKLINE>
    '''
    # Algorithm for delete:
    # 1. If this node is None, return that
    # 2. If data is less than node.data, delete it from left child and
    #     return this node
    # 3. If data is more than node.data, delete it from right child
    #     and return this node
    # 4. If node with data has fewer than two children,
    #     and you know one is None, return the other one
    # 5. If node with data has two non-None children,
    #     replace data with that of its largest child in the left subtree,
    #     and delete that child, and return this node
    return_node = node
    if node is None:
        pass
    elif node.data > data:
        node.left = delete(node.left, data)
    elif node.data < data:
        node.right = delete(node.right, data)
    elif node.left is None:
        return_node = node.right
    elif node.right is None:
        return_node = node.left
    else:
        node.data = _find_max(node.left).data
        node.left = delete(node.left, node.data)
    return return_node

      List a todo list and follows it. That is a good way to be thorough and organized.
     

Impression of Week 7

      LinkedList was introduced to us this week. And we are using that to do iteration and mutation.
      The way to solve LinkedList problems is iteration. We go over every element in the linked list and find what we want, then we make mutations.
      For example, the __contains__ method we did in the lecture:

def __contains__(self, value):
        ''' (LinkedList, object) -> bool

        Return whether LinkedList (self) contains value.

        >>> lnk = LinkedList()
        >>> lnk.prepend(0)
        >>> lnk.prepend(1)
        >>> lnk.prepend(2)
        >>> lnk.__contains__(1)
        True
        >>> lnk.__contains__(3)
        False
        '''
        cur_node = self.front
        while cur_node:
            if cur_node.value == value:
                return True
            cur_node = cur_node.nxt
        return False

      In this example, we are checking if value is in a linked list. Our thought was to go over all the nodes in the linked list, check every one of them to see if it has the same value as value. So, we store the node we are checking in a variable called cur_node, as we go deeper into the linked list, cur_node changes. If cur_node's value is equal to value, we return True, if not, we set cur_node to the next node and keep checking. When we go over all the nodes and nothing is returned, that means there are no value in the linked list, so we return False.

Recursion

      Recursion is a pretty new stuff that we just learned in class. It is somehow different from what we already known about python.
      Recursion is used in functions to solve problem with unknown layers and cannot be solved simply by for or while loops, for example, checking elements in arbitrarily nested-lists and that is the main problem that we've trying to solve with recursion so far. Recursion and loops are doing the same job which is repeating some lines of code, but the difference between them is that when recursion is used in a function, it is calling the function itself inside this function.
      This is an example of recursion:

    def sum_list(L):
        ’’’

        (arbitrarily nested list of int or int) -> int
        Return the sum of all ints in L.

        >>> sum_list([1, [2, 3], [4, 5, [6, 7], 8]])
        36
        ’’’

        if isinstance(L, list):
            return sum([sum_list(x) for x in L])

        else:
            return L

      This function is summing all the elements in the list up. The recursive idea in this function is that we keep looking inside nested-lists until there are no nested-lists left. As we can see in this function, a recursion contains an if statement. This if statement is important when we are trying to make a recursion. How do we so that?
      First, we need a base case which can be done without recursing. Base case is also the thing we are looking for using the recursion. In this case, is when L is an int, so that we don't need to look inside lists to find int and there is no need so sum up an int so we return that int. Now we have our first part of the code. Then we need to consider other cases. If L is a list, we should check the elements in L. If the element is an int, we return it and if it is a list, we keep checking the elements inside it. This is where we need recursion. We call this function on every element in L, so that this function does what we want. Using a list comprehension to collect the results and sum them up. The recursion basically looks like this: 'if base case, else: recursion'.
      When running this function on the doctest, the process should be as follows:
      sum_list([1, [2, 3], [4, 5, [6, 7], 8]])
-> sum([sum_list(1), sum_list([2, 3]), sum_list([4, 5, [6, 7], 8])])
-> sum([1, sum([sum_list(2), sum_list(3)]), sum([sum_list(4), sum_list(5), sum_list([6, 7]), sum_list(8)])])
-> sum([1, sum([2, 3]), sum([4, 5, sum([sum_list(6), sum_list(7)]), 8])])
-> sum([1, 5, sum([4, 5, sum([6, 7]), 8])
-> sum([1, 5, sum([4, 5, 13, 8])])
-> sum([1, 5, 30])
-> 36
      Basically what recursion does is it stops and return stuff when we find what we need, int for example, if not we keep checking.

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!

week 3's topic: Why Geeks Should Write?

I saw this topic after I finished my week 3 SLOG!!! God!!

For this topic, I think I'm gonna start with the word geek. Geek should refer to someone who is super smart and has inadequate communication with others. Those people who might have issue to talk with others or they are too busy doing their work and have no spare time. Why do this kind of people write? It seems obvious right now. To fill in the communication gap between them and others.

For them, writing is a good way to record and show others their work. They cannot simply go around the world and tell everybody they meet what they did in order to publish their work. If he just talk to people about his work, there is no guarantee that others won't just stole his work and claim that it is theirs. But, as long as they write it down, they make it sure that their work can be read all over the world. And provide an evidence of proving his work.

Secondly, it provides a chance for them to communicate with others and show their world to others. Some geeks are not understood or accepted by others for their different behaviours. Writing seems to be a good way for them to express themselves and get people to know about their thoughts, their own minds. Definitely better than speaking as you got to arrange your word when you are writing and in this way you express better.

Those are the reasons I can think of for now, I'll add things if I come up with new ideas.

The Third Week's SLOG

    It's already the third week of this semester and the SLOG starts as usual! Why did I say as usual? I've done this last semester for 165 which was also taught by Danny!
    This semester, in the beginning, we are doing class, which we briefly talked about in 108. This week, we are discussing subclasses.
    We implement a general class, and then use subclasses to implement the different consequences. As Danny did in the lecture, a general class is Shape, functions like draw and get_area are in the class but they cannot be implemented in the general class as they differ in different shapes. What we did in this is: raise NotImplementedError: 'Need a subclass.' Also, using a subclass, the subclass should look like this: class Square(Shape), with the name of the general class in it. And, in the __init__ function of the subclass, we are supposed to call the function __init__ of the general class as we are going to use the functions in the general function.
the codes are:

    def draw(self, t):
        ''' (Shape, Turtle) -> NoneType

        Draw self using t.
        '''
        raise NotImplementedError('Need a subclass')

in the subclass:

from shape import Shape
import turtle

class Square(Shape):
    '''
    Represents geometric square lined up with axes

    position: inherited from Shape
    base: float               --- length of base of this Square
    '''

    def __init__(self, x, y, b):
        Shape.__init__(self, x, y)
        self.base = b

  
As for the  draw and get_area function in the subclass, they are implemented. So when we run the subclass, these functions in the subclass will completely replace the functions in the general class in which we raise an error. But when we run the general class Shape, it will still result in an error as the general class will not be influenced by any change we make in the subclass.