讲解：COMP523、Algorithmic Techniques、Python，Java、c/c++Python

COMP523 - 2019 - Second CA AssignmentAdvanced Algorithmic TechniquesAssessment InformationAssignment Number 2 (of 2)Weighting 12.5%Assignment Circulated 15 Nov 2019Deadline 1 Dec 2019, 16:00Submission Mode Please submit your solutions electronically (PDF or DOC format) at theelectronic submission system of the Computer Science Departmentwhich you can find at the following url.Learning outcome assessed 3. Identify which of the studied design principles are used in a given algorithmtaking account of the similarities and differences between the principles.4. Apply the studied design principles to produce efficient algorithmic solutionsto a given problem taking account of the strengths and weaknessesof the applicable principles.Purpose of assessment Design and analysis of algorithms for a given problem.The aims are: to identify the complexity of a problem and designgood algorithms based on the different design principles covered in class.Marking criteria Based on the marking descriptors of the University’s Code of Practice on AssessmentSubmission necessary in order Noto satisfy Module requirements?Late Submission Penalty Standard UoL Policy.Plagiarism and Collusion Please be aware of the University guidelines on plagiarism and collusion.Task specificationProvide an answer to the following problem. You may consider any of the material that was presented in the lecturesas known.Problem 1Necessary definitionsConsider the following measure of comparison between two algorithms A and B, based on their running time andapproximation ratio:• Better running time: Algorithm A has a better running time than algorithm B if A is polynomial time and Bis pseudo-polynomial time or exponential time, or if A is pseudo-polynomial time and B is exponential time.• Better performance: Algorithm A has a better performance than algorithm B if A has a smaller approximationratio than B.Remark: The comparisons above are based on the best possible analysis for the algorithms. For instance, a polynomialtime algorithm is better than a pseudopolynomial time algorithm, only if the latter can not be proven to runin polynomial time. As a concrete example (from the lectures), you can either solve the max flow problem usingthe Edmonds-Karp algorithm, or using a polynomial-time algorithm for linear programming. If you use the FordCOMP523代做、代写Algorithmic TechniFulkersonanalysis for Edmonds-Karp (which will give you a pseudopolynomial running time), it would be incorrectto claim that the LP-based algorithm is better than Edmonds-Karp, because the latter actually runs in polynomial timewith a better analysis (and they both solve the problem exactly). Similarly, if you prove an approximation ratio α for apolynomial-time algorithm A and an approximation ratio β for a polynomial-time algorithm B, you can safely claimthat A is better than B only if α for B with a better analysis.An algorithm A that has better running time and better performance than an algorithm B is better than B. An algorithmA is best, if there is no other algorithm that is better than it (assuming P 6= NP).From the definitions, it follows a polynomial-time algorithm that solves a problem P exactly is obviously best, but ifthe problem P is NP-hard, then a polynomial-time algorithm with the best possible approximation ratio α > 1 is best,or a pseudopolynomial algorithm that solves it exactly (if it exists) is best. For example, for the 0/1-Knapsack problem,the pseudopolynomial algorithm based on dynamic programming is best, the FPTAS approximation algorithm is best,but the 2-approximation Greedy algorithm is not best, because there is an approximation algorithm which runs inpolynomial time and achieves a better approximation ratio (the FPTAS).The problemConsider the following problem. A university lecturer aims to schedule a series of 1-hour Q&A sessions with n students(these are sessions for groups of students, not 1-on-1 meetings) and has set up a doodle poll where there are mavailable time slots. Every student has indicated which slots they could attend and it turns out that any student appearsin at least 1 and at most k time slots in the doodle poll. The lecturer would like to minimise the number of sessionsthat they will have to do, making sure that they do at least one session for every student (i.e., every student will have achance to attend some session).Come up with three best algorithms for the problem.Explain the limitations of your proposed solutions, as well as the limitations of the problem. Explain, wheneverpossible, why your proposed algorithms are best. If you are not sure whether they are best, what kind of improvementscould you be looking for?2转自：http://www.daixie0.com/contents/13/4377.html