数学代写：Algebra MAT062 代数代写，90高分通过

Algebra 高分代写案例

a) You are asked to solve a particular problem concerning a simple graph with n vertices and m edges. Three different algorithms A, B, and C are available for solving this problem. In the worst case the maximum number of steps carried out by these algorithms are as follows: A = 2n2 + 10; B = 4m; C = 105 . Using big-O notation, discuss the relative benefits and drawbacks of these algorithms

b) Consider the graph G below, together with its adjacency list.

Starting at v1 show the spanning trees produced by the BFS and DFS algorithms. In both cases, clearly indicate the order in which edges are added to the trees.

c) Prove whether or not the graph in Part b) is planar

d) Let Kn be a complete edge-weighted graph on n vertices. Edge weights are denoted by w(u,v) (where w(u,v) = w(v,u)). You are asked to design an algorithm that will partition the vertices of this graph into k sets such that the sum of the weights across all groups is minimised. That is, given a vertex partition {S1, S2,…, Sk} we want to minimise the cost

Describe an application of the simulated annealing algorithm for this problem. In your answer be sure to describe:

· A method of generating an initial solution,

· Any neighbourhood operators,

· The acceptance criteria,

· The role of “temperature” in the algorithm,

· The differences between this method and the random descent method.

Given a simple graph, give definitions and draw examples of the following: i) a bridge, ii) a cut vertex, iii) a complete graph, iv) a complement graph, v) a simple path.

b) Given a simple graph G = (V, E), let L(v) denote a list of “permissible” colours for each vertex v in V. We are now interested in colouring the vertices of V such that

· Adjacent vertices are always assigned to different colours

· The number of different colours used across the graph is minimal

· Each vertex v is assigned to a colour appearing in its list L(v).

Prove that this problem is NP-complete / NP-hard.

Design a simple greedy algorithm for the problem stated in Part b). In cases where a vertex cannot be coloured, it is acceptable to leave it uncoloured.

d) Consider the problem of sorting a list of n integers. It is easy to check (in O(n) time) whether any arbitrary arrangement is in numerical order. On the other hand, the number of different ways of arranging n integers is O(n!). Does this mean that the sorting problem is NP-complete? In your answer, fully discuss your reasoning.

Recent Case

盘点留学生常用5 种最佳笔记方法，哪一种适合您

SCI期刊论文的发表过程是一项复杂而细致的工作，涉

轻松掌握万能Essay模板，撰写一篇合格的英文论文

Python可谓是当下最火的编程语言，同时，Pyt