2.3. Checking for symmetry.   

How do we check for "symmetry"? We know it means a[i,j] = a[j,i] but how do we test this condition? We may do something like: 


        for each element in array do

          compare it against its corresponding element

and we should be systematic about our comparisons therefore we should use roughly the same type of accessing of the elements as we used when reading them in: 

      for each row i do

          for each column j do

              check a[i,j] for symmetry

What do we do when the symmetric test is true? And what when it is false? Notice that this is an important point- if we find a particular i,j pair for which a[i,j] = a[j,i] it only means that the array might be symmetric, whereas finding a pair where it doesn't hold means that the array cannot possibly be symmetric. This is very important as it gives our approach to the problem. We will assume that the array is symmetric and then see if that is incorrect. We will use a logical or boolean variable to indicate the correctness of our assumption. It will be set to true initially and then set to false if a case of non symmetry arises.
What is the pseudo-code for the algorithm?

Try to write the pseudo-code to process the array before looking at the solution here.
Don't Cheat.

Is this the correct solution to the "check array for symmetry" algorithm? 


Add the symmetric  true statement.

Since symmetric is a boolean and the condition a[i,j]=a[j,i] returns a boolean result, we could assign this to symmetric directly: 

                symmetric  (a[row,column] = a[column,row])

giving 

      symmetric  true

      for row  1 to n do

          for column  1 to n do

              symmetric  (a[row,column] = a[column,row])

          endfor

      endfor

How much more efficient is this? No if statement is needed- just a direct assignment from the conditional. Note that the assignment is always done now whereas before it was only done if the condition held. Therefore is it more efficient? Which version would you choose and why?

Choose before looking at the solution here.
Don't Cheat.

This is valid since once symmetric is set false it can only be set to false again since any boolean anded with a false value is false. This is quite a reasonable solution although it may require a brush up on boolean values and how they combine.

It may seem dubious to use a[row,column] and a[column,row] since they seem to indicate different things. This is true but there is nothing stopping us from using simple variables such as row and column in any syntactically correct manner. For the purposes of our algorithm we choose to use them in this straight forward manner. 




Remember that all arrays in Java start at subscript 0!


Our complete algorithm minus var declarations and heading is thus: 


      for row  1 to n do

        for column  1 to n do

           input a[row,column]

        endfor

      endfor

      symmetric  true

      for row  1 to n do

        for column  1 to n do

           if a[row,column] != a[column,row] then symmetric  false

           endif

        endfor

      endfor

      if symmetric then output "symmetric"

      else              output "not symmetric"

      endif