Question 1 (25pt)
Given the input , track the divide-and-conquer algorithm to find the maximum contiguous subarray. You need to show the recursive calls as a tree. The input and output for each recursive call should also be indicated as well.
Question 2 (25pt)
Given two polynomials and , track the algorithm to calculate . You need to show the recursive calls as a tree. The input and output for each recursive call should also be indicated as well.
Question 3 (20pt)
In the deterministic linear-time divide-and-conquer algorithm taught in class for the selection problem, the input array is divided into groups of 5 elements. Analyze the running time of the algorithm if the input array is divided into groups of 7. Does your algorithm run in linear time?
Question 4 (15pt)
A segment is a pair of positive integers , where . Two segments and intersect if .
Given a sequence of segments sorted increasingly by ’s ( if ) within the ( for all ), design a divide-and-conquer algorithm to justify if there are two segments intersect.
You need to
a)Describe your algorithm in a high-level presentation. (5pt)
b)Write down the pseudo code. (5pt)
c)Analyze the time complexity of your algorithm. (5pt)
Question 5 (10pt)
In lecture 3, we studied the divide-and-conquer algorithm for the polynomial multiplication problem. To let polynomials evenly split into sub-polynomials, the algorithm on page 17 (Line 4 - 7) nicely considers all the cases and uses the ceiling function (the last term in is ).
However, Goliath is lazy. He does not want to use any ceiling function or floor function in his implementation. To make his life easy, he simply assumes that
“The number of terms in the polynomials is always an integer power of .”
In other words, for some .
But, the polynomial multiplication problem in general contains polynomials whose number of terms is not an integer power of 2. Thus, you need to
a)Define a method to convert polynomials in general to polynomials whose number of terms is an integer power of 2. (5pt)
b)Discuss the consequence by doing so. Does it increase the time complexity comparing to the original algorithm (Algorithm 2 on page 17 in lecture 03)? Why? (5pt)
(Hint: please pay attention to the input size)
Assume Goliath’s implementation has the interface . You can consider that the algorithm with Goliath’s implementation works as follows.
请加QQ:99515681 邮箱:99515681@qq.com WX:codinghelp
- 全球“最独特”的一台华为 nova 6 5G 版手机是什么样子的?
- 拼多多抖音淘宝京东,谁是真低价?
- 老杨第一次再度抓握住一瓶水,他由此产生了新的憧憬
- 丰田章男称未来依然需要内燃机 已经启动电动机新项目
- B站更新决策机构名单:共有 29 名掌权管理者,包括陈睿、徐逸、李旎、樊欣等人
- 苹果罕见大降价,华为的压力给到了?
- 三明列东又有房子要拆迁!住这里的人要发了!
- 放大招后,广州又忍不住了…
- 私募积极加仓,百亿股票私募仓位指数创出近八周新高
- 他,传闻中马云最想见的人
- 升级的脉脉,正在以招聘业务铺开商业化版图
- 如何经营一家好企业,需要具备什么要素特点
- 智慧驱动 共创未来| 东芝硬盘创新数据存储技术
- 创意驱动增长,Adobe护城河够深吗?
- 全力打造中国“创业之都”名片,第十届中国创业者大会将在郑州召开