Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
COMP-4540/8540 Design and Analysis of Algorithms Assignment 2
- Any algorithm you present in this course (for assignment or test) without correctness proof or time complexity analysis will receive a 0 mark.
- The time complexity of your algorithm must not be higher than that stated in the question.
- You are advised to do the following before presenting your algorithm. Give a clear description of the key idea underlying your algorithm. You may give some examples to illustrate the key idea. However, they are not equivalent to the correctness proof.
- Never submit a program to support the correctness of your algorithm. They will be ignored as they cannot prove the correctness of your algorithm. Hence, your effort will be wasted.
1. Given an m × n array. First, sort the elements in each row into ascending order. Then, sort the elements in each column into ascending order. Prove that the elements in each row remain sorted.
2. Let D be an m × n array of real numbers such that:
D[i, j] + D[k, ℓ] ≤ D[i, ℓ] + D[k, j], 1 ≤ i < k ≤ m, 1 ≤ j < ℓ ≤ n.
(a) Let lm(i) be the index of the column containing the leftmost smallest number in row i, 1 ≤ i ≤ m.Prove that lm(i) ≤ lm(i + 1), 1 ≤ i < m.(b) Present a divide-and-conquer algorithm that finds lm(i), 1 ≤ i ≤ m, in O(m + n lg m) time.
On reading in the first element a1, it outputs a1;
On reading in the second element a2, it outputs the median of the list a1, a2;
On reading in the ith element ai , it outputs the median of the list a1, a2, . . . , ai , and so on.
(a) Show that using this algorithm, you can sort a list of n elements by giving an O(n)-time reduction from sorting to this problem of finding medians interactively.
(b) Deduce an Ω(n lg n) lower bound for the problem of finding medians interactively.
Note: Some hints are given on the following page. You are not required to solve the problems using the hints. Therefore, do not look at the hints unless you feel that you have to.
3.
(a) Duplicate the min and max elements of the given list a certain number of times each. Append the duplicated min elements to one end of the input list and append the duplicated max elements to the other end. Submit the resulting list to Algorithm Interactive-Median as input. The sorted given input list will appear in the output as a subsequence.