首页 >
> 详细

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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Cpslp程序语言代写、代做python编程设计、Program程序实验代写 2020-11-25
- Csci 1110作业代做、Data留学生编程代写、Java程序语言调试代做 2020-11-25
- 代写program程序、代做r课程编程、R程序实验代做代做留学生prolog 2020-11-25
- Be491留学生编程代做、代写java，Python/C++程序设计调试ma 2020-11-25
- 代写cmpt 214编程、代做programming语言、代写c/C++程序 2020-11-08
- 代写csci 2122课程、代做program编程实验、C++程序语言代写代 2020-11-08
- Fit5032语言编程代做、代写web程序实验、Web、Html程序语言代做 2020-11-08
- Com3503程序编程代做、Java，C++，Python留学生编程代写代写 2020-11-08
- 代写program程序课程、代写c++编程实验、C/C++编程语言代做 代做 2020-11-08
- Data留学生编程代做、代写python程序、Java，C++程序语言代写 2020-11-08
- 代写secj 1023实验编程、Programming程序代做、代写c++语 2020-11-08
- 代写cmpsc 465编程、代做java程序语言、Python，C++编程设 2020-11-07
- 代做mf 703语言编程、代写programming程序、Sql编程语言调试 2020-11-07
- 954246编程设计调试、代做programming程序、C++编程语言代写 2020-11-07
- Pstat 115程序实验代写、R编程语言调试、Data留学生程序代做 代写 2020-11-07
- Com1005课程编程代做、代写python程序、Java，C++程序语言调 2020-11-07
- Tcp留学生程序代写、Java程序设计调试、Java编程语言代写 帮做r语言 2020-11-07
- 代写program语言编程、代做data留学生程序、Python，Java编 2020-11-07
- 代做cosc2666编程、代写programming程序、C/C++程序语言 2020-11-07
- Digital编程设计代写、代做r程序实验、代写r留学生程序 调试matla 2020-11-07