Revisit

    For this SLOG post, I will be revisiting an old post and talking about how my opinion might have changed throughout this course... The post that I will be revisiting is actually my first post, "Why Geeks Should Write!".

    In that post, I talked about the importance of computer scientists being able to write. Throughout this course, I found that writing about  my weekly experiences and the material that I didn't understand allowed to to get a grasp of where I stand in this course. It allowed me to see what areas I need to work on to do well in this course.

    Throughout this course, I also found myself browsing quite a few forums about programming i.e. stackoverflow and /r/learnprogramming to ask questions or read about some concepts that I don't quite understand. Overall I think that writing a SLOG has helped me succeed in this course. I also still stand by my opinion about why geeks should write!

Assert, Unit Tests and Call Stacks

    This week we learned about asserts and how to make assertions. Assertions are extremely helpful when it comes to debugging because instead of executing your code line by line in the debugger or printing something after every line or so it will only print when the code does something you didn't expect it to do. In other words, it will print a message telling where things went wrong even though you didn't expect it to go wrong! Pretty useful eh?

    Another thing we covered was coming up with good test cases for unit testing. An exercise we did was figuring out what makes a good test case and what doesn't. So with that being said we starting to come up with test cases to see if our minimax strategy was working properly. We looked at different test cases for minimax being used with our game, subtract square, and we tried to figure out if the test case provided us with information on if our minimax was working. properly. We looked at 3 test cases for subtract square; 9, 10, and 11. After looking at the possible number of winning moves or losing moves each current total for subtract square provided, we concluded that either very little information is given or no information is given about whether or not our minimax was working properly. We then concluded that in order for us to come up with a good test case, the test case required more losing moves than winning moves. Thus we came up with test cases with only 1 winning move and 4 losing moves; 25, 27, 28, and 29. Since these test cases had only 1 winning move and 4 losing moves, the probability of winning all 4 games was (1/5)^4 which is about a 0.16% chance of our minimax NOT working properly but still leading us to the winning move by randomly selecting a move...

    The last thing we covered was the function call stack. At first I was like "what's a function call stack" and about 20 seconds later it hit me... It's pretty much what the name says it is... A stack of function calls. HAHAHAHA! We did an example to show how each function call is added onto the stack and once it has finished it's job it gets removed from the stack and we go back to finish the previous function call.

BST/Term Test 2

    This week we went back to work with the binary search tree. We previously learned how BST work and its uses but we never really got to the code for inserting and deleting an item in a BST. The insert function was pretty easy to implement because if the item we are trying to insert into the tree is less than the current nodes item we would call the insert method on the current node's left tree, but if it's greater than the current node's item we would call the insert method on the current node's right tree (this is when recursion comes in handy because the insert method is constantly called again on different subtrees in the BST until the item we are trying to insert is in its right place). We also worked on the delete function for the BST. I'll be completely honest here... Implementing the delete function was not as easy as implementing the insert function because it required a lot more thought into the possible scenarios that would happen when we delete a node in a BST. We first come up with the algorithm in plain English to see what scenarios we needed to cover:

    # 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

    After coming up with the algorithm in English, we put it into code:

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>
    '''

    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

    We also had our second term test this week... I feel like a did quite well on the test because I made sure that I understood all the materials by going over the lecture slides and examples and also redoing the weekly labs. But I guess I won't know how well I really did on the test because the TA's are still on strike. Hopefully the strike will end soon...

Linked Lists

    This week we learned about a new data structure called 'linked list'. A linked list is a group of nodes that represents a sequence. Each node in a linked list consists of a data and a reference (link) to the next node in the sequence.

   At first I didn't really understand what a linked list was, but after we worked on a few example methods such as the __getitem__ and append method for our LinkedList class, I started to get a better understanding of what it was and how it works. Since our LinkedList class only had a 'front' and a 'back' it was very clear that in order to access an item (that wasn't the first item or the last item) in a linked list we would have to iterate through the list i.e. walk along the list with a for loop. Another thing that also became clear to me and actually surprised me a bit was that reverse traversing ('walking backwards') can be extremely difficult!

    Due to the TA strike I had a slight bit of difficulty doing lab 07 with linked lists because even though I understood some of the things, there were also a few things that I didn't quite fully understand until I spent some time drawing out a linked list and seeing how to properly implement methods for the linked list.

Summary of Abstract Data Types (ADT)

    Over the past few weeks we've been working with recursion and a few new abstract data types. Since I've already talked about recursion in a previous post, I'll be talking about abstract data types in this post. An ADT specifies a set of operations (or methods) and semantics of operations (what they do), but it does not specify the implementation of the operations (that's what makes them abstract).

    The first ADTs that we learned in class were the Stack and Queue. Both stacks and queues are collections which means that they are data structures that contain multiple elements. They are also generic data structures which means that we can add any type of items to it (int, string, float, etc.). In class we implemented the stack and queue with python lists to use their built-in append, remove, and pop methods.

    A stack is last-in, first-out which means that the last item that is placed onto the stack will also be the first item to be removed from the stack. Our implementation of the stack had 3 main methods: pop, is_empty, and push. Since we implemented our stack as a list, we were able to use the pop method the exact same way for the stack and for the push method we used the list's append method. For the is_empty method we just compared our stack to and empty list, [].

    A queue on the other hand, is first-in, first-out which means that the first item that is placed onto the queue will also be the first item out of the stack (like a line if you were to line-up for something). The implementation for the queue was very similar to the stack. Both the queue method and is_empty method had the exact implementation as the pop method and is_empty method for the stack, but the dequeue method for the queue did not use the list's pop method, it used the remove method instead to remove the item at position 0.

   The next ADT that we learned and worked with was the Tree. Trees simulate a hierarchical tree structure, with a root value and subtrees of children, represented as a set of link nodes. Trees are made up of nodes or vertices with edges without having to cycle. The root of the tree is also known as the top node of the tree and a leaf is a node with no children.

    Another type of tree that we've started to work with is the Binary Search Tree (BST). A BST is a tree where each node contains up to 2 subtrees and each subtree itself is a BST. The left subtree of any node contains nodes with keys that are strictly less than the node's key and the right subtree of any node contains nodes with keys that are strictly greater than the node's key.

   Since BST keep the keys in order it is very easy to find any key in the tree without visiting all the nodes. For example, let's say we want to know if the BST contains the key '7'. We can look at the root and determine which which subtree the key could possibly be in. Since we know that 7 < 8 we can just look in the left subtree (that means we don't even have to look at the entire right subtree!). Now the current node we are looking at has the key '3' and we know that 7 > 3 so we can ignore node 3's left subtree and only look in the right subtree. And since we know that 7 > 6 we can then just look at the right subtree. BAM! We just found '7' in the BST without looking at all the nodes. Now you might be thinking "oh yea, big whop! we didn't have to look at a few nodes and we only saved like 1-2 seconds...", BUT YOU'RE WRONG! Imagine if you have a HUGE BST that is symmetrical in terms of height, each time you compare the keys you are eliminating half the possible subtrees you would have to look through (THINK OF ALL THAT TIME YOU'RE SAVING!).

    Now that we understand how BST work we can easily write some recursive code for it to determine if a BST contains a certain value.

    This first thing this code does is check if there even exists a BST. It then determines if the value we are looking for is less than the current node's value or greater than the current nodes value. If it falls under one of these categories then it will use recursion and call bst_contains on its respected subtree. But if it doesn't fall under one of these categories it will return True because the current node we are looking at contains the value we are looking for!