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.