辅导CSCI 3110程序、写作Python课程设计程序

” 辅导CSCI 3110程序、写作Python课程设计程序CSCI 3110 Final Exam posted: 7 am ADT 31.07.2020There are 6 questions on this exam, each worth 6 marks, with 1 bonus mark. They can allbe answered in under half a page each; there is no coding. Your overall mark out 30 of willbe the sum of the marks for your best 5 answers; the bonus cannot raise your mark above30. You can check the textbook, the scribe notes (some of which were uploaded or updatedyesterday!), the Brightspace page and the rest of the internet but you must work on yourown and all work you submit must be your own! You can an use an automatictranslator if you want, for example, but it is cheating to post or discuss the exam withclassmates or anyone else except Travis before midnight. Signs of collusion or plagiarismwill be reported to FCS as evidence of a possible Academic Integrity Offence. You can emailTravis for clarifications but he will not give hints. Please do not contact the TAs duringthe exam. Submit your answers as a single PDF to the final exam assignment folder onBrightspace. Good luck!11. Describe a polynomial-time divide-and-conquer algorithm that, given a tree T with aweight assigned to each vertex, returns a vertex cover with minimum total weight. Forexample, in the tree shown below, the vertex cover with the minimum total weight isd, f, g, h, i, k even though the smallest vertex cover is e, g, i. You need not proveyour algorithm correct.(Hint: Because (e, f) is an edge in the example, any vertex cover includes either eor f or both. Removing (e, f) splits the tree into two pieces, Te including e and Tfincluding f. If you can work out the weight w1 = 6 of the lightest vertex cover ofTe, and the weight w2 = 10 of the lightest vertex cover of Te that includes e, and theweight w3 = 7 of the lightest vertex cover of Tf , and the weight w4 = 10 of the lightestvertex cover of Tf that includes f, then the weight of the lightest vertex cover of T ismin(w1 + w4, w2 + w3) = 16. How do you work out w1 and w3? More interestingly,how do you work out w2 and w4?) 辅导CSCI 3110作业、写作Python课程设计作业2. Recall that for the NP-complete problem Knapsack we are given a sequence S =(w1, p1), . . . ,(wn, pn) of weight-profit pairs, a target T and a capacity C, and asked ifthere exists a subsequence S.For the problem Pockets we are again given a sequence S = (w1, p1), . . . ,(wn, pn) ofweight-profit pairs and a target T but now, instead of a single capacity C, we are givena Sequence C = c1, . . . , cm of capacities. Assume w1 wn and c1 cm. Weare asked if there exists a subsequence S.In other words, we have n items and m pockets, each pocket has a capacity, and wewant to put at most one item in each pocket so as to obtain total profit at least Twithout overfilling any pocket.Describe a polynomial-time greedy algorithm for Pockets. For example, ifS = (7, 8),(5, 5),(5, 6),(5, 2),(4, 1),(4, 4)T = 13C = 6, 5, 5Tthen your algorithm should return yes, since with S0 = (5, 5),(5, 6),(4, 4) we obtainprofit 5 + 6 + 4 = 15 without overfilling any pocket (since 5 6, 5 5 and 4 5).You need not prove your algorithm correct (although looking for a proof is a good wayto catch mistakes anyway).(Hint: Assuming the pockets are sorted in decreasing order by capacity made it easierto state the problem, but its not the best order for solving it. What should you putin the smallest pocket?)33. A semi-wildcard in a string is special character representing a non-empty subset ofThe normal alphabet, and a string containing a mix of normal characters and semiwildcardsrepresents the set of all normal strings that can be obtained by replacingeach semi-wildcard by a character from the subset it represents. For example, if thenormal alphabet is {A, B, C, D} and S = BA?C!AD with ? representing {B, D} and !representing {A, D}, then S represents the set {BABCAAD, BABCDAD, BADCAAD, BADCDAD}.Describe a polynomial-time dynamic-programming algorithm that, given a string S[1..n]containing a mix of normal characters and semi-wildcards and a normal string T[1..m],computesmin{ED(S, T) : S S}where ED(S, T) denotes the edit distance between S and T. For example, given S =BAC!AD as described above and T = BADCAD, your algorithm should return 1, since theedit distance from either BADCAAD or BADCDAD and BADCAD is 1. Notice that in generalthe set of strings represented by S can contain exponentially many strings, so tryingthem one by one is not feasible! You need not prove your algorithm correct.(Hint: This questions isnt as hard as it sounds at first. Start with the grid withdiagonal arrows idea we saw in class and add some more arrows in some rows.)4. For the problem Fair 3-Colourability we are given a graph G on n vertices andasked if it is possible to colour exactly n/3 vertices red, exactly n/3 vertices green andexactly n/3 vertices yellow such that no vertex shares an edge with a vertex of thesame colour. Show that Fair 3-Colorability is NP-complete by both showing it isin NP And reducing a known NP-complete problem to it.(Hint: Dont reduce from 3-Sat again; its easier than that.)5. Describe a polynomial-time algorithm that, given a directed acyclic graph G with apositive weight assigned to each edge, finds the minimum distance from s to each othervertex when the length of a path is defined to be the product of the weights along thatpath, instead of their sum. Can you find a faster algorithm if all the edge weights areat least 1? For example, the distances from s to the other vertices are shown in thegraph below. You need not prove your algorithm(s) correct.(Hint: You can solve this either by modifying algorithms you already know or byreducing to the problems they solve.)46. Suppose that due to various catastrophes, next semester your professor ends up teachingboth 3110 and 3136 with exactly the same n students in each one; the 2-hour finalexams are scheduled back to back; both exams are in the same room with exactly nimmovable, arbitrarily placed desks; and that room is available only for those 4 hours.The pandemic is over, so at least your professor doesnt have to worry about socialdistancing, But he still doesnt want students writing the same exam to be sittingwithin two meters of each other. Some of the desks are too close together, so he canthave all the students write the same exam at the same time, but he decides to havesome students start with the 3110 exam and others start with the 3136 exam, andthen switch halfway through. However, even this wont work if, for example, theresa triangle Of three desks with each one within 2 meters of the other two. Describea polynomial-time algorithm that lets your professor check if his idea works with therooms seating arrangement.Bonus (1 mark): What if in the winter semester your poor professor is in the samesituation but with three exams in six hours? What about four exams in eight hours(perish the thought)?(Hint: You Should be able to find the algorithm for two exams by yourself, but forthree or more, Google unit disk graph, where is the standard name for thisproblem.)5如有需要，请加QQ：99515681 或邮箱：99515681@qq.com

“