Week 9: Complexity

One thing I love about CS is the logic involved. The signature approach to the permutation problem was really neat. It strike me that seeing and solving a problem from another angle can ultimately be the solution you're looking for. Except, how does one come up with a different approach? Unfortunately, I do not have an exact answer for this one. Perhaps you'll eventually come up with it if you expose yourself to the problem regularly.

This week's lab, we were confused by how you can call a Node and expect the function to find the appropriate class to solve the problem. Our TA explained that it was Dynamic Binding, where the function called depends on the argument or object.

For example,

class BST(object):
...
    def count_less(self, item):
        """(BST, object) -> int
        Return the number of items in this BST that are strictly less than
        item.
        """
        return self.count_less(self.root, item)
        # The line above calls BSTNode.count_less(item) because self.root is a _BSTNode
 ...

class _BSTNode(object):
...
    def count_less(self: '_BSTNode', item: object) -> int:
        """
        Return the number of items in the BST rooted at this node that are
        strictly less than item.
        """
        if self.item < item:
            return self.count_less(self.left) + 1 + self.count_less(self.right)
        elif self.item >= item:
            return self.count_less(self.left)
        else:
            return self.count_less(item)

# Strangely enough, it calls the class addressing None Nodes at the right time as well:

class _BSTNone(_BSTNode):
...
    def count_less(self, item):
        """(_BSTNone, object) -> int
        Return the number of items in the BST rooted at this node that are
        strictly less than item.
        """
        return 0

I'm still not sure how it works, so I Googled a bit. It's called late binding as well. It refers to runtime binding, as contrast to early binding that refers to compile time binding. (Source: http://stackoverflow.com/questions/10580/what-is-early-and-late-binding) That made absolutely no sense to me, just like the Wikipedia page. So I found this website: http://www.i-programmer.info/programming/theory/1477-late-binding-myths-and-reality.html

There's a detailed explanation with an example in C# language. I decided that I should probably worry about it later and spend time to look at this week's code and maybe practice a bit instead.