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!

Week #5: Recursion

A recursive function is a function that calls itself. These functions are useful in programming as they provide an optimized method for implementing repetition in a program.

In Lab #3 we practiced tracing recursive functions involving nested lists. Here is an example given in the lab:

     def nd(L):
         ’’’(list or non-list) -> int
         ’’’
         if isinstance(L, list):

             return 1 + max([nd(x) for x in (L + [’ox’])])
         else: # L is a non-list

             return 0

This recursive function has an incomplete docstring. Therefore you have to carefully analyze the code given to figure what it does and you can test it with simple examples to confirm your understanding. When tracing a recursive function you must trace the function calls in order. You can replace return with --> and if you have already traced a similar call you can just plug in the result. For the example above we can trace nd('ox'), nd([2,3]), and nd([2, [3, 8], 5, [2, 6], 7]):

     (from lab #3 sheet)
     nd(’ox’)  
     --> 0 # ’ox’ is a non-list 

     nd([2,3])
     --> 1 + max([nd(x) for x in [2, 3, 'ox']])
     --> 1 + max([0, 0, 0]) #already traced nd of non-list
     --> 1 + 0
     --> 1

     nd([2, [3, 8], 5, [2, 6], 7])
     --> 1 + max([nd(x) for x in [2, [3, 8], 5, [2, 6], 7, 'ox']])
     --> 1 + max([0, 1, 0, 1, 0, 0]) #already traced nd of a non-list and a list consisting of non-lists
     --> 1 + 1
     --> 2

Week #4: The First Few Weeks....

     The semester started with some review of main concepts we learned in CSC108. We then progressed on to more complicated things such as classes and subclasses interactions. Our very first assignment was based mainly on this.

     I struggled quite a bit with this assignment. One main obstacle that I struggled with was organizing all the classes and subclasses. I had absolutely no clue where to start. Initially I found it quite confusing to keep track of all the variables and the functions. However with the help of several posts on piazza, many of my questions where answered.  As the completion of the program progressed,  things made more sense, but of course there are always errors. However with patience and the help of TA's, the assignment finally came together. 

There are two main things i've learned from the past couple of weeks:

1. With this course there are several resources from which you can get help with your programming. These include the Computer Science Help Centre, Tutorials and piazza. It is definitely worth your time to use them.

2. As it might be obvious from my description of how this assignment went, I was very frustrated. This is not a sign of a good programmer. 

Primarily I need to manage my time better and definitely improve on organizing my process for completing an assignment. Another aspect I need to improve on is debugging. Debugging is a very useful skill to have in programming, if you know how to efficiently do it, you can save a lot of time and effort.

     Overall, although some of these weeks have been stressful, I did take away an important lesson that will help me in the future.

Week #3: Why Geeks Need to Know How to Write.....

     Communication is arguably one of the most important life skills to possess. Communication is not always verbal, therefore it is extremely useful to be able to communicate at the same level through writing as you can verbally in this day and age. Communicating verbally and through writing are dependent on one another.

    Geeks are often described to be intelligent people that are glued to a computer or merely focused on scientific and mathematical equations. They are portrayed as if they live in a world of their own where they create and accomplish incredible things. However in order for them to be successful in whatever field they are passionate about, they need to be able to properly communicate their thoughts, ideas, and creations with everyone else. Geeks are perceived as preferring to focus on computers instead of people and this missing social aspect can be a great flaw in character.