首页 新闻 聚焦 科技 财经 创业 综合 图片 视频

IT界

旗下栏目: 行业 生态 IT界 创新

代写Algorithms 3027程序、代做Computer Science程序

来源:珠穆朗玛网 发布时间:2020-03-25

代写Algorithms 3027作业、代做Computer Science作业、Python,Java,c++编程设计作业代写
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

如有需要,请加QQ:99515681 或邮箱:99515681@qq.com 微信:codehelp

责任编辑:珠穆朗玛网

最火资讯