算法代写|COMP2721 Algorithms and Data Structures Coursework 1

这是一个英国的算法与数据结构CS作业代写

1. Execute breadth-first search and depth-first search on the following graph. Start at
vertex a and handle neighbours in alphabetical order.

(a) Provide the ordering of the vertices as they are visited by a BFS. Your answer
should be a string σ−1(1)σ−1(2) · ·· σ−1(16) without separators.
[0:15h expected time] [6 marks]

(b) List the neighbours of f in the BFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(c) List the neighbours of g in the BFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(d) List the neighbours of j in the BFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(e) List the neighbours of k in the BFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(f) Provide the ordering of the vertices as they are visited by a DFS.
[0:15h expected time] [6 marks]

(g) List the neighbours of f in the DFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(h) List the neighbours of g in the DFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(i) List the neighbours of j in the DFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

(j) List the neighbours of k in the DFS-tree in alphabetic order.
[0:01h expected time] [1 mark]

2. Consider the function Magic, whose pseudocode is illustrated in Algorithm 1. The
algorithm takes a graph as an input and outputs either true or false. The algorithm
also uses a global array p that holds a Boolean value for every v 2 V and a global
integer variable c.

blank

Algorithm 1: What am I computing?

Given a graph G, then the function Magic returns true if:

• the graph G is connected,
• the graph G has an even number of vertices,
• the graph G has an even number of edges,
• all components of G have exactly two vertices,
• all components of G have an even number of edges,
• all components of G have an even number of vertices.

3. Execute the DFS-based topological sort on the following directed graph. If there is
a choice handle vertices in alphabetic order.

blank

(a) Give the first three vertices of the topological ordering as a string
σ−1(1)σ−1(2)σ−1(3) without separators. [0:05h expected time] [2 marks]

(b) Give the next three vertices of the topological ordering as a string
σ−1(4)σ−1(5)σ−1(6) without separators. [0:05h expected time] [2 marks]

(c) Give the next five vertices of the topological ordering.
[0:05h expected time] [2 marks]

(d) Give the next four vertices of the topological ordering.
[0:05h expected time] [2 marks]

(e) Give the final five vertices of the topological ordering.
[0:05h expected time] [2 marks]


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


blank

本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: itcsdx@outlook.com  微信:itcsdx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论