CSCI3160 Exercise：勘误与阅读说明

本套文档共覆盖136题。Regular有官方答案可对照，Special均为独立题解，不把自行推导称为官方答案。以下记录影响理解或正确性的重点；不是说除所列项目之外已对所有细枝末节作形式化证明。

来源限制

Regular 12：单独题目PDF为空，但官方答案PDF完整包含四题，已据此完成。
Special 9：2026-09-30 核验时当前链接为空。网页检索缓存可读教师2024 Fall目录中的五题，直接下载历史PDF返回404。已写历史题面解析，不能据此声称恢复了当前版原件；证据（本地资料）。
Special 1–3 原件标题写作CSCI3610，但来自CSCI3160官网目录。解析保留该来源差异。

原题或答案的实质问题

位置	核对结果与处理
Regular 1 Q1、Q2	拒绝采样精确期望1.28；二次幂构造的成功概率界依赖n大于候选范围一半，不是随机输出必须在上半区。
Regular 3 Q4	官方九区间反例受平局选择影响，并非必返3个；解析列明两类执行，并构造唯一首选的十一区间反例。
Regular 4 Q1、Q4	单顶点树没有度1叶子；最坏对数查找需要平衡树，重复key需用id区分。
Regular 5 Q3、Q4	建trie应按码字读完停止，不能遇到初始叶根就停；单字母非空编码与零频率影响严格满分支结论。
Regular 6 Q3	相邻端点时内部切点集合为空，原函数缺边界；文档给条件算法及不同补值会改变结果的例子。
Regular 7 Q1、Q3	LCS应比较删末字符的前缀长度；矩阵链用精确标量操作数作代价，不能直接把大O表达式作数值最小化。
Regular 9 Q1、Q3、Q5、Q6	候选距离是真最短距离的上界；路径存在需可达；单源负环检测不能覆盖不可达分量，给反例及全零初始化修正。
Regular 10 Q4	随机划分应遍历V，不是初始为空的S。
Regular 12 Q3	给定候选点可能有区间无法刺中，须检测无解，不能从宇宙中删掉这种区间。
Regular 13 Q4–6	明确不连通与零距离情况、平方距离比较的编码模型、至多k中心补齐成恰好k。
Special 5 Q2、Q5	n=1且要求非空码字时log₂n=0的说法不成立，单列边界。
Special 6 Q2	与Regular6 Q3类似缺相邻边界，不能给出未经指定的唯一有限答案。
Special 7 Q4	路径约束的逐步范围应到路径长度ℓ；路径长度按格数计，基例1。
Special 8 Q1	按题递推算出的180为未归一加权成本，除总权重100才是平均比较次数1.8。
Special 10 Q4、Q5	每轮中间结果依赖松弛顺序；零权环下不能把全部紧边直接当树，提供发现树构造。
Special 12 Q2	子句必须非空；空OR为假，无法满足至少一半概率。

发现与答案不同，先排除约定差异。 Sp10 的原地松弛与同步松弛可以有不同中间表；Sp13 的收益平局可以有不同合法选择；Sp08 的 180 和 1.8 分别是加权总成本与平均比较次数。这三类差异不应立即当作数学错误，应先统一执行顺序、平局和单位。

真正缺条件则必须给出影响：空子句使“至少一半满足”失败；缺相邻区间基例使 DP 无从开始；不可达负环使单源检测看不到。正文会保留原题并标明补充条件或修正版，读者应能区分原要求与为了得到可运行算法而添加的假设。

自测：一个小规模穷举全部通过，能证明一般的贪心算法吗？

不能。它能验证所枚举输入中的数值和反例，但一般正确性还需要交换论证、循环不变量或完整的数学归纳。反过来，一个合法反例就足以否定“对所有输入都正确”的命题。

核验做了什么

已检查每个List题号连续、题数与读取的题面匹配，Special每题均有先“题解”后“具体解析”。对LCS、BST、Huffman、最短路、重赋权、中心选择、集合覆盖收益等具体数值独立计算；对小图MST、顶点覆盖、TSP、关键贪心反例作穷举或另一算法核验。原图箭头与权重、区间递推的端点都看过渲染页。

全量核验记录（本地资料）保存覆盖与计算结果。小规模枚举支持例子的正确性，不能替代一般数学证明；一般情形的逻辑仍在对应题目正文逐步展开。课程catalog校验只证明路径、清单、哈希和本地引用一致，不代表数学内容自动正确。