COMP523 : Advanced Algorithmic Techniques - Analysing Correctness and Asymptotic Performance - Computer Science Assignment Help

Assignment Task :

Learning outcome assessed

1. Identify which of the studied design principles are used in a given algorithm taking account of the similarities and differences between the principles.

2. 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.

3. Outline methods of analysing correctness and asymptotic performance of the studied classes of algorithms, and apply them to analyse correctness and asymptotic performance of a given algorithm.

Task specification 

Provide answers to the following problems. You may refer to any of the algorithms that were presented in the lectures or the tutorials. 

Problem 1 

An independent set of a graph G = (V, E) is a set S ⊆ V of vertices, such that for every two vertices u and v, there is not an edge (u, v) in E. Also, recall the definition of a vertex cover, i.e., a set T of vertices such that for every edge (u, v) ∈ E, at least one of u and v is in T. 

Prove that S is an independent set if any only if V − S is a vertex cover.  

Consider the decision version of the Maximum Independent Set problem: given a graph G = (V, E) and an integer k, decide whether there is an independent set S of size at least k in G (i.e., whether |S| ≥ k.) Also recall the decision version of the (minimum) Vertex Cover problem: given a graph G = (V, E) and an integer k, decide whether there is a vertex cover of size at most k in G. 

Assume that you have an algorithm A for solving the decision version of the Vertex Cover problem in O(1) time. Design a polynomial time algorithm B that uses the algorithm A, which solves the decision version of the Maximum Independent Set problem. Provide an argument for the correctness of the algorithm. What is the implication of the existence of algorithm B on the computational complexity of the decision version of the Maximum Independent Set problem?  

Assume that you have an algorithm A for solving the decision version of the Vertex Cover problem in O(n2· 2k) time, where n = |V | and k is the input integer parameter for the decision version of Vertex Cover. Does algorithm B solve the decision version of the Maximum Independent Set problem in time O(n2· 2k), where n = |V | and k is the input integer parameter for the decision version of Maximum Independent Set? Justify your answer.  

Problem 2 

Dr. Rasi Flosi-Starkasi has prepared 50 problems for the exam of his module “Advanced Algorithmic Techniques”. Each one of these problems has two attributes: 

- Its type: it is either a problem on graph algorithms, approximation algorithms or randomised algorithms. - Its difficulty: it is either easy, moderate or difficult. 

For example, it could be that Problem #34 is an easy problem on approximation algorithms. 

Dr. Flosi-Starkasi would like to prepare an exam consisting of 24 of those problems, but he wants to make sure that the exam containts 8 problems on graph algorithms, 8 problems on approximation algorithms and 8 problems on ran domised algorithms and at the same time 8 easy problems, 8 moderate problems and 8 difficult problems. 

Model this problem as a maximum flow problem, by explaining all the parameters of the flow network. Explain how to find a feasible exam set (i.e., satisfying the constraints set by Dr. Flosi-Starkasi above) from the maximum flow in the network, if it exists, or how to decide that it does not exist.  

It turned out that the exam set by Dr. Flosi-Starkasi in the previous part of the problem was really boring. For that reason, he decided to record an additional attribute for each problem, its entertainment value, which is a real number 

This Computer Science Assignment has been solved by our Computer Science  Experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.

Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.