首页 > > 详细

COMP3027辅导、讲解Algorithms、Java,Python,C++程序语言辅导解析Haskell程序|解析Haskell程序

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.

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!