COMP3035J Advanced Program Construction 完整复习资料

目标：不是只背代码，而是按教授 slide 的程序构造方式，完整写出 derivation：Postcondition → domain model → theorem / recurrence → invariant → initialization → guard → variant function → loop body → final algorithm。

最重要提醒：这门课考试不是普通算法题。你不能只写“用 DP / two pointers / doodle 一下”。要把“为什么这个循环是对的”写出来，尤其是 invariant 和 loop body 的推导。

0. 这门课到底怎么答题

COMP3035J 的核心不是“想出代码”，而是从数学 postcondition 构造程序。标准答案通常长这样：

写 Postcondition。明确最后要得到什么，例如 r = f.N，或者 r = K.M。

定义 domain model。把自然语言问题转成函数，例如 K.m、D.m.n、A.i.j。

找 theorem / recurrence。写出如何从小问题得到大问题，例如 K.m = ↑ i : ...。

Rewrite Postcondition。把最终目标写成适合循环维护的形式，例如 C.m ∧ m = M。

Choose invariants。通常就是 rewritten postcondition 去掉终止条件。

Establish invariants。写初始化并说明为什么成立。

Guard + Variant Function。guard 通常是 m ≠ M，variant 通常是 M-m。

Loop body。通过 weakest precondition / text substitution 推出每轮该做什么。

Finished algorithm。把所有子程序合并，最后赋值 r := ...。

一句话：每道题都要写“状态代表什么、为什么初始化对、为什么更新后 invariant 还对、为什么结束后得到 postcondition”。

1. 符号与 GCL 速查

符号	含义	例子
`〈∀ i : R.i : P.i〉`	对所有满足范围 R 的 i，P 都成立	`〈∀ j : 0 ≤ j ≤ m : H.j = K.j〉`
`〈∃ i : R.i : P.i〉`	存在一个 i 使 P 成立	Yes/no change
`〈↑ i : R.i : E.i〉`	最大值	Rod cutting / Knapsack
`〈↓ i : R.i : E.i〉`	最小值	Minimum coins
`〈+ i : R.i : E.i〉`	求和 / 计数	number of ways
`Id↑`	max 的 identity，理解为负无穷	没有可选项时的最大值
`Id↓`	min 的 identity，理解为正无穷	凑不出来时的最小值

GCL 结构

if G0 → S0
[] G1 → S1
fi

do G → S od

注意：GCL 里的多重赋值是同时赋值，例如：

n, x, y := n+1, y, x + 2*y + 5

这不是先改 x 再改 y，而是右边都用旧值。

2. Sample exam 题型对应

题号	考点	对应材料	优先级	建议
Q1	Fibonacci-like recurrence	Fast Fibonacci / constant term	最高	必会，模板短，容易完整写步骤
Q2	Rod cutting DP	Rod cutting / Knapsack with repetition	最高	必会，DP 最典型题
Q3	decreasing arrays pair count	Pairs whose sum exceeds 37 / monotonicity	高	画二维区域，two pointers
Q4	shortest segment	Generic shortest segment / containing 0,1,2	高	expand right / shrink left，容易变体
Q5	minimal-prefix segment	longest prefix minimal segment	中	最后复习，别当唯一押题

3. 递推函数 / Fibonacci-like function：完整构造法

识别：题目给 f.0、f.1、f.(n+2)，要求 compute f.N。

3.1 通用二阶递推

Given: f.0 = A f.1 = B f.(n+2) = E(f.n, f.(n+1)) Post: r = f.N

3.2 选择 invariant

因为 f.(n+2) 依赖连续两项，所以保存连续两项：

P0 : x = f.n ∧ y = f.(n+1) P1 : 0 ≤ n ≤ N

3.3 Establish invariants

取 n=0，则 x=f.0=A，y=f.1=B：

n, x, y := 0, A, B

3.4 Guard 与 Variant Function

Guard: n ≠ N Vf: N - n

每次 n := n+1，所以 N-n 每轮减少 1，且下界为 0。

3.5 Loop body 推导

Observe: (n, x, y := n+1, E0, E1).P0 = {text substitution} E0 = f.(n+1) ∧ E1 = f.(n+2) = {recurrence} E0 = f.(n+1) ∧ E1 = E(f.n, f.(n+1)) = {P0: x=f.n ∧ y=f.(n+1)} E0 = y ∧ E1 = E(x, y)

所以：

n, x, y := n+1, y, E(x, y)

3.6 Finished algorithm

n, x, y := 0, A, B
;do n ≠ N →
    n, x, y := n+1, y, E(x, y)
od
;r := x

3.7 套 sample exam Q1

f.0 = 1 f.1 = 6 f.(n+2) = f.n + 2*f.(n+1) + 5

所以 E(x,y) = x + 2*y + 5。

n, x, y := 0, 1, 6
;do n ≠ N →
    n, x, y := n+1, y, x + 2*y + 5
od
;r := x

3.8 如果教授要求更高效 O(log N)

带常数项的递推可以扩一维，把常数变成矩阵的一部分。

[ f.(n+1) ] [0 1 0] [ f.n ] [ f.(n+2) ] = [1 2 5] [ f.(n+1) ] [ 1 ] [0 0 1] [ 1 ]

然后用 fast exponentiation：

T = [[0,1,0],[1,2,5],[0,0,1]] [f.N, f.(N+1), 1]^T = T^N * [f.0, f.1, 1]^T

快速幂 invariant 常用：

P0 : T^N * v = A^n * y Guard : n ≠ 0 if even.n → n, A := n div 2, A*A [] odd.n → n, y := n-1, A*y fi

4. 动态规划 DP：总规律

DP 的一句话：先定义数学函数 K 表示子问题答案，再用数组 H 保存所有 K 的值。

4.1 DP 五步法

定义状态：K.m 或 K.i.m 或 K.m.n 表示什么？
写 base case：规模为 0 时答案是什么？
找最后一步：最后切了什么、用了什么、选了什么、匹配了什么？
写 recurrence：最大用 ↑，最小用 ↓，是否可行用 ∃，计数用 +。
表格化：用 H 存 K，写 invariant ∀ j : H.j = K.j。

4.2 聚合符号决定题型

目标	符号	identity	例子
最大价值	`↑`	`Id↑` / 负无穷	Rod cutting, repeated knapsack
最小数量	`↓`	`Id↓` / 正无穷	Minimum coins
能不能	`∃` / `∨`	`false`	Yes/no change
多少种	`+`	`0`	count ways
匹配长度	`↑`	`0`	LCS

4.3 一维 DP 统一骨架

H.0 := base
;m := 0
;do m ≠ M →
    "compute H.(m+1) from H.0..H.m"
    ;m := m+1
od
;r := H.M

Invariant: P0 : C.m P1 : 0 ≤ m ≤ M C.m ≡ 〈∀ j : 0 ≤ j ≤ m : H.j = K.j〉

4A. Rod cutting：完整 slide 风格构造

题目：长度为 M 的 rod，可以切成长度数组 L[0..N) 中的长度，对应价格 P[0..N)，求最大价值。

Step 1. Define function K

K.m = maximum price obtainable from a rod of length m

Step 2. Base case

(0) K.0 = 0

Step 3. Recurrence / theorem

最后一次选择切一段长度 L.i，剩余长度为 m - L.i。

(1) K.m = 〈↑ i : 0 ≤ i < N ∧ L.i ≤ m : K.(m-L.i) + P.i〉

Step 4. Design decision

计算 K.m 需要更小的 K.(m-L.i)，所以从小到大填表。

Use array H[0..M] Post : 〈∀ j : 0 ≤ j ≤ M : H.j = K.j〉

Step 5. Model domain C.m

(2) C.m ≡ 〈∀ j : 0 ≤ j ≤ m : H.j = K.j〉

推导初始：

C.0 = {definition of C} 〈∀ j : 0 ≤ j ≤ 0 : H.j = K.j〉 = {one-point rule} H.0 = K.0 = {(0)} H.0 = 0

(3) C.0 ≡ H.0 = 0

Step 6. Split C.(m+1)

C.(m+1) = {definition of C} 〈∀ j : 0 ≤ j ≤ m+1 : H.j = K.j〉 = {split off j = m+1} 〈∀ j : 0 ≤ j ≤ m : H.j = K.j〉 ∧ H.(m+1) = K.(m+1) = {(2)} C.m ∧ H.(m+1) = K.(m+1) = {(1)} C.m ∧ H.(m+1) = 〈↑ i : 0 ≤ i < N ∧ L.i ≤ m+1 : H.((m+1)-L.i)+P.i〉

Step 7. Define subproblem D.m.n

为了计算上面的最大值，再定义一个内部 accumulation 函数。

D.m.n ≡ 〈↑ i : 0 ≤ i < n ∧ L.i ≤ m : H.(m-L.i)+P.i〉

那么：

K.(m+1) = D.(m+1).N

Step 8. D 的递推

D.m.0 = Id↑ D.m.(n+1) = D.m.n ⇐ L.n > m D.m.(n+1) = D.m.n ↑ (H.(m-L.n)+P.n) ⇐ L.n ≤ m

Step 9. Rewrite Postcondition

Post : C.m ∧ m = M

Step 10. Choose invariants

P0 : C.m P1 : 0 ≤ m ≤ M

Step 11. Establish invariants

m, H.0 := 0, 0

Step 12. Guard and Variant

Guard : m ≠ M Vf : M - m

Step 13. Loop body obligation

To establish (m := m+1).P0, need: C.(m+1) = C.m ∧ H.(m+1) = D.(m+1).N Since P0 gives C.m, it remains to compute: H.(m+1) = D.(m+1).N

Step 14. Inner loop for D.(m+1).N

Inner invariant: Q0 : s = D.(m+1).n Q1 : 0 ≤ n ≤ N Establish: n, s := 0, Id↑ Guard: n ≠ N Loop body: if L.n > m+1 → n, s := n+1, s [] L.n ≤ m+1 → n, s := n+1, s ↑ (H.((m+1)-L.n)+P.n) fi

Step 15. Finished algorithm

m, H.0 := 0, 0
;do m ≠ M →
    n, s := 0, Id↑
    ;do n ≠ N →
        if L.n > m+1 →
            n, s := n+1, s
        [] L.n ≤ m+1 →
            n, s := n+1, s ↑ (H.((m+1)-L.n) + P.n)
        fi
    od
    ;m, H.(m+1) := m+1, s
od
;r := H.M

Step 16. Complexity

Outer loop: M times Inner loop: N times Time: O(MN) Space: O(M)

4B. Coin change / Minimum coins：同一个 DP 模板换聚合符号

Yes/no change

K.m = amount m is makeable K.0 = true K.m = 〈∃ i : 0 ≤ i < N ∧ V.i ≤ m : K.(m-V.i)〉

H.0 := true
;m := 0
;do m ≠ M →
    n, s := 0, false
    ;do n ≠ N →
        if V.n > m+1 → n, s := n+1, s
        [] V.n ≤ m+1 → n, s := n+1, s ∨ H.((m+1)-V.n)
        fi
    od
    ;m, H.(m+1) := m+1, s
od
;r := H.M

Minimum number of coins

K.m = minimum number of coins needed to make amount m K.0 = 0 K.m = 〈↓ i : 0 ≤ i < N ∧ V.i ≤ m ∧ K.(m-V.i) ≠ Id↓ : K.(m-V.i)+1〉

H.0 := 0
;m := 0
;do m ≠ M →
    n, s := 0, Id↓
    ;do n ≠ N →
        if V.n > m+1 ∨ H.((m+1)-V.n) = Id↓ →
            n, s := n+1, s
        [] V.n ≤ m+1 ∧ H.((m+1)-V.n) ≠ Id↓ →
            n, s := n+1, s ↓ (H.((m+1)-V.n)+1)
        fi
    od
    ;m, H.(m+1) := m+1, s
od
;r := H.M

4C. LCS：二维 DP 完整结构

给两个序列 X[0..M) 和 Y[0..N)，求 longest common subsequence length。

Define function

L.m.n = length of LCS of X[0..m) and Y[0..n)

Base cases

L.0.n = 0 L.m.0 = 0

Recurrence

If X.(m-1) = Y.(n-1): L.m.n = 1 + L.(m-1).(n-1) If X.(m-1) ≠ Y.(n-1): L.m.n = L.(m-1).n ↑ L.m.(n-1)

Algorithm

i := 0
;do i ≠ M+1 →
    H.i.0 := 0
    ;i := i+1
od

j := 0
;do j ≠ N+1 →
    H.0.j := 0
    ;j := j+1
od

i := 1
;do i ≠ M+1 →
    j := 1
    ;do j ≠ N+1 →
        if X.(i-1) = Y.(j-1) →
            H.i.j := 1 + H.(i-1).(j-1)
        [] X.(i-1) ≠ Y.(j-1) →
            H.i.j := H.(i-1).j ↑ H.i.(j-1)
        fi
        ;j := j+1
    od
    ;i := i+1
od
;r := H.M.N

记忆：二维 DP 看最后两个元素；相等走左上角 +1，不等取上方和左方最大。

5. Monotonicity / Two pointers：pair count 完整思路

Sample Q3：f[0..M)、g[0..N) 都 decreasing，统计满足 f.i > g.j 的 pair 数。

Step 1. Postcondition

Post : r = 〈+ i,j : 0 ≤ i < M ∧ 0 ≤ j < N ∧ f.i > g.j : 1〉

Step 2. Domain model

定义已经处理过前 i 行的计数：

C.i ≡ r = 〈+ p,q : 0 ≤ p < i ∧ 0 ≤ q < N ∧ f.p > g.q : 1〉

Step 3. Monotonic boundary

因为 g decreasing，对于固定的 i，若某个 j 满足 f.i > g.j，则所有更大的 j 也满足。

找到最小 j 使 f.i > g.j 则贡献为 N - j

Step 4. Invariant

P0 : C.i P1 : 0 ≤ i ≤ M P2 : 0 ≤ j ≤ N P3 : j is boundary for current row i, found by inner loop

Step 5. Algorithm

i, r := 0, 0
;do i ≠ M →
    j := 0
    ;do j ≠ N ∧ f.i ≤ g.j →
        j := j + 1
    od
    ;r := r + (N - j)
    ;i := i + 1
od

注意：如果你想利用更强的 monotonicity 让 j 不重置，需要先证明边界单调。考试稳妥写法可以每行重新找，复杂度 O(MN)；更优写法需小心方向。

6. Shortest segment：完整构造法

题目常给性质 A.i.j，要求找最短满足 A.i.j 的 segment 长度。Sample Q4 让你改成包含 0 和 1 的最短 segment。

Step 1. Postcondition

Post : r = 〈↓ i,j : 0 ≤ i ≤ j ≤ N ∧ A.i.j : j-i〉

Step 2. Generic monotonic property

(0) ¬A.i.i (1) ¬A.i.j ⇒ 〈∀ k : i ≤ k ≤ j : ¬A.k.j〉

直观意思：如果 [i,j) 不满足，那么同一个右端 j 下，从更靠右的 k 开始也不会满足。这个性质支持 sliding window。

Step 3. 针对“包含 0 和 1”定义 A

A.i.j ≡ segment f[i..j) contains at least one 0 and at least one 1

Step 4. 用窗口变量

a = left boundary b = right boundary c0 = number of zeros in f[a..b) c1 = number of ones in f[a..b) A.a.b ≡ c0 > 0 ∧ c1 > 0

Step 5. Invariant

P0 : 0 ≤ a ≤ b ≤ N P1 : c0 = count of 0 in f[a..b) P2 : c1 = count of 1 in f[a..b) P3 : r is the shortest valid segment already seen

Step 6. Loop body pattern

If current window is not valid: expand right boundary b If current window is valid: update answer r shrink left boundary a

Step 7. Finished algorithm

a, b, c0, c1, r := 0, 0, 0, 0, Id↓
;do a ≠ N →
    do b ≠ N ∧ ¬(c0 > 0 ∧ c1 > 0) →
        if f.b = 0 → c0 := c0 + 1
        [] f.b = 1 → c1 := c1 + 1
        [] f.b ≠ 0 ∧ f.b ≠ 1 → skip
        fi
        ;b := b + 1
    od

    if c0 > 0 ∧ c1 > 0 →
        r := r ↓ (b-a)
    [] ¬(c0 > 0 ∧ c1 > 0) →
        skip
    fi

    if f.a = 0 → c0 := c0 - 1
    [] f.a = 1 → c1 := c1 - 1
    [] f.a ≠ 0 ∧ f.a ≠ 1 → skip
    fi
    ;a := a + 1
od

Step 8. Complexity

a moves from 0 to N once b moves from 0 to N once Time: O(N) Space: O(1)

7. Searching by elimination：保留候选区间

这类题的核心是：维护一个候选区间，证明答案一定还在里面，然后每一步删掉一部分不可能的区域。

通用结构

Post : answer in original domain Invariant: answer in current domain [l..r) 0 ≤ l ≤ r ≤ N Guard: domain not small enough Loop body: compare / use theorem eliminate left or right part Variant: r - l

Algorithm skeleton

l, r := 0, N
;do r-l ≠ 1 →
    m := (l+r) div 2
    if condition says answer is left →
        r := m
    [] condition says answer is right →
        l := m
    fi
od
;answer := l

这类题要写清楚 theorem：为什么某个比较结果允许你删掉一半？没有 theorem，只有代码，教授可能不给高分。

8. Minimal-prefix segment：最后复习但要知道结构

Sample Q5 定义：

MP.i.j ≡ 〈∀ k : i ≤ k < j : f.i ≤ f.k〉

意思是：在 segment [i,j) 里，开头元素 f.i 不大于后面所有元素，所以它是这个 segment 的 minimal prefix。

Postcondition

Post : r = 〈↑ i,j : 0 ≤ i ≤ j ≤ N ∧ MP.i.j : j-i〉

思路

对于每个起点 i，尽量向右扩展 j，直到遇到第一个 f.j < f.i。这时 [i,j) 是以 i 开头的最长 minimal-prefix segment。

直接算法

r := 0
;i := 0
;do i ≠ N →
    j := i
    ;do j ≠ N ∧ f.i ≤ f.j →
        j := j + 1
    od
    ;r := r ↑ (j-i)
    ;i := i + 1
od

这是容易理解但不是最高效的版本。若材料要求优化，需要利用 previous boundary 或 stack-like elimination；但考试里先写清 domain model 和 invariant 比盲目优化更重要。

9. 万能答题模板

9.1 一维 DP 模板

Define:
    K.m = ...

Base:
    K.0 = ...

Recurrence:
    K.m = combine over choices i of candidate

Use H[0..M].
C.m ≡ 〈∀ j : 0 ≤ j ≤ m : H.j = K.j〉

Post:
    C.M

Rewrite:
    Post : C.m ∧ m = M

Invariants:
    P0 : C.m
    P1 : 0 ≤ m ≤ M

Establish:
    m, H.0 := 0, base

Guard:
    m ≠ M

Vf:
    M-m

Loop body:
    compute H.(m+1)
    m := m+1

Final:
    r := H.M

9.2 递推函数模板

Post:
    r = f.N

Invariant:
    P0 : x = f.n ∧ y = f.(n+1)
    P1 : 0 ≤ n ≤ N

Initialize:
    n, x, y := 0, f.0, f.1

Guard:
    n ≠ N

Vf:
    N-n

Loop:
    n, x, y := n+1, y, recurrence-expression-with-x-y

Final:
    r := x

9.3 Sliding window 模板

a, b := 0, 0
;initialize summary of f[a..b)
;r := Id↓
;do a ≠ N →
    do b ≠ N ∧ window not valid →
        add f.b to summary
        ;b := b+1
    od
    if window valid → r := r ↓ (b-a)
    [] otherwise → skip
    fi
    remove f.a from summary
    ;a := a+1
od

10. 常见扣分点

扣分点	为什么错	正确做法
只写代码，不写 invariant	这门课考程序构造，不只是算法实现	每题至少写 Post、Invariant、Guard、Vf
DP 里直接写 `H.m = ...`，没定义 `K.m`	缺少数学 model	先 `K.m = ...`，再说 `H.m = K.m`
递推函数顺序赋值	旧值被覆盖	用 simultaneous assignment：`x,y := y, ...`
Rod cutting 写成 `K.(m-i)` 但题目长度是 `L.i`	如果长度数组不是 1,2,3... 就错	写 `K.(m-L.i)`
Minimum coins 没处理 impossible	凑不出来时不能加 1	用 `Id↓` 并检查 `H.(m-V.i) ≠ Id↓`
Shortest segment 没维护窗口 summary	无法 O(1) 判断窗口是否满足	用计数器，例如 `c0,c1`
忘记 variant function	没有终止性证明	写 `N-n`、`M-m`、`r-l`

11. 考前 2 小时速背

递推函数

x=f.n,y=f.(n+1)

n,x,y := n+1,y,E(x,y)

结束 r:=x

Rod cutting

K.m = ↑ i : L.i≤m : K.(m-L.i)+P.i

外层 m，内层 i。

Minimum coins

K.m = ↓ i : V.i≤m : K.(m-V.i)+1

记得 impossible / Id↓。

Yes/no change

K.0=true

K.m = ∃ i : V.i≤m : K.(m-V.i)

LCS

相等：左上 +1。

不等：上/左取 max。

Shortest segment

不满足就扩右边。

满足就更新答案、缩左边。

考试策略：优先准备 Q1 递推 + Q2 DP + Q4 shortest segment。它们最容易写出完整步骤。Q3 用图辅助，Q5 最后复习。