Agent Work: Homework3

Claude Opus 4.6 · COMP 382: Reasoning about Algorithms

COMP 382: Reasoning about Algorithms

Homework 3

Total Points: 100

---

Problem 1: String Merging [15 points]

Let X, Y, and Z be three strings, where |X| = m, |Y| = n, and |Z| = m + n. We say that Z *merges* X and Y iff Z can be formed by interleaving the characters from X and Y in a way that maintains the left-to-right ordering of the characters from each string. For example, both abucvwx and uavwbxc merge the strings abc and uvwx.

Part 1 [5 points]

Give an efficient dynamic programming algorithm that determines whether Z merges X and Y. What is the time complexity of your algorithm?

Part 2 [10 points]

We will now generalize the problem so that the input includes a number K (in addition to the strings X, Y, Z). K is the maximum number of errors (substitutions) that we can allow during the merging. That is, the computational problem is to determine if there exists a string Z' (of length m + n) such that: (i) Z' merges X and Y, and (ii) Z, Z' differ at a maximum of K positions (i.e., the Hamming distance between Z and Z' is at most K).

Give an efficient dynamic programming algorithm for this problem. What is the time complexity of your algorithm?

---

Problem 2: Inventory Planning [20 Points]

The Rinky Dink Company makes machines that resurface ice rinks. The demand for such products varies from month to month, and so the company needs to develop a strategy to plan its manufacturing given the fluctuating, but predictable, demand.

The company wishes to design a plan for the next n months. For each month i, the company knows the demand dᵢ, that is, the number of machines that it will sell. Let D = Σᵢ₌₁ⁿ dᵢ be the total demand over the next n months.

The company keeps a full-time staff who provide labor to manufacture up to m machines per month. If the company needs to make more than m machines in a given month, it can hire additional, part-time labor, at a cost that works out to c dollars per machine.

Furthermore, if, at the end of a month, the company is holding any unsold machines, it must pay inventory costs. The cost for holding j machines is given as a function h(j) for j = 1, 2, ..., D, where h(j) ≥ 0 for 1 ≤ j ≤ D and h(j) ≤ h(j + 1) for 1 ≤ j ≤ D − 1.

Give an algorithm that calculates a plan for the company that minimizes its costs while fulfilling all the demand. The running time should be polynomial in n and D.

---

Problem 3: Optimal Matching of Sequences [30 Points]

For an integer n ≥ 1, we define [n] = {1, ..., n}. Suppose we are given as input sequences (i.e., arrays) of integers X = [x₁, ..., xₘ] and Y = [y₁, ..., yₙ]. A *matching* for (X, Y) is a subset M ⊆ [m] × [n] (containing pairs of indexes) that satisfies the following properties:

(i) (Left covered) For every index i ∈ [m] there is some j ∈ [n] such that (i, j) ∈ M.

(ii) (Right covered) For every index j ∈ [n] there is some i ∈ [m] such that (i, j) ∈ M.

(iii) (No crossing) There are no indexes i, i' ∈ [m] and j, j' ∈ [n] with i < i' and j < j' such that (i, j') ∈ M and (i', j) ∈ M.

The *cost* of a matching M for (X, Y) is defined as follows:

$$\text{cost}(M) = \sum_{(i,j) \in M} (x_i - y_j)^2$$

We are interested in finding an *optimal matching*, that is, a matching with minimal cost.

Part 1 [3 points]

Prove that every matching contains the pairs (1, 1) and (m, n).

Part 2 [7 points]

Let f(m, n) be the number of all possible matchings for (X, Y), where X = [x₁, ..., xₘ] and Y = [y₁, ..., yₙ]. Give a recursive definition for the function f and carefully explain how you obtained it.

Part 3 [20 points]

Design an algorithm that computes a matching with minimal cost. Explain why it is correct and discuss its time and space complexity.

---

Problem 4: Edit Distance & LCS [35 Points]

We will consider a generalization of the concept of edit distance, where the cost of an insertion, deletion and substitution is cᵢ, c_d and c_s respectively. Each parameter can be chosen to be any positive extended real number, i.e., an element of {x ∈ ℝ | x > 0} ∪ {∞}.

Keep in mind the following properties of ∞:

∞ + ∞ = ∞
x + ∞ = ∞
x < ∞

for every x ∈ ℝ.

Part 1 [3 points]

Provide pseudocode for the procedure EDITDISTANCE(X, Y, cᵢ, c_d, c_s), where X[1..m] and Y[1..n] are strings and cᵢ, c_d, c_s are the edit operation costs. This procedure should return the edit distance from X to Y, which we denote by D(X, Y). Recall that:

D(X, Y) = min{cost(W) | edit sequence W for (X, Y)}

as we defined in the lectures.

Part 2 [12 points]

Prove that D(xa, ya) = D(x, y) for all strings x, y and every letter a.

Note: This is not a trivial claim. You should justify it with a careful proof using the definition of edit distance.

Part 3 [20 points]

Let L(x, y) be the length of the longest common subsequence of strings x, y. We know from CLRS (page 396) that L is given by the following recursive definition:

L(x, ε) = 0
L(ε, y) = 0
L(xa, ya) = L(x, y) + 1
L(xa, yb) = max(L(xa, y), L(x, yb)) when a ≠ b

for all strings x, y and letters a, b.

For strings X and Y, show how L(X, Y) can be computed in one line of code using only one invocation of the procedure EDITDISTANCE(X, Y, cᵢ, c_d, c_s). Justify the correctness of your approach with a careful proof.

writeup.md206 B

markdown

# COMP382 Homework 3

## Student Responses

<!-- Write your solutions below. Add sections for each problem as needed. -->
<!-- Use proper mathematical notation where applicable. -->

[Your solutions here]

COMP382 Homework 3

Student Responses

---

Problem 1: String Merging

Part 1 [5 points]

Subproblem definition: Let dp[i][j] be a boolean indicating whether Z[1..i+j] can be formed by merging X[1..i] and Y[1..j].

Base case: dp[0][0] = true (the empty prefix of Z merges the empty prefixes of X and Y).

Recurrence: For i from 0 to m and j from 0 to n (skipping (0,0)):

dp[i][j] = (i > 0 AND dp[i-1][j] AND X[i] == Z[i+j])
         OR (j > 0 AND dp[i][j-1] AND Y[j] == Z[i+j])

Explanation: To form Z[1..i+j] by merging X[1..i] and Y[1..j], the last character Z[i+j] must come from either X[i] or Y[j]:

If Z[i+j] = X[i], then Z[1..i+j-1] must merge X[1..i-1] and Y[1..j].
If Z[i+j] = Y[j], then Z[1..i+j-1] must merge X[1..i] and Y[1..j-1].

Answer: Z merges X and Y if and only if dp[m][n] = true.

Time complexity: O(mn), since we fill an (m+1) x (n+1) table with O(1) work per entry.

---

Part 2 [10 points]

Subproblem definition: Let dp[i][j] be the minimum number of mismatches (Hamming distance positions) between Z[1..i+j] and the best interleaving Z'[1..i+j] that merges X[1..i] and Y[1..j].

Base case: dp[0][0] = 0.

Recurrence: For i from 0 to m and j from 0 to n (skipping (0,0)):

dp[i][j] = min(
    dp[i-1][j] + (X[i] != Z[i+j] ? 1 : 0)    if i > 0,
    dp[i][j-1] + (Y[j] != Z[i+j] ? 1 : 0)     if j > 0
)

Explanation: At position i+j in the merged string Z', we place either X[i] or Y[j]:

If we place X[i] at position i+j: the mismatch count increases by 1 if X[i] != Z[i+j], and 0 otherwise. The remaining prefix Z'[1..i+j-1] must optimally merge X[1..i-1] and Y[1..j].
If we place Y[j] at position i+j: similarly, the mismatch count increases by 1 if Y[j] != Z[i+j], and the remaining prefix must optimally merge X[1..i] and Y[1..j-1].

We take the minimum over both choices.

Answer: Z can be merged from X and Y with at most K errors if and only if dp[m][n] <= K.

Time complexity: O(mn). We fill an (m+1) x (n+1) table with O(1) work per entry. Note that the complexity does not depend on K.

---

Problem 2: Inventory Planning [20 points]

State definition: Let dp[i][j] = the minimum total cost (part-time labor + holding) over months 1 through i, given that the inventory at the end of month i is exactly j unsold machines.

Variables:

I_i = inventory at end of month i, where I_0 = 0 (no initial inventory).
p_i = number of machines produced in month i.
Relationship: I_i = I_{i-1} + p_i - d_i, so p_i = d_i + I_i - I_{i-1} = d_i + j - j' where j' = I_{i-1}.
Constraint: p_i >= 0, i.e., j' <= d_i + j.

Costs in month i:

Part-time labor: c * max(0, p_i - m) = c * max(0, d_i + j - j' - m).
Holding cost: h(j) if j >= 1, and 0 if j = 0.

Base case: dp[0][0] = 0; dp[0][j] = infinity for j > 0.

Recurrence: For month i = 1, ..., n and inventory level j = 0, 1, ..., R_i where R_i = d_{i+1} + ... + d_n is the remaining future demand:

dp[i][j] = h(j) * [j > 0] + min over j' in {0, ..., d_i + j} of {
    dp[i-1][j'] + c * max(0, d_i + j - j' - m)
}

where h(0) = 0 and [j > 0] is the indicator that j is positive.

Explanation: We iterate over all possible previous inventory levels j'. The production p_i = d_i + j - j' must be non-negative, so j' <= d_i + j. The part-time labor cost is c * max(0, p_i - m) (only machines beyond the full-time capacity m incur extra cost). The holding cost h(j) is paid if we end the month with j > 0 unsold machines.

Answer: The optimal cost is dp[n][0] (end with no leftover inventory, which is optimal since holding costs are non-negative and there is no future demand to satisfy).

Correctness: The inventory at the end of any month is bounded by the remaining demand (there is no benefit to producing more than can ever be sold, since holding costs are non-negative and non-decreasing). Thus j ranges from 0 to R_i <= D. The recurrence correctly captures all feasible production decisions by iterating over all valid previous inventory levels.

Time complexity: O(nD^2). There are O(n) months. For each month, the inventory ranges over O(D) values, and for each inventory value we examine O(D) possible previous inventories. Since D = sum of all demands, the running time is polynomial in n and D.

Space complexity: O(D) using a rolling array (only need the previous month's row).

---

Problem 3: Optimal Matching of Sequences

Part 1 [3 points]

Claim: Every matching M contains (1, 1) and (m, n).

Proof that (1, 1) in M:

By the *left covered* property, there exists some j such that (1, j) in M. By the *right covered* property, there exists some i such that (i, 1) in M.

Suppose for contradiction that (1, 1) not in M. Then j > 1 (since (1, j) in M but j != 1) and i > 1 (since (i, 1) in M but i != 1).

Apply the no-crossing condition with indices i_1 = 1, i_2 = i, j_1 = 1, j_2 = j:

We have i_1 < i_2 (since 1 < i) and j_1 < j_2 (since 1 < j).
We have (i_1, j_2) = (1, j) in M and (i_2, j_1) = (i, 1) in M.
This is a crossing, contradicting property (iii).

Therefore, either j = 1 or i = 1, and in both cases (1, 1) in M.

Proof that (m, n) in M:

By the *left covered* property, there exists some j such that (m, j) in M. By the *right covered* property, there exists some i such that (i, n) in M.

Suppose for contradiction that (m, n) not in M. Then j < n and i < m.

Apply the no-crossing condition with indices i_1 = i, i_2 = m, j_1 = j, j_2 = n:

We have i_1 < i_2 (since i < m) and j_1 < j_2 (since j < n).
We have (i_1, j_2) = (i, n) in M and (i_2, j_1) = (m, j) in M.
This is a crossing, contradicting property (iii).

Therefore, either j = n or i = m, and in both cases (m, n) in M. QED

---

Part 2 [7 points]

Recursive definition of f(m, n):

Base cases:

f(1, n) = 1 for all n >= 1.
f(m, 1) = 1 for all m >= 1.

Recurrence (for m >= 2 and n >= 2):

f(m, n) = f(m-1, n) + f(m, n-1) + f(m-1, n-1)

Derivation:

By Part 1, every matching for [m] x [n] must contain (m, n). We partition all matchings into three disjoint cases based on what other pairs involve index m or n:

First, we establish a key structural property: it is impossible for both (m, j) with j < n and (i, n) with i < m to be in the same matching. Proof: if (m, j) in M and (i, n) in M with i < m and j < n, then taking i_1 = i, i_2 = m, j_1 = j, j_2 = n, we get i_1 < i_2 and j_1 < j_2 with (i_1, j_2) = (i, n) in M and (i_2, j_1) = (m, j) in M — a crossing. Contradiction.

This gives three disjoint, exhaustive cases:

Case A: There exists j < n with (m, j) in M, and no i < m with (i, n) in M. Then n is matched only with m. All indices [n-1] on the right must be covered by pairs with left indices in [m]. All indices [m] on the left must be matched with indices in [n-1] (plus m is also matched with n). The restriction of M to [m] x [n-1] (removing only the pair (m, n)) forms a valid matching for sequences of length m and n-1. There are f(m, n-1) such matchings.

Case B: There exists i < m with (i, n) in M, and no j < n with (m, j) in M. Symmetric to Case A. The restriction to [m-1] x [n] forms a valid matching. There are f(m-1, n) such matchings.

Case C: No j < n with (m, j) in M, and no i < m with (i, n) in M. Then m is matched only with n, and n is matched only with m. Removing (m, n), the remaining pairs form a valid matching for [m-1] x [n-1]. There are f(m-1, n-1) such matchings.

Since the three cases are disjoint and exhaustive: f(m, n) = f(m, n-1) + f(m-1, n) + f(m-1, n-1).

Base case justification: When m = 1, left coverage requires (1, j) in M for some j, but by the same argument, (1, 1) and (1, n) must both be in M (the single left index must cover all right indices). The only valid matching is {(1, 1), (1, 2), ..., (1, n)}, so f(1, n) = 1. Similarly f(m, 1) = 1.

Verification: f(2, 2) = f(1, 2) + f(2, 1) + f(1, 1) = 1 + 1 + 1 = 3. The three matchings for [2] x [2] are: {(1,1),(2,2)}, {(1,1),(1,2),(2,2)}, and {(1,1),(2,1),(2,2)}. Confirmed.

---

Part 3 [20 points]

Algorithm:

Define OPT(i, j) = cost of an optimal matching for X[1..i] and Y[1..j].

Base cases:

OPT(1, 1) = (x_1 - y_1)^2
OPT(1, j) = OPT(1, j-1) + (x_1 - y_j)^2 for j >= 2 (the unique matching {(1,1),...,(1,j)})
OPT(i, 1) = OPT(i-1, 1) + (x_i - y_1)^2 for i >= 2 (the unique matching {(1,1),...,(i,1)})

Recurrence (for i >= 2 and j >= 2):

OPT(i, j) = (x_i - y_j)^2 + min(OPT(i-1, j-1), OPT(i-1, j), OPT(i, j-1))

Answer: The minimum cost matching has cost OPT(m, n).

Correctness proof:

By Part 1, every matching contains (i, j), so every matching pays at least (x_i - y_j)^2 for this pair. The remaining cost comes from the other pairs in the matching.

From the three cases in Part 2:

Case A (exists (i, j') with j' < j in M, no (i', j) with i' < i): The pairs other than (i, j) form a valid matching for [i] x [j-1], contributing cost OPT(i, j-1).
Case B (exists (i', j) with i' < i, no (i, j') with j' < j): The pairs other than (i, j) form a valid matching for [i-1] x [j], contributing cost OPT(i-1, j).
Case C (only (i, j) involves i or j): The remaining pairs form a matching for [i-1] x [j-1], contributing cost OPT(i-1, j-1).

Taking the minimum over all three cases gives the recurrence.

For the base cases: f(1, j) = 1, so the unique matching for [1] x [j] is {(1,1), (1,2), ..., (1,j)} with cost sum_{k=1}^{j} (x_1 - y_k)^2, which matches the recurrence OPT(1, j) = OPT(1, j-1) + (x_1 - y_j)^2. Similarly for OPT(i, 1).

Pseudocode:

OPTIMAL_MATCHING(X[1..m], Y[1..n]):
    // Base cases
    OPT[1][1] = (X[1] - Y[1])^2
    for j = 2 to n:
        OPT[1][j] = OPT[1][j-1] + (X[1] - Y[j])^2
    for i = 2 to m:
        OPT[i][1] = OPT[i-1][1] + (X[i] - Y[1])^2

    // Fill table
    for i = 2 to m:
        for j = 2 to n:
            OPT[i][j] = (X[i] - Y[j])^2 + min(OPT[i-1][j-1], OPT[i-1][j], OPT[i][j-1])

    return OPT[m][n]

Time complexity: O(mn) — we fill an m x n table with O(1) work per entry.

Space complexity: O(mn) for the full table. This can be reduced to O(min(m, n)) using a rolling array since each row only depends on the current and previous rows.

---

Problem 4: Edit Distance & LCS

Part 1 [3 points]

EDITDISTANCE(X[1..m], Y[1..n], c_i, c_d, c_s):
    // Initialize table
    D[0][0] = 0
    for i = 1 to m:
        D[i][0] = i * c_d          // delete all of X[1..i]
    for j = 1 to n:
        D[0][j] = j * c_i          // insert all of Y[1..j]

    // Fill table
    for i = 1 to m:
        for j = 1 to n:
            if X[i] == Y[j]:
                match_cost = D[i-1][j-1]       // characters match, no cost
            else:
                match_cost = D[i-1][j-1] + c_s  // substitution

            D[i][j] = min(match_cost,
                          D[i-1][j] + c_d,       // delete X[i]
                          D[i][j-1] + c_i)        // insert Y[j]

    return D[m][n]

Explanation:

D[i][j] represents the minimum-cost edit distance from X[1..i] to Y[1..j].
D[i][0] = i * c_d: transforming X[1..i] to the empty string requires i deletions.
D[0][j] = j * c_i: transforming the empty string to Y[1..j] requires j insertions.
For the recurrence, we consider three operations applied to transform X[1..i] into Y[1..j]:

- Match/Substitute: Align X[i] with Y[j]. Cost is 0 if they are equal, c_s otherwise. - Delete: Remove X[i], then transform X[1..i-1] into Y[1..j]. Cost: c_d. - Insert: Insert Y[j] at the end, then transform X[1..i] into Y[1..j-1]. Cost: c_i.

---

Part 2 [12 points]

Claim: D(xa, ya) = D(x, y) for all strings x, y and every letter a.

Proof:

We use the alignment view of edit distance. An alignment between strings S and T is a sequence of operations (match, substitute, delete, insert) that transforms S into T, where characters of S are consumed left-to-right and characters of T are produced left-to-right. In any valid alignment, if S[i] is matched/substituted with T[j] and S[i'] is matched/substituted with T[j'], then i < i' implies j < j' (no crossing).

Direction 1: D(xa, ya) <= D(x, y).

Let W be an optimal edit sequence (alignment) from x to y with cost D(x, y). We construct an alignment from xa to ya by appending a Match(a, a) operation to W. This matches the last character 'a' of xa with the last character 'a' of ya at cost 0. The total cost is D(x, y) + 0 = D(x, y). Therefore D(xa, ya) <= D(x, y).

Direction 2: D(x, y) <= D(xa, ya).

Let A be an optimal alignment from xa to ya with cost D(xa, ya). Let |x| = m, |y| = n, so xa has length m+1 and ya has length n+1. We show that A can be transformed into an alignment from x to y without increasing cost.

Consider the roles of xa[m+1] = a and ya[n+1] = a in alignment A.

Key observation: It is impossible for xa[m+1] to be aligned (matched/substituted) with some ya[j] (j <= n) while simultaneously ya[n+1] is aligned with some xa[i] (i <= m). Proof: Since i <= m < m+1 and j <= n < n+1, the no-crossing property of alignments requires that if xa[i] is aligned with ya[n+1], then xa[m+1] must be aligned with some ya[j'] where j' > n+1. But ya has length n+1, so no such j' exists. Contradiction.

Therefore, exactly one of these four cases holds:

Case (a): xa[m+1] is aligned with ya[n+1]. The cost of this alignment is 0 (both are 'a'). Removing this pair from A yields a valid alignment from x to y with cost D(xa, ya) - 0 = D(xa, ya). So D(x, y) <= D(xa, ya).

Case (b): xa[m+1] is deleted (cost c_d) and ya[n+1] is inserted (cost c_i). Removing both operations from A yields a valid alignment from x to y with cost D(xa, ya) - c_d - c_i < D(xa, ya). So D(x, y) <= D(xa, ya).

Case (c): xa[m+1] is aligned with ya[j] for some j <= n, and ya[n+1] is inserted. Since xa[m+1] is the last character of xa, all characters ya[j+1], ..., ya[n+1] after position j must be insertions. We modify A: instead of aligning xa[m+1] with ya[j], align xa[m+1] with ya[n+1] (cost 0, since both are 'a'). Now ya[j] is unmatched, so insert ya[j] (cost c_i). The characters ya[j+1], ..., ya[n] remain inserted, and ya[n+1] is no longer inserted.

The new cost is: (original cost) - (cost of aligning xa[m+1] with ya[j]) - c_i (for inserting ya[n+1]) + 0 (for matching xa[m+1] with ya[n+1]) + c_i (for inserting ya[j]).

The cost of aligning xa[m+1] with ya[j] was either 0 (if ya[j] = a) or c_s (if ya[j] != a). So the new cost = original cost - (0 or c_s) <= original cost.

After this modification, we are in Case (a). Removing the match of xa[m+1] with ya[n+1] gives an alignment from x to y with cost <= D(xa, ya). So D(x, y) <= D(xa, ya).

Case (d): xa[m+1] is deleted, and ya[n+1] is aligned with xa[i] for some i <= m. Since ya[n+1] is the last character of ya, all characters xa[i+1], ..., xa[m+1] after position i must be deletions. We modify A: instead of aligning xa[i] with ya[n+1], delete xa[i] (cost c_d). Instead of deleting xa[m+1], align xa[m+1] with ya[n+1] (cost 0, both are 'a').

The new cost is: original cost - (cost of aligning xa[i] with ya[n+1]) - c_d (for deleting xa[m+1]) + c_d (for deleting xa[i]) + 0 (for matching xa[m+1] with ya[n+1]).

The cost of aligning xa[i] with ya[n+1] was either 0 (if xa[i] = a) or c_s (if xa[i] != a). So the new cost = original cost - (0 or c_s) <= original cost.

After this modification, we are in Case (a), and D(x, y) <= D(xa, ya).

Combining both directions: D(xa, ya) = D(x, y). QED

---

Part 3 [20 points]

One-line computation:

L(X, Y) = (|X| + |Y| - EDITDISTANCE(X, Y, 1, 1, infinity)) / 2

That is, invoke EDITDISTANCE(X, Y, c_i, c_d, c_s) with c_i = 1, c_d = 1, c_s = infinity, and compute L(X, Y) = (m + n - D(X, Y)) / 2.

Proof of correctness:

We prove that when c_i = c_d = 1 and c_s = infinity:

D(X, Y) = m + n - 2 * L(X, Y)

which yields L(X, Y) = (m + n - D(X, Y)) / 2.

Step 1: Characterize edit sequences when c_s = infinity.

Since substitutions have infinite cost, any finite-cost edit sequence from X to Y uses only insertions and deletions (no substitutions). If a substitution were used, the total cost would be infinity, which cannot be optimal when a finite-cost sequence exists (and one always does: delete all of X, insert all of Y, with cost m + n).

Step 2: Relate insertion/deletion-only sequences to common subsequences.

An edit sequence using only insertions and deletions corresponds to an alignment where each position of X is either:

Matched with a position of Y (same character), or
Deleted.

And each position of Y is either:

Matched with a position of X (same character), or
Inserted.

Since substitutions are forbidden, matched positions must have the same character. The matched positions, read left-to-right, form a common subsequence of X and Y. (The no-crossing property of alignments ensures the subsequence order is preserved in both X and Y.)

Step 3: Express cost in terms of common subsequence length.

If the common subsequence has length l, then:

Number of deletions = m - l (unmatched positions of X).
Number of insertions = n - l (unmatched positions of Y).
Total cost = (m - l) * 1 + (n - l) * 1 = m + n - 2l.

Step 4: Minimize cost by maximizing subsequence length.

The edit distance D(X, Y) = min over all valid alignments of (m + n - 2l) = m + n - 2 * max(l). The maximum possible l is exactly L(X, Y), the length of the longest common subsequence.

Therefore: **D(X, Y) = m + n - 2 * L(X, Y)**.

Rearranging: L(X, Y) = (m + n - D(X, Y)) / 2 = (|X| + |Y| - EDITDISTANCE(X, Y, 1, 1, infinity)) / 2.

Verification against LCS recurrence:

Let D[i][j] denote the edit distance from X[1..i] to Y[1..j] with c_i = c_d = 1, c_s = infinity, and let L[i][j] = (i + j - D[i][j]) / 2.

L[0][j] = (0 + j - j) / 2 = 0. Matches L(epsilon, y) = 0.
L[i][0] = (i + 0 - i) / 2 = 0. Matches L(x, epsilon) = 0.

When X[i] = Y[j]: D[i][j] = min(D[i-1][j-1], D[i-1][j] + 1, D[i][j-1] + 1).

Since adding one character to a string can change the LCS by at most 1, we have L[i-1][j] <= L[i-1][j-1] + 1 and L[i][j-1] <= L[i-1][j-1] + 1, which translates to D[i-1][j] >= D[i-1][j-1] - 1 and D[i][j-1] >= D[i-1][j-1] - 1. Therefore D[i-1][j] + 1 >= D[i-1][j-1] and D[i][j-1] + 1 >= D[i-1][j-1], so D[i][j] = D[i-1][j-1].

Then L[i][j] = (i + j - D[i-1][j-1]) / 2 = (i - 1 + j - 1 - D[i-1][j-1]) / 2 + 1 = L[i-1][j-1] + 1. Matches L(xa, ya) = L(x, y) + 1.

When X[i] != Y[j]: D[i][j] = min(D[i-1][j] + 1, D[i][j-1] + 1) (the substitution option gives D[i-1][j-1] + infinity = infinity).

Then L[i][j] = (i + j - D[i][j]) / 2 = max((i + j - D[i-1][j] - 1)/2, (i + j - D[i][j-1] - 1)/2) = max(L[i-1][j], L[i][j-1]). Matches L(xa, yb) = max(L(xa, y), L(x, yb)) when a != b.

This confirms that L[i][j] = (i + j - EDITDISTANCE(X[1..i], Y[1..j], 1, 1, infinity)) / 2 satisfies the CLRS recurrence for LCS. QED

Problem 1: String Merging [15 points]

Part 1

Score: 5/5

Assessment:

Approach: Standard 2D boolean DP on prefixes of X and Y.

Strengths:

Correct subproblem definition: dp[i][j] = whether Z[1..i+j] merges X[1..i] and Y[1..j]
Correct base case dp[0][0] = true
Correct recurrence matching the reference solution exactly
Clear explanation of why the last character must come from either X[i] or Y[j]
Correct time complexity O(mn)

Errors/Gaps: None.

Rubric Breakdown:

Subproblem definition: 1/1
Recurrence (including base/boundary cases): 2/2
Output and correctness argument: 1/1
Time complexity: 1/1

---

Part 2

Score: 10/10

Assessment:

Approach: Minimization DP tracking the minimum Hamming distance, equivalent to the reference solution's T[i,j] formulation.

Strengths:

Correct reformulation from boolean to integer (minimum mismatches)
The mismatch indicator (X[i] != Z[i+j] ? 1 : 0) is equivalent to the reference's ν(a,b) helper
Boundary cases dp[i,0] and dp[0,j] are implicitly and correctly handled by the "skipping (0,0)" formulation (e.g., dp[1,0] only uses the i>0 branch, giving dp[0,0] + mismatch, which is correct)
Correct output condition: dp[m][n] ≤ K
Correct time complexity O(mn), with the good observation that complexity does not depend on K

Errors/Gaps: None.

Rubric Breakdown:

Subproblem definition: 2/2
Recurrence with mismatch counting: 4/4
Output condition (comparison with K): 2/2
Time complexity: 2/2

---

Problem 2: Inventory Planning [20 Points]

Score: 20/20

Assessment:

Approach: Forward DP with state dp[i][j] = minimum cost over months 1..i with inventory j at end of month i. This is a valid alternative to the reference's backward DP formulation.

Strengths:

Clear state definition with well-defined variables
Correct base case: dp[0][0] = 0, dp[0][j] = ∞ for j > 0
Correct transition: iterates over previous inventory j', computes production p_i = d_i + j - j', applies part-time cost c·max(0, p_i - m) and holding cost h(j)
Correct answer: dp[n][0], with good justification that ending with zero inventory is optimal
Correct bound on inventory by remaining demand R_i
Correct time complexity O(nD²), matching the reference
Bonus: mentions O(D) space optimization with rolling array

Errors/Gaps: None. The forward DP formulation is fully equivalent to the reference's backward formulation.

Rubric Breakdown:

State definition and variables: 4/4
Base cases: 3/3
Recurrence with correct cost components: 6/6
Output and correctness justification: 4/4
Time complexity: 3/3

---

Problem 3: Optimal Matching of Sequences [30 Points]

Part 1

Score: 3/3

Assessment:

Approach: Proof by contradiction using the no-crossing property, matching the reference solution.

Strengths:

Clear proof for both (1,1) and (m,n)
Correctly identifies the crossing that arises from the assumption
Explicit application of the no-crossing condition with named indices
Rigorous logical structure

Errors/Gaps: None.

Rubric Breakdown:

Proof (1,1) ∈ M: 1.5/1.5
Proof (m,n) ∈ M: 1.5/1.5

---

Part 2

Score: 7/7

Assessment:

Approach: Partition matchings into three disjoint cases based on how indices m and n participate beyond the mandatory pair (m,n).

Strengths:

Correct base cases: f(1,n) = 1, f(m,1) = 1 with justification
Correct recurrence: f(m,n) = f(m-1,n) + f(m,n-1) + f(m-1,n-1)
Excellent derivation: proves the key structural lemma that (m,j) with j<n and (i,n) with i<m cannot coexist (using no-crossing), then cleanly partitions into three exhaustive cases
Each case is carefully explained with the correct bijection to sub-matchings
Verification with f(2,2) = 3 and enumeration of all three matchings

Errors/Gaps: None. This is an exceptionally thorough derivation.

Rubric Breakdown:

Base cases: 1/1
Correct recurrence formula: 2/2
Derivation/justification of three cases: 3/3
Exhaustiveness and disjointness argument: 1/1

---

Part 3

Score: 20/20

Assessment:

Approach: Standard bottom-up DP using the three-case decomposition from Part 2.

Strengths:

Correct subproblem: OPT(i,j) = minimum cost matching for X[1..i] and Y[1..j]
Correct base cases matching the unique matchings for f(1,n) = f(m,1) = 1
Correct recurrence: OPT(i,j) = (x_i - y_j)² + min(OPT(i-1,j-1), OPT(i-1,j), OPT(i,j-1))
Rigorous correctness proof tying back to the three cases from Part 2
Clean pseudocode
Correct time complexity O(mn) and space complexity O(mn) with O(min(m,n)) optimization noted

Errors/Gaps: None.

Rubric Breakdown:

Subproblem definition: 3/3
Base cases: 3/3
Recurrence: 5/5
Correctness proof: 5/5
Pseudocode: 2/2
Complexity analysis: 2/2

---

Problem 4: Edit Distance & LCS [35 Points]

Part 1

Score: 3/3

Assessment:

Approach: Standard edit distance DP with parameterized costs.

Strengths:

Correct pseudocode with proper initialization (D[i][0] = i·c_d, D[0][j] = j·c_i)
Correct recurrence handling match vs. substitution based on character equality
Clear explanation of each operation (match/substitute, delete, insert)

Errors/Gaps: None.

Rubric Breakdown:

Correct pseudocode: 3/3

---

Part 2

Score: 12/12

Assessment:

Approach: Alignment-based proof with four exhaustive cases for the ≥ direction.

Strengths:

Direction 1 (≤): Clean argument appending Match(a,a) at cost 0. Correct.
Direction 2 (≥): The student uses a sophisticated case analysis:

- Proves a key structural lemma (xa[m+1] aligned with ya[j≤n] AND ya[n+1] aligned with xa[i≤m] is impossible due to no-crossing) - Identifies four exhaustive, disjoint cases: (a) aligned together, (b) both removed, (c) xa[m+1] aligned elsewhere + ya[n+1] inserted, (d) symmetric - Cases (c) and (d) are reduced to case (a) via cost-preserving rearrangement, with careful accounting showing the new cost ≤ original cost

This proof is actually more rigorous than the reference solution, which is more sketchy about the rearrangement details

Errors/Gaps: None. This is an exemplary proof.

Rubric Breakdown:

Direction ≤: 3/3
Direction ≥ (case analysis): 6/6
Rigor and completeness: 3/3

---

Part 3

Score: 20/20

Assessment:

Approach: Establishes D(X,Y) = m + n - 2L(X,Y) when c_s = ∞, then solves for L.

Strengths:

Correct one-line formula: L(X,Y) = (|X| + |Y| - EDITDISTANCE(X, Y, 1, 1, ∞)) / 2
Well-structured four-step proof:

1. When c_s = ∞, no substitutions are used (finite-cost sequences always exist) 2. Insertion/deletion-only alignments correspond to common subsequences 3. Cost = m + n - 2l for a common subsequence of length l 4. Minimizing cost ↔ maximizing l ↔ LCS

Bonus verification: The student goes beyond the reference by explicitly verifying that the formula satisfies all four cases of the CLRS LCS recurrence, including the non-trivial argument that D[i-1][j-1] ≤ D[i-1][j]+1 and D[i-1][j-1] ≤ D[i][j-1]+1 when X[i]=Y[j]

Errors/Gaps: None.

Rubric Breakdown:

Correct formula with single EDITDISTANCE invocation: 4/4
Proof that c_s = ∞ eliminates substitutions: 3/3
Proof relating edit distance to LCS: 8/8
Verification against LCS recurrence: 5/5

---

Overall Summary

Problem	Score	Notes
1.1	5/5	Correct DP with proper recurrence and complexity
1.2	10/10	Correct minimization DP with mismatch counting
2	20/20	Correct forward DP, equivalent to reference's backward formulation
3.1	3/3	Rigorous contradiction proof
3.2	7/7	Thorough derivation with structural lemma and verification
3.3	20/20	Correct DP with complete correctness proof
4.1	3/3	Correct parameterized edit distance pseudocode
4.2	12/12	Exceptionally detailed proof with four exhaustive cases
4.3	20/20	Correct formula with rigorous proof and recurrence verification
Total	100/100

General Comments:

This is an outstanding submission. Every problem is solved correctly with clear, rigorous justifications. The student demonstrates deep understanding of dynamic programming, proof techniques, and the connections between edit distance and LCS. Several proofs go beyond the reference solution in rigor and detail — notably Problem 4 Part 2's four-case alignment analysis and Part 3's verification against the CLRS recurrence. The writing is precise, well-organized, and mathematically sound throughout.

Total: 100/100

writeup.md

diff --git a/writeup.md b/writeup.md
index 5119c04..f1b71f8 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,8 +2,381 @@
 
 ## Student Responses
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+---
 
-[Your solutions here]
+## Problem 1: String Merging
 
+### Part 1 [5 points]
+
+**Subproblem definition:** Let `dp[i][j]` be a boolean indicating whether `Z[1..i+j]` can be formed by merging `X[1..i]` and `Y[1..j]`.
+
+**Base case:** `dp[0][0] = true` (the empty prefix of Z merges the empty prefixes of X and Y).
+
+**Recurrence:** For `i` from 0 to `m` and `j` from 0 to `n` (skipping `(0,0)`):
+
+```
+dp[i][j] = (i > 0 AND dp[i-1][j] AND X[i] == Z[i+j])
+         OR (j > 0 AND dp[i][j-1] AND Y[j] == Z[i+j])
+```
+
+**Explanation:** To form `Z[1..i+j]` by merging `X[1..i]` and `Y[1..j]`, the last character `Z[i+j]` must come from either `X[i]` or `Y[j]`:
+- If `Z[i+j] = X[i]`, then `Z[1..i+j-1]` must merge `X[1..i-1]` and `Y[1..j]`.
+- If `Z[i+j] = Y[j]`, then `Z[1..i+j-1]` must merge `X[1..i]` and `Y[1..j-1]`.
+
+**Answer:** Z merges X and Y if and only if `dp[m][n] = true`.
+
+**Time complexity:** O(mn), since we fill an (m+1) x (n+1) table with O(1) work per entry.
+
+---
+
+### Part 2 [10 points]
+
+**Subproblem definition:** Let `dp[i][j]` be the **minimum number of mismatches** (Hamming distance positions) between `Z[1..i+j]` and the best interleaving `Z'[1..i+j]` that merges `X[1..i]` and `Y[1..j]`.
+
+**Base case:** `dp[0][0] = 0`.
+
+**Recurrence:** For `i` from 0 to `m` and `j` from 0 to `n` (skipping `(0,0)`):
+
+```
+dp[i][j] = min(
+    dp[i-1][j] + (X[i] != Z[i+j] ? 1 : 0)    if i > 0,
+    dp[i][j-1] + (Y[j] != Z[i+j] ? 1 : 0)     if j > 0
+)
+```
+
+**Explanation:** At position `i+j` in the merged string Z', we place either `X[i]` or `Y[j]`:
+- If we place `X[i]` at position `i+j`: the mismatch count increases by 1 if `X[i] != Z[i+j]`, and 0 otherwise. The remaining prefix `Z'[1..i+j-1]` must optimally merge `X[1..i-1]` and `Y[1..j]`.
+- If we place `Y[j]` at position `i+j`: similarly, the mismatch count increases by 1 if `Y[j] != Z[i+j]`, and the remaining prefix must optimally merge `X[1..i]` and `Y[1..j-1]`.
+
+We take the minimum over both choices.
+
+**Answer:** Z can be merged from X and Y with at most K errors if and only if `dp[m][n] <= K`.
+
+**Time complexity:** O(mn). We fill an (m+1) x (n+1) table with O(1) work per entry. Note that the complexity does not depend on K.
+
+---
+
+## Problem 2: Inventory Planning [20 points]
+
+**State definition:** Let `dp[i][j]` = the minimum total cost (part-time labor + holding) over months 1 through `i`, given that the inventory at the end of month `i` is exactly `j` unsold machines.
+
+**Variables:**
+- `I_i` = inventory at end of month `i`, where `I_0 = 0` (no initial inventory).
+- `p_i` = number of machines produced in month `i`.
+- Relationship: `I_i = I_{i-1} + p_i - d_i`, so `p_i = d_i + I_i - I_{i-1} = d_i + j - j'` where `j' = I_{i-1}`.
+- Constraint: `p_i >= 0`, i.e., `j' <= d_i + j`.
+
+**Costs in month i:**
+- Part-time labor: `c * max(0, p_i - m) = c * max(0, d_i + j - j' - m)`.
+- Holding cost: `h(j)` if `j >= 1`, and `0` if `j = 0`.
+
+**Base case:** `dp[0][0] = 0`; `dp[0][j] = infinity` for `j > 0`.
+
+**Recurrence:** For month `i = 1, ..., n` and inventory level `j = 0, 1, ..., R_i` where `R_i = d_{i+1} + ... + d_n` is the remaining future demand:
+
+```
+dp[i][j] = h(j) * [j > 0] + min over j' in {0, ..., d_i + j} of {
+    dp[i-1][j'] + c * max(0, d_i + j - j' - m)
+}
+```
+
+where `h(0) = 0` and `[j > 0]` is the indicator that j is positive.
+
+**Explanation:** We iterate over all possible previous inventory levels `j'`. The production `p_i = d_i + j - j'` must be non-negative, so `j' <= d_i + j`. The part-time labor cost is `c * max(0, p_i - m)` (only machines beyond the full-time capacity `m` incur extra cost). The holding cost `h(j)` is paid if we end the month with `j > 0` unsold machines.
+
+**Answer:** The optimal cost is `dp[n][0]` (end with no leftover inventory, which is optimal since holding costs are non-negative and there is no future demand to satisfy).
+
+**Correctness:** The inventory at the end of any month is bounded by the remaining demand (there is no benefit to producing more than can ever be sold, since holding costs are non-negative and non-decreasing). Thus `j` ranges from 0 to `R_i <= D`. The recurrence correctly captures all feasible production decisions by iterating over all valid previous inventory levels.
+
+**Time complexity:** O(nD^2). There are O(n) months. For each month, the inventory ranges over O(D) values, and for each inventory value we examine O(D) possible previous inventories. Since D = sum of all demands, the running time is polynomial in n and D.
+
+**Space complexity:** O(D) using a rolling array (only need the previous month's row).
+
+---
+
+## Problem 3: Optimal Matching of Sequences
+
+### Part 1 [3 points]
+
+**Claim:** Every matching M contains (1, 1) and (m, n).
+
+**Proof that (1, 1) in M:**
+
+By the *left covered* property, there exists some `j` such that `(1, j) in M`.
+By the *right covered* property, there exists some `i` such that `(i, 1) in M`.
+
+Suppose for contradiction that `(1, 1) not in M`. Then `j > 1` (since `(1, j) in M` but `j != 1`) and `i > 1` (since `(i, 1) in M` but `i != 1`).
+
+Apply the no-crossing condition with indices `i_1 = 1`, `i_2 = i`, `j_1 = 1`, `j_2 = j`:
+- We have `i_1 < i_2` (since `1 < i`) and `j_1 < j_2` (since `1 < j`).
+- We have `(i_1, j_2) = (1, j) in M` and `(i_2, j_1) = (i, 1) in M`.
+- This is a crossing, contradicting property (iii).
+
+Therefore, either `j = 1` or `i = 1`, and in both cases `(1, 1) in M`.
+
+**Proof that (m, n) in M:**
+
+By the *left covered* property, there exists some `j` such that `(m, j) in M`.
+By the *right covered* property, there exists some `i` such that `(i, n) in M`.
+
+Suppose for contradiction that `(m, n) not in M`. Then `j < n` and `i < m`.
+
+Apply the no-crossing condition with indices `i_1 = i`, `i_2 = m`, `j_1 = j`, `j_2 = n`:
+- We have `i_1 < i_2` (since `i < m`) and `j_1 < j_2` (since `j < n`).
+- We have `(i_1, j_2) = (i, n) in M` and `(i_2, j_1) = (m, j) in M`.
+- This is a crossing, contradicting property (iii).
+
+Therefore, either `j = n` or `i = m`, and in both cases `(m, n) in M`. **QED**
+
+---
+
+### Part 2 [7 points]
+
+**Recursive definition of f(m, n):**
+
+**Base cases:**
+- `f(1, n) = 1` for all `n >= 1`.
+- `f(m, 1) = 1` for all `m >= 1`.
+
+**Recurrence (for m >= 2 and n >= 2):**
+
+```
+f(m, n) = f(m-1, n) + f(m, n-1) + f(m-1, n-1)
+```
+
+**Derivation:**
+
+By Part 1, every matching for `[m] x [n]` must contain `(m, n)`. We partition all matchings into three disjoint cases based on what other pairs involve index `m` or `n`:
+
+First, we establish a key structural property: **it is impossible for both** `(m, j)` with `j < n` **and** `(i, n)` with `i < m` to be in the same matching. Proof: if `(m, j) in M` and `(i, n) in M` with `i < m` and `j < n`, then taking `i_1 = i`, `i_2 = m`, `j_1 = j`, `j_2 = n`, we get `i_1 < i_2` and `j_1 < j_2` with `(i_1, j_2) = (i, n) in M` and `(i_2, j_1) = (m, j) in M` — a crossing. Contradiction.
+
+This gives three disjoint, exhaustive cases:
+
+**Case A:** There exists `j < n` with `(m, j) in M`, and no `i < m` with `(i, n) in M`.
+Then `n` is matched only with `m`. All indices `[n-1]` on the right must be covered by pairs with left indices in `[m]`. All indices `[m]` on the left must be matched with indices in `[n-1]` (plus `m` is also matched with `n`). The restriction of M to `[m] x [n-1]` (removing only the pair `(m, n)`) forms a valid matching for sequences of length `m` and `n-1`. There are `f(m, n-1)` such matchings.
+
+**Case B:** There exists `i < m` with `(i, n) in M`, and no `j < n` with `(m, j) in M`.
+Symmetric to Case A. The restriction to `[m-1] x [n]` forms a valid matching. There are `f(m-1, n)` such matchings.
+
+**Case C:** No `j < n` with `(m, j) in M`, and no `i < m` with `(i, n) in M`.
+Then `m` is matched only with `n`, and `n` is matched only with `m`. Removing `(m, n)`, the remaining pairs form a valid matching for `[m-1] x [n-1]`. There are `f(m-1, n-1)` such matchings.
+
+Since the three cases are disjoint and exhaustive: `f(m, n) = f(m, n-1) + f(m-1, n) + f(m-1, n-1)`.
+
+**Base case justification:** When `m = 1`, left coverage requires `(1, j) in M` for some `j`, but by the same argument, `(1, 1)` and `(1, n)` must both be in M (the single left index must cover all right indices). The only valid matching is `{(1, 1), (1, 2), ..., (1, n)}`, so `f(1, n) = 1`. Similarly `f(m, 1) = 1`.
+
+**Verification:** `f(2, 2) = f(1, 2) + f(2, 1) + f(1, 1) = 1 + 1 + 1 = 3`. The three matchings for `[2] x [2]` are: `{(1,1),(2,2)}`, `{(1,1),(1,2),(2,2)}`, and `{(1,1),(2,1),(2,2)}`. Confirmed.
+
+---
+
+### Part 3 [20 points]
+
+**Algorithm:**
+
+Define `OPT(i, j)` = cost of an optimal matching for `X[1..i]` and `Y[1..j]`.
+
+**Base cases:**
+- `OPT(1, 1) = (x_1 - y_1)^2`
+- `OPT(1, j) = OPT(1, j-1) + (x_1 - y_j)^2` for `j >= 2` (the unique matching `{(1,1),...,(1,j)}`)
+- `OPT(i, 1) = OPT(i-1, 1) + (x_i - y_1)^2` for `i >= 2` (the unique matching `{(1,1),...,(i,1)}`)
+
+**Recurrence (for i >= 2 and j >= 2):**
+
+```
+OPT(i, j) = (x_i - y_j)^2 + min(OPT(i-1, j-1), OPT(i-1, j), OPT(i, j-1))
+```
+
+**Answer:** The minimum cost matching has cost `OPT(m, n)`.
+
+**Correctness proof:**
+
+By Part 1, every matching contains `(i, j)`, so every matching pays at least `(x_i - y_j)^2` for this pair. The remaining cost comes from the other pairs in the matching.
+
+From the three cases in Part 2:
+- **Case A** (exists `(i, j')` with `j' < j` in M, no `(i', j)` with `i' < i`): The pairs other than `(i, j)` form a valid matching for `[i] x [j-1]`, contributing cost `OPT(i, j-1)`.
+- **Case B** (exists `(i', j)` with `i' < i`, no `(i, j')` with `j' < j`): The pairs other than `(i, j)` form a valid matching for `[i-1] x [j]`, contributing cost `OPT(i-1, j)`.
+- **Case C** (only `(i, j)` involves `i` or `j`): The remaining pairs form a matching for `[i-1] x [j-1]`, contributing cost `OPT(i-1, j-1)`.
+
+Taking the minimum over all three cases gives the recurrence.
+
+For the base cases: `f(1, j) = 1`, so the unique matching for `[1] x [j]` is `{(1,1), (1,2), ..., (1,j)}` with cost `sum_{k=1}^{j} (x_1 - y_k)^2`, which matches the recurrence `OPT(1, j) = OPT(1, j-1) + (x_1 - y_j)^2`. Similarly for `OPT(i, 1)`.
+
+**Pseudocode:**
+
+```
+OPTIMAL_MATCHING(X[1..m], Y[1..n]):
+    // Base cases
+    OPT[1][1] = (X[1] - Y[1])^2
+    for j = 2 to n:
+        OPT[1][j] = OPT[1][j-1] + (X[1] - Y[j])^2
+    for i = 2 to m:
+        OPT[i][1] = OPT[i-1][1] + (X[i] - Y[1])^2
+
+    // Fill table
+    for i = 2 to m:
+        for j = 2 to n:
+            OPT[i][j] = (X[i] - Y[j])^2 + min(OPT[i-1][j-1], OPT[i-1][j], OPT[i][j-1])
+
+    return OPT[m][n]
+```
+
+**Time complexity:** O(mn) — we fill an m x n table with O(1) work per entry.
+
+**Space complexity:** O(mn) for the full table. This can be reduced to O(min(m, n)) using a rolling array since each row only depends on the current and previous rows.
+
+---
+
+## Problem 4: Edit Distance & LCS
+
+### Part 1 [3 points]
+
+```
+EDITDISTANCE(X[1..m], Y[1..n], c_i, c_d, c_s):
+    // Initialize table
+    D[0][0] = 0
+    for i = 1 to m:
+        D[i][0] = i * c_d          // delete all of X[1..i]
+    for j = 1 to n:
+        D[0][j] = j * c_i          // insert all of Y[1..j]
+
+    // Fill table
+    for i = 1 to m:
+        for j = 1 to n:
+            if X[i] == Y[j]:
+                match_cost = D[i-1][j-1]       // characters match, no cost
+            else:
+                match_cost = D[i-1][j-1] + c_s  // substitution
+
+            D[i][j] = min(match_cost,
+                          D[i-1][j] + c_d,       // delete X[i]
+                          D[i][j-1] + c_i)        // insert Y[j]
+
+    return D[m][n]
+```
+
+**Explanation:**
+- `D[i][j]` represents the minimum-cost edit distance from `X[1..i]` to `Y[1..j]`.
+- `D[i][0] = i * c_d`: transforming `X[1..i]` to the empty string requires `i` deletions.
+- `D[0][j] = j * c_i`: transforming the empty string to `Y[1..j]` requires `j` insertions.
+- For the recurrence, we consider three operations applied to transform `X[1..i]` into `Y[1..j]`:
+  - **Match/Substitute:** Align `X[i]` with `Y[j]`. Cost is 0 if they are equal, `c_s` otherwise.
+  - **Delete:** Remove `X[i]`, then transform `X[1..i-1]` into `Y[1..j]`. Cost: `c_d`.
+  - **Insert:** Insert `Y[j]` at the end, then transform `X[1..i]` into `Y[1..j-1]`. Cost: `c_i`.
+
+---
+
+### Part 2 [12 points]
+
+**Claim:** D(xa, ya) = D(x, y) for all strings x, y and every letter a.
+
+**Proof:**
+
+We use the alignment view of edit distance. An alignment between strings S and T is a sequence of operations (match, substitute, delete, insert) that transforms S into T, where characters of S are consumed left-to-right and characters of T are produced left-to-right. In any valid alignment, if S[i] is matched/substituted with T[j] and S[i'] is matched/substituted with T[j'], then i < i' implies j < j' (no crossing).
+
+**Direction 1: D(xa, ya) <= D(x, y).**
+
+Let W be an optimal edit sequence (alignment) from x to y with cost D(x, y). We construct an alignment from xa to ya by appending a Match(a, a) operation to W. This matches the last character 'a' of xa with the last character 'a' of ya at cost 0. The total cost is D(x, y) + 0 = D(x, y). Therefore D(xa, ya) <= D(x, y).
+
+**Direction 2: D(x, y) <= D(xa, ya).**
+
+Let A be an optimal alignment from xa to ya with cost D(xa, ya). Let |x| = m, |y| = n, so xa has length m+1 and ya has length n+1. We show that A can be transformed into an alignment from x to y without increasing cost.
+
+Consider the roles of xa[m+1] = a and ya[n+1] = a in alignment A.
+
+**Key observation:** It is impossible for xa[m+1] to be aligned (matched/substituted) with some ya[j] (j <= n) while simultaneously ya[n+1] is aligned with some xa[i] (i <= m). Proof: Since i <= m < m+1 and j <= n < n+1, the no-crossing property of alignments requires that if xa[i] is aligned with ya[n+1], then xa[m+1] must be aligned with some ya[j'] where j' > n+1. But ya has length n+1, so no such j' exists. Contradiction.
+
+Therefore, exactly one of these four cases holds:
+
+**Case (a):** xa[m+1] is aligned with ya[n+1]. The cost of this alignment is 0 (both are 'a'). Removing this pair from A yields a valid alignment from x to y with cost D(xa, ya) - 0 = D(xa, ya). So D(x, y) <= D(xa, ya).
+
+**Case (b):** xa[m+1] is deleted (cost c_d) and ya[n+1] is inserted (cost c_i). Removing both operations from A yields a valid alignment from x to y with cost D(xa, ya) - c_d - c_i < D(xa, ya). So D(x, y) <= D(xa, ya).
+
+**Case (c):** xa[m+1] is aligned with ya[j] for some j <= n, and ya[n+1] is inserted. Since xa[m+1] is the last character of xa, all characters ya[j+1], ..., ya[n+1] after position j must be insertions. We modify A: instead of aligning xa[m+1] with ya[j], align xa[m+1] with ya[n+1] (cost 0, since both are 'a'). Now ya[j] is unmatched, so insert ya[j] (cost c_i). The characters ya[j+1], ..., ya[n] remain inserted, and ya[n+1] is no longer inserted.
+
+The new cost is: (original cost) - (cost of aligning xa[m+1] with ya[j]) - c_i (for inserting ya[n+1]) + 0 (for matching xa[m+1] with ya[n+1]) + c_i (for inserting ya[j]).
+
+The cost of aligning xa[m+1] with ya[j] was either 0 (if ya[j] = a) or c_s (if ya[j] != a). So the new cost = original cost - (0 or c_s) <= original cost.
+
+After this modification, we are in Case (a). Removing the match of xa[m+1] with ya[n+1] gives an alignment from x to y with cost <= D(xa, ya). So D(x, y) <= D(xa, ya).
+
+**Case (d):** xa[m+1] is deleted, and ya[n+1] is aligned with xa[i] for some i <= m. Since ya[n+1] is the last character of ya, all characters xa[i+1], ..., xa[m+1] after position i must be deletions. We modify A: instead of aligning xa[i] with ya[n+1], delete xa[i] (cost c_d). Instead of deleting xa[m+1], align xa[m+1] with ya[n+1] (cost 0, both are 'a').
+
+The new cost is: original cost - (cost of aligning xa[i] with ya[n+1]) - c_d (for deleting xa[m+1]) + c_d (for deleting xa[i]) + 0 (for matching xa[m+1] with ya[n+1]).
+
+The cost of aligning xa[i] with ya[n+1] was either 0 (if xa[i] = a) or c_s (if xa[i] != a). So the new cost = original cost - (0 or c_s) <= original cost.
+
+After this modification, we are in Case (a), and D(x, y) <= D(xa, ya).
+
+**Combining both directions:** D(xa, ya) = D(x, y). **QED**
+
+---
+
+### Part 3 [20 points]
+
+**One-line computation:**
+
+```
+L(X, Y) = (|X| + |Y| - EDITDISTANCE(X, Y, 1, 1, infinity)) / 2
+```
+
+That is, invoke `EDITDISTANCE(X, Y, c_i, c_d, c_s)` with `c_i = 1`, `c_d = 1`, `c_s = infinity`, and compute `L(X, Y) = (m + n - D(X, Y)) / 2`.
+
+**Proof of correctness:**
+
+We prove that when `c_i = c_d = 1` and `c_s = infinity`:
+
+```
+D(X, Y) = m + n - 2 * L(X, Y)
+```
+
+which yields `L(X, Y) = (m + n - D(X, Y)) / 2`.
+
+**Step 1: Characterize edit sequences when c_s = infinity.**
+
+Since substitutions have infinite cost, any finite-cost edit sequence from X to Y uses only insertions and deletions (no substitutions). If a substitution were used, the total cost would be infinity, which cannot be optimal when a finite-cost sequence exists (and one always does: delete all of X, insert all of Y, with cost m + n).
+
+**Step 2: Relate insertion/deletion-only sequences to common subsequences.**
+
+An edit sequence using only insertions and deletions corresponds to an alignment where each position of X is either:
+- **Matched** with a position of Y (same character), or
+- **Deleted**.
+
+And each position of Y is either:
+- **Matched** with a position of X (same character), or
+- **Inserted**.
+
+Since substitutions are forbidden, matched positions must have the same character. The matched positions, read left-to-right, form a **common subsequence** of X and Y. (The no-crossing property of alignments ensures the subsequence order is preserved in both X and Y.)
+
+**Step 3: Express cost in terms of common subsequence length.**
+
+If the common subsequence has length l, then:
+- Number of deletions = m - l (unmatched positions of X).
+- Number of insertions = n - l (unmatched positions of Y).
+- Total cost = (m - l) * 1 + (n - l) * 1 = m + n - 2l.
+
+**Step 4: Minimize cost by maximizing subsequence length.**
+
+The edit distance D(X, Y) = min over all valid alignments of (m + n - 2l) = m + n - 2 * max(l). The maximum possible l is exactly L(X, Y), the length of the longest common subsequence.
+
+Therefore: **D(X, Y) = m + n - 2 * L(X, Y)**.
+
+Rearranging: **L(X, Y) = (m + n - D(X, Y)) / 2 = (|X| + |Y| - EDITDISTANCE(X, Y, 1, 1, infinity)) / 2**.
+
+**Verification against LCS recurrence:**
+
+Let `D[i][j]` denote the edit distance from `X[1..i]` to `Y[1..j]` with `c_i = c_d = 1`, `c_s = infinity`, and let `L[i][j] = (i + j - D[i][j]) / 2`.
+
+- `L[0][j] = (0 + j - j) / 2 = 0`. Matches `L(epsilon, y) = 0`.
+- `L[i][0] = (i + 0 - i) / 2 = 0`. Matches `L(x, epsilon) = 0`.
+
+When `X[i] = Y[j]`: `D[i][j] = min(D[i-1][j-1], D[i-1][j] + 1, D[i][j-1] + 1)`.
+
+Since adding one character to a string can change the LCS by at most 1, we have `L[i-1][j] <= L[i-1][j-1] + 1` and `L[i][j-1] <= L[i-1][j-1] + 1`, which translates to `D[i-1][j] >= D[i-1][j-1] - 1` and `D[i][j-1] >= D[i-1][j-1] - 1`. Therefore `D[i-1][j] + 1 >= D[i-1][j-1]` and `D[i][j-1] + 1 >= D[i-1][j-1]`, so `D[i][j] = D[i-1][j-1]`.
+
+Then `L[i][j] = (i + j - D[i-1][j-1]) / 2 = (i - 1 + j - 1 - D[i-1][j-1]) / 2 + 1 = L[i-1][j-1] + 1`. Matches `L(xa, ya) = L(x, y) + 1`.
+
+When `X[i] != Y[j]`: `D[i][j] = min(D[i-1][j] + 1, D[i][j-1] + 1)` (the substitution option gives `D[i-1][j-1] + infinity = infinity`).
+
+Then `L[i][j] = (i + j - D[i][j]) / 2 = max((i + j - D[i-1][j] - 1)/2, (i + j - D[i][j-1] - 1)/2) = max(L[i-1][j], L[i][j-1])`. Matches `L(xa, yb) = max(L(xa, y), L(x, yb))` when `a != b`.
+
+This confirms that `L[i][j] = (i + j - EDITDISTANCE(X[1..i], Y[1..j], 1, 1, infinity)) / 2` satisfies the CLRS recurrence for LCS. **QED**

Agent Work: Homework3

COMP 382: Reasoning about Algorithms

Homework 3

Problem 1: String Merging [15 points]

Part 1 [5 points]

Part 2 [10 points]

Problem 2: Inventory Planning [20 Points]

Problem 3: Optimal Matching of Sequences [30 Points]

Part 1 [3 points]

Part 2 [7 points]

Part 3 [20 points]

Problem 4: Edit Distance & LCS [35 Points]

Part 1 [3 points]

Part 2 [12 points]

Part 3 [20 points]

COMP382 Homework 3

Student Responses

Problem 1: String Merging

Part 1 [5 points]

Part 2 [10 points]

Problem 2: Inventory Planning [20 points]

Problem 3: Optimal Matching of Sequences

Part 1 [3 points]

Part 2 [7 points]

Part 3 [20 points]

Problem 4: Edit Distance & LCS

Part 1 [3 points]

Part 2 [12 points]

Part 3 [20 points]

Problem 1: String Merging [15 points]

Part 1

Rubric Breakdown:

Part 2

Rubric Breakdown:

Problem 2: Inventory Planning [20 Points]

Score: 20/20

Rubric Breakdown:

Problem 3: Optimal Matching of Sequences [30 Points]

Part 1

Rubric Breakdown:

Part 2

Rubric Breakdown:

Part 3

Rubric Breakdown:

Problem 4: Edit Distance & LCS [35 Points]

Part 1

Rubric Breakdown:

Part 2

Rubric Breakdown:

Part 3

Rubric Breakdown:

Overall Summary

General Comments:

Sub-Model Usage