COMP 3711 – Design and Analysis of Algorithms 2022 Spring Semester – Written Assignment # 1 Distributed: Feb 18 2022 – Due: March 4, 2022
Your solutions should contain (i) your name, (ii) your student ID #, and (iii) your email address
Some Notes:
􏵵 Please write clearly and briefly.

Copyright By PowCoder代写 加微信 powcoder

􏵵 Please follow the guidelines on doing your own work and avoiding plagiarism as described in the class policies. You must acknowledge individuals who as- sisted you, or sources where you found solutions. Failure to do so will be considered plagiarism.
􏵵 All assignments must be submitted online via canvas. Hard copies will not be accepted. Email submissions will not be accepted. Late submissions will not accepted without prior approval.
􏵵 Please make a copy of your assignment before submitting it. If we can’t find your submission, we will ask you to resubmit the copy.
􏵵 If your submission is a scan of a handwritten solution, make sure that it is of high enough resolution to be easily read. At least 300dpi and possibly denser.

Problem 1 [17 pts] For each pair of expressions (A, B) below, indicate whether A is O, Ω , or Θ of B. Note that zero, one, or more of these relations may hold for a given pair. List the most appropriate relation. If A = Θ(B) then write A = Θ(B) instead of A = O(B) or A = Ω(B). It often happens that some students will get the directions wrong, so please write out the relation in full, i.e., A = O(B),A = Ω(B), or A = Θ(B) and not O(B), Ω(B) or Θ(B).
(a) A=n3 −100n,B=n2 +50n; (b) A=log2n2,B=log2.7n4;
(c) A=1010000,B= n ; 1010000
(d) A = 2nlogn, B = n10 + 8n2; (e) A = 2n, B = 2n+logn;
(f) A=33n,B=32n;
(g) A = (√2)logn, B = √logn;
Problem 2 [17 pts] For each of the following two problems, separately, give an asymptotic upper bound for T (n) satisfying the associated recurrence. Make your bounds as tight as possible. You must prove these bounds from scratch (either using the expansion method or the tree method). You may assume that n is a power of 2 for (a) and a power of 4 for (b).
(a) T(1)=1;T(n)=4T(n/2)+n2 forn>1 (b) T(1)=1;T(n)=16T(n/4)+nforn>1
Problem 3 [17 pts] Give asymptotic upper bounds for T(n) satisfying the following recurrences. Make your bounds as tight as possible. A correct answer will gain full credits. It is not necessary to show your work BUT, if your answer was wrong, showing your work steps may gain you partial credits. If showing your work, you may use theorems shown in class or can prove results from scratch.
(a) T(n) = 3T(n/2) + n2
(b) T(n)=2T(n/2)+nlogn
(c) T(n) = 7T(n/3) + n2 (d) T(n) = 3T(n/3) + n/2
(e) T(n)=6T(n/3)+n2logn

Problem 4 [21 pts] Suppose you are given an array A[1…n] of distinct numbers that you are told satisfies
A[1] > A[2] > … > A[i − 1] > A[i] CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

The post CS代考 COMP 3711 – Design and Analysis of Algorithms 2022 Spring Semester – Writte appeared first on PowCoder代写.