Data Structures & Algorithms Algorithmic Paradigms Syllabus

Algorithmic Paradigms syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Algorithmic Paradigms in Data Structures & Algorithms, not a summary of it.

1. 1

   Divide & Conquer

   3 topics

   • Paradigm Overview
   • Classic Problems
   • Karatsuba Multiplication
2. 2

   Greedy Algorithms

   3 topics

   • Greedy Choice Property
   • Classic Greedy Problems
   • Greedy vs Dynamic Programming
3. 3

   Dynamic Programming

   5 topics

   • DP Fundamentals
   • 1D DP Problems
   • 2D DP Problems
   • Knapsack Patterns
   • DP on Trees and Graphs
4. 4

   Backtracking

   3 topics

   • Backtracking Template
   • Classic Problems
   • Pruning Techniques
5. 5

   Branch & Bound

   2 topics

   • Overview and State Space
   • Travelling Salesman Problem

Algorithmic Paradigms flashcards for Data Structures & Algorithms

25 of 52 cards from the Algorithmic Paradigms deck — real questions with worked answers.

1. What is an algorithmic paradigm?

   A general, reusable strategy or design method for solving classes of problems — e.g., divide and conquer, greedy, dynamic programming, and backtracking. It describes the high-level approach, not a specific algorithm.

2. Name the four core algorithmic paradigms covered in a typical DSA course.

   Divide and conquer, greedy, dynamic programming, and backtracking (with branch and bound as a refinement of backtracking).

3. What are the three conceptual steps of the divide-and-conquer paradigm?

   1) Divide the problem into smaller subproblems, 2) Conquer by solving the subproblems recursively, and 3) Combine the subproblem solutions into a solution for the original problem.

4. State the Master Theorem recurrence form and give its three cases.

   For $T(n)=aT(n/b)+f(n)$ with $a\geq 1,\ b>1$, let $c=\log_b a$. Case 1: if $f(n)=O(n^{c-\epsilon})$ then $T(n)=\Theta(n^{c})$. Case 2: if $f(n)=\Theta(n^{c})$ then $T(n)=\Theta(n^{c}\log n)$. Case 3: if $f(n)=\Omega(n^{c+\epsilon})$ (with regularity) then $T(n)=\Theta(f(n))$.

5. Give three classic divide-and-conquer problems and their time complexities.

   Merge sort $\Theta(n\log n)$, binary search $\Theta(\log n)$, and Karatsuba multiplication $\Theta(n^{\log_2 3})\approx\Theta(n^{1.585})$.

6. What recurrence does merge sort satisfy, and what does the Master Theorem give?

   $T(n)=2T(n/2)+\Theta(n)$. Here $c=\log_2 2=1$ and $f(n)=\Theta(n)$, so Case 2 gives $T(n)=\Theta(n\log n)$.

7. What problem does Karatsuba's algorithm solve, and what is its key idea?

   It multiplies two large $n$-digit integers using only 3 recursive multiplications of half-size numbers instead of 4, by algebraic rewriting — reducing the naive $\Theta(n^{2})$ cost.

8. Write the Karatsuba decomposition for $x=x_1 B + x_0$ and $y=y_1 B + y_0$.

   $xy = x_1 y_1 B^{2} + \big[(x_1+x_0)(y_1+y_0) - x_1 y_1 - x_0 y_0\big]B + x_0 y_0$, where $B=10^{n/2}$ (or $2^{n/2}$). The middle term reuses the products $x_1y_1$ and $x_0y_0$.

9. What recurrence and complexity characterize Karatsuba multiplication?

   $T(n)=3T(n/2)+\Theta(n)$, giving $T(n)=\Theta(n^{\log_2 3})\approx\Theta(n^{1.585})$ by Master Theorem Case 1.

10. Define a greedy algorithm.

    An algorithm that builds a solution step by step, at each step making the choice that looks best locally (the greedy choice), never reconsidering previous choices, hoping this yields a globally optimal solution.

11. What is the greedy-choice property?

    The property that a globally optimal solution can be reached by making a locally optimal (greedy) choice at each step — the first greedy choice can always be extended to some optimal solution.

12. What two ingredients must a problem have for a greedy algorithm to yield an optimal solution?

    The greedy-choice property and optimal substructure (an optimal solution contains optimal solutions to subproblems).

13. How does the greedy-choice property differ from optimal substructure?

    Greedy-choice property: a locally optimal choice leads to a global optimum without needing to solve subproblems first. Optimal substructure: optimal solutions are composed of optimal subsolutions. DP relies on optimal substructure but not the greedy-choice property.

14. For the activity-selection problem, what is the greedy rule that gives optimality?

    Repeatedly select the activity with the earliest finishing time among those compatible with previously chosen activities. Sorting by finish time and greedily picking is optimal in $O(n\log n)$.

15. State the greedy strategy and complexity for Huffman coding.

    Repeatedly merge the two lowest-frequency nodes into a new node whose frequency is their sum, building the tree bottom-up. Using a min-heap, it runs in $O(n\log n)$ and produces an optimal prefix code.

16. What greedy strategy solves the fractional knapsack problem, and why does it fail for 0/1 knapsack?

    Sort items by value-to-weight ratio $\frac{v_i}{w_i}$ (descending) and take as much of each as fits, taking fractions of the last. It fails for 0/1 knapsack because items cannot be split, so a locally best ratio choice may not lead to the global optimum.

17. Which greedy algorithms find minimum spanning trees, and what greedy choice does each make?

    Kruskal's algorithm picks the smallest-weight edge that does not form a cycle; Prim's algorithm grows a tree by repeatedly adding the smallest-weight edge crossing the cut from the tree to the rest.

18. What greedy shortest-path algorithm requires non-negative edge weights, and what invariant does it maintain?

    Dijkstra's algorithm. It greedily extracts the unvisited vertex with the smallest tentative distance and finalizes it, maintaining that finalized vertices have their true shortest distances.

19. Compare greedy and dynamic programming: how do they treat local choices?

    Greedy makes one irrevocable locally optimal choice per step and never revisits it. Dynamic programming explores all choices at each subproblem, storing and combining subproblem solutions to guarantee global optimality.

20. When is greedy preferable to DP, given both may apply?

    When the greedy-choice property holds, greedy is preferable because it is simpler and usually faster (often $O(n\log n)$) and uses less memory, whereas DP explores more states and typically needs more time and space.

21. Give an example where greedy fails but DP succeeds, in the context of coin change.

    For coin denominations $\{1,3,4\}$ making 6, greedy gives $4+1+1=3$ coins, but DP finds the optimum $3+3=2$ coins. Greedy is not optimal for arbitrary denominations.

22. Define dynamic programming.

    A technique that solves problems by breaking them into overlapping subproblems, solving each subproblem once, and storing its result (memoization or tabulation) to avoid recomputation, exploiting optimal substructure.

23. What two properties must a problem have for dynamic programming to apply?

    Optimal substructure (an optimal solution is built from optimal subsolutions) and overlapping subproblems (the same subproblems recur many times).

24. Contrast top-down memoization with bottom-up tabulation.

    Top-down (memoization): recursion computes subproblems on demand and caches results. Bottom-up (tabulation): iteratively fills a table from base cases upward. Tabulation avoids recursion overhead; memoization only computes needed states.

25. How do you estimate the time complexity of a DP algorithm?

    Time $\approx$ (number of distinct states) $\times$ (work per state / transition cost). For example, a 2D table with $O(1)$ transitions is $O(mn)$.

See more Algorithmic Paradigms flashcards →

Planning Algorithmic Paradigms for Data Structures & Algorithms

Algorithmic Paradigms (Data Structures & Algorithms) FAQ