Assignment Store | Assignment Chef

[SOLVED] COMP 3711 Design and Analysis of Algorithms 2025 Spring Semester Written Assignment 1R

COMP 3711 – Design and Analysis of Algorithms 2025 Spring Semester – Written Assignment 1 Distributed: 9:00 on February 14, 2025 Due: 23:59 on February 28, 2025 Your solution should contain (i) your name, (ii) your student ID #, and (iii) your email address at the top of its first page. Some Notes: • Please write clearly and briefly. In particular, your solutions should be written or printed on clean white paper with no watermarks, i.e., student society paper is not allowed. • Please also follow the guidelines on doing your own work and avoiding plagiarism as described on the class home page. You must acknowl-edge individuals who assisted you, or sources where you found solutions. Failure to do so will be considered plagiarism. • The term Documented Pseudocode means that your pseudocode must con-tain documentation, i.e., comments, inside the pseudocode, briefly ex-plaining what each part does. • Many questions ask you to explain things, e.g., what an algorithm is doing, why it is correct, etc. To receive full points, the explanation must also be understandable as well as correct. • Submit a SOFTCOPY of your assignment to Canvas by the deadline. 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. 1. (20 points) 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 all applicable relations. No explanation is needed. If A = Θ(B) then write A = Θ(B) which already implies that A = O(B) and A = Ω(B). If A = Θ(B) and you write A = O(B) or A = Ω(B) only, you will only receive partial credits. 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 just O(B), Ω(B) or Θ(B). 2. (20 points) Derive asymptotic upper bounds for T(n) in the following recurrences. Make your bounds as tight as possible. Do not use the master theorem. Derive your solutions from scratch. Show all your steps in order to gain full credits (either using the repeated expansion method or the recursion tree method). You may assume that n is a power of 2 for (b), n is a power of 3 for (c), √ n is an integer for (d), and n is a power of 5 for (e). (a) T(1) = 1; T(n) = T(n − 1) + n log n for n > 1. (b) T(1) = 1; T(n) = 5T(n/2) + n 2 for n > 1. (c) T(1) = 1; T(n) = 2T(n/3) + n for n > 1. (d) T(c) = 1 for any constant c > 1 that is convenient for you; T(n) = T( √n) + 1 for n > c. (e) T(c) = 1 for any constant c > 1 that is convenient for you; T(n) = T(n/5) + T(4n/5) + n for n > 1. Hint: Draw the recursion tree. Examine of the sum of costs across a level. Guess a solution. Then, try to prove by induction. 3. (20 points) Let A[1..n] be an array of n numbers, where n is a positive integer. (a) (10 points) Describe a recursive algorithm that returns a list of all per-mutations of A[1..n]. Describe your algorithm using a documented pseudocode. Make sure that your algorithm is recursive; otherwise, you will lose most of the points for problem 3. Make sure that your description is understandable. (b) (10 points) Write down the recurrence for the running time of your recursive algorithm in (a) with the boundary condition(s). Explain your notations. Solve your recurrence from scratch to obtain the the running time of your algorithm. 4. (20 points) Let P = {(xi , yi) : 1 ≤ i ≤ n} be a set of n points in the plane. Assume that no two of them have the same x- or y-coordinate. A point (xi , yi) is dominant if for every point (xj , yj ) ∈ P, xj > xi implies that yj < yi . Design an O(n log n)-time algorithm to find all dominant points in P by following the steps below. (a) Recursively find the dominant points in the subset {(xi, yi) : 1 ≤ i ≤ n/2}. (b) Recursively find the dominant points in the subset {(xi, yi) : n/2+1 ≤ i ≤ n}. (c) “Combine” these two sets of dominant points into the set of dominant points of P. Describe your algorithm. Explain in detail how the “combine” step works and why it works. Derive the running time of the algorithm by establish-ing a recurrence and solving it. 5. (20 points) (a) (10 points) You are given an array A[1..n], where n ≥ 3, A[1] = 0, A[n] = 0, and all the other elements are distinct positive numbers, i.e., A[i] > 0, for all i ∈ [2, n − 1]. For any i ∈ [2, n − 1], A[i] is a peak element if it is larger than both its neighbors, i.e., A[i] > A[i − 1] and A[i] > A[i + 1]. For example if A = [0, 8, 9, 2, 1, 3, 0], the peak elements are A[3] = 9 and A[6] = 3. Describe an O(log n) divide-and-conquer algorithm for returning the position of a peak element in A (no need to find all peak elements). Give the pseudo-code, describe and justify the recurrence for the running time T(n), and solve your recurrence. (b) (10 points) You are given an array A[1..n], where all elements are distinct positive numbers (not necessarily integers). Describe an O(n log n) algorithm that rearranges the elements of A, so that (i) every element at an even position is a peak element, and (ii) the peak elements are in increasing order. For example, if A = [7, 1, 3, 4, 5, 6, 2], valid outputs include: [1,3,2,5,4,7,6] or [1,5,2,6,3,7,4] (the peak elements are in bold). Recall from the previous part that A[i] is a peak element, if A[i] > A[i − 1] and A[i] > A[i + 1]. Show that the running time of your algorithm is O(n log n). Hint: You can use any sorting algorithm as a black box.