CSCI 3110 — Design and Analysis of Algorithms I

Fall 2020

Assignment 4

Distributed Thursday, October 8 2020.

Due 5:00PM, Thursday, October 15 2020.

Instructions:

1. Before starting to work on the assignment, make sure that you have read and understood

policies regarding the assignments of this course, especially the policy regarding

collaboration.

2. Submit a PDF file with your assignment solutions via Brightspace. If you have not

used Brightspace for assignment submission before, you may find the the following

documentation for Brightspace useful: https://documentation.brightspace.com/

EN/le/assignments/learner/submit_assignments.htm

3. If you submit a joint assignment, only one person in the study group should make the

submission. At the beginning of the assignment, clearly write down the names and

student IDs of the up to three group members.

4. We encourage you to typeset your solutions using LaTeX. However, you are free to

use other software or submit scanned handwritten assignments as long as they are

legible. We have the right to take marks off for illegible answers.

5. You may submit as many times as needed before the end of the grace period. A

good strategy is to create an initial submission days in advance after you solve some

problems, and make updates later.

1. [12 marks] For each of the following recurrences, use the “master theorem” and give

the solution using big-Θ notation. Explain your reasoning. If the “master theorem”

does not apply to a recurrence, show your reasoning, but you need not give a solution.

(a) T(n) = 3T(n/2) + n lg n;

(b) T(n) = 9T(n/3) + Θ(n

2/ lg n);

(c) T(n) = T(?n/4?) + T(?n/4?) + √

n;

(d) T(n) = 4T(?n/7?) + 1

4

n.

2. [10 marks] Recall the algorithm that prints all the permutations of {1, 2, . . . , n}, studied

in Lecture 8:

http://web.cs.dal.ca/~mhe/csci3110/handouts/lecture8.htm.

As shown in class, its running time satisfies

T(m, n) = (

n(T(m + 1, n ? 1) + m + 1 + n) if n > 1;

m + 1 if n = 1.

(1)

Recall that I gave the solution to this equation as

T(m, n) = (m + 1 + n)a(n) ? n! (2)

in which the number series a(n) is defined by

a(n) = (

n(a(n ? 1) + 1) if n ≥ 1;

0 if n = 0.

(3)

You tasks is to prove that equation 2 holds.

Hint: Even though T(m, n) has two parameters, you can still prove it by induction on

n. Use n = 1 for the base case.

3. [8 marks] A point (x1, y1) is said to dominate another point (x2, y2) in the plane if both

x1 ≥ x2 and y1 ≥ y2 hold. For example, (5, 2) dominates (3, 1) and (5, 1), but neither

of the two points (3, 2) or (2, 5) dominates the other. A point p is a skyline point of a

point set S if there does not exist another point in S that dominates p.

The problem of computing the skyline of a given point set, is to report, from left to

right, all the skyline points in a given point set.

Prove that the worst-case running time of any algorithm for the above problem is

?(n lg n) under the comparison-based model. In this model you are allowed to do

comparisons and arithmetic operations involving the inputs, and the running time is

measured by the number of comparisons performed.

To prove this, you can use the known fact that the worst-case running time of any

algorithm for sorting an array of n distinct integers is ?(n lg n) under the same model.

You can also assume that the coordinates are integers.

You can make the following assumptions about the input and the output of any algorithm

that solves the problem of computing skylines:

2

Input: An array S[1..n] of pairs of integers (x, y) representing the x- and y-coordinates

of a set of points in the plane. You can assume that there are no duplicate points in

S.

Output: An array M of pairs of integers such that its elements M[1], M[2], . . . give the

coordinates of all the skyline points in S, listed from left to right.

Note: You are NOT asked to give an algorithmic solution to the above problem.

Instead, you are asked to prove a lower bound on the worst-case running time of any

algorithm that solves this problem.

3

版权所有：编程辅导网 2018 All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。