算法设计练习题说课材料.doc

《算法设计练习题说课材料.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、精品好文档，推荐学习交流算法设计练习题一.计算复杂性1．P18410.3设计一个多项式时间的算法判断一个无向图G是否是2可着色的算法：2-COLORING输入：无向图G(V,E)输出：该图是2可着色的，则输出yes；否则，输出no.1.取任一节点，标记为白色2.所有与它邻接的节点标记为黑色3.对任意已标记的节点v，将所有与v邻接且未标记的节点标记为与v相反的颜色4.重复步骤3，直到不存在与已标记节点邻接且还未标记的节点5.如果图中还有未标记的节点，那么这些节点一定在一个新的连通分量中，再选择其中一个节点标记为白色，转到步

2、骤36.如果得到的图中，所有邻接的节点都标记为不同的颜色，则输出yes；否则，输出no.End2-COLORING时间复杂度分析：在n个顶点和m条边的图上进行分析，算法的运行时间是2．P185-18610.16团集问题的NP完全性是由可满足性问题归约到它证明的，给出一个从顶点覆盖到团集的较简单的归约法1：规约方法：设G=（V，E）是连通无向图，SV是一个团集当且仅当是中的一个顶点覆盖。证明：设e=(u,v)是G中的任意边，SV是一个团集当且仅当u和v都在S中，即是中的一个顶点覆盖。法2：证明：设G=（V，E）是连通无向图

3、，SV是G中的一个独立集，则S是的一个团集，独立集∝poly团集。因为顶点覆盖∝poly独立集，根据定理10.3，顶点覆盖∝poly团集。3．P185-18610.26用顶点覆盖问题规约到集合覆盖问题，证明集合覆盖问题是NP完全问题。证明：第一步是说明集合覆盖问题是NP的。因为一个不确定性算法可以从猜测一个集合X的子集族F开始，然后验证是否存在F中的k个子集的并是集合X。第二步证明顶点覆盖问题可以在多项式时间内规约到集合覆盖问题。设任意连通无向图G=(V,E)，集合X为G中所有与边相邻的顶点的集合，其子集族则是每个顶点与

4、其相邻的顶点构成的子集。集合X是满足集合覆盖的当且仅当X的子集族中存在k个子集的并是X，当且仅当G中存在大小为k的顶点覆盖。4．P21512.16证明：设{x1,x2,…,xn}是一个正实数集合。对于每一个实数xi，我们使它和二维平面中的点{(x1,1),(xj,0)

5、j∈2,…,n仅供学习与交流，如有侵权请联系网站删除谢谢8精品好文档，推荐学习交流}相联系，这样，所构造的n个点都位于三角形边上。如果我们用TRIANGULATION问题的任何算法求解构造的实例，输出将是根据它们的x坐标排序的构造点的表，遍历表并读出每点的

6、第一个坐标，结果是排序好的数。所以，排序问题规约到TRIANGULATION问题，排序问题是Ω(nlogn)，TRIANGULATION问题也是Ω(nlogn)。1．P21512.17证明：设{x1,x2,…,xn}是一个升序排列的正实数集合，及实数x。对于实数x及每一个实数xi，我们使它和二维平面中的点{(x,0),(xi,0)

7、i∈1,…,n}相联系，这样，所构造的点都位于x轴上。如果我们用NEARESTPOINT问题的任何算法求解，输出就是二分搜索要查找的数。所以，二分搜索问题规约到NEARESTPOINT问题，二

8、分搜索问题是Ω(logn)，NEARESTPOINT问题也是Ω(logn)。2．P21512.18证明：设{x1,x2,…,xn}是一个正实数集合，对于每一个实数xi，我们构造点(xi,0)与之对应，于是这些点在x轴上。如果我们用ALLNEARESTPOINT问题的任何算法求解，输出将是每个点(xi,0)对应的最近点对(xi,0)，(xj,0)。所以，CLOSEST-PAIR问题规约到ALLNEARESTPOINT问题，CLOSEST-PAIR问题是Ω(nlogn)，ALLNEARESTPOINT问题也是Ω(nlogn)

9、。二.随机算法1．P24114.2假定你有一枚硬币，请设计一个有效的随机算法用来生成整数1,2...n的随机排列，n为正整数，分析你的算法的时间复杂性。基本思想：从空序列开始，逐个向序列添加1,2,…,n。根据二分搜索的思想，并利用多次抛硬币，来随机确定每个添加的数在序列中的位置。算法RANDOMIZE2输入：正整数n输出：1,2,…,n的一个随机排列。A[1]=1fori=2tonj=randombisearch(1,i-1)//在数组A中随机确定i的插入位置。insert(A,j,i)//在数组A的j位置上插入值i。

10、endforoutputA[1..n]endRONDOMIZE2过程randombisearch(low,high)//利用二分搜索在A[low..high+1]中随机确定值i的插入位置，//并返回该位置。iflow>highthenreturnlowelsemid=k=random(1,2)//抛一次硬币。ifk=