COMP 3711 – Design and Analysis of Algorithms 2022 Spring Semester – Written Assignment 2 Distributed: March 4, 2022
Due: March 18, 2022
Your solutions should contain (i) your name, (ii) your student ID #, and (iii) your email address
Some Notes:
Copyright By PowCoder代写 加微信 powcoder
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 follow the guidelines on doing your own work and avoiding plagia- rism as described in the class policies. You must acknowledge indi- viduals who assisted you, or sources where you found solutions. Failure to do so will be considered plagiarism.
The term Documented Pseudocode means that you must include clear comments inside your pseudocode.
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.
Submit a SOFTCOPY of your assignment to Canvas by the deadline. The softcopy should be one PDF file (no word or jpegs permitted, nor multiple files). 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 possible denser.
Problem 1 [20 pts] Greedy algorithms
You are given a set I of n time intervals. A time instant ti hits a time interval Ij = [sj,ej] if sj ≤ ti ≤ ej. Your task is to design a greedy algorithm that finds a smallest set of time instants that hits all the time intervals.
For example, suppose that I = {[2, 4], [1, 4], [4, 5], [3, 5]}. Then the set {3, 5} of time instants hits all these time intervals as each time interval is hit by either instant 3 or 5. the optimal solution is the time instant 4, which hits all intervals.
Give a greedy algorithm that finds the smallest set of time instants. Provide both documented pseudocode and an explanation in words as to what it does. Justify the correctness of your algorithm.
Problem 2 [20 pts] Radix Sorting
You are given a set of 10 decimal integers in the range of 1 to 65535:
A = [32121, 28932, 34789, 54233, 52608, 18987, 47689, 35700, 23781, 61231].
(a) Please conduct Radix sort on A using Base 10. Illustrate your result after each step.
(b) NowconvertthesedecimalintegerstohexadecimalandconductRadix sort again, this time using Base 16. Illustrate your result after each step.
Problem 3 [30 pts] (Selection Procedure)
Recall the selection problem that we learned in class. Given an unsorted array A = [x1 , x2 , …, xn ], we need to return the ith smallest element in A. We have already learned a randomized algorithm for the selection problem with expected running time O(n).
The Problem:
(a) Consider a new pivot choosing strategy. First, we generate a uniform random permutation of A. Let [y1,…,yn] denote the permutation. The probability that xi is yj for an arbitrary 1 ≤ j ≤ n is exactly
Next, we choose yi as the pivot with a probability of
Pr[yi is chosen as a pivot] = i . 1+···+n
After replacing the original pivot selection strategy with the new one, we have a new randomized algorithm for the selection problem. Assume that we can produce a uniform random permutation of A in O(n) time and a pivot can be chosen in O(1) following the random
distribution. Please analyse the expected running time of the new algorithm.
Hints: You can follow the analysis in class and compute the proba- bility that a good pivot is chosen.
(b) Now suppose that you are given two unsorted arrays A and B, con- taining m and n elements respectively. You are also given a black box O(n) selection algorithm SEL that can be called on A and B separately and, in addition, a small number (say, ten) of extra mem- ory words that can be used to store some extra data. Using SEL as a subroutine, design an O(n + m) algorithm for finding the kth smallest element in the combined set of O(m + n) elements.
You may not merge the two arrays in another array and call an algo- rithm (either SEL or something you wrote) on this third array. This is because there is no extra memory available to build this third array.
Problem 4 [30 pts] (Using Selection)
Note: Recall the Selection problem of calculating Select(A,p,r,i) that we learned in class. We actually learned a randomized linear, i.e., O(r−p+1), time algorithm for solving Selection. We also stated that a deterministic linear time algorithm for solving this problem exists. For the sake of this problem, you may assume that you have been given this deterministic lin- ear time algorithm and can use it as a subroutine. (calling it exactly as Select(A, p, r, i)). You may not use any other algorithm as a subroutine without explicitly providing the code and proving correctness from scratch.
The Manhattan Distance between two 2-dimensional points p = (x, y) and p′ =(x′,y′)is
d1(p, p′) = |x − x′| + |y − y′|
In what follows you are given real numbers x1, …, xn and y1, …, yn. They
are NOT necessarily sorted.
Define the n two-dimensional points pi = (xi,yi). The Manhattan Ware- house problem is to find a point p = (x,y) that minimizes the average distance to all the pi. That is, to find p such that
∀p′ =(x′,y′)∈R2,d1(p,pi)≤d1(p′,pi).
(Dividing both sides of the equation by n gives the average.)
Design a O(n) worst case time algorithm for solving the Manhattan Ware- house problem. We split this into two parts.
(A) Solve the one-dimensional problem.
Given (unsorted) x1, …xn, define the function
f (x) = |x − xi |.
Call x ̄ a center if it minimizes f(x), i.e.,
∀x ∈ R, f(x ̄) ≤ f(x).
(a) Prove that there exist z1 , z2 such that z1 ≤ z2 and (i) f(x) is monotonically decreasing for x ∈ [−∞,z1]. (ii) f(z1) = f(x) = f(z2) for all x ∈ [z1,z2].
(iii) f(x) is monotonically increasing for x ∈ [z2 , ∞]. Note that it is possible that z1 = z2.
(b) Give an O(n) time algorithm for finding a center of n one- dimensional points x1, …, xn.
First give documented pseudocode for your algorithm.
In addition, below your algorithm, explain in words/symbols what your algorithm is doing and justify the correctness.
(c) Explain why your algorithm runs in O(n) time.
(B) Solve the Manhattan Warehouse Problem.
(a) Give an O(n) time algorithm for solving the Manhattan Ware- house Problem given n points p1, p2, …, pn where pi = (xi, yi). First give documented pseudocode for your algorithm.
In addition, below your algorithm, explain in words/symbols what your algorithm is doing and justify the correctness.
(b) Explain why your algorithm runs in O(n) time.
– For simplicity, you may assume that none of the xi or yi repeat, i.e., there is no pair i,j such that xi =xj or yi =yj.
– Part A(a) is only meant as a hint to get you started. Note that if you know z1, z2, then (you must prove this) any x ∈ [z1, z2] will be a solution to the one-dimensional center problem.
A more detailed understanding of the behavior of f(x), that lets you find z1,z2, therefore permits solving the remainder of A. You may, if you like, fully analyze the behavior of f(x) in A(a), write this as a mathematical lemma and then quote that lemma in A(c).
– We strongly recommend that before trying to solve part A you choose 5 or 6 points xi and then graph the resultant function f(x). Seeing the diagram should help you solve the problem.
– The algorithm for part (B) can use the result of part (A) as a sub- routine.
– The main work in solving this problem is in understanding how to solve it using selection. Once you understand that, the actual pseu- docode might be quite short.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com