Last CSC SLOG Update?

I guess this is the last SLOG update! It's been interesting keeping up a blog of all my thoughts on the new things we learned and assignments. I found it rather difficult to keep updating though, since sometimes I wouldn't know what to talk about and just my tendency to forget to update regularly.

Without further ado, a few brief descriptions of the sorts:

Selection Sort
This sort basically works by finding the maximum or minimum (depending on whether you're going descending or ascending order) and puts it in the correct place (if maximum, then at the end, if minimum then at the start). This process continues, excluding all of the elements that have technically been "sorted"/put into their correct place.

Best run-time complexity is: O(n^2)
If the list is already sorted, it still has to check the whole list for minimum/maximum values.

Worst run-time complexity is: O(n^2)
That is the performance of a completely unsorted list.

Quick Sort
This sort works by taking an index or pivot and then partitioning the rest of the values around that one. It rearranges all of the values <pivot on the left and >pivot on the right. Then you apply the same divide and conquer method for everything left of the pivot and right of the pivot. Once you get to a list of size 0 or 1, then we assume that those are sorted.

Best run-time complexity is: O(n logn)
Any pivot other then the leftmost and rightmost guarantees us this behaviour such as choosing the middle, or a random pivot.

Worst run-time complexity is: O(n^2)
If the pivot point turns out to be skewed to the left or right of the list. This causes the partitioning of a list of 0 elements and a list of the rest of the elements. This applies especially for already sorted lists.

Merge Sort
This sort splits the list in the middle, then continually splits the left and right lists until only a list of one element is left (since that is assumed to be sorted). Then it continually compares sublists and compares them with another until there is only one list left.

Best run-time complexity is: O(n)
If a list is already sorted, it will take O(n) if you check whether the list is already sorted and if it is splitting it log2n times won't be necessary.

Worst run-time complexity is: O(n logn)
An unsorted list. It still uses memory to store the two halves of the lists though.


From the tutorial, we can see how each sort varies to the other by looking at the graphs:

It's interesting to note the efficiency of bubble sort, tim sort (list.sort) and how circumstantial the efficiency of selection sort and insertion sort is.
Hint: Looking at the profile comparisons in tutorial 11 shows that one of the methods that took up quite a huge chunk of time was calling the length of the list. This is bound to hurt for enormous lists, so to optimize it perhaps you could cut down the number of calls to length.

Some thoughts

The recent test went pretty well I think! It was simply and straight forward, which is exactly how tests should be. If you went to the labs or listened to the lectures and actively finished the exercises, it shouldn't have been that bad.

Some thoughts on the course so far:

1. I really wish we'd gone more into depth with big O notation and runtime complexity. It was a good refresher to be taught about the different sorting algorithms but it still felt a little rushed.

2. The recent lecture was really useful! I hadn't heard of the property method before, so now that I know of it this will definitely help with making attributes more private in the future. These are exactly the kind of tips I was expecting from this course.

Until next time!

Hectic

So this week has been crazy hectic in terms of assignments, essays, and presentations in general. That assignment #2 wasn't as bad the first one, in my opinion. But I'm sure there are different and more efficient ways of going about solving it. There is one thing that I learned when working on the second assignment, and was very disappointed by. Python doesn't have switch cases. WHY? You can read more about that here. But there are still numerous ways to go about comparing a variable to integral values.

1. Using if and elif blocks.

if variable == 1:
    print ("One is a prime.")
elif variable == 2:
    print ("Two is a prime.")
elif variable > 2:
    print ("Prime numbers are only odd now!")
else:  # similar to default
    print ("Numbers!")

This is probably a common method and an easy one. Though it can get messy if you write really long if statements.

2. Using dictionaries (taking advantage of the fact that they are similar to associative arrays)

def check(var):
    return {
        1: 'one',
        2: 'two',
        3: 'three',
        }.get(var, 'not important') # use get as default if x not found

or:

def zero():
    return "Zero."

def one():
    return "One."

def two():
    return "Two."

def prime():
    return "Prime numbers are odd now."
   
def check(var):
    return {0 : zero(),
            1 : one(),
            2 : two()}.get(var, prime()) # use get as default if x not found

A third method would be to create your own class that acts similar to switch/case. That'd be good practice!

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.