CSC 148 Trees Post #5

Note: Please grade my OOP summary which is post #4.

In CSC148, we have started learning about Trees which are another ADT. To be quite honest, for me Trees are a bit difficult to understand, especially since a lot of the functions that Trees use have a lot of recursion in it and there is also a lot of terminology that are associated with trees. When we first started talking about them, professor Heap talked about what a Tree contains, such as nodes, children nodes, edges, root, leafs, height, depth, etc. and it is actually quite overwhelming.

Okay so what exactly is a Tree? So from all that terminology, a Tree is a set of nodes with directed edges between nodes. The root note or the parent node starts at the top, and all the other nodes that "branch" out from the root note are called children. The nodes that have children are called inner nodes while nodes that have no children are called leafs. Take a look at this example,

A is the root note with directed edges towards children nodes B and C. Node B which is an inner node also has children nodes D, E, and F. Nodes C, D, E, and F are all leafs because they have no children. The height and depth of node A is 3 and 0, while the height and depth at node F is 0 and 3.

What can we do with Trees? Well in Assignment 2, we are kind of using Trees to build all the possible moves for our games. I say "kind of" because we will see it as a Tree but its really going to be a bunch of lists. The reason we are using Trees is for the minimax strategy which takes a look at all the possible moves and chooses the best moves in order to win. Our job is to create that Tree and put together all the successive moves one after another and check which move would make the player win.

How are Trees implemented? So far we have covered over how to look into Trees, and basically we have implemented functions to check whether or not values are contained in Trees and whether or how many leaves there are. For A2, we will want to implement functions that will build a Tree where nodes branch off to all the next possible moves.

A friend of mine, in one of his slog posts, he posted a pretty funny picture of a Christmas tree in the shape of a Tree. In his post he also covers a little of what I talked about here as well. Go check it out here: http://timothylock.ca/sLOG/CSC148/?p=80

As I said earlier, I am not too comfortable with Trees and just thinking about how I will create a Tree that contains all the possible moves is just quite overwhelming. I guess I'll just need to practice more. Though thanks for reading!

CSC148 OOP Post #4

Reading week is here! Which means we are already half way through CSC148, I guess time flies by when you're busy programming! CSC148 has been great so far and I hope that it will be even better after the break. Throughout the first half of the course, we mainly focused on Object Oriented Programming or OOP for short. So in this slog post, I'm going to spend some time talking about OOP, why we need it, and where we use it.

In my second slog post, I did talk a little about OOP and the concepts that we looked at so far including creating classes and objects, special methods, and inheritance. In general, in OOP, the idea is to create objects of a particular class. When we instantiate an object, the object can come with properties and methods that belong to that object.

In Python, this is what we call the __init__ method, which assigns the properties to that object. We then have special methods such as __str__ which when called gives a string representation of the object, __eq__ which compares two objects together, and __repr__ which gives a string that can be put into the shell to create to create another object with the same properties. Objects also have normal methods where they just basically normal function calls.

Now inheritance is the concept of extending a class. In my second blog post I said that inheritance is not 100% needed to make your program work, but it helps reduce code, which is what the purpose of inheritance is. There are times where in a parent class, code may or may not be useful in some cases, but it may be very useful in other classes. So instead of rewriting the functions into a different class, we can extend the parent class onto the sub-class. The sub-class will "inherit" all the functions and properties of the parent class, thus reducing the amount of code in your program.

Okay, so why is this all important? Why do we need OOP? Well like inheritance, we want to eliminate any duplicate code, and sometimes, code can be changed. Professor Heap told us that code is always being fixed or added to create new features. However, if we drastically change our code on our end, it could spell problems on the client end. Essentially OOP is needed to easily change code.

If you copy and paste code all over the program, then when something needs to be fixed, all the duplicate code has to be fixed as well. If you accidentally miss something, let's just say good luck finding the bug. But with functions, you can change it once, and call it throughout the program. This is why we write methods and classes, which eliminates the need to duplicate code. And by reducing the amount of code in our function, we can also have a faster run time, but I'm going to leave that topic for another day.

Speaking of duplicate code, recursion does a great job in handling these sort of things. Since the idea of recursion is for a function to call itself, it eliminates the need to manually write out code for each case. I guess in a sense, recursion is sort of like a loop.

I came across another slog where they talked about how to come up with the design for classes from the description that they give you and they also talked about inheritance with a good easy example. You can check out his slog here.

So that is my summary of OOP, why we need it, and where its used in our programs. Thanks for reading!

CSC148 Recursion Post #3

In Week 4, we talked about recursion. Basically recursion is calling a function in itself. So in class we were given a worksheet and we had to trace a recursive function. Getting a worksheet again reminds me of CSC108 where we got a worksheet for the lesson and we were able to go through the worksheet with the professor. To be quite honest, I think getting worksheets in class help me more than just watching Professor Heap code. It allows me to think about what we are doing and actually try it myself. It would be best if Professor Heap could hand out worksheets for the lesson and we could go through it.

Anyways back to recursion, on the worksheet, the given recursive function was:

def sum_list(L):
     if isinstance(L, list):
          return sum([sum_list(x) for x in L])
     else:
          return L

This function takes in a list as an argument and essentially checks if the argument is a list, if it is not a list, then the function will return the argument. If it is, then it will return the sum of the list where for each item, the function calls itself again to see whether or not the item in the list is a list. Now this is the recursive part, the function is calling itself within itself to check whether or not the item is a list.

To make sense of what's going on here, this an example from our worksheet:

sum_list([4, 1, 8])

In this example, the argument that is passed in is a list, which means it satisfies the first if condition. Now the function will proceed to return the sum of the elements in the list, where for each element, the function will call itself again to check whether or not the element is a list. So for 4, the function will pass in 4 for L and check, since it is not a list, the function will simply return 4 back into the list comprehension. It will do the same for 1 and 8 as well, so at the end of the recursive checking, the final list that will be summed is [4, 1, 8]. Thus the final result is 13.

Now if in the original list, one of the elements was a list, so in other words a nested list was passed in as the argument, then the function will call itself, while it has already called itself. So in this case, we would have gotten into depth 2. The more nested lists there are, the more depths we go into.

So this is recursion and my understanding of it. I think recursion is actually pretty simple once you get the hang of it, though I don't see any practical use for recursion yet. I hope that we will see some functions that will make use of recursion in a useful way, instead of just seeing simple functions that just calculate.

Thanks for reading!

CSC148 So Far - Post #2

It's been 3 weeks since the Winter term started and CSC148 has been enjoyable so far. Basically up until now we have been continuing from 108 on objects and classes. In the first week we started with a neat Python program called Turtle. So essentially what it does is that it draws a "Turtle" which looks like an arrow on the screen and then you can begin to move and create arms for the Turtle. This was really interesting because all we've done so far are text based programs and functions but nothing visual.

So the point of the Turtle program was just to show objects and classes. First in the Turtle class we created a turtle object. Along with this object came with some properties that were established in the __init__ method such as self.arms = n which creates arms for the object, where n is the number of arms. In this class also contained other methods such as move which would move the turtle around the screen.

We also covered over some other special methods or built-in methods in classes such as __str__ and __eq__ and that we can modify them. However, Professor Heap gave us a good warning to be careful not to reinvent the wheel.

Moving onto the second week, we got into some new stuff such as making variables and functions "private", new data types, and finished off with some doc-testing and unit testing. We talked about by just adding a "_" in front of variable will make the variable inaccessible to other programmers, but it doesn't prevent them from just importing the code and changing the variable themselves.

We also talked about ADT (Abstract Data Type), but really all we need to know about them is how we call them and what we get back when we call them. Then we looked at doc-testing where it tests through each example in your docstrings and unit test where it runs a file that has bunch of tests that are used to test another file.

Finally, up to week 3 we moved into talking about sub-classes and inheritance. So basically what it is, is that we can essentially expand a class with other classes. Why do we want to this you ask? Well really sub-classes and inheritance is not absolutely mandatory in order for your program to work, but what the purpose of using inheritance is to organize and minimize code. In Python, we can extend a class by adding in new functions and variables that the parent class did not have, and we can also override the parent class by overwriting functions in the parent class in the new class. It is always better to extend or override code then copy and paste it into a new class.

Speaking of inheritance, sometimes in the parent class, functions requires a sub-class in order to run. For example in lab 2, we had to create a class that either took in a str or an int as one of the parameters. But it's not reasonable to have that class handle both at the same time, so we created two new sub-classes, one to handle the str and one to handle the int. So in the parent class for that function, we put in a "raise NotImplementedError("Error! Need a sub-class")" to alert the user that this function is not implemented in this class but it is in the sub-classes.

So yeah, this has been CSC148 so far. We just finished assignment 1 and our first midterm is coming up. I hope that I'll pass! Thanks for reading!