Dynamic Programming is an efficient way to implement some divide and conquer algorithms — it solves overlapping subproblems once, stores them, and uses those results to build the final answer. It works best when:

• Subproblems repeat (overlapping subproblems)
• The best solution is built from smaller best solutions (optimal substructure)

A. Assembly Line Scheduling

Time complexity: $O(n)$ Dynamic Table: $f_i[j]$ Only “$j$” needs to be iterated (is changing), so one-dimension. (The line numbers, 1 and 2, are fixed)

B. The 0-1 Knapsack Problem

Time complexity: $O(nW)$ Dynamic Table: $f[i][w]$ “i” and “w” need to be iterated, so two-dimension. (”v” follows “i”)

C. Longest Common Sequence (Lab 5)

2021-2022 Resit

Goal:

Find the longest common length: 3

Find the longest common sequence: ACG

Need to know how to draw the table

Describing the design of algorithm (F2023-2024 Q3)

Which paradigm to use?

DP (0-1 knapsack problem)

1. 0-1 knapsack problem has optimal substructure, meaning the solution to a problem can be constructed from solutions to its subproblems.
2. It also has overlapping subproblems, since the same sub-instances (i.e., selecting items up to a certain capacity) are solved repeatedly.
3. (Why not others)
   • A Greedy Algorithm is not applicable here because selecting items with smallest weights or highest values may lead to suboptimal results.
   • Divide-and-Conquer does not exploit overlapping subproblems and would be less efficient compared to DP.

Greedy (Activity Selection Problem)

1. Activity Selection has the greedy-choice property: choosing the activity that finishes earliest leads to an optimal overall schedule.
2. It also satisfies optimal substructure, as the remaining problem (after selecting an activity) is similar in structure and independent.
3. (Why not others)
   • Dynamic Programming is unnecessary because there are no overlapping subproblems, and we only need to make a local decision at each step.
   • Divide-and-Conquer is not applicable here, since splitting the problem and recombining solutions is more complex and less efficient than greedy.