Week 11: Recursion revisited

After working out recursive solutions for Assignment 2 and Assignment 3, my fascination with recursion has only increased. Moreso in Assignment 3, I find it amazing that recursive functions can span less than a dozen lines in order to achieve their purpose. However, even while the body of the recursive functions and respective helper functions often totaled no more than a dozen lines, it was often the case that the amount of time spent thinking was tremendous. I often found that I was always thinking way too hard about the implementation of a recursive function and always ended up hitting dead ends and writing very convoluted code. As such, one benefit of dealing with recursion is that I learned to slow down my working process and really think before I code instead typing a few lines thinking "This may or may not work..."

Week 8 SLOG: Binary Trees and Binary Search Trees

In week 8, we learned about Binary Trees and Binary Search Trees.

Binary Trees are simply trees that have a node, and at max have two children under each node.

Binary Search Trees (BST) are a special type of binary tree. They have three distinguishing characteristics:
(1) All data in BSTs are comparable.
(2) The data in the left subtree are less than the root node
(3) The data in the right subtree are greater than the root node.

As such, they are useful when holding information that needs to be compared because the structure of a BST makes it very easy and efficient to traverse.

There are three different ways to traverse a Binary Tree: Preorder, Postorder, and Inorder.
The names of these traversals are very self-explanatory.
In Preorder, the main node is visited first, then the left subtree second, and finally the right subtree.
In Postorder, the left subtree is visited first, then the right subtree, and finally the node itself.
In Inorder, the left subtree is visited first, then the node itself, then finally the right subtree.

Week 7: Abstract Data Types

An abstract data type (ADT) is a functional model of a specific data structure. Example ADTs are Stacks and Queues. It can be said that the implementation of an ADT does not define it, but rather the data held inside it and its associated operations. For example, inside a Stack, one can store sets of objects and push() and pop() items out. As such, abstract data types explicitly have two parts:
(1) a set of operations that can be performed on the specific ADT (2) a name to specify a set of data.

There is also an underlying principle regarding abstract data types, in that they hide information. For example, if I wanted to implement an ADT in the form of a Queue. I can do so by writing:

class Queue:
    ''' Represent a FIFO queue.
    '''

    def __init__(self):
        ''' (Queue) -> NoneType
        '''
        self._data = []

    def enqueue(self, o):
        ''' (Queue, object) -> NoneType
        '''
        self._data.append(o)

    def dequeue(self):
        ''' (Queue) -> object
        '''
        return self._data.pop(0)

    def is_empty(self):
        ''' (Queue) -> bool
        '''
        return self._data == []

And thus I have implemented a Queue for anyone to use. However, when I allow someone to use my implementation of this Queue, I only need to provide the operations and the name so that someone may utilize this fully. In other words, I do not need to let them know the implementation information, but they are still able to use the Queue if I give them the operations like: enqueue, dequeue, and is_empty.


As such, some information is abstracted to the user and hidden (the actual code), but the user is still able to fully utilize the ADT knowing its methods.