# CS 2110 Lab 8 Characterizing a Relation

\$30.00

## Description

Today’s lab will help reinforce your understanding of relations that we discussed in the theory
class. In particular, you will focus on relations defined on a single set. Your task is to read in
a relation given to you as a adjacency matrix and report the following.
1. Is the relation is an equivalence relation? If so, what are the equivalence classes?
2. Is the relation a partial order?
Apart from the above basic properties that you must report about, you will have to report one
of the following.
1. Report the transitive closure of the given relation using Warshall’s algorithm. See http:
this algorithm.
2. If the relation is a partial order, report a topologically sorted list of the partial order.
Think of your own algorithm to solve this problem. Its OK if your algorithm is naive,
but it should be correct. Avoid going to the Internet.
For this lab, you are allowed to remind yourself of the definitions by looking for them on
of the information. In particular, look under the section titled “Relations over a set.” You may
use the si
0.1 Command Line Arguments
Your command line argument for this assignment is a single input file name.
1
0.2 The Input File Format
Each input file should contain one relation. The format is as follows. First you must have an
integer n which represents the number of elements in the set on which the relation is defined.
Given n, the n-element set is implicitly understood to be {0, 1, . . . , n−1}. Then, you will need
to have a n × n binary matrix. The following is an example.
4
1 0 0 1
1 0 1 1
0 0 0 0
0 1 0 1
0.3 Output Format
For this lab, you get a reprieve from strict output formatting. You must simply report all the
required information in an understandable way.