😄
Junkai’s Blogs
AboutDonate

Introduction to Algorithm

Introduction

Imagine you're making a peanut butter and jelly sandwich. You don't just magically have one appear, right? You follow a series of steps:
  • Get the bread
  • Get the peanut butter
  • Get the jelly
  • Spread peanut butter on one slice
  • Spread jelly on the other
  • Put the two slices together
An algorithm is basically that same idea, but for computers. It's a set of well-defined instructions for solving a problem or accomplishing a task.
Key Characteristics of Algorithms:
  • Input: Algorithms usually take some data as input. For the sandwich, our ingredients are the input.
  • Output: They produce a result. For the sandwich, the finished sandwich is the output.
  • Finiteness: They must have a stopping point. You can't make a sandwich forever.
  • Definiteness: Each step is clear and unambiguous. You know what "spread" means.
  • Effectiveness: The instructions must be do-able. You can't "teleport the bread" you need to "get it".
In Short: An algorithm is a step-by-step recipe that a computer can follow to solve a problem.

Algorithm Design Principles

Okay, so how do we actually create these recipes? There are a few principles that help us:
  • Correctness: The algorithm should always produce the correct output for valid inputs. If you use the sandwich recipe, you should get a PB&J and not a ham sandwich.
  • Efficiency: The algorithm should use resources (like time and memory) wisely. You wouldn't want a 100-step sandwich recipe if you could do it in 6.
  • Clarity: The algorithm should be easy to understand and implement. No riddles in our recipe, please.
  • Simplicity: Aim for the simplest solution that works. The less complicated the better.

Algorithm Analysis

Now, how do we know if one algorithm is better than another? This is where analysis comes in:
  • Big O Notation: This is a fancy way of describing how the running time of an algorithm grows as the input size increases. It focuses on the worst-case scenario.
    • - Constant Time: The running time doesn't change regardless of the input size. Think about checking if the last sock you just pulled is a match.
    • - Logarithmic Time: The time increases slowly as input size goes up, like looking up a word in a dictionary (using binary search).
    • - Linear Time: The time increases directly with input size, think of going through each sock in the pile to find a match.
    • - Log-Linear Time: The time grows as input size grows but not as quickly as n^2 , a good example is a good sort algorithm.
    • - Quadratic Time: The time increases dramatically with input size, think about comparing every sock to every other sock in the pile.
    • - Exponential Time: The time grows very, very fast. Often considered unusable for large inputs. (e.g. Solving the travelling salesman problem with brute force)
  • Time Complexity: How much time does the algorithm take? It's described using Big O notation. It focuses on the number of computational steps involved.
  • Space Complexity: How much memory (space) does the algorithm use? Also described with Big O notation and it focuses on how much extra memory an algorithm needs.
      • Analogy: Imagine sorting books on a shelf.
    • Time Complexity = How long it takes to sort all the books.
    • Space Complexity = How much extra space you need to lay out the books while sorting them
Why Big O matters: Imagine you are Google and you are searching a database of trillions of documents, using an algorithm would take exponentially longer than using an algorithm.

Pseudocode and Flowcharts

These are tools to help describe algorithms:
  • Pseudocode: This is like "fake code" - it uses plain English-like instructions to describe the algorithm's steps. It's more structured than plain English but not as strict as a programming language.
    • Example:
        • // Algorithm to find the sum of two numbers
START
  INPUT number1, number2
  sum = number1 + number2
  OUTPUT sum
END
  • Flowcharts: These are visual diagrams that show the flow of the algorithm using boxes and arrows. They can be very helpful to visualize processes.
    • Example: A flowchart to make a sandwich will have boxes for "get bread", "get pb", "get jelly" etc.

Problem-Solving Techniques

Let's talk about solving problems using algorithms:
  1. Understand the Problem: What is the goal? What are the inputs and outputs? Read the fine print and constraints.
  1. Plan Your Approach: What kind of algorithm might work?
  1. Design the Algorithm: Write the steps in pseudocode or sketch it out in a flowchart.
  1. Implement the Algorithm: Turn the algorithm into code.
  1. Test and Debug: Make sure it works correctly for all cases, including edge cases and invalid inputs.
  1. Analyze and Optimize: Check the time and space complexity and see if you can make it better.

Example:

Let's say you want to search for a name in a phone book.
  • Problem: Find a name in a phone book.
  • Plan: You can use a linear search (look at each name one by one) or a binary search (start in the middle and go left or right).
  • Design:
    • Linear Search: start at the first name and check each one until the name is found or we reach the end.
    • Binary Search: open the book in the middle, check if the name is before or after the middle name and repeat in that new half.
  • Implementation: Write the pseudocode for each approach.
  • Testing: Make sure both methods find the right name and not miss cases.
  • Analysis: Linear search is O(n), while Binary Search is O(log n). The binary search is faster for big phone books.