Red Rover Red Rover

Perhaps the title of the week's post is a little stupid, but that is actually the first thought that occurred to me while practicing with linked lists. Red Rover is a game children play consisting of two teams (West and East) where the goal is to try and diminish a team to only one person. The teams shout out "Red Rover, Red Rover, we call [person's name] over" and the person who was called tries to run through the other team who has linked hands together. If they succeed in breaking the link, they are allowed to return to their team otherwise they join the end of the opposing team. There's a point to this, I promise. Linked lists, like linked hands in Red Rover are very similar in that:

1. Every node contains a value (like a person) and holds a reference to another node(another person). This allows the nodes to link together similar to a list.

2. When a Linked List consists of one node (e.g. person), it only points to None (i.e. no one) or a terminator that signifies the end of the list!

3. It is easy to insert and delete nodes from the list. Instead of forcing your whole team to move in order to make space for you when you join in Red Rovers, you may link hands without changing your position (though humans are limited to how long their arms are of course and it would be easier to locate a certain person if you did change your position). Linked lists allow you to change where each node references to, making it the optimal solution if you have to insert and delete many items. Due to the fact that there is no memory reallocation since nodes do not have to be stored contiguously in memory, it's quicker when dealing with a lot of data.

This may not have been the best real world example to explain linked lists but it was just a thought.


Reading Piazza last week made me realize just the large amount of posts that were asking how e5b can be solved without a helper function and with recursion. I hope this post sheds some light on how you would go about doing that.

Let's say for some reason, we are interested in finding the height in the left subtree and the right subtree of our tree separately. We could try to approach this similar to the nested_depth example that Professor Danny showed in class a while back, but that would be... rather difficult. That approach is much easier to implement when searching for a height taking into account all paths in the tree such as:

def get_height(self: 'BTNode') -> int:

    return 1 + max([self.left.get_height() if self.left is not None else -1] +

                            [self.right.get_height() if self.right is not None else -1])

(The above example could probably improved)
N.B. The above example uses Professor Danny's hint about using -1 as a depth for an empty tree to properly calculate the height of the tree.

But since we want the heights of two different subtrees, our function should run recursively and store into two different internal variables. This is made possible with the + (list concatenation) or list.extend() method. Usually you may pass parameters in your recursive function (which makes matters much easier in my opinion) unless you are instructed against it as in our assignment.

One of the useful tips I've learned throughout the exercise is to take one variable at a time if you're having trouble. That means write the internal variable and base case for one variable, then when that works implement the other.

The recursive function can take the form (as mine did):

def get_max_depth(self: 'BTNode') -> tuple:

    leaves = []

    internals = []

    # Base case and if statements here

    leaves = (recursive call goes here, and the + or extend)

    internals = (recursive call goes here, and the + or extend)

    return leaves, internals

I'll post one of my solutions a little later so as not to give it away. Stay classy.

Now to end with a completely pointless but funny picture I found:

 

Trees (week #6)

"Of all the trees we could've hit, we had to get one that hits back." - J.K. Rowling

That is exactly how I felt about exercise 4 for CSC148. Exercise 4 a) was not a difficult task, so long you followed the professor's advice about "working it out on paper before programming". It took me a few hours before it hit me while I was on the subway. I had found the task of creating a tree from preordered and inordered lists difficult until I realized the simple fact that all of the hints required were ALREADY written on the paper (silly me for spending 2 hours figuring them out myself), and that trees consist of subtrees (the main reason recursion is so useful). Implementing the recursion I found, was a breeze contrary to my usual difficulty with it.

Exercise 4. b) was much easier to implement since we have already worked out so many list comprehensions at this point (one for max depth and one for sum of a list) so I found it wasn't as challenging as the first. I wasn't certain whether or not a list like : [1, [], None] would be tested but I handled that case as well just in case.

My only question now is why the hint that an empty tree has a depth of -1 is useful...

Week #5

I've only ever blogged once before so I'm kind of new to adding updates and general changes throughout the week. Anyway that first assignment was interesting. It didn't pose too much of a challenge, thankfully, except for creating a general recursive function that would work for an n amount of stools. It was an exceptionally clever assignment though; teaching two important concepts all at once through the Canterbury tale of Anne Hoy and her cheese problem.

What is this 'recursion' everyone so often speaks of? 

Recursion is an unusually simple but difficult concept to grasp. It’s an extremely efficient way to handle certain situations but is often neglected or overlooked. My programming teacher in high school always said “You either understand recursion or you don’t. Usually it just hits you one day and you get it”. The “What is recursion?” question is regularly asked by programmers. If you search on Google, you get a variety of answers ranging from “Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem” or “Recursion is the process of defining a problem in terms of itself”. In other words, recursion is a function that calls itself a number of times.  It is important because it allows programmers to efficiently solve a mathematical model/algorithm that has definite boundaries/parameters. There are a variety of examples where recursion would prove handy such as; traversing trees, modelling mathematical formulas such as factorials (our Towers of Hanoi algorithm too!), fractals, etc. Recursive functions are usually easier to read and understand than solving with loops. Other benefits are that it’s simple, uncomplicated, and time-efficient as opposed to loops.

What's so special about Object Oriented Programming?

Object oriented programming (OOP) is a very important concept to grasp because, as has been mentioned so many times before, it allows us to model things from the real world. In our world, we don’t just deal with procedures but we deal with objects that have specific characteristics and functions. Methods and attributes of classes are extremely useful for distinguishing what is unique to our object compared to others. Attributes are characteristics of the real world object such as eye colour and methods are actions that a real world object may take in response to a call such as barking. This is beneficial since, as can be seen in our first assignment, we were able to create objects of CheeseView, a class inheriting from cheese, containing characteristics such as size and methods like place to represent Anne Hoy’s situation. We didn't want our cheese to know how to move itself across other stools in optimal moves, we wanted it to sit there like a cheese would. Encapsulation is also an important aspect of OOP since it allows you to hide data so as to prevent unwanted modifications from the outside. We don't want our solver function messing with the size of our cheeses, that'd just be crazy.

Though I hope our future assignments will be a little simpler, the recursive function for 4 stools was a real mind twister. At least all that head banging turned out to be for good use.