问题求解第三学期作业订正替代方案 - Githubissues

courses-at-nju-by-hfwei / problem-solving-class-problems

Problem Sets for Problem Solving Class

MIT License

14 stars 7 forks source link

问题求解第三学期作业订正替代方案 #16

Closed hengxin closed 5 years ago

hengxin commented 5 years ago

说明:

任选一道题目即可
在下面留言领取题目（多人可选同一题目）
截止日期: 2019年01月20日晚上 20:00 (依成绩统计进度，截止日期可能会有延后; 但这不是你犯拖延症的理由。)
提交方式: 与作业订正提交方式相同。此外，也可同时向该 Git 项目提交 pull request。

1. 平摊分析

问题: "自组织列表"平摊分析
参考资料: MIT OCW on Self-organizing Lists
要求: 观看教学视频，作笔记。描述问题、给出严格的证明过程

2. 最小生成树

2.1 Updating MST

问题: 已知图 G 的最小生成树 T。当出现如下情况时，如何高效地得到 G 的新的最小生成树。
- T 中某条边权值增加
- T 中某条边权值减少
- G 中某条边 (不在 T 中) 权值增加
- G 中某条边 (不在 T 中) 权值减少
要求: 给出严格的证明。
提醒: 对某一两个小题, 给出严格的证明可能并非想象中那么简单。

2.2 Critical Edges

问题: An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. Show how to find all critical edges in a graph in time proportional to E log E.
参考资料: Find all critical edges for minimum spanning tree @ cs-stackexchange
要求: 自行给出算法并给出严格证明; 或者检查参考资料中的算法与证明是否成立。 (两种方案均需提交报告。)

3. 带负权边的无向图上的最短路径问题

问题: 利用 Perfect Matching 求无向图(允许有负权边，但不允许有负圈)中的最短简单路径
参考资料: Shortest Path Algorithms (math.sfu.ca, Math 408, Luis Goddyn).pdf
要求: 给出严格而详细的证明。
提醒: 参考材料中有少量笔误和大量未加证明的陈述。

4. 匹配

问题: 稳定婚姻问题
参考资料: Youtube 视频: Stable Marriage Problem, Part 1、Stable Marriage Problem: Part 2
要求: 观看视频，作笔记。描述问题、算法以及证明。（可选: 问题的历史与发展）

5. 网络流

问题: 七个等价定理
参考资料: Equivalence of Seven Major Theorems in Combinatorics (Robert Borgersen, 2004).pdf
要求: 任选其中三个定理，证明它们的相互等价性，要给出严格而详细的证明过程。

congee524 commented 5 years ago

B.K. Huang 171240513, wanna prepare for Question 5.

massimodong commented 5 years ago

选择题目2.2

Michael1015198808 commented 5 years ago

2.1. Seeking for 大腿

FancyPei commented 5 years ago

Problem 3.

ghost commented 5 years ago

Problem 4 Zhao H. Yin

zxy8888 commented 5 years ago

problem 4 161120181赵新榆