Module 9 - Algorithms Header

Module 9 - Algorithms

Introduction to Algorithms

Introduction to Algorithms:

An algorithm is a step-by-step procedure or a set of instructions used to solve a specific problem or accomplish a particular task. It serves as a blueprint for solving problems in a systematic and efficient manner. Algorithms are essential in computer science and programming as they provide a structured approach to problem-solving.

Algorithms can be found in various domains, such as sorting and searching data, graph traversal, mathematical computations, artificial intelligence, and more. They are designed to handle specific inputs and produce desired outputs through a series of well-defined steps.

Developing an Algorithm:

Developing an algorithm involves several phases, from understanding the problem to reassembling the response. Let's break down the process into detailed steps:

Understanding the Problem:

  • Read and analyze the problem statement carefully.
  • Identify the inputs, desired outputs, and any constraints or requirements.
  • Clarify any ambiguous or unclear parts of the problem through questions if necessary.
  • Develop a solid understanding of the problem's context and objectives.

Breaking Down the Problem:

  • Break down the problem into smaller, manageable components or sub-problems.
  • Identify the key operations or computations required to solve each sub-problem.
  • Determine the relationships and dependencies between sub-problems.

Designing the Algorithm:

  • Decide on an overall strategy for solving the problem.
  • Choose appropriate data structures and algorithms that align with the problem requirements.
  • Design a step-by-step plan or a set of instructions to solve each sub-problem.
  • Represent the algorithm using pseudocode, flowcharts, or any other suitable method.

Implementing the Algorithm:

  • Translate the algorithm design into a programming language like Python.
  • Write the code that corresponds to each step and operation defined in the algorithm.
  • Utilize programming constructs such as loops, conditionals, functions, and data structures to implement the algorithm.
  • Handle edge cases, exceptions, and validations as necessary.

Testing and Debugging:

  • Test the algorithm using various inputs and scenarios to ensure it produces the correct outputs.
  • Verify that the algorithm handles both normal and boundary cases correctly.
  • Debug and fix any errors or unexpected behaviors encountered during testing.
  • Use debugging tools and techniques to identify and resolve issues efficiently.

Optimizing the Algorithm:

  • Analyze the efficiency of the algorithm in terms of time and space complexity.
  • Identify bottlenecks or areas for improvement in terms of performance.
  • Consider algorithmic optimizations like using better data structures, employing algorithmic techniques, or reducing redundant operations.
  • Measure and compare the algorithm's performance to determine if it meets the desired requirements.

Reassembling the Response:

  • Gather the results or outputs produced by the algorithm.
  • Organize and format the outputs as required by the problem statement.
  • Present the final response or output in a clear and understandable manner.

Documentation and Maintenance:

  • Document the algorithm thoroughly, including explanations of its purpose, inputs, outputs, and any specific instructions.
  • Maintain proper code documentation, including comments and relevant information for understanding and maintaining the algorithm in the future.
  • Update the documentation as needed when modifications or improvements are made.

Remember, developing an algorithm is an iterative process. It involves analyzing, designing, implementing, testing, and refining the solution until the desired outcome is achieved.

By following these detailed steps, you can effectively develop algorithms that solve problems accurately and efficiently. Continuous practice and refinement of algorithmic skills will lead to better problem-solving abilities in computer science and programming.



An Algorithmic Example

Here's an algorithmic approach to identifying and cleaning email addresses in a string, without using regular expressions, along with the steps and explanations:

Problem: Given a string containing email addresses with extraneous characters, write a Python function that identifies and cleans the email addresses before storing them in an array.

Algorithmic Approach:

Understanding the Problem: We have a string that may contain email addresses along with other characters. We need to identify the email addresses and clean them by removing any extraneous characters. The cleaned email addresses should be stored in an array.

Designing the Algorithm:

If we break down the task of extracting emails from a text string, then it might look something like this:

  1. Initialize an empty array to store the cleaned email addresses.
  2. Split the string into words using whitespace as the delimiter.
  3. Iterate through each word in the string.
    For each “word” in the string, we:
    1. Check if the word contains the "@" symbol to identify potential email addresses.
    2. Clean the email address by removing any extraneous characters, such as leading/trailing spaces, punctuation, or invalid characters.
    3. Append the cleaned email address to the array.

By breaking the problem and solution into steps, we discover that this complex problem is actually just a series of simpler problems all connected together.  Using this list of simple probems as our guide, we can now write the parts of the algorithm.

Example Code:

def clean_email_addresses(string):
cleaned_addresses = []
words = string.split()
for word in words:
if "@" in word:
# Clean the email address
cleaned_address = ""
for char in word:
if char.isalpha() or char.isdigit() or char in ['.', '_', '-']:
cleaned_address += char
cleaned_addresses.append(cleaned_address)
return cleaned_addresses

Testing the Code:

text = "Please contact me at john.doe@example.com or jane_123@example.com"
result = clean_email_addresses(text)
print(result) # Output: ['john.doe@example.com', 'jane_123@example.com']

It is important that when you test the code, you give it many different test cases,  or in this case different strings.  For example, how about one that has different kinds of punctuation, or an invalid email address that looks valid.  What happens if you feed the algorithm an empty string?  A thorough approach to testing might include all of these test cases.

Optimization: In this example, the algorithm is relatively simple. However, you can optimize it further by considering additional checks, such as validating the email address structure (e.g., checking for the presence of a domain and a top-level domain) or removing any duplicates from the array.

Documentation and Maintenance: Provide clear comments and instructions within the code to explain the purpose, inputs, and outputs of the function. Regularly maintain and update the code and documentation as needed.

This algorithmic approach allows you to identify and clean email addresses in a string using string methods in Python. By following these steps, you can extract valid email addresses while disregarding any extraneous characters present in the string.

Videos for Module 9 - Algorithms

9-1: What's an Algorithm? (10:06)

9-2: Steps for Algorithm Creation (4:21)

9-3: Thinking in Pseudocode (:58)

9-4: Email Cleaning Algorithm Explained (4:32)

9-5: Email Cleaning Algorithm Code (15:49)

9-6: Algorithm Debugging Techniques (2:57)

9-7: S9 Explanation (2:30)

Key Terms for Module 9 - Algorithms

No terms have been published for this module.

Quiz Yourself - Module 9 - Algorithms

Test your knowledge of this module by choosing options below. You can keep trying until you get the right answer.

Skip to the Next Question 

Activities for this Module

S9 - Text Sophistication Algorithm

Note: Sandbox assignments are designed to be formative activities that are somewhat open-ended. To get the most value, spend some time playing around as you code.

In this sandbox, we are going to build on what we did last time — We explored some different things that one might use to measure how smart or intelligent a piece of writing is.  In this sandbox, we are going to take this idea a step further and create an algorithm that gives us some kind of score indicating how “smart” a piece of text is.  

You might want to use some of the ideas you explored last module, but also introduce some new ones.  You will need to think critically about how much weight to give different things, like word variety, word length, and length of the writing sample.

When you are done, you should be able to enter a text sample, and it should output a score.
To test it, use the following three samples of text:

4th Grade Level:
The moon seems to change shape every night. These shapes are called moon phases. The cycle starts with the new moon, which we can't see because it's between the Earth and the sun. Then, as the moon moves, we see more of it lit up, first a crescent, then a half moon, and finally a full moon, which is all bright and round. After the full moon, it looks like the moon is shrinking, going back through the half moon and crescent until it's new again. This whole cycle takes about a month.

10th Grade Level:
The moon goes through different phases, which make it look like it's changing shape. This happens over a cycle called a lunar month, lasting about 29.5 days. It starts with the new moon, when the moon is lined up between Earth and the sun, showing us its shadowed side. As the moon moves, we see more of its sunlit side, moving through crescent to quarter, then to a full moon when it's completely lit up. After the full moon, the moon's visible light starts to decrease, moving back towards the new moon.

Ph.D. Level:
The lunar phases reflect a cyclical pattern of visibility and illumination, governed by the moon’s synodic period of roughly 29.53 days. Initially, during the new moon phase, the moon is positioned directly between Earth and the sun, displaying its unilluminated side to us. As it orbits, the sunlit portion we can see increases—this is called waxing. It progresses through crescent to gibbous until the full moon, where the entire face is visible. Then it begins to wane, or decrease in visibility, returning once more to the new moon phase, completing the cycle.

You can use the code from the Lincoln vs. Swift sandbox to help you get started. Using the three samples of writing above, try to come up with an algorithm that will “know” the difference between the different levels of writing.

For an extra challenge, find some additional text snippets to test out, and see how it works.
Take a screenshot of the results, and submit it to this discussion with an explanation of how you designed it to work.