Today we're going to continue working on algorithms. In the context of the Sandvig reading for this week, we're going to think about some different ways of "seeing" algorithms, although we are not going to visualize them, per se.
The Sandvig text discussed the fact that algorithms operate digital machinery in way that is different from say industrial manufacturing machinery. The "algorithm" that operates an assembly line and the algorithm of a computational process both may be out-of-sight for someone without access to the space in which those processes run. But Sandvig claims that at least in the manufacturing context, were one to gain access to the machines, it would be clear to see the process of their operation, whereas with the computational process, even if one were to gain access to a data center, or even to the inside of a server, it still would be impossible to directly observe the algorithm unfold. The article goes on to consider different ways that people have visualized such computational algorithms
But at the end of the piece, Sandvig suggests we might try to develop a "countervisuality of algorithms" that is perhaps more than visual representation: "We require more than a depiction of how algorithms work: we need to know how [they] work." (Emphasis added.)
What if "seeing" algorithms is not enough, and perhaps even might be part of how we continue to be baffled by algorithms. Does visualizing always induce understanding? Sandvig writes that "depictions of algorithms slow down the action of a computer so that it can be seen." Today we are going to develop some techinques for analyzing algorithms that require stepping through them and understanding their logic.
A visualization of an insertion sort on 10, 50, and 100 items. Click here to download this video. You can also click through to watch it on YouTube.
Table of contents for the topics today: (Click each to jump down to the corresponding section.)
A technique for stepping through code and making a list of all variable values as they change.
Can be tedious but a powerful way to practice reading code and wrapping your head around the implementation of an algorithm.
Let's revist the insertion sort algorithm that I shared at the end of last class.
Today we'll be looking at a slightly different version of this algorithm than did last week.
Last week we looked at a sort that created a new list. Today we'll be looking at a version of this algorithm that sorts the list in place. In other words, it modifies the list that is your input data and puts it in order.
Let's look at this code. How to make sense of it? Let's try stepping through it for some sample values
my_list = [ 50, 85, 12, 42, 8 ]
i = 1
while i < len(my_list):
current_position = i
current_item = my_list[i]
while current_position > 0 and my_list[current_position-1] > current_item:
my_list[current_position] = my_list[current_position - 1]
current_position = current_position - 1
my_list[current_position] = current_item
i = i + 1
Another algorithm we can experiment with is finding items that are included in two lists.