CSCI 422 Fall 2021: Lab 3

CSCI 422 Fall 2021: Lab 3: Poset Transitive Closure and Reduction

(For the student to submit, using git.)
Due: Nov 5, 11:59 pm

You are to use git to get the testapp.cpp and poset.cpp files and amend them so that the transitive closure and the transitive reduction are computed. Once the Reachability Matrix (transitive closure) has been computed, populate the appropriate vector representations of the poset. You must be able to write the poset out to a file (of same name, with extension ".treduc"), using posetWrite. This subprogram must print out the poset's transitive closure into a file with the same name as the input file, but with extension ".tclose" (this code is provided). Also, the poset's reduction is to be written into a file with extension ".treduc". The code for the write routine is provided in posetWrite. Note that these must be written from data in the vectors UpperCover and UpperIdeal, as in the code provided. We want to test that you have developed these space-efficient representations of the poset correctly. Testapp will allow you to test the functionality.

Note that, to compute the transitive reduction, you do not have to implement the O(n^2.379) algorithm; you can use the $O(V³)$ or $O(V \cdot E)$ algorithm indicated in class (three nested for-loops, or the DP solution). Also, for the transitive reduction, there is a way to do it with three nested for-loops or as Dynamic Programming. That is sufficient for this lab. See if you can figure out how to do it (or you can look it up). For this lab, you will submit the code via git. Instructions are here:
Tutorials

You will be marked on:

clarity of code -- comment your code

correctness -- test it on lots of data. Use gen to create random input data, and contruct input data that specifically tests particular test cases. Your instructor will be testing your program adversarially -- i.e., she will try to break your code. Try breaking it yourself, and fixing it, before you get marks taken off.

design -- your code should do the job elegantly, but should not sacrifice correctness or comprehensabilty for elegance.