Week 10

This week we learned about sorting algorithms. There are a lot of sorting algorithms out there and we learned a few of them like bubble sort, quick sort, merge sort and insertion sort. My favourite one is Bubble sort because it sounds like I'm saying "Bulbasaur" and it is probably one of the slowest sorting algorithms for extremely large sets of data.

I remember implementing and learning about sorting algorithms in grade 11 programming class back in high school, that was really fun. There, we actually did an assignment where we searched up some different kinds of sorting algorithms that weren't as cliche to learn in a CS class (Yeah, I'm talking about CSC148). On the test there, one of the questions asked to implement one of the sorting methods we did on the assignment and I remember writing code for "Gnome Sort", I don't even remember implementing it correctly at all.

Any ways, the great thing about the sorting algorithms that we did in the CSC148 lectures that I already knew about is that there are countless ways to implement them in any programming language. The simpler the implementation, the more efficient the sorting algorithm performs, right? WRONG! Each sorting algorithm has an efficiency that is already been determined based on the worst case scenario.

I did OK on the test, didn't try very hard at all. Probably should have studied more, but I was busy playing Alliance of Valiant Arms. Didn't bother going to the lab, because I had some medical stuff to do, not that it would matter to anyone. Just waiting for the exam now so that this class can end.

Week 9

This week we learned about complexity. We were introduced to Big-Oh notation which help us understand the efficiency of our code based on many how steps the code takes. The lecture started with working on creating a program that finds all of the words that are anagrams of a given word. First thought was to use the permutation approach, which was not a very good solution since the amount of work we estimated was a lot depending on the length of the word and checking if all of the generated permutations are real words or not.

The second method to solving the anagram code was something Dan called "Signature approach". Basically, you take the argument word and re-arrange its letters in alphabetical order and then that becomes the argument's "signature". We can then generate a list of anagrams of the argument by checking if their signature is the same as our initial one and this proved to be a better solution.

I am not very comfortable with determining time effficiency yet, but I will be practicing it this weekend so I should be ready for next week. I think next week's lab will be based on determining time efficiency of given code and finding most efficient solutions for given functions.

Week 8

Binary Search Trees was the topic of week 8. BSTs are like an extended version of a basic binary tree, except you've got your insert() and find() method as well some specially designed classes called nodes with their own unique methods as well.

Nodes are the thing inside the BST that contain the object you want. A BST has left and right spots and by default they are None OR you can define a custom version of BST Node called BSTNoneNode or something similar to represent a Node that is null. By creating this empty Node class, you can avoid getting errors when searching through BSTs, because you won't be accessing a Node that doesn't exist.

BSTs use recursion to find items as well as calculate their maximum height. The lab we did, we were given 4 classes BST_rec.py and we implemented a method count_less(n) that counts number of items in BST less than n and returns that value.

Essentially, all 4 of the py files, we used recursion to create the count_less() method. I ended up creating one-liner count_less() methods and they were pretty efficient I'd say. My initial idea was to use ternary expressions to count items less than n.

For example, I don't know if a lot of people know this or not in our class, but I can convert boolean expressions to an integer by type casting them:

int(True) == 1 # This would return True because if you convert True to an integer, it becomes 1

Along with the above, ternary expressions proved most useful, because essentially, what the count_less() method returns is 1 or 0 along with a recursive call count_less() on both of its nodes (if they exist).

Week 7

This week we learned about Linked Lists. A Linked List is kind of like a list of lists, except in a Linked List, you've got the item (can be any object) and the next item (can be None or another Linked List). This week's lab was learning to re-create Queue class using the Linked List instead of python's built-in list class.

The goal in this lab was to see how implementing Linked Lists for Queue class improved efficiency. When we implemented the Queue class using a basic list, the dequeue() method was what really made the whole class perform slow.

A lot of people didn't finish the lab, so next week's lab will be the same thing (try to finish the enqueue() and dequeue() methods to receive the mark).

Linked Lists are a pretty easy concept and are easy to re-create. You just have to understand why they are called "Linked" Lists.

Week 6

This week we learned about Binary Trees and just Trees in general. Even though this data structure is called a Tree, it has nothing to do with a real tree, except some of its characteristics that match a real tree. Of course, you don't need to know about a real tree to understand what the Tree's characteristics mean.

A Tree has a root, branches and leaves. Leaves are the outermost objects that have no children. Roots are the parents of children and branches are what connects parents and children. Roots start out empty and you can fill the left and right sides of it and then do the same for those.

You can trace trees using recursion; meaning you can calculate its height or find a specific element just by going through the tree.

We also did a list-of-lists implementation of Binary Tree, which was moderately easy enough to follow and understand. I was even able to re-write the implementation at home a few hours later without having to look at class notes at all.

The test went well and I am happy with my mark, considering I was quite ill and barely had enough strength to make it to class without vomiting brutally.