Algorithm Design

Algorithm Design: Your Toolbox for Solving Problems

Imagine you’re a chef in a kitchen. You have different tools for different jobs: a knife for cutting, a pan for cooking, a blender for mixing. Algorithm design is just like that! It’s your toolbox of strategies for solving problems.

Today, we’ll learn 8 powerful tools. Each one is special. Each one solves certain problems better than others.

The Big Picture: What is Algorithm Design?

Think of a problem like a maze. You want to get from START to END.

Algorithm design = choosing the BEST WAY to solve the maze.

Some ways are slow but always work. Some ways are fast but tricky. Let’s meet each tool!

graph TD
    A["Problem"] --> B{Choose Strategy}
    B --> C["Brute Force"]
    B --> D["Divide & Conquer"]
    B --> E["Greedy"]
    B --> F["Dynamic Programming"]
    B --> G["Memoization"]
    B --> H["Backtracking"]
    B --> I["Two Pointers"]
    B --> J["Sliding Window"]
    C --> K["Solution!"]
    D --> K
    E --> K
    F --> K
    G --> K
    H --> K
    I --> K
    J --> K

1. Brute Force: Try Everything!

The Story

Imagine you lost your toy in your room. What’s the simplest way to find it?

Look EVERYWHERE! Check under the bed. Check in the closet. Check behind the door. Check every single spot until you find it.

That’s Brute Force. It’s simple. It’s slow. But it ALWAYS works!

How It Works

• Try every possible answer
• Check if each answer works
• Stop when you find the right one

Real Example: Finding a Password

Imagine a 3-digit lock (000 to 999).

Brute force = Try 000, then 001, then 002… all the way to 999.

Try: 000 ❌
Try: 001 ❌
Try: 002 ❌
...
Try: 742 ✅ Found it!

When to Use It

• When the problem is small
• When you need the CORRECT answer (no shortcuts)
• When you can’t think of a smarter way

The Good and Bad

2. Divide and Conquer: Break It Down!

The Story

Imagine you have a HUGE pizza to eat. Way too big for one bite!

What do you do? Cut it into slices! Now each slice is easy to eat.

That’s Divide and Conquer:

1. Divide the big problem into smaller pieces
2. Conquer each small piece
3. Combine the answers together

How It Works

graph TD
    A["Big Problem"] --> B["Small Problem 1"]
    A --> C["Small Problem 2"]
    B --> D["Solve 1"]
    C --> E["Solve 2"]
    D --> F["Combine Answers"]
    E --> F
    F --> G["Final Answer!"]

Real Example: Sorting Cards

You have 8 messy cards: [5, 2, 8, 1, 9, 3, 7, 4]

Step 1: Divide

• Split into two halves: [5, 2, 8, 1] and [9, 3, 7, 4]

Step 2: Keep dividing

• [5, 2] [8, 1] [9, 3] [7, 4]
• [5] [2] [8] [1] [9] [3] [7] [4]

Step 3: Conquer (each tiny piece is already sorted!)

Step 4: Combine

• Merge [5] + [2] = [2, 5]
• Merge [8] + [1] = [1, 8]
• Keep merging…
• Final: [1, 2, 3, 4, 5, 7, 8, 9]

Famous Uses

• Merge Sort (sorting)
• Quick Sort (sorting)
• Binary Search (finding things)

3. Greedy Algorithms: Take the Best NOW!

The Story

You’re at a buffet. You want to fill your plate with the YUMMIEST food.

What do you do? At each station, grab the best thing you see!

Don’t worry about later. Just take what looks best RIGHT NOW.

That’s Greedy. Always pick the best choice at each step.

How It Works

1. Look at your options
2. Pick the BEST one right now
3. Move forward
4. Repeat until done

Real Example: Making Change

You need to give someone 36 cents using the fewest coins.

Coins available: 25¢, 10¢, 5¢, 1¢

Greedy approach:

• What’s the BIGGEST coin ≤ 36? → 25¢ ✓
• Remaining: 36 - 25 = 11¢
• Biggest ≤ 11? → 10¢ ✓
• Remaining: 11 - 10 = 1¢
• Biggest ≤ 1? → 1¢ ✓

Answer: 25¢ + 10¢ + 1¢ = 3 coins!

Warning: Greedy Isn’t Always Best!

Sometimes the “best now” choice leads to a bad ending.

Example: Coins are 1¢, 3¢, 4¢. You need 6¢.

• Greedy: 4¢ + 1¢ + 1¢ = 3 coins
• Better: 3¢ + 3¢ = 2 coins!

Greedy failed here!

When Greedy Works

• Making change with standard coins (1, 5, 10, 25)
• Scheduling tasks to minimize waiting
• Finding shortest paths (Dijkstra’s algorithm)

4. Dynamic Programming: Remember Your Work!

The Story

Imagine your teacher asks: “What’s 5 + 3?”

You think… “8!”

Then she asks: “What’s 5 + 3 + 2?”

Do you add 5 + 3 again? NO! You already know 5 + 3 = 8. Just add 2!

8 + 2 = 10

That’s Dynamic Programming (DP). Save your work. Use it later. Don’t repeat yourself!

The Key Idea

Big problems are made of overlapping smaller problems.

Instead of solving the same small problem again and again, solve it once and save the answer!

Real Example: Climbing Stairs

You have a staircase with 5 steps. You can climb 1 or 2 steps at a time.

How many different ways can you reach the top?

DP Approach:

• Ways to reach step 1 = 1 way (just take 1 step)
• Ways to reach step 2 = 2 ways (1+1 or 2)
• Ways to reach step 3 = ways(1) + ways(2) = 1 + 2 = 3
• Ways to reach step 4 = ways(2) + ways(3) = 2 + 3 = 5
• Ways to reach step 5 = ways(3) + ways(4) = 3 + 5 = 8

We built up from small answers to the big answer!

graph LR
    A["Step 1: 1"] --> C["Step 3: 3"]
    B["Step 2: 2"] --> C
    B --> D["Step 4: 5"]
    C --> D
    C --> E["Step 5: 8"]
    D --> E

Two DP Styles

5. Memoization: Your Memory Helper

The Story

Memoization is like writing answers on sticky notes.

When someone asks you a math question, you solve it and write the answer on a note. Next time someone asks the SAME question, you just read your note!

It’s the “memory” part of Dynamic Programming.

How It Works

graph TD
    A["Asked Question"] --> B{Seen Before?}
    B -->|Yes| C["Read Saved Answer"]
    B -->|No| D["Calculate Answer"]
    D --> E["Save to Memory"]
    E --> F["Return Answer"]
    C --> F

Real Example: Fibonacci Numbers

Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21…

Each number = sum of previous two.

Without Memoization (so slow!):

fib(5) calls fib(4) and fib(3)
fib(4) calls fib(3) and fib(2)
fib(3) calls fib(2) and fib(1)
... fib(3) is calculated TWICE!

With Memoization (fast!):

fib(5) calls fib(4) and fib(3)
fib(4) calls fib(3) and fib(2)
→ Save fib(2)=1, fib(3)=2, fib(4)=3
fib(5) needs fib(3)? Already saved! = 2
→ fib(5) = 3 + 2 = 5

Memo vs No Memo

6. Backtracking: Try, Fail, Try Again!

The Story

Imagine you’re in a maze. You reach a fork: left or right?

You pick left. You walk… Dead end!

What do you do? Go back to the fork. Now try right.

That’s Backtracking:

1. Try a path
2. If it fails, undo and try another
3. Keep going until you find the answer

How It Works

graph TD
    A["Start"] --> B{Choice 1}
    B -->|Try A| C["Dead End ❌"]
    C -->|Backtrack| B
    B -->|Try B| D{Choice 2}
    D -->|Try X| E["Dead End ❌"]
    E -->|Backtrack| D
    D -->|Try Y| F["Solution! ✅"]

Real Example: Solving a Sudoku

You have an empty cell. What number goes there?

Try 1: Does it work? Check rows, columns, box…

• If YES → move to next cell
• If NO → backtrack! Try 2, then 3…

If nothing works, go back to the PREVIOUS cell and try a different number there!

Backtracking Uses

• Sudoku solver
• N-Queens puzzle
• Maze solving
• Generating all combinations

Key Idea

Backtracking is like exploring a tree of choices. When you hit a dead end, climb back up and try a different branch!

7. Two-Pointer Technique: Two Friends Working Together

The Story

Imagine a long line of kids. You need to find two kids whose heights add up to 10.

Slow way: Compare every pair. Takes forever!

Smart way: Put one friend at the START, one at the END. Move them toward each other based on what you find!

That’s Two Pointers. Two markers moving through data smartly.

How It Works

Array: [1, 2, 4, 5, 7, 9]
Target sum: 9

Left pointer → 1
Right pointer → 9

1 + 9 = 10 (too big!)
Move right pointer left: 7

1 + 7 = 8 (too small!)
Move left pointer right: 2

2 + 7 = 9 ✅ FOUND!

Visual

[1, 2, 4, 5, 7, 9]
 ↑              ↑
 L              R

[1, 2, 4, 5, 7, 9]
 ↑           ↑
 L           R

[1, 2, 4, 5, 7, 9]
    ↑        ↑
    L        R  ✅

When to Use

• Finding pairs with a target sum
• Removing duplicates
• Reversing arrays/strings
• Checking palindromes

Why It’s Fast

Instead of checking ALL pairs (slow!), you make smart moves. Each pointer only moves forward or backward once. Super efficient!

8. Sliding Window: A Moving Frame

The Story

Imagine you’re looking at a long train through a window.

Your window shows exactly 3 train cars at a time.

To see the next group of 3, you don’t build a new window. You just slide it one car forward!

That’s Sliding Window. A fixed-size “frame” that moves through data.

How It Works

Array: [2, 1, 5, 1, 3, 2]
Window size: 3
Find the maximum sum of any 3 consecutive numbers.

Window 1: [2, 1, 5] → sum = 8
Window 2: [1, 5, 1] → sum = 7
Window 3: [5, 1, 3] → sum = 9 ← MAX!
Window 4: [1, 3, 2] → sum = 6

Answer: 9

The Sliding Trick

Instead of adding all 3 numbers each time:

Window 1: 2 + 1 + 5 = 8

Slide: Remove 2, Add 1
Window 2: 8 - 2 + 1 = 7

Slide: Remove 1, Add 3
Window 3: 7 - 1 + 3 = 9

Just subtract the old, add the new! Much faster!

Visual

[2, 1, 5, 1, 3, 2]
[-----]           sum = 8

[2, 1, 5, 1, 3, 2]
   [-----]        sum = 7

[2, 1, 5, 1, 3, 2]
      [-----]     sum = 9 ✅

[2, 1, 5, 1, 3, 2]
         [-----]  sum = 6

When to Use

• Maximum/minimum sum of k consecutive elements
• Longest substring with k distinct characters
• Finding averages of subarrays

Choosing Your Tool: The Quick Guide

The Big Summary

graph TD
    A["Algorithm Design Toolbox"] --> B["Brute Force"]
    A --> C["Divide & Conquer"]
    A --> D["Greedy"]
    A --> E["Dynamic Programming"]
    A --> F["Memoization"]
    A --> G["Backtracking"]
    A --> H["Two Pointers"]
    A --> I["Sliding Window"]

    B --> B1["Try everything"]
    C --> C1["Split and combine"]
    D --> D1["Best choice now"]
    E --> E1["Save work"]
    F --> F1["Remember answers"]
    G --> G1["Try and backtrack"]
    H --> H1["Two markers"]
    I --> I1["Moving frame"]

You Did It!

You now know 8 powerful ways to solve problems:

1. Brute Force - Try everything (slow but sure)
2. Divide & Conquer - Break it down, combine answers
3. Greedy - Always pick the best choice now
4. Dynamic Programming - Build from small to big, save work
5. Memoization - Remember calculations
6. Backtracking - Try, fail, undo, try again
7. Two Pointers - Two markers moving smartly
8. Sliding Window - A moving frame through data

Each tool is perfect for certain jobs. Now you get to pick the right one!

Happy problem-solving!