中科大2019级硕士算法设计与分析
计算机学院硕士HLS、WY老师版算法设计与分析2019级考试题（回忆版）。
选择题部分的28分跟历年题差别不大，比较新鲜的是：
- 哪些问题是难于近似的？
这个需要把近似算法部分介绍的算法的英文名字背过。
简答题：
1.为什么NP完全问题存在多项式时间解当且仅当P=NP.
2.证明两种近似算法的渐进性能比的定义等价。
试卷给出的两种定义的区别：
一个是课件上的OPT(I)>=N;
另一个是问题规模I>=N.
3.将异步环上的O(nlgn)算法向两侧的
4.题目给出近似算法性能比的上界
算法设计题：
1.设计一个最小定点覆盖的近似算法，求出性能比的大小，并根据试卷给出的图，写出最优解和近似解，并求性能比.
2.设计一个异步网络的广播和确认算法，使算法依赖于网的直径D而不是节点数N.