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! 

Recursion and Computer Science

Recursion is the solving of large-scale problems by solving small-scale problems of similar structure. There is always one or more "base cases", which are cases that do not need to be broken down further. A recursive solution must repeatedly break down the problem until one of these is reached. Some people may struggle with the idea of recursion, so here is a simple visual explanation of it:

The biggest doll contains similar smaller dolls within it, which contain dolls of their own, until the smallest doll is reached. Once that doll is "solved", the process goes backwards and "solves" previous dolls until the first one is finally reached and "solved" through the smaller solutions. This is a great concept for computer scientists to put to use because it goes above and beyond looping structures and can solve complex problems with elegance and efficiency. Although many or all loops can be converted into recursive functions with a little bit of work, it is difficult and sometimes impossible to convert recursive functions into loops. Recursion allows the programmer to solve problems of unknown nested depth by solving sub-problems of sub-problems of sub-problems with changing parameters - something that loops cannot do because of their strict and repetitious structure.

Object-Oriented Programming and Computer Science

Object-oriented programming (OOP) can be defined as a style of programming in which both data and behaviour are combined into "objects", which are then manipulated accordingly. OOP is a significant step forward in the field of computer science, going beyond the capabilities of procedural programming, which was the programming style that preceded OOP. In procedural programming, methods were written to manipulate data, rather than packaging both methods and data together to be dealt with simultaneously. The usefulness of OOP is similar to the concept of vectors from mathematics, which package two types of information (magnitude and direction) to allow for more efficient calculations. As well, with OOP, combining both data and variables into one "object" allows the data and functions to work as and be worked on as one single entity. Perhaps the most powerful thing about OOP is that it is closer to reality than procedural programming. In the world around us, we can see many examples of objects (e.g. cars) with data (e.g. windows, wheels) and behaviour (e.g. driving, opening windows, activating windshield wipers). Ultimately, programming is the use of computers to reconstruct and solve real-world problems, and so, as a closer representation of the real world, OOP is a powerful tool for computer scientists everywhere.