联系方式

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

您当前位置:首页 >> Java编程Java编程

日期:2021-05-18 11:07

comp2123 Assignment 5 s1 2021

This assignment is due on May 27 and should be submitted on Gradescope. All

submitted work must be done individually without consulting someone else’s solutions

in accordance with the University’s “Academic Dishonesty and Plagiarism”

policies.

As a first step go to the last page and read the section: Advice on how to do the

assignment.

Problem 1. (10 points)

We are given a rooted tree T = (V, E) and its root u, i.e., a simple connected undirected

acyclic graph and a vertex u of this tree that we consider to be its root. We

want to compute the smallest set of vertices S ? V such that every edge in E is

incident to some vertex in S.

Example:

u

v

w x

Vertex u is the root of the above tree. If we choose S = {v}, we indeed have the

property that every edge is incident to a vertex in S. Furthermore, there’s no smaller

set with this property. Picking S = {u, w, x} would also yield a set where every edge

is incident to a vertex in S, but it isn’t the smallest set. Picking S = {u, w} would

mean that edge (v, x) isn’t incident to any vertex in S.

We are given two algorithms for this problem:

degreeAlgorithm sorts the vertices of T by their degree and adds a vertex to S

if it’s incident to some edge that isn’t incident to any vertex in S.

BFSAlgorithm runs a breadth first search from the root u. Then it compares the

size of the union of all vertices in even layers to the size of the union of all vertices

in odd layers and returns the smaller of the two sets.

1: function degreeAlgorithm(M)

2: S ← ?

3: Sort vertices in T by their degree and rename such that deg(v1) ≥ deg(v2)

≥ ... ≥ deg(vn)

4: for each vi

in T do

5: if vi

is incident to some edge e

6: and e isn’t incident to any vertex in S then

7: S ← S ∪ {vi}

8: return S

1

comp2123 Assignment 5 s1 2021

1: function BFSAlgorithm(T, u)

2: layers, parent ← BFS(T, u)

3: even ← the union of all vertices in layers[i], where i is even

4: odd ← the union of all vertices in layers[i], where i is odd

5: if |even| < |odd| then

6: return even

7: else

8: return odd

Argue whether degreeAlgorithm always returns the correct answer by either

arguing its correctness (if you think it’s correct) or by providing a counterexample

(if you think it’s incorrect).

a)

Argue whether BFSAlgorithm always returns the correct answer by either

arguing its correctness (if you think it’s correct) or by providing a counterexample

(if you think it’s incorrect).

b)

Problem 2. (25 points)

Our publishing company has accepted contracts to publish a set of n books B. For

each book bi

(0 ≤ i < n) we know the number of copies ci

that we agreed to

print, the time pi

that printing a single copy of this book takes, and the deadline

di by which all copies of the book should be printed. All ci

, pi

, and di are positive

integers. We can start printing at time 0 and all deadlines are given relative to this,

i.e., if di = x this means that printing all copies of book bi should be completed by

time x.

As we’re a small printing company, we only have a single printing press, so we

can only work on printing one book at a time. We’re allowed to change which book

we’re printing after we completed a full copy (i.e., we can’t switch halfway into

printing a book). We’re worried that we agreed to publish too much and you’ve

been hired to develop an algorithm to decide if this is indeed the case (and we

might need to start apologising to our clients). In other words, you need to design

an algorithm that returns true if there is an order to print the copies of the books

such that all deadlines are met, and false otherwise.

Example:

ci pi di

b1 3 1 5

b2 1 9 18

b3 2 2 7

In this case we can indeed print all copies of all books, for example by first

printing 1 copy of b1, then 1 copy of b3, 2 more copies of b1, 1 more copy of b3, and

finally 1 copy of b2. When printing starts at time 0, the above schedule implies that

b1 finishes printing at time 5, b2 is done at time 16, and b3 is completed at time 7.

In other words all books are printed by their deadline and so our algorithm should

2

comp2123 Assignment 5 s1 2021

return true. If we were required to print more than 1 copy of b2, there would no

longer exist a way to print all books by their respective deadlines and thus our

algorithm should return false.

Your task is to give a greedy algorithm for this problem that runs in O(n log n)

time. Remember to:

a) Describe your algorithm in plain English.

b) Prove the correctness of your algorithm.

c) Analyze the time complexity of your algorithm.

Problem 3. (25 points)

We are given an array A of length n with the following property: the first k integers

occur in increasing sorted order, the next 2n/3 integers occur in decreasing sorted

order, and the final n/3 ? k + 2 integers occur in increasing sorted order. Note that

the last integer of the increasing sequence is also the first integer of the decreasing

sequence (hence, k ≥ 1), and that the last integer of the decreasing sequence is also

the first integer of the second increasing sequence. You are asked to determine the

minimum and maximum integer stored in this array. For simplicity you can assume

that n is a multiple of 3 and all integers are distinct.

Example:

A = [4, 5, 2, ?2, ?3, 0]

The first increasing sequence is [4, 5], the decreasing sequence is [5, 2, ?2, ?3], and

the second increasing sequence is [?3, 0]. The minimum integer in the array is ?3

and the maximum is 5.

Your task is to give a divide and conquer algorithm for this problem that runs

in O(log n) time. Remember to:

a) Describe your algorithm in plain English.

b) Prove the correctness of your algorithm.

c) Analyze the time complexity of your algorithm.

3

comp2123 Assignment 5 s1 2021

Advice on how to do the assignment

? Assignments should be typed and submitted as pdf (no handwriting).

? Start by typing your student ID at the top of the first page of your submission.

Do not type your name.

? Submit only your answers to the questions. Do not copy the questions.

? When designing an algorithm or data structure, it might help you (and us)

if you briefly describe your general idea, and after that you might want to

develop and elaborate on details. If we don’t see/understand your general

idea, we cannot give you points for it.

? Be careful with giving multiple or alternative answers. If you give multiple

answers, then we will give you marks only for "your worst answer", as this

indicates how well you understood the question.

? Some of the questions are very easy (with the help of the lecture notes or

book). You can use the material presented in the lecture or book without proving

it. You do not need to write more than necessary (see comment above).

? When giving answers to questions, always prove/explain/motivate your answers.

? When giving an algorithm as an answer, the algorithm does not have to be

given as (pseudo-)code.

? If you do give (pseudo-)code, then you still have to explain your code and

your ideas in plain English.

? Unless otherwise stated, we always ask about worst-case analysis, worst case

running times etc.

? As done in the lecture, and as it is typical for an algorithms course, we are

interested in the most efficient algorithms and data structures.

? If you use further resources (books, scientific papers, the internet,...) to formulate

your answers, then add references to your sources.

? If you refer to a result in a scientific paper or on the web you need to explain

the results to show that you understand the results, and how it was proven.

4


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

python代写
微信客服:codinghelp