Algorithm Design

模块目标

Produce examination-style arguments that keep specification, invariant, and runtime in one chain rather than as disconnected slogans.

课程大纲

1. 01 Specifications and proof 20h

   学习结果 Write preconditions, postconditions, and a correctness claim that can fail if either is dropped.

   形成性检查 四选一检查

2. 02 Invariants 20h

   学习结果 Propose an invariant, prove initialisation, maintenance, and termination.

   形成性检查 书面推导

3. 03 Complexity 20h

   学习结果 Give a worst-case bound with an explicit cost model and a matching family of inputs.

   形成性检查 书面推导

4. 04 Recursive design 15h

   学习结果 Turn a recurrence into a runtime bound using a tree or Master-method case that applies.

   形成性检查 书面推导

5. 05 Divide and conquer 15h

   学习结果 Identify divide, combine, and the size of subproblems on a standard problem such as mergesort.

   形成性检查 四选一检查

6. 06 Greedy algorithms 20h

   学习结果 Give an exchange or stay-ahead argument, or a counterexample showing greed fails.

   形成性检查 反例

7. 07 Dynamic programming 20h

   学习结果 State the subproblem, the recurrence, and the evaluation order.

   形成性检查 书面推导

8. 08 Examination synthesis 20h

   学习结果 Produce one end-to-end argument: specify, design, prove, analyse.

   形成性检查 书面推导

学习结果

For a stated computational problem, give a specification, an algorithm, an invariant or induction, and a big-O bound with a cost model.

学科技能

Loop invariants, induction, recurrences, greedy exchange, dynamic-programming substructure.

可迁移技能

Separate “it worked on examples” from a proof; name the model when quoting a runtime.

相关入门主题

01Specifications and proof3 个主题

1. Problem specifications and correctness
2. Loop invariants
3. Asymptotic complexity

章节链接

02Recursive design2 个主题

1. Recursive correctness and termination
2. Divide and conquer

章节链接

03Optimisation strategies2 个主题

1. Greedy strategies and exchange arguments
2. Dynamic programming and state design

章节链接

04Examination synthesis1 个主题

1. Algorithm examination synthesis

章节链接