Dynamic Programming, Memoization, and Artificial Intelligence

Back in high school, in my Grade 10 Computer Science class, I was introduced to the concept of "dynamic programming" for the first time. We never used it, but our teacher only mentioned what it was like. He said that the code changes as the program runs, which I thought was a pretty cool concept. Of course, in my naive little mind, what I thought was that the actual code changed - that is, if you looked at your code from time to time as your program was running, it could be different. (Yea, yea, laugh it up. There's a reason I said 'naive'!)

The idea of memoization is much more plausible and still just as awesome (and efficient!). I actually unknowingly used memoization back in Assignment 1 with the Tour of Anne Hoy, using a dictionary to keep track of what was the best split value for different numbers of cheeses. Running into it again in the context of call stacks, efficiency, and the Fibonacci sequence made me realize how powerful this concept is, even though it's not really a complex one.

The implications of memoization take my thought process straight to artificial intelligence. It brings to mind the idea that the computer is "learning", in a sense, and is able to retain information as it is running just like we learn things through our senses in reality. I don't know much (or anything) about artificial intelligence, but memoization seems like a very basic application of it. As I mentioned in a previous post, my Grade 11 and 12 Computer Science teacher once said that computers do exactly what programmers tell them to do, the only difference being that computers can do them much faster than humans ever could. But, with the advancement of computer science, artificial intelligence is giving computers much more than just blinding speed. Combine the speed of a computer with artificial intelligence, and ... Well ... You've seen the Terminator movies. You should know. ;) 

Sorting Algorthims and Efficiency

One of the most important concepts in Computer Science is sorting, since it makes lists and collections much easier to deal with. Most introductory programming courses teach the common sorting algorithms of selection sort, merge sort, and quick sort, like CSC148H1. Elaborating a bit more on each of these ...

Selection sort iterates through the list, finding the largest element and placing it at the end of the list. After doing this on a list of length n, the greatest element is in place, and so selection sort then continues on the sublist of length n - 1. One at a time, the maximum element of the remaining list is put in its proper place. A total of n - 1 passes are required, giving selection sort an efficiency of O(n²). This is the sort I like to use when playing card games like Crazy Eights or President, except I think it's a lot easier to do this as a human being because I don't have to individually pass through each card, but can just see which card is the greatest.

Here's a visual example of selection sort, which instead finds the minimum element and places it at the beginning of the list:

Merge sort (and quick sort, too) are more efficient than selection sort by using a divide-and-conquer strategy, eliminating the need to make passes through the entire list. Merge sort repeatedly breaks the list into halves until it has sublists of only length 1, and then uses a helper method to merge pairs of sublists together in the proper order. So, the list is completely broken down into pieces and then reconstructed, piece by piece, eventually recreating the whole list in sorted order. It's much easier to understand this visually:

It takes log(n) steps to break the lists into pieces, and then it needs to merge all n elements, so the efficiency of merge sort is O(n log n).

Quick sort is my personal favourite. Using a pivot value, quick sort breaks a list into two sublists, one with elements greater than or equal to the pivot value and one with elements less than the pivot value. It continuously breaks down the list in this way, and when it can no longer be broken down, it brings together all the sublists that were created to reconstruct the list in sorted order. Although I learned quick sort in Java first back in high school, learning it again in Python has made it my favourite for a few obvious reasons: firstly, unlike other sorting algorithms, quick sort doesn't require any helper function and can thus save memory and space that way. Secondly, in Python, the ternary if, list comprehension technique, and one-line return statement literally make this sort a one-liner. Quick sort's efficiency is the same as merge sort's: O(n log n).

One potential problem of the quick sort algorithm is the choice of the pivot value. If the pivot value is repeatedly the greatest or least element in the list being examined, then quick sort's efficiency will be reduced to O(n²). As mentioned in class, one way to prevent this is to choose a random value from the list to act as a pivot, but this still has a (very slight) chance of selecting a bad pivot value. Another solution that could be used (but that may not be the best trade-off because of the extra iterations/operations required) is to find the values of the first, last, and middle elements of the list, and to choose the median of these as the pivot (guaranteeing that you don't have the worst pivot value possible).

Until now, efficiency has never really been my primary concern. I'd rather get a working solution first than try to find both an efficient and correct solution at once. Once I have a working solution, then I try to make my code more efficient. However, I'm realizing that this isn't the best approach to programming, and that the best solution is more desired than a great solution. Sure, both will accomplish the same goal, but regarding the inner workings of a computer, it is much better if less time and space are consumed in the process. If I only looked for a quick, easy solution to sorting, for example, I probably would have settled for the familiar and natural selection sort. I wouldn't have bothered with the more complex and efficient algorithms of merge and quick sorts. This course has changed my programming approach and has equipped me well for future programming, especially with all the tricks and tips taught to us throughout the semester. So, for helping me learn how to code both correctly and efficiently, to Professor Danny, to my TAs, and to my peers, I say: thank you! :)

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! 

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.