Home Page > > Details

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.

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp2
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Cpslp Programmingghostwriter ,Help Wit... 2020-11-25
- Csci 1110 Assignmenthelp With ,Data Pr... 2020-11-25
- Ghostwriter Program Programming,Help W... 2020-11-25
- Be491 Programminghelp With ,Ghostwrite... 2020-11-25
- Ghostwriter Cmpt 214 Programming,Help ... 2020-11-08
- Ghostwriter Csci 2122 Course,Help With... 2020-11-08
- Fit5032 Programminghelp With ,Ghostwri... 2020-11-08
- Com3503 Programming Programminghelp Wi... 2020-11-08
- Ghostwriter Program Programming Course... 2020-11-08
- Data Programminghelp With ,Ghostwriter... 2020-11-08
- Ghostwriter Secj 1023 Programming,Prog... 2020-11-08
- Ghostwriter Cmpsc 465 Programming,Help... 2020-11-07
- Help With Mf 703 Programming,Ghostwrit... 2020-11-07
- 954246 Programmingdebug ,Help With Pro... 2020-11-07
- Pstat 115 Programmingghostwriter ,R Pr... 2020-11-07
- Com1005 Course Programminghelp With ,G... 2020-11-07
- Tcp Programmingghostwriter ,Java Progr... 2020-11-07
- Ghostwriter Program Programming,Help W... 2020-11-07
- Help With Cosc2666 Programming,Ghostwr... 2020-11-07
- Digital Programmingghostwriter ,Help W... 2020-11-07

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2014 www.asgnhelp.com

Programming Assignment Help！