Please help me with this question. This question is taken from the book Introduc

Question

Please help me with this question. This question is taken from the book Introduction to the Design and Analysis of Algorithms- Anany Levitin (3rd ed.), chapter 3 (Brute Force and Exhautive search), exercises section 3.1. For the implementation using a computer program part, please kindly provide source code in C. Thank you very much.

1. (20 points A network topology specifies how computers, printers, and other devices are connected over a network. The figure below illustrates three common topologies of networks: the ring, the star, and the fully connected mesh. fully connected mesh star ring You are given a Boolean matrix A whose size is n x n for n 3, which is supposed to be the adjacency matrix of a graph modeling a network with one of these topologies. Your task is to determine which of these three topologies, if any, the matrix represents. (a) (5 points) Give an example of the adjacency matrix for each case when n S 6. (a (10 points) Design a brute-force algorithm using a pseudocode. Implement the algorithm through computer program (b) (5 points) Compute time efficiency.

Explanation / Answer

See, considering it to be 2D array we can draw each mesh's matrix:

a)

int[][] ringMesh =
{
{0,1,0,0,0,1},
{1,0,1,0,0,0}, // example edge here is with 1 and 3
{0,1,0,1,0,0},
{0,0,1,0,1,0},
{0,0,0,1,0,1},
{1,0,0,0,1,0}
};
int[][] starMesh =
{
{0,1,1,1,1,1}, // example edge here is with 2,3,4,5,6
{1,0,0,0,0,0},
{1,0,0,0,0,0},
{1,0,0,0,0,0},
{1,0,0,0,0,0},
{1,0,0,0,0,0}
};
int[][] fullConnMesh =
{
{0,1,1,1,1,1},
{1,0,1,1,1,1},
{1,1,0,1,1,1}, // example edge here is with 1,2,4,5,6
{1,1,1,0,1,1},
{1,1,1,1,0,1},
{1,1,1,1,1,0}
};

b)

PSB the logic for each of the mesh correlation: [ you could wire them into a program]

// #include <stdbool.h> // for boolean operations

//For Star simply check that each node has degree 2
public bool isRingMesh() {
for (int vertex = 0; vertex < vertexCount(); vertex++) {
if (degree(vertex) != 2) {
return false;
}
}
return true;
}

//check central connectivity.
public bool isStarMesh() {
bool center = notValid;
int starEdge = 0;

for(int r = 0; r < this.matrix.length; r++) {
int notValidCount = countnotValidr(r);

if(notValidCount == 1 && !center) {
center = true;
} else if(notValidCount == this.matrix[0].length - 1 && starEdge < this.matrix[0].length - 1) {
starEdge++;
} else {
return notValid;
}
}
return true;
}

//Check full connectivity.
public bool isFullyConnMesh() {
for(int r = 0; r < this.matrix.length; r++) {
int notValidCount = countnotValidr(r);

if(notValidCount != 1 || this.matrix[r][r] != notValid) {
return notValid;
}
}
return true;
}
}

c)

Since it is a bruteforce algorithm, and deends on implementation and complexity goes to O n^2.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.