0% completed

All LessonsFree Lessons (5)

Getting Started

Course Overview

Algorithms and Complexity

Introduction to Algorithms and Complexity Correct vs. Incorrect Algorithms Time Complexity of Algorithms

Runtime Algorithms

The Big-O Notation Advantages and Disadvantages of the Big-O Notation Five Common Rules for Analyzing the Runtime Visualize Common Rules for Runtime Analysis Frequently Arising Running Times Quiz: Running Time of Algorithms

Algorithm Design Techniques

Introduction to Algorithm Design Techniques Algorithm Design: Exhaustive Search Algorithms Algorithm Design: Branch-and-Bound Algorithms Algorithm Design: Greedy Algorithms Algorithm Design: Dynamic Programming Algorithms Algorithm Design: Recursive Algorithms Algorithm Design: Divide-and-Conquer Algorithms Algorithm Design: Randomized Algorithms Quiz: Algorithm Design Techniques

Programming Challenges

Introduction to Programming Challenges Challenge: Sum of Two Digits Solution: Sum of Two Digits Challenge: Maximum Pairwise Product Naive Solution: Maximum Pairwise Product Fast Solution: Maximum Pairwise Product Evaluating Solutions to Maximum Pairwise Product Problem Solving a Programming Challenge in Four Easy Steps Quiz: Programming Challenges

Good Programming Practices

Introduction to Good Programming Practices Code Formatting and Naming Guidelines Debugging and Code Optimization C++-Specific C++ Rules For Classes And Numbers Python-Specific Quiz: Good Programming Practices

Algorithmic Warm Up

Introduction to Algorithmic Warm Up Challenge: Fibonacci Number Solution: Fibonacci Number Challenge: Last Digit of the Fibonacci Number Solution: Last Digit of Fibonacci Number Challenge: Huge Fibonacci Number Solution: Huge Fibonacci Number Challenge: Last Digit of the Sum of Fibonacci Numbers Solution: Last Digit of the Sum of Fibonacci Numbers Challenge: Last Digit of the Partial Sum of Fibonacci Numbers Solution: Last Digit of the Partial Sum of Fibonacci Numbers Challenge: Last Digit of the Sum of Fibonacci Numbers’ Squares Solution: Last Digit of the Sum of Fibonacci Numbers’ Squares Challenge: Greatest Common Divisor Solution: Greatest Common Divisor Challenge: Least Common Multiple Solution: Least Common Multiple Quiz: Algorithmic Warm Up

Greedy Algorithms

Introduction to Greedy Algorithms Greedy Strategies Prove the Correctness of Greedy Algorithms Challenge: Money Change Solution: Money Change Challenge: Maximum Value of the Loot Solution: Maximum Value of the Loot Challenge: Car Fueling Solution: Car Fueling Challenge: Maximum Advertisement Revenue Solution: Maximum Advertisement Revenue Challenge: Collecting Signatures Solution: Collecting Signatures Challenge: Maximum Number of Prizes Solution: Maximum Number of Prizes Challenge: Maximum Salary Solution: Maximum Salary Quiz: Greedy Algorithms

Divide and Conquer Algorithm

Introduction to Divide-and-Conquer Algorithms Guessing a Number Searching Sorted Data Finding a White-Black Pair Finding a Peak Multiplying Integers The Master Theorem Challenge: Sorted Array Multiple Search Solution: Sorted Array Multiple Search Challenge: Multiple Search with Duplicates Solution: Multiple Search with Duplicates Challenge: Majority Element Solution: Majority Element Challenge: Improving Quicksort Solution: Improving Quicksort Challenge: Number of Inversions Solution: Number of Inversions Challenge: Organizing a Lottery Solution: Organizing a Lottery Challenge: Closest Points Solution: Closest Points Quiz: Divide-and-Conquer Algorithms

Dynamic Programming

Introduction to Dynamic Programming

Challenge: Money Change Again

Solution: Money Change Again

Challenge: Primitive Calculator

Solution: Primitive Calculator

Challenge: Edit Distance

Solution: Edit Distance

Challenge: Longest Common Subsequence of Two Sequences

Solution: Longest Common Subsequence of Two Sequences

Challenge: Longest Common Subsequence of Three Sequences

Solution: Longest Common Subsequence of Three Sequences

Challenge: Maximum Amount of Gold

Solution: Maximum Amount of Gold

Challenge: Splitting the Pirate Loot

Solution: Splitting the Pirate Loot

Challenge: Maximum Value of an Arithmetic Expression

Solution: Maximum Value of an Arithmetic Expression

Quiz: Dynamic Programming

Conclusion

Practice Mock Interview

Algorithmic Problem Solving: Preparing for a Coding Interview/

...

/

Challenge: Edit Distance

Challenge: Edit Distance

Solve the Edit Distance Problem.

We'll cover the following...

Problem
Coding exercise

Problem

Edit Distance Problem

Compute the edit distance between two strings.

Input: Two strings.

Output: The minimum number of single symbol insertions, deletions, and substitutions to transform one string into the other one.

The Edit Distance Problem has many applications in computational biology, natural language processing, spell-checking, etc. For example, biologists often analyze edit distances when they search for disease-causing mutations.

The edit distance between two strings is defined as the minimum number of single-symbol $\color{blue}\text{insertions}$ , $\color{green}\text{deletions}$ , and ...