Skip to main content

Courses About Pricing Educators

Sign in Get started

Courses About Pricing Educators

Get started Sign in

Loading courses

Loading lessons

Greedy and Backtracking: Data Structures and Algorithms: Uncharted

Courses Data Structures and AlgorithmsGreedy and Backtracking

Greedy and BacktrackingPro

Know when a local choice is safe, then explore and prune when choices must be undone.

Data Structures and Algorithms
Unit 14 of 16
20 lessons
130 min
420 XP

This unit is part of Pro. Upgrade to open every lesson in it.

Lessons

20 total

1Take the Best BiteSeparate a greedy local-choice rule from the proof that it preserves a globally optimal completion.ProInteractiveConcept6 min20 XPOpen
2Greedy Coins Work HereApply largest-coin-first canonical change to making canonical change by taking each largest denomination first.ProCodeConcept6 min20 XPOpen
3Greedy Coins Fail ThereApply greedy counterexample checked by dynamic programming to using the 1-3-4 counterexample and a DP table as the referee.ProCodeConcept6 min20 XPOpen
4Interval SchedulingApply earliest-finish interval selection to booking the maximum meetings in one room by earliest finish time.ProCodeConcept6 min20 XPOpen
5Why Earliest Finish WinsUse an exchange argument to justify earliest-finish interval scheduling.ProInteractiveConcept6 min20 XPOpen
6Jump to the EndApply furthest-reachable greedy scan to tracking the furthest index reachable from every position seen so far.ProCodeConcept6 min20 XPOpen
7Fuel StopsApply furthest-reachable refuel choice to driving to the furthest reachable station before each necessary refill.ProCodePractice8 min20 XPOpen
8Greedy or Not?Test a proposed greedy rule by asking whether it can replace an optimal first choice without harm.ProInteractiveConcept6 min20 XPOpen
9The Exploring ForkMaintain backtracking state with a matched choose, explore, and undo sequence.ProInteractiveConcept6 min20 XPOpen
10All SubsetsApply include-or-exclude subset expansion to including or excluding every pizza topping.ProCodeConcept6 min20 XPOpen
11All PermutationsApply choose-from-remaining permutation search to choosing each remaining item as the next position.ProCodeConcept6 min20 XPOpen
12Predict the Search TreePredict depth-first backtracking output order from the stated branch order and restored parent state.ProInteractiveConcept6 min20 XPOpen
13Word Search GridApply DFS choose-mark-recurse-unmark search to marking a grid cell during DFS and unmarking it on the way out.ProCodeConcept6 min20 XPOpen
14N-Queens, LiteApply column-and-diagonal pruned queen placement to placing six queens with column and diagonal conflict sets.ProCodeConcept6 min20 XPOpen
15Prune EarlyApply sorted-candidate branch pruning to stopping a sorted combination branch as soon as it exceeds the remaining target.ProCodeConcept6 min20 XPOpen
16Combination SumApply reuse-or-advance backtracking to reusing candidates while building every target-sum combination.ProCodePractice8 min20 XPOpen
17Sudoku CornerApply budgeted choose-place-undo Sudoku search to solving a budgeted four-by-four board with choose-place-undo search.ProCodePractice8 min20 XPOpen
18The Exponential HonestyEstimate search growth from branch factor and depth, then state an input limit that makes it viable.ProInteractiveConcept6 min20 XPOpen
19Pick Your ParadigmChoose greedy, dynamic programming, or backtracking from exchange safety, repeated states, and alternative exploration.ProInteractiveConcept6 min20 XPOpen
20Greedy and Backtracking Mastery CheckApply interval-greedy plus subset-search synthesis to combining earliest-finish scheduling with a target subset search.ProCodeMastery check10 min40 XPOpen

Dynamic Programming The Pattern Playbook