” 辅导comp2123语言、 写作Python，Java程序comp2123 Assignment 5 s1 2021This assignment is due on May 27 and should be submitted on Gradescope. Allsubmitted work must be done individually without consulting someone elses solutionsin accordance with the Universitys Academic Dishonesty and Plagiarismpolicies.As a first step go to the last page and read the section: Advice on how to do theassignment.Problem 1. (10 points)We are given a rooted tree T = (V, E) and its root u, i.e., a simple connected undirectedacyclic graph and a vertex u of this Tree that we consider to be its root. Wewant to compute the smallest set of vertices S V such that every edge in E isincident to some vertex in S.Example:uvw xVertex u is the root of the above tree. If we choose S = {v}, we indeed have theproperty that every edge is incident to a vertex in S. Furthermore, theres no smallerset with this property. Picking S = {u, w, x} would also yield a set where every edgeis incident to a vertex in S, but it isnt the smallest set. Picking S = {u, w} wouldmean that edge (v, x) isnt 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 Sif its incident to some edge that isnt incident to any vertex in S.BFSAlgorithm runs a breadth first search from the root u. Then it compares thesize of the union of all vertices in even layers to the size of the union of all verticesin 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 viin T do5: if viis incident to some edge e6: and e isnt incident to any vertex in S then7: S S {vi}8: return S1comp2123 Assignment 5 s1 20211: function BFSAlgorithm(T, u)2: layers, parent BFS(T, u)3: even the union of all vertices in layers[i], where i is even4: odd the union of all vertices in layers[i], where i is odd5: if |even| |odd| then6: return even7: else8: return oddArgue whether degreeAlgorithm always returns the correct answer by eitherarguing its correctness (if you think its correct) or by providing a counterexample(if you think its incorrect).a)Argue whether BFSAlgorithm always returns the correct answer by eitherarguing its correctness (if you think its correct) or by providing a counterexample(if you think its incorrect).b)Problem 2. (25 points)Our publishing company has accepted contracts to publish a set of n books B. Foreach book bi(0 i n) we know the number of copies cithat we agreed toprint, the time pithat printing a single copy of this book takes, and the deadlinedi by which all copies of the book should be printed. All ci, pi, and di are positiveintegers. 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 bytime x.As were a small printing company, we only have a single printing press, so wecan only work on printing one book at a time. Were allowed to change which bookwere printing after we completed a full copy (i.e., we cant switch halfway intoprinting a book). Were worried that we agreed to publish too much and youvebeen hired to develop an algorithm to decide if this is indeed the case (and wemight need to start apologising to our clients). In other words, you need to designan algorithm that returns true if there is an order to print the copies of the bookssuch that all deadlines are met, and false otherwise.Example:ci pi dib1 3 1 5b2 1 9 18b3 2 2 7In this case we can indeed Print all copies of all books, for example by firstprinting 1 copy of b1, then 1 copy of b3, 2 more copies of b1, 1 more copy of b3, andfinally 1 copy of b2. When printing starts at time 0, the above schedule implies thatb1 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 should2comp2123 Assignment 5 s1 2021return true. If we were required to print more than 1 copy of b2, there would nolonger exist a way to print all books by their respective deadlines and thus ouralgorithm 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 integersoccur in increasing sorted order, the next 2n/3 integers occur in decreasing sortedorder, and the final n/3 k + 2 integers occur in increasing sorted order. Note thatthe last integer of the increasing sequence is also the first integer of the decreasingsequence (hence, k 1), and that the last integer of the decreasing sequence is alsothe first integer of the second increasing sequence. You are asked to determine theminimum and maximum integer Stored in this array. For simplicity you can assumethat 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], andthe second increasing sequence is [3, 0]. The minimum integer in the array is 3and the maximum is 5.Your task is to give a divide and conquer algorithm for this problem that runsin 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.3comp2123 Assignment 5 s1 2021Advice 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 todevelop and elaborate on details. If we dont see/understand your generalidea, we cannot give you points for it. Be careful with giving multiple or alternative answers. If you give multipleanswers, then we will give you marks only for your worst answer, as thisindicates how well you understood the question. Some of the questions are very easy (with the help of the lecture notes orbook). You can use the Material presented in the lecture or book without provingit. 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 begiven as (pseudo-)code. If you do give (pseudo-)code, then you still have to explain your code andyour ideas in plain English. Unless otherwise stated, we always ask about worst-case analysis, worst caserunning times etc. As done in the lecture, and as it is typical for an algorithms course, we areinterested in the most efficient algorithms and data structures. If you use further resources (books, scientific papers, the internet,…) to formulateyour answers, then add references to your sources. If you refer to a result in a Scientific paper or on the web you need to explainthe results to show that you understand the results, and how it was proven.请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
