Backtracking, greedy and dynamic programming

Three ways of attacking a problem: try every choice with undo, commit to the best-looking choice, or store the answers to smaller problems so that nothing is solved twice.

About 12 hours of study

Learning objectives

• Write backtracking with choose, recurse and undo
• Test a greedy rule with a counter-example
• Design a dynamic program from a subproblem
• Solve the knapsack and longest common subsequence

Lessons

1. 1

   Recursion and backtracking

   Try every choice, undo it, try the next: all subsets, all permutations, and placing queens that never attack.

2. 2

   Greedy algorithms

   Take the best-looking choice at each step: activity selection works, coin change sometimes fails, and how to tell.

3. 3

   Dynamic programming

   Solve each subproblem once and store it: Fibonacci with a memo, and the fewest coins for any amount.

4. 4

   Knapsack and longest common subsequence

   Two classic 2D tables: the 0/1 knapsack (take or leave each item) and the LCS of two strings.

Module practice

• All binary stringsEasy
• Subsets with a given sumMedium
• All permutations in orderMedium
• The n-queens puzzleHard
• Pay with the fewest taka notesEasy
• Activity selectionMedium
• Jobs with deadlinesHard
• Ways to climb the stairsEasy
• The fewest coinsMedium
• Longest increasing subsequenceHard
• Paths through a gridEasy
• The 0/1 knapsackMedium
• Longest common subsequenceMedium
• Edit distance between two wordsHard

‹ SortingGraph algorithms ›