对应课程:点击查看
起止时间:2020-02-16到2020-07-31
更新状态:已完结
作业第六周 动态规划（中） 第六周 动态规划（中） 作业
1、 请为DPLCSLength设计一个时间复杂度为O(MN)的备忘录算法
评分规则: 程序正确
2、 给定两个字符串A和B，以及下列三种字符运算：（1）删除一个字符（2）插入一个字符（3）将一个字符改写为另一个字符设计算法求将A通过以上三种操作转换为B的最小次数
评分规则: 算法正确
作业第二周 算法分析方法 第二周 算法分析方法 作业
1、 1. 对某个数据结构执行一个具有n个运算的序列。如果i为2的整数幂，则第i个运算的费用为i否则为1.使用合计方法确定每次运算的分摊费用。
评分规则: 答案正确
2、 2. 用势能方法分析上题。
评分规则: 答案正确
作业第一周 算法概述及复杂性理论 第一周 算法概述及复杂性理论 作业
1、 1. 给定一个算法，其输入是一个整数集S和一个整数m，输出是和为m的所有S的子集，算法步骤如下：（1）列出S的全部子集，求他们的和。（2）逐个查看步骤（1）列出的子集，把每个和等于m的子集输出。上述算法是否满足算法特点？说明理由。
评分规则: 回答满足算法特点
确定性
可行性
有穷性
2、 2. 利用循环不变量证明下述计算a^n算法的正确性：Exp(a,n)1 i<-12 pow<-13 while i<=n do4 pow<-pow*a5 i<-i+16 return pow
评分规则: 初始步证明考虑n==0的情况
初始步证明考虑n==1的情况
证明过程清楚
3、 3. 设有两个在同一机器上实现的算法，运行时间分别为100n^2和2^n。当n取何值时，前者比后者快？
评分规则: 答案正确
作业第四周 分治（上） 第四周 分治（上）作业
1、 给定有序数组A以及一个元素x，设计一个寻找x的分治算法并分析其时间复杂度，要求返回x在数组中的位置。
评分规则: 程序正确
2、 给定n个整数的数组A以及一个数x，设计一个分治算法，求出x在数组中出现的次数，并分析时间复杂度。
评分规则: 使用分治算法
程序正确，边界条件处理正确
作业第十二周 回溯算法 第十二周 回溯算法
1、 设计算法求解N皇后问题，要求给出测试用例，并给出你的程序运行该测试案例之后得到的结果。N皇后问题研究的是如何将 N个皇后放置在 N×N 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
评分规则: 回溯算法
2、 上题如果只让求解N皇后问题不同解法的数目，又该如何设计算法？
评分规则: 直接求解长度
作业第十四周 NP完全理论 第十四周 NP完全理论
1、 解释什么是N问题，什么是NP问题
评分规则: P就是能在多项式时间内解决的问题，NP就是能在多项式时间验证答案正确与否的问题
2、 证明如下问题是NP-完全的：输入：两个图G1 = (V1, E1) 和G2 = (V2, E2) ：预算b。输出：两个节点集合V1’∈ V1 和V2’∈ V2和它们被移除后，将在两图中分别留下至少b个节点，且图的剩余部分完全一样
为了方便下次阅读，建议在浏览器添加书签收藏本网页
添加书签方法：
1.电脑按键盘的Ctrl键+D键即可收藏本网页
2.手机浏览器可以添加书签收藏本网页
获取更多MOOC答案，欢迎在浏览器访问我们的网站：http://mooc.mengmianren.com
注：请切换至英文输入法输入域名，如果没有成功进入网站，请输入完整域名：http://mooc.mengmianren.com/
我们的公众号
打开手机微信，扫一扫下方二维码，关注微信公众号：萌面人APP
本公众号可查看各种网课答案，还可免费查看大学教材答案
点击这里，可查看公众号功能介绍
一键领取淘宝，天猫，京东，拼多多无门槛优惠券，让您购物省省省，点击这里，了解详情