CSC148 Lecture Week 7

I would like my summary of Object Oriented Programming concepts to be graded.

   Lab 6 this week is the first lab that I really struggled with. The function list_longest_path asked us to write a function that would find the longest path in a binary tree and return that path. The starter code came with the following docstring examples:

>>> list_longest_path(None)
[]
>>> list_longest_path(BTNode(5))
[5]
>>> list_longest_path(BTNode(5, BTNode(3, BTNode(2), None), BTNode(7, BTNode(4, BTNode(9)), BTNode(6))))
[5, 7, 4, 9]

The first two examples give us the two base cases for the algorithm. When there is no tree at all, the longest path contains nothing. When only the root is present, the longest path is obviously just the root itself.

Translated into code this would be:

 if node is None:
        return []
 elif is_leaf(node):
        return [node.data]

   The recursive case was what I really struggled with. I couldn't figure out how to keep track of all the data because we couldn't just find all possible paths, store them in a list and then look through that list, which is the type of recursion that we had been doing before. What really helped was one of my partner's ideas and actually drawing out the tree itself.

My partner, Wendy, realized that at each node we would need to look at the right node and the left node and then compare them. I then started walking through the tree starting at the root. Node 8 would ask Node 7, "What is your longest list?", then it would ask Node 1, "What is your longest list?". This would continue until a leaf was reached. The leaf would then know right off the bat that its longest path was itself. This information would then be sent back up the tree. The final piece of the puzzle was realizing that we would have to concatenate the data of the node itself to the data it was getting from it's children. This then lead to the final solution:

else:
        if not node.left == None:
            left = list_longest_path(node.left)
        else:
            left = []
         
        if not node.right == None:
            right = list_longest_path(node.right)
        else:
            right = []
         
        return [node.data] + left if len(left) > len(right) else [node.data] + right

Another slogger also has a great explanation of recursion here.

CSC148 Lecture Week 6

Object Oriented Programming Summary 
   Object Oriented Programming is a style of programming that involves grouping similar idea into classes. These classes are then used as blueprints that can be used to create instances of objects that have methods and attributes associated with them. Objects can then manipulate their attributes and use their methods to perform tasks.

Self
  For all methods associated with a class, the first parameter is always the object itself. By convention this parameter is named self. This then allows you to call the method using syntax like this:

object.method()

which is equivalent to:

method(object)

Inheritance 
   The major idea that we covered in object oriented programming is the concept of inheritance. Sometimes classes will have many similarities and repeated code. Instead of copying and pasting code, which can cause many problems, inheritance is a much better solution. Copying and pasting code would force you to change many files every time you changed your design. With inheritance, a parent class has all the attributes and methods that are common to all the similar classes. For example, if you were designing a program to manipulate shapes, you would have a general shape parent class and child classes for specific shapes like triangles and squares. The parent class would have general attributes like side length, and general methods like find area. The child classes would inherit all this.
   The parent class can implement some methods, but it might not actually know the specific details about methods like find area. In this case, it is not meant to be instantiated, so a NotImplementedError would be raised if the parent class' method was called. The child class would have a proper implementation that overrides the parent class method. Code that uses these classes would then be written for any general shape. It would not need to know what specific shape that it is dealing with and this allows for more flexibility.

CSC148 Lecture Week 5

  The first few weeks of class have been OK. Object oriented programming is a topic that I rather like. I have previous OOP experience in Java, so the fact that Python has no real concept of privacy is rather surprising. Using property in Python is interesting. It really makes me think about the public client interface of code vs the private implementation of code and I think that it is a really good idea. When I use built in functions like sort on a list for example, I don't really care what algorithm is being used. I just expect it to be fast. If a better way of sorting a list is discovered, it's good to know that my code will not be affected if the function is changed.

  I'm liking the way that we trace recursion in class. It is helping me understand recursion a little better. I like having a visual representation of recursion since I am a visual learner. It was hard for me to picture what was going on with recursive functions, but I now have a better tool for helping me.

  What I'm disliking about the lectures so far is their focus on the assignments. I think that it's really helpful for the professor to give tips on assignments and take questions during lecture time, but it always seems to end up eating up a massive amount of the lecture time. I want to learn concepts during lecture time and then apply them to assignments. A lot of the questions asked are being repeated or are asking for what seems like hand-holding. Asking assignment specific questions wastes the time we could spend learning general concepts that will be applicable to future situations.

CSC148 Lecture Week 4

  Ah, recursion, my old enemy, we meet again. I am actually so glad that university terms are only 12 weeks long. I can only maintain good study habits for a few months at a time before I need a break, and in high school, by the last month, I was just out of gas. That was the month that we learned recursion and I just gave up, although now that I think about it, I don't think that the Waterloo Canadian Computing Competition recursion questions that my teacher gave us were suited to our skill level.

  The basic recursion we did in class with one base case and a very simple recursive statement, I can understand. Recursion is a type of algorithm where within a function, the function calls itself as a helper function. Recursion is best used on problems that can be broken down into smaller version of the same problem. One basic application of recursion is the factorial function shown to us in tutorial. For example, 6! can be broken down into 6 x 5!, which is then 6 x 5 x 4! and so on until you get to 1! which is just 1. Every factorial can eventually be broken down until 1!, so that is the base case which terminates recursion. The recursive call is then to call the function on n-1. Tracing recursion has been a good experience. I think I have a better grasp on exactly how recursion works now.

CSC148 Lecture Week 3

And here I was thinking that I had written my last SLOG. But now I am back to the wonderful world of blogging for class.

This week's topic is: Why do geeks need to learn how to write? My answer is pretty simple: Documentation. In the wise words of the Mythbusters, "The only difference between science and screwing around it writing it down". Programming and computers may seem highly individual, but in reality they require a lot of teamwork. The apps, websites, and programs that we use everyday were not built by one person. Programmers need to be able to communicate ideas and tell each other how their code works. This requires us to be able write clearly and concisely in a way that another human being can understand.

I for one hate writing comments, but no one (at least I'm assuming) likes to read uncommented code. I can't read the mind of whoever wrote the code. The code could be the most innovative amazing thing ever, but if I can't understand it, it is of no use to me. My human brain needs some plain English to process what it going on.

As another blogger points out, knowing how to write also helps us understand the problems we are trying to solve. Computer programming is fundamentally about solving problems, and we have to know what we are trying to solve before even attempting to do something about it.

CSC165 Lecture Week 12

So this is my last SLOG. I wish I could say that I'm sad, but I'm really not.

I actually really liked assignment 3. I finally understand what the point of all those limit proofs were. For the limit of a function as x goes to infinity, if that limit is infinity, then the output of the function can be larger than any given number past a certain breakpoint for the input. For the limit of a function as x goes to infinity, if that limit equals to zero, then the output of the function can be smaller than any given number after a certain breakpoint for the input.

The zero limit also really helped in my understanding of infinity. No matter how small a number I can think of between 0 and 1, there will always be a real number that is smaller than the number I've come up with. I'm also glad, I finally managed actually apply the limits and derivatives that I have spent the past year and a half learning.

After reading some other SLOGs, I've found a couple that have good summaries of computability, which I think was the hardest of the topics that we covered:
http://fromatothis.blogspot.ca/
http://mrbunnyua.blogspot.ca/

CSC165 Lecture Week 10/11

This is technically just for lecture week 10, since we won't be having a lecture week 11 for the Tuesday evening class, but anyway, onto the SLOG.

This week in lecture we learned about computability. First let's talk about a few definitions. A function is considered to halt when it eventually stops. For some functions we can write a function halt(f, n) that can tell us whether or not the passed function f will halt with the given input n, but we cannot write a universal halt(f, n) function for all possible inputs.

A function is well defined if and only if we can tell what the output is for every input in some domain. A function is computable if and only if it is well-defined and we know how to compute the output for every input in some domain. By these definitions halt(f, n) is non-computable.

We can prove that a function is non-computable by using reductions. If a function, f, can be implemented by using another function g, that function reduces to g. If g is computable, f is also computable and by the contrapositive, if f is non computable, g is also non computable.