Week 11: Recursion revisited

No pun this time, just a few thoughts on how I've progressed through the semester on recursion. Reflections on my Week 5: Recurring thoughts about recursion.

Back when I started doing recursion, and after several simple examples/practice problems on basic recursion, I thought that I had a decent grasp on the concept. The examples mostly consisted of one simple check on types inside a list, with an else statement performing list comprehension on nested lists, which would then proceed to call itself and perform recursion.

Okay, so it's been 6 weeks, or roughly a month and a half of having extended my recursion knowledge and increased usage of recursion. Topics included mixing recursion with trees (trees, binary trees, binary search trees), linked lists, and with our second assignment on programming tippies.

Amendment: I'm not that good at recursion.

I had much trouble blending my ability to program trees and recursion. I couldn't really understand how the implementation of trees would be suitable for recursion, and even when I did, I struggled to implement them by myself. The examples seemed to flow so quickly and smoothly when Professor Heap performed them. This was also coupled with me not reviewing lecture material. Skip ahead a few weeks, and I managed to miss a few lectures on linked lists/binary trees. This didn't help my already lacking understanding of mixing recursion.

Quoting myself:

"""
Though I do struggle with some specific tree functions (such as the in_between exercise from lab #6), I do think that recursion can now be confidently added to my toolbox of useful Python tools. 
"""

I disagree wholeheartedly. Even after the second assignment and second term test, I realize that I still struggle with many of the recursive aspects of the newly introduced data types, for example, linked lists and trees, contrary to my own "update" on having "mastered" trees. Likewise, I still do hope to improve my own abilities and confidence on recursion, though with this SLOG post I'll refrain from commenting on my own prowess with such confidence.

Forgotten slog: Week 8: Linked Lists

So turns out I had this slog post saved into my drafts rather than having posted it, so a quick update to "fill-in" my missing week 8 slog post. (oops). Anyways, moving on:

This week's covered topic was of linked lists, an introduction to another data type, which to me, is a bit of a doozy. In essence, I think of linked lists as a recurring single-item list implementation with a little sprinkle of recurring trees. The way linked lists work is a single element "node" with a reference to another front "node" and "back node". This way, each node contains the element that you want to store, as well as the next and previous elements for manipulation. This notion serves as the list aspect, with the linked part commenting on the back/front references.

Let's examine this crudely drawn diagram. For demonstration, an arbitrary list could be:

[1, 2, 3, 4, 5]

A linked list would be:

[ 1 | x <-]------[->2 | x <-]------[->3 | x <-]------[->4 | x <-]------[->5 | x <-]------[->None]

The 'x' represent the pointer in which other nodes refer to them. We can see that the first element, 1, points forward as its "back" node is 2, while 2's front node is 1. This creates a linked aspect between the elements. Now for the implementation, this will explain why I see it as a single branched tree.

Each linked list has a front, which is of an arbitrary form LinkedList(<val>, front). Val points towards what you're storing, and front refers to another node, which would normally be another linked list. So, a LinkedList(<val>, LinkedList(<val2>, LinkedList(<val3>, None))) would be a nested linked list to create a 3 element linked list. Now, to perform and implement specific methods, such as append, delete, remove element, extend, reverse and all that jazz, you need to iterate over each node as per your function.

To do this, there are 2 methods: iteration and recursion. Using iteration, such as a one-way while or for loop, you check each element of the linked list one by one for your condition, perform the task, and then break the loop. It's almost identical to iterating over a regular list using "for i in range", except slightly more complicated. The other approach, which wasn't really discussed all that much in lecture was using recursion. This simplified the method bodies by reusing code from the method itself, called until the method was completed. Although recursion seems neater and is more concise, iteration for me works better as it comes more naturally to me. It's easier for me to grasp the concept of checking each item once over rather than attempting for simplify my code for a few lines' difference in method length.

So what's the benefit of using a linked list? Well for one, there are many many more operations that you can customize using a linked list. For example, as each element or node is unique in the sense of its data, in addition to its storage as a node, allows for more specific operations that would otherwise require more and more and more nested lists, which in contrast to its seemingly deceptive nature, would make the process more complicated should the standard lists be used.

Week 10: Midterm & Linked Lists

Whoops, another late post~

In this little entry, I'm going to recap the week of March 9th - March 13th, which consisted of one lecture and the second term test. Going into the Monday lecture I wasn't too prepared as I had missed roughly 4 lectures in a row due to another term test and sickness (but I'm all better now), meaning that this lecture was almost completely foreign to me. Before class, I had been reading the annotated slides on the CSC148 homepage, and was trying to fervently catch up on the material. I get to class, try my best to keep up, and attempt the worksheet.

Due to other tests, I only really spent about 6-8 hours studying for the second term test, which featured basically all the concepts that I wasn't too confident in linking together: recursion and trees, recursion and linked lists and linked list iterations. Piazza was extremely helpful, as were the professors and other online resources. In trying to answer other students' questions was when I found holes in my studying - in addition to failing the past test.

The cheat sheet on the exam was very helpful too, as one of the code snippets I put on it happened to be a slight variation to a test question, making the whole test just a bit easier. I couldn't remember exactly if a binary tree necessarily needed to be completely filled, so I took the gamble on deciding tree length. All in all, not too much CSC148 that week, but the test really forced me to catch up on concepts.

Week 9: Binary Trees, Binary Search Trees and Minimax

Whew, a delayed post from a whirlwind of a week. Unfortunately, I couldn't attend any of the CSC148 lecture offerings last week due to test and assignment conflicts, which meant that I had to spend this weekend and most of yesterday teaching and reviewing the material that I missed. With that, a little on last week's material: Binary Trees, a variant Binary Search Trees and the dreaded minimax algorithm.

So first off, binary trees, or BT for short, are a method of data/object manipulation that mimic a branching tree diagram in real life, except with the binary restriction, or a maximum of two branches per node. Using the diagram below (sourced from http://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/pix/tree1.bmp), the parent node is at the top 8, and each branch has a maximum of two children (or sub-branches, if you will).

The method can be used to store information according to user-provided restrictions per branch, and is essentially an extension of recursive programming. Examining the sample code snippet below:

class Tree:
’’’ Represent a Bare-bones Tree ADT’’’

def __init__(self, value=None, children=None):
    ’’’ (Tree, object, list) -> NoneType
    Create Tree(self) with root node value
    and 0 or more children.
    ’’’
    self.value = value
    self.children = children.copy() if children else [] 

The bare-bones tree abstract data type is instantiated recursively with children, in which the children become the "parent" and thus allows for new children, which then becomes the new parent for more children and etc etc. (Except with a binary tree, the init variables are limited to self.left and self.right for its corresponding left and right children). Using this class, it's possible to implement many manipulative methods, such as getting the height (the number of nodes from the parent to the last leaf, or children-less node), getting the arity (maximum number of branches), or counting the number of leaf nodes.

Now, binary search trees, or BSTs for short, are a subset of binary trees (which in themselves are a subset of trees), except with an imposed limitation of increasing node value from left to right. All values that are less than that of the parent node are added to the left branch, and similarly, all values that are greater than that of the parent are appended to the right branch. Using the following image (sourced from programminggeeks.com), let's traverse the tree.

Suppose the values were appended in this order: 8, 10, 3, 1, 14, 6, 7, 4, 13.

The value 8 is situated as the parent node, that much is apparent. Next, the value 10 is compared to 8. It is larger, and thus placed on the right branch. Next, 3 is smaller than 8 and is placed on the left branch; the branches for the binary tree node 8 are now complete, which means that further values to be placed onto the tree are compared with its children 3 and 10. 1 is smaller than 3, and now becomes the left child of 3. 14 is larger than 10, so it becomes the right child. Similarly, 6, 7, and 4 are sorted into their own tree, and the tree ends at value 13 becoming the final left leaf of the node 14. The BST is now complete in that all values can be scanned from left to right in accordance to its literal value from smallest to largest. To me, its implementation is very similar to that of the standard binary tree, barring a condition that would examine each value before being appended to the tree.

Finally, onto the topic of minimax and assignment 2. Assignment 2's main objective was to utilize a system to "plug in" our own methods to a pre-written set of methods provided by the professors. The game that we had to implement was Tippy, or tic-tac-toe with Tetris' Z/S tetrominos. This game was created purposely such that the first player to move was guaranteed a win no matter the actions of the other player: an ideal situation to implement minimax, an unbeatable computer.

After creating my Tippy state and functions, I looked to minimax. It was an algorithm that rated each move on a basis of -1.0 for detrimental, 0.0 for neutral or non-game-ending, and 1.0 for a winning move. By playing out every single possible combination of the board and looking for the best score for itself, the computer would then play accordingly. What stumped me for the longest time was integrating the scores into choosing a move. I had solidly implemented a fashion of rating the moves with their appropriate score, but struggled with deciding which move to play based on the said score - my AI stubbornly randomly chose a move despite there being an obvious winning move.

I consulted Prof. Heap for help, and the solution seemed much more simple than I had thought: I simply wasn't telling the computer that the highest score was the best move (that, and my recursion was a bit wonky). Ironing these little kinks out, my AI worked: it could now crush me every single time, just like all my math exams.

Week 7: Marked SLOG

@TA Note: Please mark my Week 5 SLOG on recursion.

Thank you very much!