Algorithms Through Problem Solving

Foundations / Python 3 / 16 lessons

Studying algorithms means solving the same problem in different ways and comparing why each works and how much work it takes. Learn to start with a small correct solution and improve it.

• Who it is for: You can read Python variables, conditions, loops, and functions.
• Useful background: Arrays, stacks, queues, trees, and graphs. If these are new, begin with the data structures course.
• Format: A problem, a strategy, a small example, operation costs, and a question with an explanation. Every lesson is free to read.
• Goal: Explain a method’s assumptions and counterexamples, then select a strategy suited to the input size.

Focus on three questions: Did I miss any candidates? Am I repeating the same calculation? Will today’s choice still be valid later?

Lessons

1. 01 Define the ProblemSpecify inputs, outputs, and edge cases before choosing a method.
2. 02 Compare the Amount of WorkCount loop iterations and distinguish time from extra space.
3. 03 Try Every CandidateStart with a straightforward correct method and count its candidates.
4. 04 Divide, Solve, and CombineUse merge sort to combine solutions to smaller problems.
5. 05 Greedy ChoicesCompare a provably correct greedy choice with a counterexample.
6. 06 Remember Results with Dynamic ProgrammingDefine states and recurrences instead of solving the same subproblem again.
7. 07 Take It or Leave It: KnapsackChoose items under a capacity limit, using each item at most once.
8. 08 Find a Common SubsequenceUse longest common subsequence to build a DP over two inputs.
9. 09 Backtrack from Impossible ChoicesBuild and undo choices while pruning branches that cannot satisfy the rules.
10. 10 Prune with Branch and BoundCompare the best known answer with an optimistic bound.
11. 11 Compute Shortest Distances with DijkstraCombine a priority queue with distance relaxation.
12. 12 Find a Pattern in TextCompare a direct scan with methods that reuse earlier comparisons.
13. 13 Reduce Integer Problems with RemaindersJustify reducing candidates in greatest common divisor and primality problems.
14. 14 Geometry: Points and TurnsUse simple calculations to reason about nearby points and turn direction.
15. 15 Hard Problems and Approximate AnswersDistinguish checking from finding an answer and state what a method guarantees.
16. 16 Working with Large DataAccount for parallel work and data that does not fit in memory.