Click image to open full size
Algorithm Design Paradigms Cheat Sheet
A printable reference covering brute force, divide and conquer, greedy algorithms, dynamic programming, backtracking, and complexity analysis for college.
Related Tools
Related Labs
Related Worksheets
Related Infographics
Algorithm design paradigms are general strategies for turning computational problems into correct and efficient algorithms. This cheat sheet helps students compare major approaches such as brute force, divide and conquer, greedy methods, dynamic programming, and backtracking. It is useful when choosing a strategy, proving correctness, and estimating running time. College computer science students need these patterns because many advanced algorithms are variations of a small set of design ideas. The core skill is matching problem structure to an algorithmic technique. Divide and conquer breaks a problem into independent subproblems, greedy algorithms make locally best choices, and dynamic programming reuses overlapping subproblem results. Backtracking searches a decision space while pruning impossible paths, while brute force provides a simple baseline. Complexity tools such as recurrences, Big O notation, and state counts help compare these designs.
Key Facts
- Brute force solves a problem by checking all candidates, so its time is often proportional to the size of the search space.
- Divide and conquer usually follows T(n) = aT(n/b) + f(n), where a is the number of subproblems, n/b is each subproblem size, and f(n) is combine work.
- A greedy algorithm is appropriate when the problem has the greedy-choice property and optimal substructure.
- Dynamic programming is appropriate when a problem has optimal substructure and overlapping subproblems.
- Top-down dynamic programming uses recursion plus memoization, while bottom-up dynamic programming fills a table in dependency order.
- Backtracking builds partial solutions recursively and abandons a branch when constraints prove it cannot lead to a valid solution.
- Branch and bound is a search strategy that prunes branches using bounds on the best possible objective value.
- Big O notation describes asymptotic upper growth, such as O(n log n), O(n^2), or O(2^n), while ignoring constant factors and lower-order terms.
Vocabulary
- Algorithm design paradigm
- A general method or pattern for designing algorithms for a class of problems.
- Optimal substructure
- A property where an optimal solution can be built from optimal solutions to smaller subproblems.
- Overlapping subproblems
- A property where the same smaller subproblems are solved many times during a recursive solution.
- Greedy-choice property
- A property where making a locally optimal choice can still lead to a globally optimal solution.
- Recurrence relation
- An equation that defines an algorithm's running time or value in terms of smaller input sizes or states.
- Pruning
- The act of skipping parts of a search space because they cannot produce a valid or better solution.
Common Mistakes to Avoid
- Using a greedy algorithm without proving the greedy-choice property is wrong because a locally best choice may block the global optimum.
- Using dynamic programming for every recursive problem is wrong because DP only helps when subproblems overlap or repeated computation is significant.
- Writing a recurrence but forgetting combine work is wrong because T(n) must include both recursive calls and nonrecursive work such as merging or partitioning.
- Counting only recursive depth instead of total nodes in backtracking is wrong because the running time depends on how many partial solutions are explored.
- Comparing algorithms only by worst-case Big O is incomplete because input size, constants, memory use, and typical-case behavior can affect the best practical choice.
Practice Questions
- 1 A divide and conquer algorithm solves 2 subproblems of size n/2 and spends O(n) time combining results. Write its recurrence and give its asymptotic running time.
- 2 A dynamic programming solution has 500 states, and each state checks 20 transitions. What is the total number of transition checks, and what is the time complexity in terms of states S and transitions per state K?
- 3 A backtracking algorithm chooses one of 3 options at each of 8 levels with no pruning. How many leaves are in the complete search tree?
- 4 A shortest-path problem has nonnegative edge weights. Explain why Dijkstra's algorithm is considered greedy and what property makes the greedy choice safe.