# 代写Algorithms 3027作业、代做Computer Science作业、Python，Java，c++编程设计作业代写帮做Java程序|代做Java

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

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