Professor Heap gave the following hint for exercise 4, part b:
"Assigning a depth of -1 to empty trees should simplify your code—you should be able to treat this case more uniformly."
I managed to solve this exercise without much difficulty and in writing the function, nowhere did I see the need to assign a depth of -1 to empty trees. Defining the depth of an empty tree to be 0 seems much more natural to me and my code was quite simple—only around 6 lines. I was curious if any other students incorporated this hint into their code and found it useful. If so, how did it simplify your code? Perhaps the hint made more sense for certain approaches to the function than to others.
Sunday, 27 October 2013
Midterm
I only have one midterm left this month after a very busy week last week, so now that the time is available it seems fitting to write about the CSC148 midterm. I'm not always great at test-taking and thinking under pressure so I didn't do as well as I thought I could have, but on the whole I thought it was a very fair midterm; the questions were at a good difficulty level and the length of the test was very reasonable. One thing I found difficult was writing code with pen and paper. Although conceptually everything is the same, it felt very strange since for the most part I have only been typing code on my laptop. Another difficulty I had was that I was a little unsure of what was expected for the last question, which was on describing test cases, and I spent a little too much time worrying and thinking about what to write. The first question was a good exercise in carefully going through what a function does when it is called and, although it was tedious, I thought it was an appropriate question for the test.
I think this midterm exposed that I have a bit of reliance on my computer for quickly checking that my code works and that I didn't leave certain cases untreated, after having quickly typed something up. Being more careful and mentally checking code while programming is something I will have to work on for the next midterm.
Monday, 14 October 2013
The PEP8 Checker is Foolishly Consistent
Need I say more? I guess it's natural for an automated PEP8 checker to be foolishly consistent, as it would be difficult to program one to be able to recognize when readability and style are improved upon by not following PEP8, something that is quite subjective. PEP8 checkers therefore tend to sometimes check for consistency even when it is foolish, and thereby do not really check for PEP8 at all. "Programs must be written for people to read, and only incidentally for machines to execute." (Abelson & Sussman, Structure and Interpretation of Computer Programs). Maybe someday computers will be able to better evaluate what is subjectively more readable for humans than humans can. Until then, humans are probably the best PEP8 checkers.
Saturday, 12 October 2013
Recursion
Recursion is a very powerful way of defining functions and data structures. Whenever a problem has self-similarity in its solution, that is whenever it breaks down into simpler problems of the same type, recursion can be used to define a function to solve the problem and achieve the desired result. Also, whenever an object has self-similarity in its structure, recursion can be used to model the object as a recursive data structure. This is because recursion works by using self-reference: the recursive functions call themselves, which might in turn call itself again with a more simple argument, and so on and so forth until one or more base cases of the function are called with the simplest arguments possible where the solution is trivial and defined explicitly. As long as the base case is always reached, the function is well-defined. Recursive data structures work in a similar way: a recursive data structure is defined in terms of simpler cases of the same recursive data structure, which eventually reduce to a simple base case of the data structure. For example, a binary tree can be defined as a list of an object and two binary trees, each of which is a list of an object and two binary trees. A binary tree defined this way with nodes referring to a finite number of objects is well-defined, since eventually the binary trees in the lists reduce to the base case of an empty binary tree, which could be represented by None.
What first struck me was the apparent complexity of the problems given to us to be solved by a recursive function. For example, it seemed an insurmountable problem to find the maximum element of a nested list of integers, since each nested list that could be passed to a function could have a wildly different structure. However, each of the different structures would have a similarity, they are all self-similar: each nested list is made up of smaller nested lists, the degenerate base cases of which are ordinary lists integers. It was then possible to write a very simple, one-line recursive function to find the maximum element of a nested list, and even though it made complete sense that the function would work, it still seemed surprising that it actually did! The solution seemed too simple. It was quite clear to me how recursion worked—it is after all just mathematical induction in disguise and thought of in the reverse way, an idea which I am very comfortable with from doing mathematical proofs—however the power of recursion still makes it seem like magic.
Writing my own recursive functions took a little while to get used to. At first I would begin by focusing on the general case of the problem, trying to figure out a way to reduce it to a simpler case that would eventually reach a base case. This approach was sometimes difficult when the self-similarty of the problem wasn't immediately obvious and when the problem was self-similar in more than one way it wasn't clear which approach would work best. A strategy I found more effective was to first consider degenerate, base cases and what the function would return, then pretend as if I had a solution to the an arbitrary case of the problem and extend that solution to the next case of the problem. Then, looking in reverse, the extended solution can be used as the general solution which breaks down to the solution to arbitrary case it was extended from, and so on and so forth, until the base case is reached. I was able to figure out the recursive solutions much more quickly with this approach, and writing recursive functions became more easy. The lab on recursive functions helped me develop the method of thinking of recursion that works best for me. Recursive functions are a great deal of fun to write and the results when first testing out a successfully written one are very satisfying.
What first struck me was the apparent complexity of the problems given to us to be solved by a recursive function. For example, it seemed an insurmountable problem to find the maximum element of a nested list of integers, since each nested list that could be passed to a function could have a wildly different structure. However, each of the different structures would have a similarity, they are all self-similar: each nested list is made up of smaller nested lists, the degenerate base cases of which are ordinary lists integers. It was then possible to write a very simple, one-line recursive function to find the maximum element of a nested list, and even though it made complete sense that the function would work, it still seemed surprising that it actually did! The solution seemed too simple. It was quite clear to me how recursion worked—it is after all just mathematical induction in disguise and thought of in the reverse way, an idea which I am very comfortable with from doing mathematical proofs—however the power of recursion still makes it seem like magic.
Writing my own recursive functions took a little while to get used to. At first I would begin by focusing on the general case of the problem, trying to figure out a way to reduce it to a simpler case that would eventually reach a base case. This approach was sometimes difficult when the self-similarty of the problem wasn't immediately obvious and when the problem was self-similar in more than one way it wasn't clear which approach would work best. A strategy I found more effective was to first consider degenerate, base cases and what the function would return, then pretend as if I had a solution to the an arbitrary case of the problem and extend that solution to the next case of the problem. Then, looking in reverse, the extended solution can be used as the general solution which breaks down to the solution to arbitrary case it was extended from, and so on and so forth, until the base case is reached. I was able to figure out the recursive solutions much more quickly with this approach, and writing recursive functions became more easy. The lab on recursive functions helped me develop the method of thinking of recursion that works best for me. Recursive functions are a great deal of fun to write and the results when first testing out a successfully written one are very satisfying.
Object-Oriented Programming
In CSC148 we are learning to program in Python3, an object-oriented programming language. What is object-oriented programming? That's an easy question to answer: "Object-oriented programming (OOP) is a method of programming that is oriented on objects!" Not a satisfying answer. A more explicit, and less unsatisfying, answer is: "Object-oriented programming (OOP) is a method of programming that focuses on representing objects with code by defining different properties (attributes) that the objects have and actions that can be done with the objects (methods). The objects are represented as particular cases of a blank representation of the object (a class)." This definition still seems pretty vague and general. Almost anything can be thought of as an object, and each of these can have all sorts of properties and things that can be done with them. Classes, blank representations or blueprints for objects, are even more abstract and general. Python, however, isn't the first programming language I have been exposed to. The first language I learnt was C# (also object-oriented), which I took a class for two years ago, and although from the beginning of the class I was aware of a similar definition of OOP, it took me a long time to really understood what it meant and it wasn't until the beginning of this semester when it all started to make sense to me.
In my first class in computer programming, we began by learning how to write some very basic programs without the use of classes and objects. When classes were first introduced in the course I had a very difficult time understanding what was going on. There were lots of new terms, instance constructors, and I had a hard time comprehending what was happening when objects, which are instances of classes, where being constructed. It also took a lot of work and time to create classes for the extremely simple objects we were considering in our examples. This completely obscured the motivation for classes in the first place! Instead of making the programs easier to think about, write, and modify, using OOP made everything more complicated. However, after being forced to use it and after beginning to use it to write programs to solve more complex problems, OOP gradually made more sense.
At the beginning of this semester, when relearning the basics of OOP in Python, it all really clicked. Our recent assignment on animating an interactive game of Reve's puzzle as well as an automated solution, which was a rather complicated problem, really required the use of OOP to simplify the programming and helped solidify the concepts involved in writing object-oriented programs and the benefits of OOP. I now realize the brilliance of the programming paradigm and how powerful it is for solving problems. The physical world is made up of objects that have properties and have actions done to/with them and consequently, humans naturally think and speak in terms of objects, their attributes, and their methods. Thus representing and using objects in programs is a very natural way to write programs about almost anything you can think of. In the physical world it is also often the case that many specific objects are closely related to each other and are members of a large class of objects, this class of objects might be closely related to other classes of objects, all of which are more specific examples of a larger class of objects, and so on. Creating classes of objects and using inheritance to create subclasses is naturally modelled in OOP. Finally, mathematical objects and mathematical structures, which are a very important aspect of computing, are also well-suited to OOP.
At the beginning of this semester, when relearning the basics of OOP in Python, it all really clicked. Our recent assignment on animating an interactive game of Reve's puzzle as well as an automated solution, which was a rather complicated problem, really required the use of OOP to simplify the programming and helped solidify the concepts involved in writing object-oriented programs and the benefits of OOP. I now realize the brilliance of the programming paradigm and how powerful it is for solving problems. The physical world is made up of objects that have properties and have actions done to/with them and consequently, humans naturally think and speak in terms of objects, their attributes, and their methods. Thus representing and using objects in programs is a very natural way to write programs about almost anything you can think of. In the physical world it is also often the case that many specific objects are closely related to each other and are members of a large class of objects, this class of objects might be closely related to other classes of objects, all of which are more specific examples of a larger class of objects, and so on. Creating classes of objects and using inheritance to create subclasses is naturally modelled in OOP. Finally, mathematical objects and mathematical structures, which are a very important aspect of computing, are also well-suited to OOP.
To somebody new to OOP, the definition given at the start of this entry might seem so general that it hardly says anything at all about what OOP really is. However, the definition does a good job of capturing the generality of what can be coded in an OOP language, which is one of its main strengths.
Subscribe to:
Posts (Atom)