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] < A[i + 1] < ...A[n − 1] < A[n]
for some unknown i . Such an array is known as unimodal (with the mode being a minimum). Give an O(logn) time algorithm for finding the minimum item A[i] in such an array. As an example, in the array below, the minimum item is 4.
9 5 4 6 8 12 14
To get full marks you must fully describe your algorithm (pseudocode is fine), explain
why it returns a correct answer and show why it runs in O(logn) time.
Problem 5 [28 pts] A city’s silhouette is what is seen when viewing the city’s buildings from a distance. For this problem assume that buildings are defined as rectangles. The city is flat and all the building floors are at the same level, designated as 0. Each building is formally defined by triple (l, r, h) and the problems’ input is a set of n triples (li, ri, hi), i = 1,...,n:
– l is the building’s left boundary,
– r is the building’s right boundary and
– h is the height of the building’s top floor.
From a distance, it is impossible to distinguish between the buildings. At any point x, you can only tell the top of the highest building
maxheight(x) = max{hi : [li, ri] contains x}.
The output of the problem should be a curve describing the silhouette listing, in sorted
order, the line segments at the top of the silhoutte.
In the example below the input is the set of rectangles seen on the left: (l1, r1, 2), (l2, r2, 5), (l3, r3, 3), (l4, r4, 3), (l5, r5, 4).
The output is the heavy horizontal line segments in the curve on the right: (l1, 2), (l5, 4), (r5, 3), (r4, 0), (l3, 3), (l2, 5), (r2, 3)(r3, 0).
More specifically, the output should be a list in the form (xj,Hj), j = 1,...k.
- x1 = min1≤i≤nli, xk = max1≤i≤nri
-x1