Week 7 Recursion

I would like to talk about Recursion for week 7 CSC 148 SLOG post. Although I've briefly talked about it on Week 5 tracing recursion and unit tests post, there are new materials that I learnt after posting my Week 5 SLOG. Recursion is very important in Python 3 as it allows the clients to check from a root to leaves in class tree.

I would like to go over the terms for tree as knowing these terms is very crucial in order to understand recursion. The terms are leaf, depth, root, internal node and arity.

The definition of these terms are based on Danny's Week 6 lecture note.
(Source: http://www.cdf.utoronto.ca/~csc148h/winter/Lectures/Danny/W6/w6.pdf)

Leaf - a node that does not have any children
Depth - Height of the entire tree - height of a node
Root - first one node
Internal node - a node with one or more children
Arity - maximum number of children for nodes
(Source: http://www.cdf.utoronto.ca/~csc148h/winter/Lectures/Danny/W6/w6.pdf)

I had problems understanding these terms when I first encountered. I thought that leaves which are located at the bottom of the tree in a tree diagram are roots. However, I soon realized that the first node should be a root which supports a whole tree.

First, I would like to  revisit my week 5 SLOG post. Week 5 was mostly based on tracing recursion rather than implementation of recursion. So I had no problem understanding the materials.

I posted the tracing count_elements  recursion problem that I had posted on Week 5 SLOG post below. (Lab 3 Source: http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab03/handout.pdf).

def count_elements(L):
    """ (list or non-list) -> int

    Return 1 if L is a non-list, or number of non-list elements in possibly-nested list L.
    """

    if isinstance(L, list):
        return sum([count_elements(x) for x in L])
    else:
        return 1
                              (Source: http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab03/handout.pdf).

1. count_elements('snork') -> 1  # since 'snork' is a non-list
2. count_elements([2, 1, 3]) -> sum([count_elements(x) for x in [2, 1, 3])
                                             -> sum([1, 1, 1])  # already traced count_elements(int)
                                              -> 1+ 1 + 1
                                             -> 3
3. count_elements([2, 1, 3, '[4]']) -> sum([count_elements(x) for x in [2, 1, 3, '[4]'])
                                                      -> sum([1, 1, 1, 1]) # already traced count_elements(int) and                                                                                                   # count_elements(str) before
                                                      -> 1 + 1 + 1 + 1
                                                      -> 4
4. count_elements([7, [2, 1, 3], 9, [3, 2, 4]]) -> sum([count_elements(x) for x in [7, [2, 1, 3], 9, [3, 2,  4]]) 
                                                           -> sum([1, 3, 1, 3])     # already traced count_elements(list of                                                                                                                                        # int) before
                                                            -> 8
                            (Source: http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab03/handout.pdf).

What I had the troubles the most were Lab 5 and Lab 6. For lab 5, I first tried to work alone trying to implement list_all, list_leaves, list_interior, list_if and list_to_depth at home. However, after 30 tries, I realized that I am not fully understanding recursion material. So I reviewed lab 3 and Danny's slides on recursion for two hours. But as I was not able to implement even a single method. I was so tired. That was when I decided to work with my friend as a pair to crack this problem.

The way he and I did to solve the problems for lab 5 is shown below.
1. First, I wrote codes for each method of a Tree and tried to run it.
2. My friend took a look at the outcome and tried to debug it by adding or writing some new codes in it.
3. Each of us takes a turn to debug the code until the result shows no problem.

Although we spent quite a lot of time doing this process, we actually achieved to implement all the codes. One thing I learnt through this process is that working together is more efficient if it is allowed. He and I were so happy that we solved the problem.

We tried the same thing for lab 6. At first, we had no clue on how to implement the methods for class BTNode. However, we tackled the problem in various perspectives and searched about binary tree to learn about what binary tree is. After two hours of coding at Bahen Centre, we completed all the implementation of methods for class BTNode. He and I were so glad that we were able to finish it. Although a programmer suffers lots of stress while coding, the feeling he or she gets when the implementation is done is really amazing.

During the lab 6 section, I tried to implement additional exercises posted by Danny and Diane. I posted the implementation for leaf_count method for class BTNode below in order to demonstrate my understanding on recursion.
       if t is None:
           return 0
       else:
           return sum([count(t.left), count(t.right)])

(Source: http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab06/additional.py)

def count(t):
    ''' (BTNode) -> int

    Return the number of nodes in BTNode t.

    >>> tree = BTNode(5)
    >>> count(tree)
    1
    >>> 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)
    >>> count(tree)
    7
    '''
    if t is None:
        return 0
    else:
        return sum([count(t.left), count(t.right)]) + 1

(Source: http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab06/additional.py)

As I fully understood recursion materials, I had no problem with lab 5 and 6 quizzes. I am
glad that I am taking Computer Science at U of T. I commented on other students' SLOG posts that are interesting. One thing I found was thatmost of them wrote on recursion. 

http://alexandraamatuzio.blogspot.ca/2015/02/recursion.html?showComment=1425098064316#c695105407004633210

http://lhzuigao.blogspot.ca/2015/02/summary-of-object-oriented-programming.html?showComment=1425098326916#c5293325936651694830

Week #6: Object-Oriented Programming Concepts

When I first thought of Object-Oriented Programming, I had no clue what this term means. However, as I started to study Computer Science, my knowledge in Object-Oriented Programming is improved. Object-Oriented Programming is a programming where we mainly focus on objects themselves instead of its way to get to the solution. Some examples of Object-Oriented Programming are C++, Java and Python.

Some basic components of Object-Oriented Programming are class, object, method, instance and recursion.

We already learnt what class is and how to create a class. I will implement only the init method for each class. I will also try to explain instances in Python.
For example,
class Cake:
    def __init__(self, candle, topping):
        """ (Cake, int, str) -> NoneType
       
        Initialize class Cake with candle and topping
        """
        self.candle = candle    # This can be considered as instance variable for specific instance
        self.topping = topping

We can use inheritance to use class Cake in other class like a class CheeseCake to pass the information that class Cake contains to a new class CheeseCake. I will also demonstrate class variable in class CheeseCake. Object-oriented Programming can have multiple inheritance.

class CheeseCake(Cake):
    Cake_List = []     #This is the variable class that is shared inside the class
    def __init__(self, candle, topping):
        """ (CheeseCake, int, str) -> NoneType

        Initialize class CheeseCake with candle and topping
        """
        Cake.__init__(self, candle, topping)

Method is based on object. For Python, we learnt that method is inside a class of an object.

class Feeling:
    def tired(self, feeling):
        #body implementation omitted

def tired(self, feeling) is considered a method since it is inside a class Feeling.

However, function is different compared to method. Function does not depend on object.
def hello(self, greeting):
    #body implementation omitted

def hello(self, greeting) is considered a function as it is not inside class of an object.

We can think of a method as a function that depends on an object like class.

Interestingly, recursion is also one of the basic concepts in Object-Oriented Programming.
As I've already covered this topic deeply in previous SLOG posts, I will skip this one.

Object-Oriented Programming has now become a significant part of our CS society. Although the only OOP I know is Python, I hope to learn Java and C++ during my third and fourth years at UofT. Another thing I found interesting is the number of OOP. There are more than 20 OOPs in the world. I guess I cannot master all of them. Instead, I will study 2 or 3 OOPs in depth for my future career.

Learning OOP is so interesting to me. Maybe, in the future, I hope to create a new OOP that is much easier than Python so that anyone can learn OOP.

Week 5: Tracing recursion and unit tests

Learning how to trace recursion in CSC 148 was an amazing experience. Although I had very little knowledge about it, Professor Heap taught us in details which helped my understanding. I also had a quiz on tracing recursion last week.

I would like to demonstrate my skills on tracing recursion. I will use the function count_elements that was posted on CSC 148 lab 3 made by professors. I will try to solve the first four count_elements questions that are posted as well.
(Lab 3 Source: http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab03/handout.pdf).

def count_elements(L):
    """ (list or non-list) -> int

    Return 1 if L is a non-list, or number of non-list elements in possibly-nested list L.
    """

    if isinstance(L, list):
        return sum([count_elements(x) for x in L])
    else:
        return 1
                              (Source: http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab03/handout.pdf).

1. count_elements('snork') -> 1  # since 'snork' is a non-list
2. count_elements([2, 1, 3]) -> sum([count_elements(x) for x in [2, 1, 3])
                                             -> sum([1, 1, 1])  # already traced count_elements(int)
                                              -> 1+ 1 + 1
                                             -> 3
3. count_elements([2, 1, 3, '[4]']) -> sum([count_elements(x) for x in [2, 1, 3, '[4]'])
                                                      -> sum([1, 1, 1, 1]) # already traced count_elements(int) and                                                                                                   # count_elements(str) before
                                                      -> 1 + 1 + 1 + 1
                                                      -> 4
4. count_elements([7, [2, 1, 3], 9, [3, 2, 4]]) -> sum([count_elements(x) for x in [7, [2, 1, 3], 9, [3, 2,  4]])
                                                           -> sum([1, 3, 1, 3])     # already traced count_elements(list of                                                                                                                                        # int) before
                                                            -> 8
                                   (Source: http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab03/handout.pdf).

This week, I learnt how to write codes for unit tests. However, I was not able to review the materials covered on Monday as I had my first CSC 148 term test on Wednesday. So I mainly focused on studying the previous course materials such as the basics of Object-Oriented Programming. I hope I can achieve high marks for this term test. Right after I finished my term test, I studied about unit tests for two hours. Although I had some trouble understanding the material, I managed to learn the course materials well. Although both queue and stack are basically lists, how we remove and return the removed elements are different. Stack is LIFO(Last In First Out) whereas Queue is FIFO(First In First Out). I realized how we can use lists to create new class like Stack and Queue. Writing codes for queue_list and stack_list was very easy for me as I already reviewed the materials. Although I have encountered unit tests in CSC 108, this was my first time writing codes for unit tests. I really love CSC 148 course. It always teaches me various things about programming.