联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> C/C++编程C/C++编程

日期:2020-03-24 11:11

Algorithms 3027/3927 Assignment 2 The University of Sydney

2020 Semester 1 School of Computer Science

This assignment is for COMP3027 students only.

Task: Design a divide-and-conquer algorithm [100 marks]

You are given a list of n non-intersecting rectangles R1, . . . , Rn of height 1. Each rectangle Ri

is specified

by a left coordinate `i

, a right coordinate ri and an altitude yi

. The coordinates and altitudes will always

be non-negative integers.

A rectangle Ri

is said to be “obstructed” if it cannot be seen from below: if for every `i ≤ x ≤ ri

, there

exists a rectangle Rj with yj < yi and `j ≤ x ≤ rj . The goal is to compute the number of obstructed

rectangles.

Figure 1: Four rectangles given by the data [ { `:0, r:1, y:1 }, { `:1, r:2, y:2 }, { `:2, r:3, y:3 }, { `:0, r:3,

y:5 }]. Only the top rectangle is obstructed.

Your task is to design a divide-and-conquer algorithm to compute the number of obstructed rectangles.

(a) Description of how your algorithm works (“in plain English”).

(b) Prove that your algorithm correctly computes the number of obstructed rectangles.

(c) Prove an upper bound on the time complexity of your algorithm.

Submission details

? Submission deadline is Wednesday 25th March, at 23:59. Late submissions without special

consideration will be subject to the penalties specified in the first lecture (20% per day). Submissions

later than Friday 27th March, 23:59 will not be accepted.

? Submit your answers as a single document to Gradescope. Your work must be typed (no images

of text, although you can use diagrams if you think it helps.) Please try to be reasonably concise

(one to two pages of a4).

? Your report will be subject to automatic and manual plagiarism detection systems. Remember, it’s

acceptable to discuss high level ideas with your peers, but you should not share the detail of your

work, such as parts as the precise algorithms, examples, proofs, writing, or code.

? To facilitate anonymous grading, please do not write your name on your submission.

1


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp