One More Lab to Go!

Thinking today about how CSC148 is coming to a close, I realized that the lab I was about to do (the one I did this morning) was the second last lab of the entire course. It made me a little sad because I enjoyed the labs and the course, but I noticed a wise way in which the course and its grading system had been structured.

I recently met with my Linear Algebra course's coordinator to learn how to write proofs better. He said it was a difficult technique for most people to master and usually required a few months of exposure to them. For that purpose, in the continuation (MAT224) of my current Linear Algebra course (MAT223), he said he would give proof assignments that would be automatically graded as 100% upon submission and then reviewed to give feedback. This way, students could develop the skill of proving without the pressure of having to do well.

This is exactly what has been done with our labs; we are simply given the mark based on participation, not progress, so the stress of being graded is removed. In such a way, the labs are instead focused on teamwork, understanding code and concepts, discussions, and asking questions to gain clarification.

Having the lab component of the course has really helped me nail down, solidify, and practice some of the things taught in class. Although today's lab was not as intense from a programming perspective, it really helped me understand algorithm efficiency by tweaking, testing, and talking about various sorting methods.

Perhaps the best part about the ease of today's lab was my partner's suggestion to test bogosort. This shuffles a list until it is in sorted order, and actually isn't the worst sort out there (look up bogobogosort if you're interested). My partner, our TA, and I all had a good laugh at the fact that, when bogosorting 10 elements, we were able to do some homework and check back to find no progress had been made. It actually took 35 minutes to sort the 10-item list, so I think Python should consider tossing Timsort and implementing bogosort as its built-in function instead, in all seriousness. ;)

Goodbye, CSC Courses - For Now!

You may not know, but I'm a bit of an imposter - that is, I'm actually aiming to do a specialist in Astronomy and Physics, not a Computer Science degree of any sort.

Although I thoroughly enjoyed programming in high school, I thought that I would be saying good bye to it when I entered university. At the Open House at U of T, I asked an Astronomy grad student what jobs a physics degree could prepare me for. She claimed there were many due to the amount of math, physics, and - you guessed it - programming that you learn in your undergrad (which was both a shock and a source of excitement for me!).

So, unexpectedly, here I am, taking a Computer Science course. I wasn't sure how useful Python would be for me until I learned that a lot of physics programming is done in Python. In fact, modelling simple physical scenarios has and continues to be a central part of my Physics (PHY151) tutorials. For example, we programmed this simple simulation of a falling object, alongside an approximate graph of its position and velocity as functions of time: (My apologies for the quality - or lack thereof!)

For our own entertainment, we were also given the code for this program:

And this program (one bar swinging another bar in such a way that its own movement is affected ... or, if you see it like my brother and I do, it's a headless, red-armed jedi swinging a lightsaber):

Pretty cool, right? Of course, I don't know how to program the previous two, but I am quite excited to learn how to within my undergrad years! All of these use a special visual package in Python, which makes things much simpler to code than you may think; a lot of what we need for such simulations is already built in (phew!), such as the Sphere object.

Apparently, astronomy involves a lot of programming, especially since U of T isn't sending any students into space to do experiments. CSC148 was a recommended course for a third year astronomy course I plan to take, and CSC206 was recommended as well (but wasn't offered this year).

As this semester ends, the time nears for me to say goodbye to you and Computer Science courses, but not forever. Perhaps you want to take CSC206 as well; if so, I'll see you there next year, and if not, then all the best with your programming! :)

Eigenvalues and Sorting

This week in Computer Science, we learned about sorting algorithms, and, recently, I learned about eigenvectors and eigenvalues in Linear Algebra, which do share some grounds for comparison.

Linear algebra often involves the multiplication of matrices and vectors, in which a matrix is essentially a grid of numbers and vectors are represented by a column of numbers. It is not a difficult operation, but it can be tedious. It leaves lots of room for simple errors in calculation and is wearisome for larger matrices. However, the concept of eigenvectors and eigenvalues reduces this time-consuming task into simple scalar multiplication, which is considerably easier.

One may ask: what's the point of sorting? Can't a collection of items be dealt with in an unordered manner? Does it really make a difference to have something sorted? Although sorting isn't always necessary, there are countless cases in which sorting makes complex tasks very simple. Imagine trying to find someone's number in an unordered phone book and you'll understand very quickly.

Yes, you can work with unordered collections just as you can work with matrices and vectors, but with powerful concepts like eigenvectors and sorting, why not take the shortcut where applicable? There is a large array of tools at our disposal as computer scientists, since we are able to use a variety of sorting techniques like insertion sort, quick sort, merge sort, and other sorting algorithms. The trade-off is worth it most of the time, being able to use a simple sorting function to make a collection's behaviour predictable and more manageable.

In the long run, sorting can make our solution to a problem more efficient and less time-consuming, just like eigenvectors in linear algebra. I hope to master and make use of these weapons at my disposal, and I hope you do, too.

Implicit Differentiation and Recursion

This weekend, I had to work on my Calculus (MAT137Y1Y) Problem Set #4, which is due this coming Tuesday. One of the questions involved an equation defined implicitly in terms of x and y, and asked us to differentiate it in two different ways: 1) by making the implicit definition an explicit equation of y = f(x), and then differentiating, and 2) by implicitly differentiating the given equation.

Since the function was already given implicitly, it was messy and tedious to turn it into an explicit definition. It took more time, more care, more calculations, and resulted in the same answer as the implicit differentiation process. On the other hand, implicitly differentiating it was quick, simple, and (most importantly) correct. I guess the professor was trying to prove to us that, although implicit functions can be made explicit and then derived (but perhaps not always), problems expressed implicitly are efficiently handled with implicit differentiation.

Sound familiar?

Dealing with an implicit definition in an explicit way is similar to an iterable approach to a recursive coding problem, whereas implicit differentiation is much like recursion. Sometimes, although the result is the same, approaching a problem with iterations will take more time and will be much messier, if it's even possible to approach the problem this way. Recursion goes straight to the core of the problem and gives the correct result much more elegantly.

Much like approaching the implicit definition explicitly, this week's lab ended with a challenge to iterably program the count_less method, which was easily programmed with recursion. Recursion and implicit differentiation are extremely useful and powerful in certain situations, as my problem set and Computer Science lab taught me, so to my professors I say: lesson learned.

The Ease of Linked Nodes

Throughout the past two weeks, we have been working with linked nodes, a common concept used for internal implementations of objects and data structures. What surprises me most about the use of linked nodes is the ease with which they can be used.

           
Consider, for example, the implementation of a Stack ADT using linked nodes. If one was to program the push() method of this class, the algorithm would involve linking the new top node to the rest of the stack and changing the "top" pointer. Simply enough, that's exactly how it would be coded in literally just one line of code per step (if not one in total with tuple unpacking).

           

The use of nodes is very basic, since they all contain two simples pieces of information (that is, their value and their link(s)). All operations on nodes involve working with just these two things, and for those who like diagrams or may be visual learners, nodes are easy to visualize and draw when trying to understand how they work or how to code with them.

For myself, I realized how simple node operations can be when working on the exercises of this week as well as in the tutorial. Yes, as expected, coding does involve thinking, even if using nodes can be basic; but, once you understand the way that you need to manipulate the nodes, the way you manipulate them is only usually a matter of changing values and changing reference pointers. The code for the exercises was short once I understood how exactly I was supposed to work on the nodes, and in tutorial, my partner and I had no difficulty translating the English of our discussion to the Python of our program. Even when errors arrived, the simplicity of node operations made it easy to understand what our code was doing (and what our code was doing wrong!).

But, perhaps I speak too soon when I say all this. Perhaps nodes only seem simple because all we've been taught are the basics. Maybe there are more complexities than just these "simple" manipulations of references and values. Well, there's only one way to find out: Assignment 2.

Stubborn as a Programmer

Last week, Professor Danny said that a programmer always thinks his way is best. As I was working on e4b.py this week, I found that stubborn programmer mentality in myself. After reading the assignment description, I made the foolishly ambitious decision to try to program sum_to_deepest(t) my own complex way: creating a list of lists, where each inner list contained the keys in one of the paths. In doing so, I could easily just sum the longest list, and voila!

The task set before me was more difficult than expected. I tried to code multiple recursive functions, sometimes trying to return lists, and at other times trying to pass down a list that would receive elements with each function call. Nothing worked, most likely because I didn't understand Python's working of reference pointers when lists were passed down. Not only did my code not find all the paths, it also always created a messy, unexpected jumble of nested lists.

After mulling over the exercise for a few hours, going back and forth between thinking, writing, and coding, I eventually gave up and decided to do things Danny's way (that is: "define a helper function that returns both the depth of the deepest leaf and the sum along the path to that leaf.").

Using a similar structure to the preorder traversal, I only had to keep track of two integers (the sum and the path length) rather than a list and its reference pointer, which was much easier to handle. Using a dictionary to associate path lengths with the sum, I was able to easily sum the keys and access the longest path - an approach that took less than an hour to code and (most importantly) worked! All this made me realize that the stubborn programmer we often argue with is ourselves. So, the moral of the SLOG is: don't be afraid to change your approach when coding. Sometimes, a fresh perspective is the best solution!

Tour of Anne Hoy and the Beauty of Recursion

Like the majority of my class, the first CSC148H1F assignment, the "Tour of Anne Hoy" was quite a challenge. Frustrating on some days and entertaining on others, it was definitely a program that both tested and sharpened my programming abilities.

What I enjoyed most about this project (when I was finally done with it, not when I was working on it!) was how it displayed the elegance of recursion, especially with SolvingController. Once I finally had SolvingController working, it was entertaining to watch my program automatically display the 10-cheese solution in the same time I could manually solve a five-, six-, or seven-cheese problem. What amazed me even more that visually showed recursion at work was how, in the process of moving the stack of cheeses from the first to the last stool, intermediate steps built up smaller towers of cheese on intermediate stools:

For smaller numbers of cheeses, I could manually imitate SolvingController's solution based on intuition. As the cheeses increased, however, I would easily make mistakes and get lost because I wasn't using recursive logic and calculations. SolvingController didn't care how many cheeses were present because, in all cases, the recursive logic was the same. It reminded me of one lesson that I was taught in a high school programming course: computers are not smart; they're just fast. All SolvingController did was recursively define my intuition and repeat it at higher speeds than I could calculate and move cheeses - and, when the stress of the assignment was finally gone, it was quite fun to watch!