Algorithms Summary

List or String Analysis

In these algorithms, we iterate through a list or string to determine something about it, such as:

• What is the highest value in the list?
• What do the values add to?
• How many times does a value appear in a list?

The general implementation of these algorithms is:

my_list = [5, 2, 6, 1, 6, 7]
the_thing_I_want_to_determine = 0 # or an appropriate initial value

for i in range(len(my_list)):
    # Add some logic here that examines the current list value, held in my_list[i],
    # and updates the_thing_I_want_do_determine based on that value

print(the_thing_I_want_to_determine)

Let's look at an example where the_thing_I_want_to_determine is a list of the even numbers from the original list:

my_list = [5, 2, 6, 1, 6, 7]
evens_only = []

for i in range(len(my_list)):
    if my_list[i] % 2 == 0:
        evens_only.append(my_list[i])

print(evens_only)

The same approach could be used to extract all vowels from a string:

my_string = "magnificent"
vowels_only = ""

for i in range(len(my_string)):
    if my_string[i] in ['a', 'e', 'i', 'o', 'u']:
        vowels_only += my_string[i]

print(vowels_only)

List or String Item Comparison

In these algorithms, we look at positions in a list/string in relation to each other. Normally, within a loop, i represents the current position, i+1 represents the next position, etc.

Find all double letters and their positions

my_string = "mississippi"

for i in range(len(my_string) - 1):
    if my_string[i] == my_string[i+1]:
        print(f"Found double letter {my_string[i]} at indexes {i} and {i+1}")

Notice the range in the above example only goes to len(my_string) - 1, to ensure that i+1 never references a position past the end of the string.

Nested Loops

These algorithms contain loops inside of loops. For each iteration of the outer loop, the inner loop completes all of it's iterations.

Print a grid pattern

for i in range(4):
    for j in range(5):
        print("*", end="") # Prints * without a new line
    print() # Prints a new line

This next example is almost identical to the one above, except for a small change in the second line:

Print a triangle pattern

for i in range(4):
    for j in range(i):
        print("*", end="") # Prints * without a new line
    print() # Prints a new line

This algorithm counts the number of times the letter e appears in a list of words:

words = ['cup', 'pencil', 'tree', 'phone']
e_count = 0

for word in words:
    for letter in word:
        if letter == "e":
            e_count += 1

print(f"The letter e appears {e_count} times")

Finite State Machines

I will go over how these work in class. As an example, let's suppose we want to determine if a string contains two consecutive digits. The finite state diagram for this problem looks like this:

Here is the Python implementation:

def has_consecutive_digits(string):
    state = "no_digits_found"

    for char in string:

        if state == "no_digits_found":
            if char.isnumeric():
                state = "one_digit_found"

            continue # Start the next loop iteration

        if state == "one_digit_found":
            if char.isnumeric():
                print("Yes")
                return # Exit the subprogram

            else:
                state = "no_digits_found"

            continue # Start the next loop iteration

    # If we get here, we've reached the end of the string
    # and have not found consecutive digits
    print("No")

# Program execution starts here
has_consecutive_digits("Hello") # No
has_consecutive_digits("abc123def") # Yes
has_consecutive_digits("a2b") # No