41 41 Insertion Sort 4 Design 137 the a algorithm for genera

4.1 4.1 Insertion Sort 4. Design 137 the a algorithm for generating the power set of a set of n elements. (The power set of a set s is the set of all the subsets of S,including empty set and S itself.) 5. Consider the following algorithm to check connectivity of graph defined by adjacency a ALGORITHM Connected (A 0...n-1, 0..n ij) Input: Adjacency matrix Alo..n 1,0. n -1) of an undirected graph G //Output: 1 (true) if G is connected and 0 (false) if it is not if n 1 return 1 //one-vertex graph is connected by definition else if not Connected(AI0..n -2, 0. n 2]) return 0 else for j 0 to n 2 do if Aln 1, jlreturn 1 return 0 Does this algorithm work correctly for every undirected graph with n 0 vertices? If you answer yes, indicate the algorithm\'s efficiency class in the worst case; if you answer no, explain why. 6. Team You have the results ofa completed round-robin tournament ordering Each game ended either with a nloured each other once,

Solution

The answer is No

One example, where it would fail for some cases is, when call to Connected( A[0..n-2, 0...n-2 ] ) would return false, and we consider the graph represented by A[0..n-1, 0...n-1 ] to be not connected

This is because, that n-1 th vertex can very well connect the graph represented by A[0..n-2, 0...n-2 ] and thus graph can be connected, and our algorithm fails.

Let me give a simple example, say following is the adjacency matrix:

Now clearly A[0..1,0..1] is not connected, i.e. vertex 0 and 1 are not connected.

But vertex 2 connects them, by being the middle one, and thus whole graph is infact connected. The given algorithm will fail here.

0	0	1
0	0	1
1	1	0