COMP-4540/8540
Design and Analysis of Algorithms
Winter 2021 Assignment 2
Due Date: March 9 (before 11:59p.m.)
Copyright By PowCoder代写 加微信 powcoder
The following rules apply to all assignments handed out in this course. • For every algorithm you present, you must include:
1. a clear English description of the key idea underlying the algorithm
2. the algorithm in a pseudo-code, possibly with examples to show how it works, 3. a correctness proof of the algorithm,
4. an analysis of the time complexity of the algorithm.
• Your solution must be hand-written. Please make sure that your hand-writing is legible. The marks you will receive depends not only on the correctness and efficiency of the algorithm, but also the presentation.
——————————————————————————————————————————————-
1. Given a list of n elements, a1, a2, . . . , an, drawn from a totally ordered set. Present an O(n lg n)-time
algorithm that counts the number of ordered pairs, (ai,aj), in the list such that i < j and ai > 2aj. [Hint: Use a divide-and-conquer approach.]
2. You are given an algorithm, called Interactive-Median, that determines the medians of a list of elements (drawn from a totally ordered set) interactively in the following sense:
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. You may assume that Algorithm Interactive-Median takes O(1) time to determine each of the medians.
(b) Deduce an Ω(n lg n) lower bound for the problem of finding medians interactively.
3. Given an n × n array of distinct real numbers A. The neighbours of an entry A[i, j], 1 ≤ i, j ≤ n, are the entries A[i − 1,j],A[i + 1,j],A[i,j − 1],A[i,j + 1] (note that when i = 1 or j = 1, some of the neighbours do not exist). An entry is a local min if its number is less than those of its neighbours.
(a) Let B be the set of all entries on the border of A (i.e. on row 1, row n, column 1, or column n). Suppose A satisfies this condition: it contains an entry which is not in B but has a neighbour in B and its number is less than all the numbers in B.
Present an O(n)-time algorithm to determine a local min in A.
(b) Extend the result in Part (a) so that the resulting algorithm can determine a local min in arrays that do not satisfy the condition in O(n) time.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com