一、函数增长率排序Asymptotic Growth Ordering适用场景Problem Set 1 第1题。给一堆奇怪函数如指数嵌套、阶乘按增长率从小到大排。答题模板英文正文Simplify the expressions using logarithm/exponent rules (e.g., (\log_2 8^n 3n), constants are (O(1))).Categorize into general complexity classes: Constant (\ll) Logarithmic (\ll) Polynomial (\ll) Exponential (\ll) Factorial.For exponentials ((a^n)), compare the base (a) and the growth rate of the exponent. For polynomials, compare the degree.Final order: Write the sequence using strict inequalities, e.g., (f_5 f_3 f_8 \dots).二、主定理与递推式求解Master Theorem适用场景Problem Set 1 归并排序复杂度推导或分治算法Karatsuba/Strassen的复杂度分析。答题模板英文正文Identify the recurrence form: (T(n) aT(n/b) O(n^d)).Compare (\log_b a) with (d):If (\log_b a d), then (T(n) O(n^{\log_b a})).If (\log_b a d), then (T(n) O(n^d \log n)).If (\log_b a d), then (T(n) O(n^d)).Conclusion: Substitute the specific constants to get the final complexity.三、分治算法设计Divide and Conquer适用场景Problem Set 1 链表归并排序 / 网格找局部最小值或高级题 Karatsuba乘法 / 最近点对。答题模板英文正文Divide: Split the input into (a) subproblems of size (n/b) (e.g., split the grid by middle row/column, or split numbers into two halves).Conquer: Recursively solve these subproblems.Combine: Merge the results with cost (O(n^d)) (e.g., linear merge, or boundary probing for grid local min).Recurrence: Write (T(n) aT(n/b) O(n^d)). Apply Master Theorem.Correctness (Induction): Assume recursive calls return correct results for subproblems. The merge step correctly combines them, so the overall algorithm is correct.四、贪心算法Greedy与交换论证Exchange Argument适用场景Problem Set 1 区间覆盖 / 最小加油次数或课程中的区间调度 / 最小生成树。答题模板英文正文Algorithm description: Sort the items (by finish time / coordinate / deadline). Initialize (R -\infty) and (count 0). Iterate, selecting the first compatible item and updating (R).Proof of Correctness (Exchange Argument):Let (G) be the greedy solution and (O) be an optimal solution. Suppose they share the first (k-1) choices.At step (k), greedy picks (g) (with the earliest finish time / farthest reach). Let (o) be the (k)-th choice in (O).Since greedy picks optimally, (finish(g) \le finish(o)) (or (reach(g) \ge reach(o))).Exchange: Replace (o) with (g) in (O). Feasibility is maintained and quality does not decrease. Repeating this transforms (O) into (G).Complexity: Sorting dominates, total (O(n \log n)).五、动态规划Dynamic Programming适用场景Problem Set 2 最大和递增子序列 / 分组背包 / 区间涂色或课程中序列比对 / Bellman-Ford。答题模板英文正文State Definition: Define (dp[i]) (or (dp[i][w]), or (f[i][j])) as the optimal value for the subproblem ending at (i) / using first (i) items / covering interval ([i, j]).Base Case:LIS: (dp[i] a[i]).Group Knapsack: (dp[0][w] 0).Interval Painting: (f[i][i] 1).Transition Equation:LIS: (dp[i] \max(a[i], \max_{j i, a[j] a[i]} (dp[j] a[i]))).Group Knapsack: (dp[i][w] \max(dp[i-1][w], \max_{c \le w} (dp[i-1][w-c] v))).Interval Painting: If (s[i] s[j]), then (f[i][j] f[i][j-1]); else (f[i][j] \min_{k} (f[i][k] f[k1][j])).Complexity: Time (O(n^2)) / (O(nW)) / (O(n^3)); Space accordingly.Correctness (Optimal Substructure): The recurrence considers all possible choices for the last element / partition point and takes the optimum over them, thus covering every feasible solution.六、网络流建模Max Flow / Min Cut适用场景Problem Set 2 Ford-Fulkerson手算增广 / 学生选课建模 / Animal Crossing二分答案或课程中图像分割 / 棒球淘汰。答题模板英文正文Ford-Fulkerson Execution (for hand calculation):Find an augmenting path (s \to \dots \to t).Compute bottleneck (f \min)(residual capacities along the path).Update: forward edges (- f), backward edges ( f).Repeat until no (s)-(t) path exists in the residual network.Max Flow Value sum of bottlenecks. By Max-Flow Min-Cut Theorem, this equals min cut capacity.Flow Network Construction (for modeling):Create super source (S) and sink (T).Left side (Students/Days): (S \to Node), capacity limit (e.g., (k_i), or daily capacity).Middle (Eligibility): Left (\to) Right, capacity 1 or (\infty), if the relation exists.Right side (Courses/Events): Node (\to T), capacity demand (e.g., (c_j)).Feasibility Check: Compute Max Flow. If it equals the total demand ((\sum c_i)), the instance is feasible.七、NP-完全性证明NP-Completeness Proof—— 必考大题适用场景Problem Set 3 链路干扰 / 巡逻点 / 单调3-SAT / 双容量装箱 / 网格黑白棋子。答题模板英文正文Show the problem is in NP: Given a certificate (e.g., subset (L’)), we can verify (|L’| \ge k) and scan all constraints in (O(|V||E|)) time. Thus it is in NP.Polynomial-time Reduction from a known NPC problem:State: “We reduce fromIndependent Set / Vertex Cover / 3-SAT / Subset Sum.”Mapping: Construct the instance explicitly (e.g., “For each vertex (v_i), create a link (\ell_i). For each edge ((u,v)), create an interference pair ((\ell_u, \ell_v)).”). This takes polynomial time.Correctness (Bidirectional):((\Rightarrow)): If the known problem instance is YES (e.g., there is an independent set of size (k)), then the constructed instance is also YES (the corresponding links have no conflicts).((\Leftarrow)): If the constructed instance is YES (e.g., a set of non-conflicting links), then mapping back yields a YES solution to the known problem (a valid independent set).Conclusion: Since the problem is in NP and an NPC problem reduces to it, the problem is NP-Complete.八、PSPACE 与 QSAT概念/简答适用场景Problem Set 3 没直接考但课程讲义有。如果问“PSPACE-complete是什么”或“QSAT怎么理解”。答题模板英文正文Definition of QSAT: A quantified Boolean formula (\exists x_1 \forall x_2 \exists x_3 \dots \Phi(x_1, \dots, x_n)), where (\Phi) is a 3-CNF.Interpretation: This models a two-player game. The (\exists) player chooses values for existential variables, and the (\forall) player chooses for universal variables. The question is whether the (\exists) player has a winning strategy.PSPACE-Completeness: QSAT is the canonical PSPACE-Complete problem. It is considered harder than NP because it involves alternating quantifiers (game-playing), whereas NP only involves a single (\exists) quantifier.九、参数化算法FPT - Fixed Parameter Tractability适用场景课程讲义重点。问“小顶点覆盖Vertex Cover当k很小时怎么设计算法”。答题模板英文正文Algorithm (Branching):If (G) has no edges, return True.If (k 0), return False.Pick an arbitrary edge ((u, v)).Branch 1: include (u) in the cover, recurse on (G - {u}) with (k-1).Branch 2: include (v) in the cover, recurse on (G - {v}) with (k-1).Time Complexity: (T(n, k) 2T(n-1, k-1) O(n) \implies O(2^k \cdot n)).Correctness: For any edge, at least one endpoint must be in the vertex cover. Both possibilities are considered, so no solution is missed.十、局部搜索与纳什均衡Local Search / Nash Equilibrium适用场景课程讲义高级题。问“最大割局部最优的近似比”或“路由博弈的势函数”。答题模板英文正文Local Search for Max-Cut: Start with any partition. Repeatedly flip a vertex if moving it to the other side increases the cut. Stop at a local optimum.Approximation Guarantee: Any local optimum for Max-Cut is a2-approximation(cut size (\ge OPT/2)).Potential for Routing:Define (\Phi \sum_{e} c_e \cdot H(x_e)), where (x_e) is load on edge (e).When a player changes route to lower their own cost, (\Phi) strictly decreases. Since (\Phi) is bounded below, a Nash Equilibrium exists.Price of Stability (PoS): Best Nash equilibrium is at most (H(k) O(\log k)) times the social optimum.十一、摊还分析Amortized Analysis适用场景Problem Set 4 懒队列 / 墓碑压缩 / 三角数校准或课程中斐波那契堆 / 动态表。答题模板英文正文Aggregate Method: Sum total cost over (m) operations. Since each element (queue entry / tombstone) is processed at most once, total cost is (O(m)). Amortized cost ( O(1)).Accounting Method: Charge each operation (c) tokens. Actual cost is (a). Store (c-a) credits. Prove the credit balance is never negative (e.g., each insertion stores 1 credit, which pays for future expensive deletions).Potential Method: Define (\Phi) (e.g., (\Phi C \cdot |Q|), or (\Phi C \cdot #\text{Tombstones})). Ensure (\Phi_0 0) and (\Phi_i \ge 0). Compute (\hat{c}i c_i \Phi_i - \Phi{i-1}). Show (\hat{c}_i O(1)). The potential drop pays for the expensive operations.十二、概率与随机算法Probability Randomized适用场景Problem Set 4 超几何抽样 / 随机优先级选点或课程中 MAX-3SAT / Karger最小割 / 布隆过滤器。答题模板英文正文Define Indicator Variables: Let (X_i 1) if event (i) occurs (e.g., bad submission is selected, or clause is satisfied), else 0.Single-event Probability:Sampling: (\Pr[X_i 1] s/n).Random Priority (Graph): (\Pr[v \in S] 1/(\deg(v)1)).MAX-3SAT: A random assignment satisfies a clause with probability (1 - (1/2)^3 7/8).Expectation via Linearity(No independence needed!):(\mathbb{E}[X] \sum \mathbb{E}[X_i]). Simplify (e.g., for regular graph, (E[|S|] n/(d1)); for 3SAT, (E[#satisfied] 7m/8)).Tail Bound / Sufficient Condition:Failure probability: (\Pr[\text{No violation}] \le (1 - r/n)^s \le e^{-rs/n}).Set (e^{-rs/n} \le \delta \implies s \ge \frac{n}{r} \ln(1/\delta)).Bloom Filter Property: No False Negatives (if it says “not in set”, definitely not). May have False Positives with probability ((1 - e{-kn/m})k).十三、近似算法Approximation Algorithms适用场景课程讲义 Lecture 24。问“List Scheduling的近似比”或“Set Cover的贪心近似”。答题模板英文正文List Scheduling (2-approximation):Algorithm: Assign each job to the currently least loaded machine.Let (M) be the makespan. Let job (j) be the last job to finish, with length (t), and start time (T).Before job (j), all machines were busy, so (T \le OPT). Also, (t \le OPT).Therefore, (M T t \le 2OPT). It is a 2-approximation.Greedy Set Cover ((H(n))-approximation):Algorithm: Repeatedly pick the set that covers the most uncovered elements.The approximation ratio is (\ln n) (where (n) is the number of elements).Proof by charging: Each element is charged at most (OPT / (\text{remaining uncovered elements})), summing to (OPT \cdot H_n).考场战术提醒拿到卷子先看题目属于上述哪一个编号然后把对应英文模板的开头几句话如“We reduce from…”、“Define (dp[i]) as…”、“By Master Theorem…”先写上保证基础框架分到手。计算题把数字套进公式概念题把黑体关键词写全。你已经武装到牙齿了加油
