联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Java编程Java编程

日期:2020-10-26 10:50

Design and Analysis of Algorithms

Fall 2020

Assignment 1


Question 1.(10 pt) Below is the pseudo code for a divide and conquer algorithm that finds the minimum value in an array. Suppose that the input array, A, is of size n, analyze the computational cost of this algorithm in the form of T(n) and prove your conclusion.

Question 2.(10 pt) Given the following program

int function (int n){

if (n<=2)

return 1;

return function(n-1)+function(n-2);

}

Prove this program runs in O(2n) time.

Question 3.(10 pt) Consider two complex numbers, a + bi and c + di, where . How to compute their product with only 3 numerical multiplications? (Note that there is no requirement on the number of additions or subtractions.)

Question 4. (15 pt) In the linear-time divide-and-conquer algorithm taught in class for the selection problem, recall that we divided the input elements into groups of 5. Analyze the running time of this algorithm, assuming that the input elements are divided into groups of 3. Does your algorithm run in linear time?

[Use a similar proof as given in the lecture slides "Divide & Conquer: Linear Time Selection", page 8.]

Question 5. (20 pt) In the linear-time divide-and-conquer algorithm taught in class for the selection problem, recall that we divided the input elements into groups of 5. Analyze the running time of this algorithm, assuming that the input elements are divided into groups of 8. Does your algorithm run in linear time?

[Use a similar proof as given in the lecture slides "Divide & Conquer: Linear Time Selection", page 8.]

Question 6. (20 pt) Given an increasingly sorted array A[1…n] of n distinct integers. Design an O(log n) algorithm which find the index i such that A[i]=i.

Question 7. (20 pt) Let A be an array of positive integers. Design a divide-and-conquer algorithm for computing the maximum value of A[j]-A[i] with j≥i. Analyze the time complexity of your algorithm.


版权所有:留学生编程辅导网 2018 All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。