## Description

Problem Deﬁnition

Today’s lab will help reinforce your understanding of relations that we discussed in the theory class. In particular, you will focus on relations deﬁned 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: //chuck.ferzle.com/Notes/Notes/DiscreteMath/Warshall.pdf for a reminder about 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 deﬁnitions by looking for them on the web. The wikipedia page (http://en.wikipedia.org/wiki/Binary_relation) has most 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 ﬁle name.

1

0.2 The Input File Format

Each input ﬁle 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 deﬁned. 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.

Uploading into MOODLE

Your code should be written as a single .c ﬁle. You must ﬁrst compress the ﬁle using gzip -c filename.c filename.c.gz and then the compressed .gz ﬁle must be uploaded into moodle. A link will be set up for this purpose in moodle.

Your TA for this lab

CS08B031, CS10B052, CS11B001 — CS11B009 Sai Sreennivas CS11B011 — CS11B021 Nishaanth CS11B022 — CS11B032 Saurav Kant Jha CS11B033 — CS11B042 Tejas Kulkarni CS11B043 — CS11B053 Paresh Nakhe CS11B054 — CS11B063 Shrikant Polawar