Algorithms Extra Practice 2 (Optional)

Here are some practice problems that will help you prepare for our upcoming evaluation(s). They will not be evaluated, but we will go through solutions together.

Problem 4

Write an algorithm that checks if a list of numbers is already sorted from smallest to largest. The algorithm should work as follows:

• Initialize a Boolean variable unordered_pair_found to False.
• Go through each list item, and check if it is greater than the item to its right. if it is, set the unordered_pair_found variable to True.
• After getting through the list, the unordered_pair_found variable can be examined to determine the solution to the problem.

Test this out with a list of numbers that is already sorted, as well as with a list of numbers that is not already sorted.

Problem 5

A website has very strange password requirements. Passwords must:

• Start with at least one uppercase letter
• This should be followed by at least one lowercase letter
• This should be followed by at least one digit (0 through 9)

Examples of valid passwords are:

• ABCdef123
• Gh33

Examples of invalid passwords are:

• TH98 (no lowercase letters)
• rvYHH56 (lowercase letters come before uppercase letters)

Create an algorithm that determines if a string contains a valid password.

Note - you can solve this problem using a Finite State Machine, but you don't need to use this method.

View Sample Solutions

#### PROBLEM 4 ####

nums = [2, 4, 6, 7, 9, 10]

unordered_pair_found = False
for i in range(len(nums)-1):
    if nums[i+1] < nums[i]:
        unordered_pair_found = True

if unordered_pair_found:
    print("The list is unsorted")
else:
    print("The list is sorted")



### Problem 5 ###

# We can solve this using the following Finite State Machine:
#
#   _______  U   _______  L   _______  N   ________
#  | start |===>| upper |===>| lower |===>| number |
#   ~~~~~~~      ~~~~~~~      ~~~~~~~      ~~~~~~~~
#
#  Where:
#       An uppercase letter (U) transitions from "start" --> "upper"
#       An lowercase letter (L) transitions from "upper" --> "lower"
#       An number letter (N) transitions from "lower" --> "number"
#
#

state = "start"
password = "ABCs123"

is_valid = True # we will assume the password is valid until we determine otherwise
for char in password:

    # The "start" state only occurs right at the beginning, before any input
    # is read. To move onto the next state, we must get an uppercase letter.
    if state == "start":
        if char.isupper():
            state = "upper"
            continue
        else:
            is_valid = False
            break


    # Once in the "upper" state, we stay in that state as long as we see
    # uppercase letters, and move to the next state once we see a lowercase letter.
    if state == "upper":
        if char.isupper():
            continue # stay in same state
        elif char.islower():
            state = "lower"
            continue
        else:
            is_valid = False
            break


    # Once in the "lower" state, we stay in that state as long as we see
    # lowercase letters, and move to the next state once we see a number.
    if state == "lower":
        if char.islower():
            continue # stay in same state
        if char.isnumeric():
            state = "number"
            continue
        else:
            is_valid = False
            break


    # Once in the "number" state, we stay in that state as long as we see
    # numbers. Anything else at this point is invalid.
    if state == "number":
        if char.isnumeric():
            continue # stay in same state
        else:
            is_valid = False
            break


# For the password to be valid, the is_valid variable needs to still be True,
# and we need to have made it all the way to the "number" state.
if is_valid and state == "number":
    print("Password is valid")
else:
    print("Password is Invalid")