Determining loop invariants for nested for loops in C++

44 Views Asked by At

I am learning about loop invariants and algorithm verification for C++ loops. While I understand the steps to prove the corectness of an iterative algorithm (the invariant must be true initially, executions of the loop must preserve the invariant, invariant must capture the correctness of the algorithm, and loop must terminate), I am having trouble determining what the loop invariant is. Can someone help me determine what the invariant is for each of the following 2 nested for loops in this method that prints the adjaceny matrix for a directed graph:

template <class LabelType>
void AdjacencyMatrix<LabelType>::printAdjacencyMatrix() const {
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            std::cout << (matrix[i][j] ? "1 " : "0 ");
        }
        std::cout << std::endl;
    }
}

I tried determining the the invariant, but it does not hold true at all steps of the loop. I am having trouble finding the correct invariant for each of the loops.

0

There are 0 best solutions below