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:
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.