Code as a Liberal Art, Spring 2024

Unit 1, Lesson 2 — Thursday, February 1

Coding algorithms

Today we're going to go from the abstract idea of what algorithms are to actually implementing some algorithms in computer program code. We're going from the first exercise where you devised an algorithm for sorting a deck of cards, to implementing some algorithms in Python to sort numbers, words, and even filtering the pixels of an image.

So often in discussions of digital media, we talk about and theorize algorithms in general terms, as abstract, formal sequences of instructions. So much recent socio-political study of technology has rightly realized the need to reckon with the power and prevalence of algorithms and the ways they shape daily life, from shopping to socializing to how we acquire news.

Introductory computer programming and creative coding classes and bootcamps often claim to educate about how algorithms actually work, but the fact is that most of the coding that we do in those contexts does not actually involve puzzling through the implementation of algorithms of the kinds studied by computer scientists, nor of the kinds that have become such influential mediators of our socio-cultural patterns. Today we're going to work through some exercises that might hopefully help you start to fill in that gap.

Table of contents for the topics today: (Click each to jump down to the corresponding section.)

1. Python Primer
   1. Statements, expressions, and operators
   2. Comments
   3. Variables
   4. Lists
   5. forloops
   6. if statements
2. Coding algorithms (search)
3. Sorting
4. Wrapping up & homework

I. A (Brief!) Python Primer

As I described in class, this semester we will be taking more of a deductive mode of learning rather than an inductive mode. By that I mean that in a more inductive style coding class (like my Code Toolkit class), we might start from some core building blocks, and work our way up to more complicated ideas, step by step. By contrast, in this class we will start from higher level concepts, like searching and sorting algorithms, kind of working our way backwards and learning just enough coding building blocks to understand the examples we'll be examining.

To that end, today we'll be experimeting with coding our first algorithm, which will be a searching algorithm (e.g. finding the smallest number in a list) but first let's take a step back and review some code coding concepts in Python to make sure you'll be able to understand the code for this algorithm.

So here is a very, very, way-too brief primer of some Python concepts including: statements, expressions, operators; variables; lists; for loops; and if statements.

a. Statements, expressions, and operators (oh my?)

In Python, as in most major programming languages, code can be described as consisting of statements, expressions, and operators.

Statements comprise one line of Python code. In some programming languages that you may have seen (like Javascript), statements are ended with semicolons (;). But this is not the case in Python, where statements are simply ended by a line break.

Statements consist of expressions and operators. Expressions are things that have a value. They can be numbers or text, as well as variables that hold numerical or textual values (which we'll talk about in the next section) and even other data types like images, files, lists, or other data structures.

Here's an example of a statement. The expressions here are score and 42, and the = is an operator.

score = 42

Operators include all arithmetic with the symbols +, -, * (multiplication), and / (division). If you remember "PEMDAS" from algebra, that applies here as the order of operations, so you can use parenthesis to control that. Here is another statement. The entire right-hand side is an expression comprised of other expressions combined by arithmetic operators:

average = ( score1 + score2 + score3 ) / 3

Here's another statement in which the expression is the string of text "My name is Gritty", and the operator is print(). (Some people might disagree with me that print is technically considered an operator, and if we're being precise about Python structure that's probably true. But for the purposes of this discussion I think we can call it an operator.) This statement would print out this string of text in the terminal.

print("My name is Gritty")

b. Comments

In your code you can leave notes to yourself.

In Python, anything the hashtag character # to the end of the line is ignored by Python.

# This is a comment
print("Hello") # Comments can also be placed at the end of other statements

Another way to include a comment with three double-quotes, """, like this:

"""
This is a multi-line comment.
It can span many lines.
"""

In your classwork this semester, please include a multi-line comment at the top of each code file with your name and the assignment name, as you would do if you were handing in a written paper.

"""
Rory Solomon
Code as a Liberal Art, Spring 2024
Unit 1, Lesson 2 Homework
"""

Aside from that, use comments as a way to leave notes in your code to help explain the code to yourself and others. Reading code is hard, so leaving comments as you write it can be extremely useful.

c. Variables

In computer programs, instead of specifying values directly like 42 or "Gritty", we often use variables. A variable is a placeholder. It is a word that holds a value.

To use a variable you make up a name, assign a value to it, and then reference that name in place of the value. The equal sign (=) is the assignment operator and you can read it from right to left. Python will evaluate the expression on the right, and then assign it to the variable named on the left. So you can almost read the assignment operator as like an arrow pointing from right to left.

score = 42
name = "Gritty"

Now we can use these values in other statements, and you can then change the value of the variable later on.

print(name)
name = "Monster"
print(name)

These three lines would output the following:

Gritty
Monster

Note that when I re-assigned the value "Monster" to my variable name, it kind of just overwrites any value that was there previously.

An extremely common technique is to modify the value of a variable rather than completely overwriting it with a new value. You can modify the value with an operator and then assign that new value back to itself. For example:

score = score + 1

In this case, Python evaluates the expression on the right by getting the current value of score, then increasing it by 1, then re-assigning that to the variable score as a new value. This pattern of increasing a variable value by 1 is called an increment and is very common.

The purpose of variables is that they allow you to write code that can implement some algorithm in which you don't know in advance all the values that you'll be working on. In contrast to variables, we say that values specified directly are hard-coded. If you could only write code with hard-coded values, it would be a lot less useful. Think about a program that greets its user with a print() statement. If you had to hard-code the user's name, the program would not be useful to other people. By using variables in your code, you can write programs that dynamically respond to input data in various ways. But this makes writing programs more challenging because you don't often know the precise values that you are operating on. Instead, you have some possible range of values, and you have to write your code with variables to that it operates correctly for any value in that range of possibilities.

c. Lists

Lists are a special kind of variable called a data structure. Data structures allow you to store more than one value in a single variable. We'll talk about data structures more later in the semetser.

Lists, as the name implies, store lists of many values. (In other programming languages these are sometimes referred to as arrays.)

For example:

names = [ "Gritty", "Bernie", "Sharkie" ]

Lists are created with the above square bracket notation ([ ]) with individual values separated by commas.

After creating a list, you can reference individual values in the list by number, called the index, also using square brackets, like names[0]. So the following code:

print( names[0] )
print( names[1] )
print( names[2] )

would have this output:

"Gritty"
"Bernie"
"Sharkie"

Note that the index always begins with 0, so a list with four items would be referenced with 0, 1, 2, and 3.

You can add more items to a list with the append() command like this:

names.append("Gnash")

You can print an entire list with the print() command:

print(names)

which outputs the list in a nearly identical format to the syntax used to create a list.

You can also ask for the number of items in a list with the len() command (short for "length").

print( len(names) )

d. for loops

The power of lists becomes more apparent when we can write code to do something with each item in the list. The first technique we'll see for how to do this is with a control structure called a for loop.

The syntax looks like this:

for name in names:
    print(name)

This code visits each item in the list one-by-one, sequentially, in the order in which they were added to the list. For each value in the list, it sets that value in a kind of temporary way to the variable name, and then runs any lines of code that are "inside" the loop, i.e. the lines that are indented after the colon :.

The above loop would simply print each name in the list, but this opens up the possibility to implement sophisticated algorithms by executing any code operations once for each item in a list.

e. if statements

The last bit of code we'll need to discuss to help you understand the algorithm for today is another control structure known as an if statement.

An if statement is used to ask a question about variables in your code, and to execute different code block possibilites based on the answer to that question.

For example:

if len(names) < 3:
    print("There are less than 3 names")
else:
    print("There are 3 or more names")

The else here can be understood as "if not". So the above code snippet is like saying: if the length of the names array is less than 3, then print the first message, otherwise (if not) then print the second message.

The < is called a comparison operator and Python allows many comparisons: < (less than), > (greater than), == (equal to), <= (less than or equal to), and >= (greater than or equal to).

Note that the double equal sign (==) is not an assignment operator but rather a question that is asking if two values are equivalent.

You are also able to combine comparisons together using the logical operators and (both terms must be True), or (either term must be True, and note (the term must be False).

This is a very quick overview of these coding techniques, and I'll include more explanation about them throughout the semester, but hopefully this is enough to enable you to understand the implementation of the below algorithm.

(jump back up to table of contents)

II. Coding algorithms (search)

To implement our first algorithm in code, let's start by thinking about how you would design the following algorithm:

 Find the smallest number in a list of numbers.

(Similar to command line code and Python code, I will use this gray background with thin double-borders to indicate "pseudocode": this is not valid programming language syntax, but is plain English that is meant to read algorithmically. It is a kind of in-between step in the process of translating from human communication to machine instructions.)

It might be hard to actually think through the process that your brain is going through when you find the smallest number in a list. Maybe it will help if we consider an actual list of (basically random) numbers:

If you are like me, your mind may have done something like this:

Look at the first number, and let's call that "the smallest number" for the moment.

Now, compare the next number to "the smallest number":
  if the next number is smaller than "the smallest number", then it now becomes the smallest.
  Repeat this for every other number.

At the end of the list, "the smallest number" will be smaller than all the others.

Let's try to translate this into Python code.

Create a new folder for all your work this week. Close any VS Code windows, open a new one, and drag that folder into it to set this week's folder as your VS Code workspace. Now, in VS Code let's create a new file (File > New File) and give it a name. Anything that ends with .py, for example unit1_smallest_number.py.

Start by creating the list of numbers with this Python code:

number_list = [ 2342, 3142, 4124, 6873, 6741, 8922, 5173, 3453, 2484, 9091, 2248, 3920, 2721, 7592 ]

Now, let's implement the first part of the algorithm:

number_list = [ 2342, 3142, 4124, 6873, 6741, 8922, 5173, 3453, 2484, 9091, 2248, 3920, 2721, 7592 ]

smallest_number = number_list[0]

This new syntax says take the first item in the list (the [0]) and assign that to a variable called smallest_number.

The next part of the algorithm said to "compare". We do that with an if statement, like this:

number_list = [ 2342, 3142, 4124, 6873, 6741, 8922, 5173, 3453, 2484, 9091, 2248, 3920, 2721, 7592 ]

smallest_number = number_list[0]

if number_list[1] < smallest_number:
    smallest_number = number_list[1]

Then our pseudocode said to "Repeat this for every other number". We implement repetition with a for loop, like this:

number_list = [ 2342, 3142, 4124, 6873, 6741, 8922, 5173, 3453, 2484, 9091, 2248, 3920, 2721, 7592 ]

smallest_number = number_list[0]

for n in number_list:
    if n < smallest_number:
        smallest_number = n

That will loop over every number in the list, and temporarily refer to each one as n. Each time the loop executes, it will compare n (the current number in the list) to the current smallest number (i.e. smallest_number) and if n is smaller, it now becomes the smallest number.

That's it! That's all there is to this algorithm. Now we can just print an informative message at the end:

Example 1: Find the smallest number

number_list = [ 2342, 3142, 4124, 6873, 6741, 8922, 5173, 3453, 2484, 9091, 2248, 3920, 2721, 7592 ]

smallest_number = number_list[0]

for n in number_list:
    if n < smallest_number:
        smallest_number = n

print("The smallest number in this list is: " + str(smallest_number) )

In my print() statement, the plus sign (+) is not addition, but string concatenation: it appends one string onto another. Remember how numbers and strings are different? The str() command converts the number into a string so that it can be concatenated. Without that, the addition operator + would give a TypeError.

Alternatively, the print() command allows you to print multiple values separated by commas, so you could modify the above print() statement like this:

print("The smallest number in this list is: ", smallest_number )

Try running this file from the command line and see what happens:

$ python unit1_smallest_number.py
The smallest number in this list is: 2248

Let's call this type of algorithm a search: we are looking through a collection of data for some particular value. In this case we are simply looking for the smallest number, but we could do more complicated things.

You can combine different logical statements with the and operator. So if we were looking for the smallest number that was greater than 100, we could say this:

for n in number_list:
    if n > 100 and n < smallest_number:
        smallest_number = n

Experimenting with this further will be part of the homework for this week.

Swapping out text for numbers

One great thing about Python is that many of the comparison operators (e.g. < and >) work equally well for text as for numbers. This will be an exercise in the homework.

(jump back up to table of contents)

III. Sorting

(Note: We did not get to this section of the lesson in class. The homework reflects this and does not ask any questions about sorting algorithms like this one. If we have time next week we'll review this sorting example.)

Let's try a slightly more complicated algorithm: putting a list of numbers in order.

Computer scientists call this sorting. Perhaps this is somewhat of a misnomer. Usually in common language "sorting" might mean putting items into buckets or categories, while arranging things in sequence would probably be called "ordering". But in any case, in computer science, sorting means putting a collection of things into some order and it is one of the most common algorithms. Sorting algorithms can be some of the simplest introductions to working with algorithms, but they can also get incredibly complex as we try to find faster and more efficient ways of implementing them.

Thinking back to your card sorting algorithm, how might we describe a strategy to put a list of numbers into increasing order?

Using some of the same principles from our Smallest Number algorithm, let's try this:

Given a list of unordered numbers

Make a new, empty list

Put the first item from the unordered list into the new list

Now consider the next item in the unordered list:
    If it is smaller than the item in the new list, then put it first
    If it is larger than the item in the new list, put after

For each subsequent item in the unordered list, find where it fits into the new list.
In other words:
For each item in the unordered list:
    Compare it to each item in the new list:
        If it is bigger, move on
        If it is smaller, insert it before
      

Let's implement this in Python as well. Make a new file in VS Code (File > New File). Start with the input list again:

unordered_list = [ 2342, 3142, 4124, 6873, 6741, 8922, 5173, 3453, 2484, 9091, 2248, 3920, 2721, 7592 ]

Now we'll make a new, empty list, like this:

unordered_list = [ 2342, 3142, 4124, 6873, 6741, 8922, 5173, 3453, 2484, 9091, 2248, 3920, 2721, 7592 ]
	
new_list = []

Now, as I described, take the first item from the unordered list and put it into the new list:

unordered_list = [ 2342, 3142, 4124, 6873, 6741, 8922, 5173, 3453, 2484, 9091, 2248, 3920, 2721, 7592 ]
	
new_list = []

new_list.append( unordered_list[0] )

unordered_list[0] is how we reference the first item in the unordered list, and .append() is the command to add an item to a list.

Next we'll add a loop, to loop over all the items in the unordered list:

unordered_list = [ 2342, 3142, 4124, 6873, 6741, 8922, 5173, 3453, 2484, 9091, 2248, 3920, 2721, 7592 ]
	
new_list = []

new_list.append( unordered_list[0] )

for item in unordered_list:

    # something will go in here ... 

Note my use of a comment here as I work from pseudocode to actual code.

What do we do with each item from the underline list? We have to check it against each item in the new list. So we need another loop. This one will look a little different:

unordered_list = [ 2342, 3142, 4124, 6873, 6741, 8922, 5173, 3453, 2484, 9091, 2248, 3920, 2721, 7592 ]

new_list = []

new_list.append( unordered_list[0] )

for item in unordered_list:

    j = 0
    while item > new_list[j]:
        j = j + 1

    new_list.insert( j, item )

This is a new control structure called a while loop. This new variable j starts out as 0. Then we compare the item from the unordered list with the first item of the new list. If it is greater, we increase j and keep repeating this process. But as soon as the item is not greater than the next item in the new list, we'll have found the place where it belongs. In other words, j will indicate its position. So we can use the .insert() command to insert item at the position indicated by j.

There's only one last problem. Try saving this and running it. You will probably get an error message like this:

$ python unit1-insertion-sort.py
Traceback (most recent call last):
  File "unit1-insertion-sort.py", line 14, in <module>
    while  item > new_list[j]:
IndexError: list index out of range

The problem here occurs when item is greater than everything in the new list. So this while loop gets to the very end, and j is bigger than the size of the list. So the insert gives an error. We can fix it with the following check:

unordered_list = [ 2342, 3142, 4124, 6873, 6741, 8922, 5173, 3453, 2484, 9091, 2248, 3920, 2721, 7592 ]

new_list = []

new_list.append( unordered_list[0] )

for item in unordered_list:

    j = 0
    while j < len(new_list) and item > new_list[j]:
        j = j + 1

    new_list.insert( j, item )

This will guarantee that j does not get too big.

Save this, run it again, and you shouldn't see any error messages. But did it work? We can add some print() statements to watch the new list getting sorted as the algorithm runs. The reading for this week will talk about different techniques for visualizing algorithms. You can think of these print() statements here as a kind of very basic visualization. It allows us to observe how the algorithm ran.

Example 2: Insertion sort

unordered_list = [ 2342, 3142, 4124, 6873, 6741, 8922, 5173, 3453, 2484, 9091, 2248, 3920, 2721, 7592 ]

new_list = []

new_list.append( unordered_list[0] )

print(new_list)

for item in unordered_list:

    print(item)

    j = 0
    while j < len(new_list) and item > new_list[j]:
        j = j + 1

    new_list.insert( j, item )

    print(new_list)

(jump back up to table of contents)

IV. Wrapping up & homework

The homework for this week has some opportunities for you to experiment with these ideas. I hope you find it challenging and rewarding.

---