Algorithms in Python
Learn to design, analyze, and improve the efficiency of algorithms in Python — from tracing code and proving correctness to estimating runtime.
Tokenization
Instances of a Problem
Solving a Simpler Problem
Tracing Algorithms
Enumeration
Level Review
Preconditions and Postconditions
Reasoning about Correctness
Loop Invariants
Counterexamples
Level Review
Best and Worst Cases
Time Complexity
Estimating with Big-O
The Multiplication Principle
Level Review
The Cost of Slicing
The Cost of Lists
Improving Efficiency
Level Review
Course description
In this course you will design, analyze, and improve the efficiency of algorithms in Python, building programs involved in natural language processing along the way. Starting with the problem of breaking text into tokens, you will build algorithms from scratch, then develop tools for reasoning about whether they are correct and how fast they run. Topics include preconditions and postconditions, loop invariants, counterexamples, time complexity, big-O notation, and hidden runtime costs in everyday Python operations like slicing and list lookups.
Topics covered
- Tokenization
- Instances of a Problem
- Solving a Simpler Problem
- Tracing Algorithms
- Enumeration
- Preconditions and Postconditions
- Reasoning about Correctness
- Loop Invariants
- Counterexamples
- Best and Worst Cases
- Time Complexity
- Estimating with Big-O
- The Multiplication Principle
- The Cost of Slicing
- The Cost of Lists
- Improving Efficiency
Prerequisites and next steps
This course is a great next step if you're comfortable writing Python functions and working with loops, strings, and lists. Use it to learn how to think critically about the algorithms you write — whether they're correct, how fast they run, and how to make them more efficient.