Chapter 3: Understanding Algorithms and Algorithmic Thinking

In this chapter, we will focus more closely on understanding algorithms and algorithmic thinking. While this is the last step in the computational thinking process, it is critical that we understand how algorithmic thinking helps us plan and understand our problems better. That is, the more we practice algorithmic design and algorithmic thinking, the easier it is to understand, decompose, and recognize patterns when problems are presented to us.

In this chapter, we will cover the following topics:

• Defining algorithms in depth
• Designing algorithms
• Analyzing algorithms

After reading this chapter, you'll understand algorithms better. So, we'll begin by analyzing the definition of algorithms again, which we covered previously in Chapter 2, Elements of Computational Thinking, as well as how to design mathematical and computational algorithms.

Technical requirements

You will need the latest version of Python to run the codes in this chapter. You will find the full source code used in this chapter here: https://github.com/PacktPublishing/Applied-Computational-Thinking-with-Python/tree/master/Chapter03

Defining algorithms in depth

As we mentioned in Chapter 2, Elements of Computational Thinking, an algorithm is simply a set of instructions. We use instructions in everyday life, sometimes consciously, sometimes unconsciously. Think about the routines you follow in the morning, for example. The alarm clock sounds. What do you do next? Do you go prepare coffee? Shower? Brush your teeth first?

Most of us follow the same steps every single morning. You could say we've programmed ourselves to follow those steps. Now think of a time your schedule changed and your routine was different. I know I've had to stop and regroup many times because my program no longer works. I can't wake up at 6 a.m. for a 5 a.m. flight, for example.

Algorithms for computers are similar in that we need to reprogram the set of instructions if a set of conditions has changed. The programs can only go as far as we have stated parameters for them. Most programs cannot adjust or adapt to any new information that is not previously coded into it. That said, machine learning and artificial learning are evolving. We're not talking about those kinds of programs, but even in those instances, we'd still need to adjust those programs to do what we need them to.

To design algorithms, we need to make sure that they meet some specific characteristics:

• They are clear and unambiguous.
• They have inputs that are well defined.
• They have outputs that are well defined.
• They have finiteness.
• They are feasible.
• They are language-independent.

Let's look at each of the characteristics in the preceding list and define them.

Algorithms should be clear and unambiguous

An algorithm is clear and unambiguous when every one of the steps can easily be understood, is easily defined, and has inputs and outputs that are also clear and well defined. There should also be only one meaning for each component of the algorithm.

Algorithms should have inputs and outputs that are well defined

The inputs for an algorithm can be user-provided, meaning that the user of the program enters the data. Input can also mean something that is defined within the program. This means that I may include a variable with a set value already provided.

For example, if I need a user to tell me the number of tickets they are purchasing, I can write the algorithm to ask for that input. I can also give that input as a defined variable with a given value already. An algorithm does not always require an input – zero-input algorithms do exist – but when the algorithm requires input, defining that input is important. An example of an input is asking for a user's name in a program. Think about modern video games. Many of them will prompt the user for a name with phrases such as, "Hello traveler. What is your name?"

As a user, I'd enter Sofia when given that prompt, which gives me the following:

"Hello Sofia. Welcome to the adventure!"

As you can see, the game will then produce an output and uses my name in that output.

This final line is the output of the program. I can write a simple program to ask that question in Python as well:

ch3_nameprompt.py

name = input("Hello traveler. What is your name? ")

salutation = "Hello %s. Welcome to the adventure!" % name

print(salutation)

Notice that we used %s and % symbols here. The syntax here is what we call an f-string. We use the %s syntax to let the program know where we want to insert the information and then we call that information by using the % symbol. In this case, we saved the input to the name variable, then called it in the salutation variable.

When run, the program looks like this:

Hello traveler. What is your name? Sofia

Hello Sofia. Welcome to the adventure!

This simple algorithm allowed us to save the name as a variable. That variable was used only once in the output of this simple code. However, in a game, that name variable may be used in multiple instances, such as during conversations with characters within the game, and so on.

The output of a program is the information that leaves a system, that is, the product of your program. Given some information or code, the output is what is produced from the instructions in the program.

Algorithms should have finiteness

An algorithm has to have finiteness. This means that an algorithm must end. Let's look at a situation where an algorithm would not end. I don't recommend writing this or running it! Nonetheless, let's look at the steps we would take to create this algorithm:

1. Define a variable, i, and set it as equal to 0:

   i = 0

2. Increase the value by 1. There are a few different ways we can do that:

   i = i + 1

   i += 1

   Both of the preceding lines of code will increase the value of i by 1.

3. Add an error! We're about to create an error in finiteness. Again, I'm only doing this to prove a point, but this is an error you want to avoid:

   i = 0

   while i >= 0:

       i += 1

       print(i)

   In this algorithm, I'm telling the program to continue to increase i by 1 so as long as it is greater than 0, then the computer is supposed to print the value. This will just continue to go on forever and ever, without stopping, because the condition will always hold true as given. So, the output for the program will begin at 1, but will continue printing the next item in the sequence as 2, 3, 4, 5, and so on. The program simply has no way to end.

Now, a similar program may be done given a few different conditions. Let's say we want to print all the values of our addition, but only so long as i is less than 15:

ch3_finiteness.py

i = 0

while i < 15:

    i += 1

    print(i)

The preceding program is a terminating program. It now only works for all values while i is less than 15 (not including 15). We will get an output shown as follows:

Figure 3.1 – Output for finiteness code

I know I said this program did not include 15. It doesn't. Since this happens while i is less than 15, the last value it will evaluate for is 14. However, it says that while the value is less than 15, we increase it by 1 (i += 1). So, when i is 14, the printed value is 14 + 1, or 15. Finiteness allows the program to terminate.

Algorithms have to be feasible

An algorithm also has to be feasible. To be feasible, an algorithm needs to be possible with the available content and resources. When writing algorithms, we have constraints, or conditions we may write into the steps. If there is no way to meet all the constraints, then the algorithm isn't feasible. Think of the two conditions, given as follows:

• It is 3:00 p.m.
• It is 5:00 p.m.

If we set both of these constraints on a variable, for example, it would not be possible. It cannot be both 3:00 p.m. and 5:00 p.m. at the same time. This is what we call infeasible. While the algorithm can continue, we're still creating a problem by making these two things true at the same time. Some constraints will never be met, so the algorithm is considered infeasible. There has to be a way for the algorithm to meet all constraints in order to be feasible. In addition, if an algorithm is written to depend on future technology, for example, it is also considered infeasible.

Algorithms are language-independent

Finally, an algorithm must be language-independent. The set of instructions in an algorithm should be written as simply as possible. A good algorithm will be such that it can be written in any language easily and produce the same output.

In this section, we learned about algorithms and the characteristics needed to design them. Keeping in mind the characteristics of a good algorithm will allow us to avoid errors and create working algorithms for whatever problems we are presented with, let's now take a look at how to design some algorithms.

Designing algorithms

When designing algorithms, order matters. There are hierarchies that matter when we are working with programming languages. That includes when we are working with Python. Think about this as the order of operations in mathematics. If you recall, we use the mnemonic PEMDAS to remember the order of operations in mathematics. PEMDAS stands for Parentheses, Exponents, Multiplication/Division, and Addition/Subtraction.

I write Multiplication/Division together like this because multiplication and division hold the same weight. That is, multiplication does not necessarily need to happen before division. If I have a division first and then a multiplication from left to right, then the division happens first. The same is true for addition and subtraction. Neither has more weight than the other, so we perform them in order of appearance from left to right.

Let's write a mathematical algorithm for a problem. We'll look at an algorithm in a food setting. And yes, I know I write about food and food algorithms a lot. I love food almost as much as I love code.

Problem 1 – An office lunch

An office is ordering catering for employees. Employees were given two lunch options: sandwiches or salads. Each sandwich meal costs $8.50, while each salad meal costs $7.95.

Office lunch mathematical algorithm

The number of employees who choose each option is unknown. Let's use some variables to help us in designing the mathematical algorithm. Let's use s for the number of sandwiches and b for the number of salad bowls. And I know what you're thinking, those two variables aren't very helpful if you come back to this problem a while from now. But we'll talk about that in a second. For now, let's just write what our total cost, c, will look like:

This is a simple mathematical problem that requires two unknown variable inputs, s and b, in order to get our total, c. Now let's look at a different version of the same lunch scenario.

Office lunch Python algorithm

Now let's think about a few more considerations when writing the program. As we design a Python algorithm for this problem, we'll need to think about two perspectives: the programmer and the user.

Sometimes we're both the programmer/developer and the end user for our programs, but many times, we'll write or develop content for someone else to use. It is important that we keep those considerations in mind because it may affect how we write our program and define our variables. In addition, if we're writing a program as part of a company, others may need to go and edit our programs at some point.

That means we need to write the program in a way that others will be able to understand. Our variables should be easily understood, so writing a simple one-letter variable may make it harder for another programmer or user to understand. Let's look at a program for Problem 1. Recall that in that problem, we're trying to determine the final cost for an office lunch for employees given two possible options:

• $8.50 for a sandwich meal
• $7.95 for a salad meal

Let's create the program for this problem using Python. Let's clarify some variables first. We'll want to use full words or a series of words separated by _ to define these variables. Before we start, you may want to recall that for Python variables, some rules need to be followed so as not to cause an error:

• Variables must start with a letter or an underscore (_).
• Variables can only contain letters, numbers, and underscores.
• Variables cannot start with a number.
• Variables are case sensitive (alpha is not the same variable as Alpha or ALPHA).

For Problem 1, we need three variables:

• The total cost of the lunch
• The number of sandwich meal lunches
• The number of salad meal lunches

Now we need to name them:

• total_cost = the total cost for all lunches
• number_of_sandwiches = the total number of sandwich meals ordered
• number_of_salads = the total number of salad meals ordered

The important thing here is that those variables are easily read and easily understood. I should make a note that I am partial to lowercase variables when programming. I do have some exceptions for when I like to use capital letters, but you'll see many examples with only lowercase letters and underscores. I found a long time ago that even when capital letters made sense to me at the time I was writing a program, I'd later forget which letters were capitalized, which was just an added headache that could be avoided if I just used lowercase letters instead.

In addition, some programmers eliminate the underscores and use variables such as numberofsandwiches or simply sandwiches, for example. Both of those are acceptable, of course, and the simple sandwiches will make it easier to write some of the code. There are both pros and cons to doing this, however. If someone else is looking at the program, readability will be important. Like I said, I am partial to clear, lowercase variables and the use of underscores, but it is up to every programmer to make that choice themselves.

Now that I have defined my variables, I can begin to write my program. What will I need to ask the user for? I need inputs from the user for both the number of sandwiches and the number of salads. What I want as an output, or what the user will want as an output, is the total cost of the lunch. To ask for input from the user in Python, we need to use the input command. However, we also need to remember that since we are using this number in an algorithm that uses a float number (decimals are float characters), we need to convert the number provided to integer or float. Employees will not be able to order half a salad, so we can safely save them as integers, or int. As a reminder, comments in Python start with a # symbol. Write the code in IDLE, shown as follows:

ch3_officelunch.py

#Ask the user for the number of sandwich meals ordered and save as variable.

number_of_sandwiches = int(input("How many sandwich lunches were ordered? "))

#Ask the user for the number of salad meals ordered and save as variable.

number_of_salads = int(input("How many salad lunches were ordered? "))

#Create total_cost variable and save the algorithm for total the new variables.

total_cost = 8.50 * number_of_sandwiches + 7.95 * number_of_salads

#Print the total cost. Don't forget to convert the total_cost to string.

print("The total cost for the employee lunch is $" + str(total_cost) + ".")

When running the code, the user can enter the number of each of the options for the office lunch. The code first asks the user for the number of sandwiches like so:

How many sandwich lunches were ordered?

The code will then ask for the number of salad lunches and provide a total cost. The following sample takes an input of 12 sandwich lunches and 23 salad lunches, which would be a total cost of $284.85:

How many sandwich lunches were ordered? 12

How many salad lunches were ordered? 23

The total cost for the employee lunch is $284.85.

Now let's take a look at a similar problem, but from a different perspective.

Problem 2 – A catering company

Let's say you start a simple catering company. You begin only selling two options, a sandwich meal for $8.50 and a salad meal for $7.95. You can create a program that stores these options using a Python dictionary.

You can find additional information on the Python programming language and dictionaries in Chapter 8, Introduction to Python, but we'll define a Python dictionary here as well. A dictionary is used when we want items that are unordered, can be changed, and are indexed. Here's an example of a dictionary for our catering company in Python:

ch3_cateringdict.py

catering_menu = {

    "sandwiches": 8.50,

    "salads": 7.95

    }

print(catering_menu)

Now, dictionaries are common and very useful for various reasons: primarily, that they are easy to read and they provide a way to change data as required.

When printed, the dictionary code looks like this:

{'salads': 7.95, 'sandwiches': 8.5}

Now that you have a dictionary, let's talk about its usefulness to your catering company. Let's say that there is a cost increase for your salad ingredients that you want to account for by changing the price of the salads. You can do so in a few different ways. You can change it in the original program, since it is so short, or you can just tell the program what you want to change based on the key. This is important because you may have two items for sale now, but what happens when your menu options become much wider? Would you want to search for each item every time you change a price? Python makes it easy to identify what you want to change and then change it.

To do so, you can use the following code:

catering_menu["salads"] = 9.50

Your new code in Python looks like this:

ch3_cateringdict2.py

catering_menu = {

    "sandwiches": 8.50,

    "salads": 7.95

    }

catering_menu["salads"] = 9.50

print(catering_menu)

When printed, the new value for the salads will be shown:

{'salads': 9.5, 'sandwiches': 8.5}

But, what happens if you want to add a menu item? Say you want to add a soup option for $3.75. In this case, you can add the menu option to your dictionary by using a simple line of code, as follows:

catering_menu["soup"] = 3.75

When you put it all together, the initial code and the changes would look like the following code block. Notice that you have the initial dictionary, then the two changes below that. When you print the dictionary, it will include all changes along with the addition of the soup option:

ch3_cateringdict3.py

catering_menu = {

    "sandwiches": 8.50,

    "salads": 7.95

    }

catering_menu["salads"] = 9.50

catering_menu["soup"] = 3.75

print(catering_menu)

Now that you have added the soup item, you can print your dictionary to see your full menu:

{'soup': 3.75, 'salads': 9.5, 'sandwiches': 8.5}

We can use the information within the dictionary to create more robust programs, such as an online menu, an ordering menu option, and much more. In this section, we learned about designing an algorithm with the help of two problems.

We will take a look at more development using Python through additional problems in the following chapters of this book, especially in Section 3, Data Processing, Analysis, and Applications Using Computational Thinking and Python. For now, we'll move on to analyzing some algorithms.

Analyzing algorithms

As mentioned previously in this chapter, when we design algorithms, they should meet the following characteristics:

• They are clear and unambiguous.
• They have inputs that are well defined.
• They have outputs that are well defined.
• They have finiteness.
• They are feasible.
• They are language-independent.

In addition to those characteristics, when we are looking at algorithms and analyzing them, we want to make sure we ask ourselves some questions:

• Does the algorithm do what we want?
• Does the output make sense?
• Is there another way to get the same information in a clearer way?

There are many more questions we can ask ourselves when analyzing algorithms, but for now, let's take a look at some algorithmic solutions and analyze them based on the aforementioned characteristics and questions.

Algorithm analysis 1 – States and capitals

A student has created an algorithm that includes a list of US states and the capitals for each of those states, but only those states she has already studied are included. Her algorithm is shown as follows:

ch3_statecapitals1.py

Ohio = "Columbus"

Alabama = "Montgomery"

Arkansas = "Little Rock"

print(Ohio)

The program is simple, yet not easy to use, nor helpful when run. Does it contain the information needed? Yes. Can we organize it in a different way so we can call the information in other ways? Yes.

Think about states and capitals as key pairs. We can use a dictionary to store the information. You may recall from earlier in this chapter that a dictionary can be adjusted and adapted easily, adding a new key with a simple line of code. Let's first convert the information in the previous code into a dictionary:

ch3_statecapitals2.py

state_capitals = {

    "Ohio" : "Columbus",

    "Alabama" : "Montgomery",

    "Arkansas" : "Little Rock"

    }

print(state_capitals["Ohio"])

Notice that we can now access the information for the state capital by simply giving the state name. The output for this code is simply Columbus. But what if you just want to run the program and ask for the user to input a state of their choosing? We can also write that in a line of code with the existing dictionary. Take a look at the following code:

ch3_statecapitals3.py

state_capitals = {

    "Ohio" : "Columbus",

    "Alabama" : "Montgomery",

    "Arkansas" : "Little Rock"

    }

state = input("What state's capital are you looking for today? ")

capital = state_capitals[state]

print("The capital of " + state + " is " + capital + ".")

In this code, the user enters the state for which they want to find the capital. This is helpful, as you can just run the code each time without having to go into it to change the line of code to be printed, which we had to do with the algorithm in the ch3_statecapitals2.py file. The code, when run, looks like this:

What state's capital are you looking for today? Alabama

The capital of Alabama is Montgomery.

Now let's look at the need for the algorithm in the first place. The student wants to continue to add states to the program. With this program, since it is dictionary-based, she can simply add a line of code when she needs to add another state. For example, if she wanted to add the state of Iowa, whose capital is Des Moines, she'd need to use the following code:

state_capitals["Iowa"] = "Des Moines"

Take a look at the following code block. Note the placement of the code within the program. It is important that we place that new code before the new variables, otherwise, if you try to run the program and input Iowa, the code will return an error rather than providing the capital of Iowa.

In algorithms, logic is extremely important. We cannot use a value we have not defined in variables that have already been used. That is, if the variables state and capital are used before identifying the new value for Iowa, then the code ends with an error when the input is Iowa. However, if we add the key pair values before we run those two variables, the code runs as expected:

ch3_statecapitals4.py

state_capitals = {

    "Ohio" : "Columbus",

    "Alabama" : "Montgomery",

    "Arkansas" : "Little Rock"

    }

state_capitals["Iowa"] = "Des Moines"

state = input("What state's capital are you looking for today? ")

capital = state_capitals[state]

print("The capital of " + state + " is " + capital + ".")

As you can see, we can adapt and adjust the code to better suit our needs. Now let's take a look at a few algorithms to determine whether they would run; that is, whether they would produce an error or run appropriately.

Algorithm analysis 2 – Terminating or not terminating?

As we discussed earlier in this chapter, algorithms should be terminating. That is, they must have a way to end, or they can cause many errors. Let's look at an algorithm and analyze it to determine whether it will terminate or not:

x = 0

while x >= 3:

x += 1

print(x)

First, let's take a look at the value of the x variable. The x variable starts the program with a value of 0. The while loop, which states the conditions under which the value of x will change, states that when the x value is greater than 3, it is incremented by a value of 1.

This algorithm terminates because it will print the original value for the variable, 0. However, this algorithm doesn't really perform any actions, as the condition will never be met. Also, notice that the print command is not indented. If it were indented, no output would be given for this algorithm, as the print command would never be called since the variable will never meet the conditions of the while loop.

Now let's take a look at the following algorithm:

j = 0

while j >= 0:

j -= 1

print(j)

In this case, the variable condition is met because j has to be greater than or equal to 0 for the program to run. Once the condition is met, the value of the variable is decremented by 1, so the print command will produce an output of -1. The code will not run a second time because the value of the variable is no longer greater than or equal to 0. This algorithm is terminating, produces an output, and is feasible.

Finally, let's take a look at the following algorithm with a changed condition:

j = 0

while j <= 0:

j -= 1

print(j)

In this case, the algorithm isn't terminating. Because we changed the while loop to be less than or equal to 0, this algorithm will now continue to run forever.

Analyzing algorithms can be very complex. We have only started to touch on some of the components of algorithms. As we delve deeper into other computational thinking problems throughout this book, we will need to keep in mind the characteristics of a good algorithm in order to analyze our own code effectively. It is also important that we continue to take into consideration the elements of the computational thinking process: decomposition, pattern recognition, pattern generalization, and algorithm design.

When we are designing the algorithm and testing it, using the characteristics of good algorithms will allow us to observe errors, adjust our algorithm for ease of use, provide better inputs and outputs, and ensure that we are not creating infeasible and non-terminating algorithms.

Summary

In this chapter, we discussed the definition of an algorithm, which is a set of steps that allows a computer to complete a process and provide some output. We went through the characteristics of algorithms.

We designed algorithms based on problem scenarios and then analyzed algorithms to determine whether they met the characteristics needed to run properly. Understanding the characteristics of algorithms and how algorithms work will allow us to create algorithms with far fewer errors than if we were unaware of these characteristics. Notice that I said fewer errors.

When working with code, errors are a fact of life. We will inevitably make mistakes and we will accidentally introduce bugs or make some code infinite. Understanding the characteristics of a good algorithm allows us to reduce those errors, even if we don't fully eliminate them from our daily lives.

In the next chapter, we will be learning more about logical reasoning. Throughout the chapter, we will discuss the definition of logic, learn about inductive and deductive reasoning, add to our knowledge of operators and Boolean logic, and learn more about logic errors. We will be using elements of computational thinking and the characteristics of algorithms to further our knowledge of logical reasoning.