Week 11

Recursion is an extremely important topic. Week 5 I talked about recursion. At that time, recursion seemed quite hard to me. I found it very difficult to trace recursive code and also writing it was quite hard for me. I hated recursion back then. After assignment 2, when we had to write recursive code, I kind of started to get the hang of it but I still wasn't good at it. I was still finding recursion hard. In test 1, I lost most of my marks in the question where we had to trace recursive code. For test 2, my main focus was to understand recursion completely and be able to write recursive code perfectly. After studying it properly for test 2, I finally understood recursion. Since then, I have started to find it easy. Whenever I am attempting a question now, I always think why I found it so hard because now it seems so easy. I was going through some of the SLOGs, I felt many people found it easy and interesting but there were a few who also found it hard. Overall, majority loved recursion and thought it was quite easy. This week we discussed the strategy 'Minimax' which we had to code for our assignment 2. Minimax is only thing that I hate the most in this course. I feel it is something that I can never code right.

Week 10

We had our term test 2 on the 11th of March, which is why we only had one lecture this week. I found term test 2 a bit harder than term test 1, but overall it went fine. This week we studied more about binary search tree, we implemented an insert and delete function. For the delete function, we went over the algorithm first in plain English and then translated that to python language. I thought this was a perfect way to do the coding, it made it quite easy. I will definitely follow this technique in the future. This is how we did that:

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 not node:
        pass
    elif data < node.data:
        node.left = delete(node.left, data)
    elif data > node.data:
        node.right = delete(node.right, data)
    elif not node.left:
        return_node = node.right
    elif not node.right:
        return_node = node.left
    else:
        node.data = _find_max(node.left).data
        node.left = delete(node.left, node.data)
    return return_node

This was extremely helpful. 

Week 9

Finally we submitted assignment 2 on the 5th of March. Implementing minimax was a tough job. The coming week we also have term test 2. This week we talked about linked lists, which are linear sequences of nodes. We defined two classes in lecture; LLNode, to represent a single node and a wrapper class, LinkedList, to represent the list a whole. We also talked about traversing a linked list and mutating a linked structure. In the LinkedList class we implemented functions to prepend and a contains function as we did for the binary trees. I found the code for the contains function for linked lists much easier than the one for the binary trees. There were fewer lines of code as well. Here is an example of a linked list and the code for the contains function:

 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
        '''
        current_node = self.front
        while current_node:
            if value == current_node.value:
                return True
            current_node = current_node.nxt
        return False    

Since assignment 2 was due, most of our lecture time was used for discussing the assignment, which was pretty useful, and so we didn't cover much material.

Week 8

The coming week assignment 2 is due, my partner and I have been working on it the whole week. Assignment 2 is quite hard especially minimax. This week we studied about binary trees. A binary tree is a tree with branching factor 2. The children are called the left and right child. We talked about tree traversal, there are three standard orders in which to traverse; in-order traversal, pre-order traversal and post-order traversal. We also talked about binary search trees. This is an example of a BST:

In lecture we wrote some code for binary tree node. We implemented a function which returns whether the binary tree contains the specified value. We wrote two different versions on this function.

def bst_contains_v1(node, v):
    ''' (BTNode, v) -> bool
    
    Return whether the binary tree rooted at node contains v.
    
    Assumption: node is the root of a binary search tree.

    >>> b = BTNode(5, BTNode(3, BTNode(1), BTNode(4)), BTNode(7))
    >>> contains(b, 17)
    False
    >>> contains(b, 5)
    True
    >>> contains(b, 3)
    True
    >>> contains(b, 4)
    True
    '''
    if v == None:
        return False
    elif v == node.data:
        return True
    elif v < node.data:
        return contains(node.left, v)
    else:
        return contains(node.right, v)

I found this version to be easier than the other one.