首页 >
> 详细

COMP523 - 2019 - Second CA Assignment

Advanced Algorithmic Techniques

Assessment Information

Assignment Number 2 (of 2)

Weighting 12.5%

Assignment Circulated 15 Nov 2019

Deadline 1 Dec 2019, 16:00

Submission Mode Please submit your solutions electronically (PDF or DOC format) at the

electronic submission system of the Computer Science Department

which you can find at the following url.

Learning outcome assessed 3. Identify which of the studied design principles are used in a given algorithm

taking account of the similarities and differences between the principles.

4. Apply the studied design principles to produce efficient algorithmic solutions

to a given problem taking account of the strengths and weaknesses

of 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 design

good 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 Assessment

Submission necessary in order No

to satisfy Module requirements?

Late Submission Penalty Standard UoL Policy.

Plagiarism and Collusion Please be aware of the University guidelines on plagiarism and collusion.

Task specification

Provide an answer to the following problem. You may consider any of the material that was presented in the lectures

as known.

Problem 1

Necessary definitions

Consider the following measure of comparison between two algorithms A and B, based on their running time and

approximation ratio:

• Better running time: Algorithm A has a better running time than algorithm B if A is polynomial time and B

is 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 approximation

ratio than B.

Remark: The comparisons above are based on the best possible analysis for the algorithms. For instance, a polynomial

time algorithm is better than a pseudopolynomial time algorithm, only if the latter can not be proven to run

in polynomial time. As a concrete example (from the lectures), you can either solve the max flow problem using

the Edmonds-Karp algorithm, or using a polynomial-time algorithm for linear programming. If you use the FordFulkerson

analysis for Edmonds-Karp (which will give you a pseudopolynomial running time), it would be incorrect

to claim that the LP-based algorithm is better than Edmonds-Karp, because the latter actually runs in polynomial time

with a better analysis (and they both solve the problem exactly). Similarly, if you prove an approximation ratio α for a

polynomial-time algorithm A and an approximation ratio β for a polynomial-time algorithm B, you can safely claim

that A is better than B only if α < β and you can not getter a better approximation ratio β0

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 algorithm

A 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 if

the 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 in

polynomial time and achieves a better approximation ratio (the FPTAS).

The problem

Consider 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 m

available time slots. Every student has indicated which slots they could attend and it turns out that any student appears

in at least 1 and at most k time slots in the doodle poll. The lecturer would like to minimise the number of sessions

that they will have to do, making sure that they do at least one session for every student (i.e., every student will have a

chance 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, whenever

possible, why your proposed algorithms are best. If you are not sure whether they are best, what kind of improvements

could you be looking for?

联系我们

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

- 代写data留学生作业、R编程语言作业调试、代做r课程设计作业帮做c/C++ 2019-12-04
- 代写mat2040留学生作业、代做linear Algebra作业、Pyth 2019-12-04
- 代写framework留学生作业、代做r编程语言作业、代写r课程设计作业、D 2019-12-04
- Plid50留学生作业代做、代写java，C++程序设计作业、代做pytho 2019-12-04
- 代写strategy Game作业、Java程序语言作业调试、Java课程设 2019-12-04
- Fs19 Stt481作业代做、代写dataset课程作业、C/C++，Py 2019-12-04
- Data留学生作业代写、代做java，Python编程设计作业、代写c/C+ 2019-12-04
- Data Frames作业代写、代做r编程语言作业、代写r课程设计作业、Uc 2019-12-04
- 代写es3c5留学生作业、Systems课程作业代做、Matlab程序语言作 2019-12-04
- Cs 1160留学生作业代做、代写programming课程作业、代做c/C 2019-12-04
- 代做comp 250作业、Math 240作业代写、Java编程语言作业调试 2019-12-04
- 代写elec5681m作业、Programming课程作业代做、代写c++实 2019-12-04
- Cs 201留学生作业代做、代写dynamic Analysis作业、代写j 2019-12-04
- 代写cs2313留学生作业、代做programming作业、C++程序语言作 2019-12-04
- Data Frame作业代写、代做r编程设计作业、代做r课程设计作业、Mas 2019-12-03
- Cs 116留学生作业代做、代写program课程作业、Python程序设计 2019-12-03
- 代写fdm留学生作业、代做c++课程设计作业、C++程序语言作业调试、Alg 2019-12-03
- 代写database课程作业、代做python/Java编程语言作业、代写p 2019-12-03
- 代做ie 6200作业、代写r编程设计作业、Data留学生作业代做、R实验作 2019-12-03
- 5Cosc001w作业代做、代写programming课程作业、代写java 2019-12-03