Algorithmic Thinking in Action

Algorithmic Thinking is one of the eight key principles of computer science. This principle deals with the formulation of computational procedures to solve problems. It requires a clear understanding of the problem at hand and the ability to design a step-by-step procedure (i.e., an algorithm) that provides a solution to that problem. Now, I suggest Algorithmic Thinking is less about the application of computation and more about how to conceptualize computation. Yes, Algorithmic Thinking is an abstract process, not a procedure. Thus, I am going to approach the discussion through the lens of the limitations of this principle. Doing so will let us see Algorithmic Thinking in action.

Ready? Let’s go.

The problem space addressed by Algorithmic Thinking is vast. It ranges from sorting a list of numbers, searching for a specific item in a database, to complex tasks like natural language processing (e.g., ChatGPT) or pathfinding for autonomous vehicles. In essence, any problem that requires a systematic solution can be approached using Algorithmic Thinking.

Algorithmic Thinking is not without limitations, however. Perhaps the most common limitation is not all problems are deterministic. Meaning, there is no clear-cut solution. For example, problems involving randomness, or heuristic-based problems (like the Traveling Salesman Problem), don’t always have deterministic solutions. Such problems require different algorithmic approaches such as probabilistic algorithms or approximations.

The importance of problem type in the context of determinism cannot be overstated. I want to linger here for a few more moments and illustrate the differentiation between deterministic and stochastic (i.e., non-deterministic) in more details. Plus, who doesn’t like code examples?

In general, a simple deterministic approach might be something like in pseudocode:

function bubbleSort(list)
    do
        swapped = false
        for i = 1 to length(list) - 1
            if list[i] > list[i + 1] then
                swap list[i] and list[i + 1]
                swapped = true
            end if
        end for
    while swapped
end function

In this expression of Algorithm Thinking, we iterate over the list multiple times. During each iteration, we compare each number to the one next to it. If the current number is greater than the next one, we swap their positions. We continue this process until we make a pass through the list without having to swap any elements, which tells us that the list is now sorted. That’s Bubble Sort.

This pseudocode demonstrates Algorithmic Thinking as we have:

1. Defined the problem: Sorting a list in ascending order.
2. Designed a step-by-step procedure (algorithm) to solve the problem: Compare each pair of elements and swap them if they’re in the wrong order; repeat until no more swaps are needed.
3. Ensured the solution is deterministic: Given the same list, the algorithm will always sort it in the same way, producing the same final order.

There it is. For the same input, we get the same output. This is possible because the nature of the problem permits deterministic solutions. Take note here because deterministic solutions are not necessarily preferred, computationally speaking. Rather, the nature of the problem lends itself to one approach versus another.

As a practical example in the context of our GameCharacter, imagine we have a group of characters we want to sort dynamically in the User Interface based on their health. Here’s how we could apply the bubble sort algorithm to this scenario using Python:

def bubble_sort_characters(characters):
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(characters) - 1):
            if characters[i].health > characters[i + 1].health:
                # Swap characters
                characters[i], characters[i + 1] = characters[i + 1], characters[i]
                swapped = True
    return characters

# Create some characters
characters = [GameCharacter(100, 20, 1, "Alice"), GameCharacter(50, 10, 1, "Bob"), GameCharacter(80, 30, 1, "Charlie")]

# Sort characters by health
sorted_characters = bubble_sort_characters(characters)

# Print out sorted characters
for character in sorted_characters:
    print(f"{character.name} has {character.health} health points.")

Here, we’ve defined a function bubble_sort_characters that sorts a list of GameCharacter objects in ascending order based on their health. It does this using the same Bubble Sort logic from the pseudocode earlier.

As much as Bubble Sort may not be the most efficient sorting technique, the use of a deterministic algorithmic is correct. Rewarding loot after defeating an enemy is not deterministic by comparison. Thus, we need a stochastic solution such as:

import random

def select_character_for_bonus(characters):
    # Select a random character for a surprise bonus
    selected_character = random.choice(characters)
    return selected_character

# Create some characters
characters = [GameCharacter(100, 20, 1, "Alice"), GameCharacter(50, 10, 1, "Bob"), GameCharacter(80, 30, 1, "Charlie")]

# Select a character for the bonus
bonus_character = select_character_for_bonus(characters)

# Print out the name of the character who received the bonus
print(f"The character {bonus_character.name} has been selected for a surprise bonus!")

In this code, the select_character_for_bonus function implements a stochastic algorithm to select a character at random from a list of characters. The random.choice function is non-deterministic; it could select any character in the list, and running the function multiple times with the same list of characters can produce different results each time.

The problem this code is addressing is the random selection of a character for a bonus, which doesn’t have a correct answer in the way sorting a list does. Therefore, a stochastic algorithm is an appropriate choice here.

Another limitation is the trade-off between efficiency and accuracy. In many cases, the most accurate algorithm might not be the most efficient one, and vice versa. Depending on the problem and the specific requirements, we might have to settle for a less-than-perfect solution in favor of performance. Conversely, we may need to accept a more resource-intensive algorithm to achieve the highest accuracy possible.

Interestingly enough, there is more to understanding this limitation than studying efficiency and accuracy specifically. Doing so- focusing on efficiency for instance- is valid and has a sizable literature pushing towards innovative solutions all the time. Green computing is one such field. However, in the context of discussing the 8 principles of computer science, I suggest we instead inquire whether there is a threshold related to the tradeoff whereby a stochastic algorithm becomes a better solution compared to a deterministic solution. This connects the limitation at hand to the previous Algorithmic Thinking limitation.

For instance, in the prior example our selection of Bubble Sort will produce accurate outputs but is not efficient. The larger the input (i.e., more elements in the array or list), the longer the sorting operation will take to complete.

Fundamentally, the trade-off between efficiency and accuracy in computer science is rooted in the limitations of computational resources and the complexity of problems. Essentially, as the complexity of a problem grows, the time and resources required to compute an exact solution can increase exponentially. This leads to situations where it might be practically impossible to find an exact solution within a reasonable time frame. Likewise, finding the solution might require using an unreasonable amount of computational resources.

This trade-off often becomes relevant in areas such as optimization, machine learning, and data analysis, where the search space can be extremely large or the computations can be particularly intensive. In these cases, we might resort to approximate or heuristic algorithms, which can provide a good enough solution much more efficiently. The consequence is there can be no guarantee of being the absolute best or correct solution.

Okay, this should cause us to ask what is good enough?

Let’s continue with our GameCharacter. Suppose we have a game where the goal is to assemble a team of characters that collectively has the maximum possible strength. Each character has a strength attribute, and we're limited by a certain total team cost (since each character also has a cost).

A deterministic solution to this problem would involve exploring all possible combinations of characters, calculating the total strength for each combination, and selecting the one with the highest strength. Pretty simple algorithm, no? While this would ensure the most optimal team selection, the logic would be computationally expensive with a large number of characters.

A stochastic solution, on the other hand, might involve a heuristic approach where we sort the characters by their strength-to-cost ratio and select the characters with the highest ratio until we’ve reached the total cost limit. This approach doesn’t guarantee the most optimal team but is significantly more efficient.

Here’s an example using Python:

import random

class GameCharacter:
    def __init__(self, strength, cost):
        self.strength = strength
        self.cost = cost

# Generate random characters
characters = [GameCharacter(random.randint(1, 100), random.randint(1, 10)) for _ in range(1000)]

# Total team cost limit
team_cost_limit = 100

# Deterministic approach - check all combinations (not feasible with large lists)
# ...

# Stochastic approach - sort by strength-to-cost ratio and select the top characters
characters.sort(key=lambda c: c.strength / c.cost, reverse=True)

team = []
total_cost = 0
for character in characters:
    if total_cost + character.cost > team_cost_limit:
        break
    team.append(character)
    total_cost += character.cost

# The total strength of the team
total_strength = sum(character.strength for character in team)

print(f"Total team strength: {total_strength}")

Overall, good enough could be a certain level of error that’s acceptable. It could be a specified performance target. Once good enough is established, the efficiency can be assessed in terms of the resources (like time or computational power) required to reach this acceptable level of accuracy. In the above example, the stochastic approach allows us to assemble a strong team quickly, but the resulting team might not be the absolute strongest possible team. The deterministic approach would give the strongest team, but would be much slower and may not be feasible with a large list of characters. This represents the trade-off between efficiency (runtime) and accuracy (optimal solution).

Algorithmic Thinking also requires a solid understanding of the problem domain and potential edge cases. Poorly defined or thought-out algorithms can lead to bad outcomes. Such includes incorrect results, gaps in use case coverage, poor performance, and so forth. Therefore, Algorithmic Thinking requires both theoretical knowledge (to understand the problem and design the algorithm) and practical skills (to implement the algorithm and test its effectiveness).

Foremost, as the complexity of the problem increases, so does the difficulty in devising an effective algorithm. There may be scenarios where the most optimal algorithm is unknown, or the problem may be an NP-hard problem where finding an optimal solution is computationally infeasible with current technology and mathematical understanding.

By the way, in case you hadn’t noticed yet, complexity comes up frequently in computer science. I think this is because complex problem domains have a wide range of rules, behaviors, and situations which is a challenge for an inherently discrete discipline. The interplay between stochastic and deterministic we discussed earlier illustrates this well in the context of Algorithmic Thinking and computation in general.

Anyway, edge cases are scenarios that occur at the extremes of the problem domain. Edge cases often have unique characteristics that aren’t covered by the general rules. Such conditions might be rare, but can significantly impact the outcome of the algorithm. If edge cases are not identified and handled properly, they can lead to unexpected and incorrect results.

Consider the following example we might encounter with our GameCharacter. Imagine we have a combat system where each GameCharacter can attack another GameCharacter. A simple function to handle this might look like this:

class GameCharacter:
    def __init__(self, name, health, attack_damage):
        self.name = name
        self.health = health
        self.attack_damage = attack_damage

    def attack(self, target):
        target.health -= self.attack_damage
        print(f"{self.name} attacked {target.name} for {self.attack_damage} damage.")

Here, when a GameCharacter attacks another, it reduces the target's health by its own attack_damage. But there are several potential edge cases and elements of the problem domain that this doesn't take into account:

1. What if the target’s health falls below zero? In many games, a character’s health shouldn’t fall below zero. Instead, it should remain at zero and the character should be marked as defeated or removed from the game. Not handling this could lead to strange results, like characters with negative health.

2. What if a character attacks itself? The current attack function doesn't prevent a character from attacking itself, which might not make sense in the context of the game.

3. What about defense? In many games, characters have a defense stat that reduces incoming damage. This isn’t taken into account in the current attack function.

Here’s an updated version of the attack function that takes these elements into account:

class GameCharacter:
    def __init__(self, name, health, attack_damage, defense=0):
        self.name = name
        self.health = health
        self.attack_damage = attack_damage
        self.defense = defense

    def attack(self, target):
        if self is target:
            print(f"{self.name} cannot attack itself.")
            return

        actual_damage = self.attack_damage - target.defense
        if actual_damage < 0:
            actual_damage = 0

        target.health -= actual_damage
        if target.health < 0:
            target.health = 0
            print(f"{target.name} has been defeated!")

        print(f"{self.name} attacked {target.name} for {actual_damage} damage.")

With this new function, a GameCharacter can't attack itself, characters can't have less than zero health, and the damage of each attack is reduced by the target's defense. This code better reflects the rules of the problem domain and handles the potential edge cases.

Despite these limitations, Algorithmic Thinking is a vital tool in a computer scientist’s toolbox. It serves as the basis for translating real-world problems into procedures that a computer can execute, and therefore, is central to the field of computer science.

I don’t personally buy into the notion that one must think like a computer, though. Remember, computation is not computing. Computation is a way to think about functions and the input those functions ingest to generate output. In contrast, computing is information processing. I understand how the difference may not make sense, especially since we are using source code examples. Trust me, by the time we finish discussing all 8 principles of computer science the difference will be quite clear. For now, I urge us to think of Algorithmic Thinking as a way to think, not as the right way to think.

Until next time, keep thinking about Algorithmic Thinking and happy computation.