Week #12: Last Impressions

Generally speaking this course has presented a moderate set of challenges that I feel have strengthened my programming skills. 

The unfamiliarity with the concept of recursion has been one of the main obstacles that I've dealt with throughout this course. Despite the initial struggles that I faced in trying to grasp this concept, I now feel I have a clear understanding of recursion. As a computer scientist with previous programming experience, the concept of recursion has introduced to me an alternative way to think about coding that I have not experienced in any previous contexts.

Another concept we covered in this course is Object Oriented Programming where we worked with different data structures such as classes and subclasses. This extended into the introduction of inheritance, another extremely useful tool to know.

Overall I'm very satisfied with the knowledge I've gained from this course. I would like to say thank you to both Professor Danny Heap and the TAs for being so wonderful and helpful. I look forward to what the field of Computer Science has to offer next. 

Week #11: Why Geeks Need to Know How to Write..... Revisited

Going back to my first blog post, I believe I could've elaborated more on my thoughts about the topic of why geeks need to know how to write, as I can clearly see it is very general and kind of confusing. I do agree with everything I said but reading through other SLogs I've come across very interesting points that I had not even considered.

One interesting idea I came across is how knowing how to write helps with coding. In coding comments are essential. As Leon Wong wrote in his blog (http://theremustbe.blogspot.ca/search?updated-max=2015-02-06T20:25:00-08:00&max-results=7) "clear and understandable comments are steady bridges between you and other programmers". Therefore knowing how to organize and clearly communicate your steps will make your code more readable and understandable by other programmers.

Week #10: Test and Mutating BST

Week #9 we had the second term test. It covered Trees including Binary Search Trees and it also covered Linked Lists. I discussed Binary Search Trees and Linked Lists in my previous blogs. Therefore refer to those for more information.

That week also learned about two important functions for mutating Binary Search Trees, insert and delete.

INSERT

This function inserts a new node into the Binary Search Tree and when it does so it must satisfy the conditions of a BST. These state that the data of the node must be comparable, the data in the left subtree must be less than that of the node and the data of the right subtree must be greater.

Here is the code (taken from class notes) for the function insert:

DELETE

The function delete, as its name states, it deletes a node from a Binary Search Tree. When deleting a node from a BST you must reconnect the remaining subtree. Here is the code (taken from class notes) for the function delete:

As demonstrated in the code, both functions use recursion to mutate the Binary Search Tree so that each node follows the appropriate criteria of BSNode.

Week #9: Linked Lists

Week #8 was about Linked Lists.

What is a Linked List?

A Linked List structure consists of nodes that have a value (object) and a reference to another object, therefore another node. When initializing a Linked List Node you pass the value as a parameter and have a default parameter for the reference, set to None.  Here is a more visual representation of the Linked List :

Linked Lists can be described as recursive structures because every node refers to a linked list.

But sometimes it is easier to approach this structure as one train of links. For this approach we implement the class Linked Lists as a "wrapper" representing the structure as a whole. We create variables to keep track of the front (head) and the back (tail) links as well as the size of the whole list. This is the approach we took when working on Lab 07.

One basic concept that we need to understand is how to traverse all the items in the Linked List. This bit of code is very useful for many functions that are used to manipulate the structure.

When traversing all the items, we need to call on the first node (front/head) and use the default parameter for the Linked List Node, nxt, that will return the next link. The python code (taken from class notes) is as follows:

cur_node = self.front

while <some condition here>:

     # do something here.....

     cur_node = cur_node.nxt

This code is only a basis that helps implement functions such as _contains_ or _get_item_. Knowing how to traverse the tree allows you to manipulate links and search for links as well.

Week #8: Binary Trees

During week #7 we were introduced to Binary Trees.  A Binary Tree differs from the generic Tree design, as it contains nodes that have a maximum of two children referred to as left and right.

Here is an example of a Binary Tree:

When traversing a Binary Tree, there are three different orders in which the nodes can be visited:

1. Inorder: left child, root, right child

2. Preorder: root, left child, right child

3. Postorder: left child, right child, node

We can extend our understanding of a Binary Tree and create a Binary Search Tree (BST). A Binary Search Tree is ordered/sorted.  The left subtree always contains data less than the node data and the right subtree always contains data that are greater than the node data, therefore the data of the all node must be comparable.

Here is an example of a Binary Search Tree:

Efficiency of a Binary Search Tree

As mentioned in our class notes, if the tree of n nodes is "balanced", it will have a height of about log(n). Therefore when using this binary search tree to find data you will access about log(n) nodes. The structure of the BST depends entirely on the order of insertion of the items. Worst case scenario would be if you had to access n nodes (linear relationship) which is the same as having a list and going through every single item to find your desired data. A balanced BST is obviously more efficient.

Here is an example of a balanced BST vs and unbalanced BST:

Week #7 - Recursion

For my Week #7 blog post please refer to my post about Recursion from Week #5.

Week #6: Object-Oriented Programming (OOP)

What is Object-Oriented Programming?

Object-Oriented Programming is type of programming that consists of objects that are manipulated to satisfy the needs of the program.

Object-Oriented Programming is what this course has been mainly focusing on. So far we have learned about how to create classes and methods including special methods such as __init__, __repr__, __str__, __eq__. To create an object you create an instance of a class.

We also learned about an important OOP concept called inheritance. Inheritance is when a class inherits code or behaviour from another class. The class inheriting the code is called the subclass or child class and the other is called the parent class.  Inheritance was a large component of Assignment 1. In the assignment we created two main parent classes for a general game state and a general strategy. These parent classes had subclasses of a state of a specific game called Subtract Square and a specific strategy that chooses randomly what move the computer makes.

Overall these are some of the concepts of Object-Oriented Programming that we have covered so far, and I'm looking forward to what we learn next!