1随机性在算法中的作用
闭卷重建随机性在算法中的作用的对象、状态、事件、不变量与一个失败反例。
算法设计与分析 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2指示变量与期望线性
闭卷重建指示变量与期望线性的对象、状态、事件、不变量与一个失败反例。
3随机快排的期望分析
闭卷重建随机快排的期望分析的对象、状态、事件、不变量与一个失败反例。
4蓄水池抽样
闭卷重建蓄水池抽样的对象、状态、事件、不变量与一个失败反例。
5随机哈希与负载
闭卷重建随机哈希与负载的对象、状态、事件、不变量与一个失败反例。
6蒙特卡洛与拉斯维加斯
闭卷重建蒙特卡洛与拉斯维加斯的对象、状态、事件、不变量与一个失败反例。
7可复现随机实验
闭卷重建可复现随机实验的对象、状态、事件、不变量与一个失败反例。
第 1 页 · 背面（答案）
核心机制：对指示变量与期望线性先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为指示变量与期望线性实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析指示变量与期望线性时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对随机性在算法中的作用先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为随机性在算法中的作用实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析随机性在算法中的作用时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对蓄水池抽样先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为蓄水池抽样实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析蓄水池抽样时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对随机快排的期望分析先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为随机快排的期望分析实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析随机快排的期望分析时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对蒙特卡洛与拉斯维加斯先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为蒙特卡洛与拉斯维加斯实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析蒙特卡洛与拉斯维加斯时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对随机哈希与负载先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为随机哈希与负载实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析随机哈希与负载时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对可复现随机实验先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为可复现随机实验实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析可复现随机实验时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。