Algorithm design paradigms help solve new problems systematically. PSC questions may ask differences among greedy, divide-and-conquer and dynamic programming, recurrence analysis, examples and when each approach is valid.

Engineering Definitions

Greedy algorithm

Standard definition: An algorithm that builds a solution by repeatedly making a locally optimal choice.

Exam meaning: हरेक step मा तत्काल राम्रो देखिने choice लिएर solution बनाउने approach।

Divide and conquer

Standard definition: A design method that divides a problem into independent subproblems, solves them recursively and combines results.

Exam meaning: Problem divide, solve र combine गर्ने recursive strategy।

Dynamic programming

Standard definition: A method for solving problems with overlapping subproblems and optimal substructure by storing subproblem results.

Exam meaning: Repeated subproblems store गरेर optimal solution बनाउने technique।

Recurrence

Standard definition: An equation that defines running time or solution in terms of smaller input sizes.

Exam meaning: Recursive algorithm को time/solution लाई smaller n बाट define गर्ने equation।

Concept Teaching

Choosing the right paradigm matters. Greedy is fast but needs proof of greedy choice. Divide and conquer works when subproblems are mostly independent. Dynamic programming is used when recursion repeats overlapping subproblems and optimal substructure exists.

Greedy Method

Greedy choices must be safe.

  • Choose locally best option.
  • Never revise previous choices.
  • Works when greedy-choice property holds.
  • Examples: activity selection, Huffman coding, Kruskal/Prim MST, Dijkstra with nonnegative weights.
  • Fails for many coin systems and knapsack variants.

Divide and Conquer

Divide, solve and combine.

  • Divide problem into smaller subproblems.
  • Solve recursively.
  • Combine sub-results.
  • Examples: binary search, merge sort, quicksort, Strassen idea.
  • Recurrence expresses cost.

Dynamic Programming

DP trades memory for avoiding repeated work.

  • Optimal substructure: optimal solution contains optimal subsolutions.
  • Overlapping subproblems: same subproblem appears repeatedly.
  • Memoization is top-down DP.
  • Tabulation is bottom-up DP.
  • Examples: Fibonacci, matrix-chain multiplication, LCS, 0/1 knapsack.

Paradigm Comparison

Exam answers often ask direct comparison.

Aspect Greedy Divide and conquer Dynamic programming
Decision Local best Independent subproblems Store overlapping subproblems
Proof need Greedy-choice property Correct decomposition Optimal substructure
Memory Usually low Recursion stack Often table/cache
Example Kruskal Merge sort LCS/knapsack

Engineering Mechanism

  • Analyze problem structure.
  • Check if choices are independent or overlapping.
  • Select paradigm.
  • Write recurrence or state definition.
  • Prove correctness idea.
  • Analyze time and space complexity.

Diagrams / Models To Draw

  • Draw recursion tree for merge sort.
  • Draw DP table for LCS/knapsack idea.
  • Draw greedy interval selection timeline.
  • Draw recurrence decomposition T(n)=2T(n/2)+n.

Formulas, Algorithms and Code Patterns

  • Merge sort: T(n)=2T(n/2)+O(n)=O(n log n).
  • Binary search: T(n)=T(n/2)+O(1)=O(log n).
  • Fibonacci naive recursion is exponential; DP is O(n).
  • DP state transition: answer[state] from smaller states.
Paradigm When suitable Risk
Greedy Local choice provably safe May be wrong without proof
Divide and conquer Independent subproblems Combine cost matters
Dynamic programming Overlapping subproblems State explosion
Backtracking Constraint search Exponential worst case
Branch and bound Optimization search Bound quality matters

Exam Point

  • Greedy needs proof; example alone is not enough.
  • DP needs state definition and transition.
  • Divide and conquer subproblems are usually independent.
  • Memoization and tabulation are both DP.
  • Always include complexity.

Worked Example

Fibonacci recurrence F(n)=F(n-1)+F(n-2) repeats many calls in naive recursion. Memoization stores each F(k) once, reducing time from exponential to O(n), with O(n) memory.

Subjective Answer Pattern

  • Define each paradigm.
  • State conditions for use.
  • Give examples.
  • Compare tradeoffs.
  • Write recurrence/state if relevant.
  • Analyze complexity.

Common Engineering Mistakes

  • Using greedy without proving choice property.
  • Calling every recursive algorithm DP.
  • Forgetting overlapping subproblems in DP.
  • Ignoring combine step in divide and conquer.
  • Writing recurrence without base case.

MCQ Revision

  • Which paradigm uses overlapping subproblems?
  • Merge sort belongs to which paradigm?
  • Dijkstra requires what edge condition?
  • What is memoization?
  • What is optimal substructure?
  • Binary search recurrence?

Final Summary

  • Algorithm paradigms guide problem solving.
  • Greedy is local-choice based and needs proof.
  • Divide and conquer solves independent smaller problems.
  • DP stores overlapping subproblem results.
  • Recurrence and complexity analysis complete the answer.