% Programming assignment 1, CSCE 235, spring 2007
% Assigned 21 February 2007; due 5 March 2007

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=9truein
\pdfhorigin=1.5truein \pdfvorigin=1truein

\headline={\hfil}
\footline={\hfil Page~\folio\hfil}

\newcount\pno
\pno=0
\def\problem{\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\noindent{\bf Problem~\hbox{#1}.} }
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\mathpart#1#2\par{{%
	\abovedisplayskip=-\ht\strutbox \advance\abovedisplayskip by-\dp\strutbox %
	\abovedisplayshortskip=-\ht\strutbox \advance\abovedisplayshortskip by-\dp\strutbox %
	\part{#1}#2\par}}

\def\implies{\;\Longrightarrow\;}
\def\N{\mathord{\bf N}}  \def\Z{\mathord{\bf Z}}
\def\Q{\mathord{\bf Q}}  \def\R{\mathord{\bf R}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}

\def\squiggle{\char`\~}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{CSCE~235: Introduction to Discrete Structures}
\centerline{{\bf Programming assignment~1} (50~points)}
\centerline{Assigned Wednesday, February~21, 2007}
\centerline{Due 11:59~p.m., Monday, March~5, 2007}

\medskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent You are to write a program that can determine whether a relation~$R$
on a set~$S$ is reflexive, symmetric, and/or transitive. Use good documentation
and programming style.

\medskip

\noindent{\bf Description of input}

\smallskip

\noindent The input to your program will contain several test cases, one test
case per line. Each line will be of the form
$$|S|\quad n\quad a_1\quad b_1\quad a_2\quad b_2\quad\ldots\quad a_n\quad b_n,$$
where $|S|$ is the cardinality of the set~$S$, $n$~is the number of ordered
pairs in the relation~$R$, and the following $2n$ numbers specify these ordered
pairs---i.e.,
$$R=\{\,(a_1,b_1),\,(a_2,b_2),\,\ldots,\,(a_n,b_n)\,\}.$$
The elements of~$S$ are consecutive positive integers, beginning with~1. Your
program should be able to handle test cases where $|S|$ is as large as~20.

The last line of the input will consist of two zeroes.

The input will be available to your program through {\it standard input}. This
means that you can use {\tt cin} to read the input in C++, {\tt scanf}~in~C,
{\tt System.in} in Java, and the corresponding functions in other programming
languages.

\medskip

\noindent{\bf Description of output}

\smallskip

\noindent The output of your program should be presented one test case per
line. Each line should begin with either ``{\tt reflexive}'' or ``{\tt not
reflexive}'', followed by a comma and a space, followed by either
``{\tt symmetric}'' or ``{\tt not symmetric}'', followed by a comma and a
space, followed by either ``{\tt transitive}'' or ``{\tt not transitive}''.

The output of your program should be sent to {\it standard output}. This means
that you should use {\tt cout} to produce the output in C++, {\tt printf}~in~C,
{\tt System.out} in Java, and the corresponding functions in other programming
languages.

Do not output any prompts or anything else other than the answers for each test
case. When your program is graded, a large input file will be piped to your
program, and the output your program produces for this input file will be saved
to an output file. This output file will be automatically compared with a file
containing the correct answers. If your output contains prompts or other
extraneous information, this comparison step will indicate that your program
produced incorrect output.

\medskip

\noindent{\bf What to hand in}

\smallskip

\noindent Hand in all source files and a README file that explains how to
compile and run your program. It is not necessary to hand in a binary
executable. Use the Web handin system at {\tt http://cse.unl.edu\slash\squiggle
cse235\slash handin} to hand in your files. Instructions for using this system
are on the back of this page.

\medskip

\noindent{\bf Sample input}

{\smallskip\narrower\narrower\parindent=0in\tt

3 5 1 1 1 2 2 1 2 2 3 3\hfil\break
5 8 1 3 2 5 3 1 3 3 4 4 4 5 5 2 5 4\hfil\break
4 6 1 1 1 3 2 2 2 4 3 3 4 4\hfil\break
0 0

\smallskip}

\noindent In this example, the first line specifies a relation on a set of
cardinality~3, so $S=\{1,2,3\}$. There are 5~ordered pairs in the relation, and
these ordered pairs are $(1,1)$,~$(1,2)$, $(2,1)$, $(2,2)$, and~$(3,3)$.

\medskip

\noindent{\bf Sample output}

{\smallskip\narrower\narrower\parindent=0in\tt

reflexive, symmetric, transitive\hfil\break
not reflexive, symmetric, not transitive\hfil\break
reflexive, not symmetric, transitive

}

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf Web handin instructions}

\bigskip

\noindent{\bf Registration}

\medskip

\noindent You have to register with the handin system before you use it for the
first time. To register, choose the ``Register'' link from the menu on the
left. Enter your CSE username along with a password ({\it not\/} your CSE
password) on the registration page, and click the ``Register'' button at the
bottom of the page to finish the process. You will then receive mail on CSE to
confirm your registration.

\bigskip

\noindent{\bf Handing in files}

\medskip

\noindent To hand in an assignment, go to the class handin Web page ({\tt
http:/$\!$/cse.unl.edu\slash\squiggle cse235\slash handin}) and fill out the form
on that page. Use the your CSE username and your handin password. Be sure to
choose the correct assignment under which to hand in the files, and choose the
files you wish to hand in with the file choosers at the bottom. If you need to
hand in more files than there are selection boxes, hand them in in two (or
more) separate batches. For example, if you need to hand in the files {\tt
file1.c}, {\tt file2.c}, {\tt file3.c}, {\tt file4.c}, {\tt file5.c}, and {\tt
file6.c}, but handin only lets you hand in five files at a time, hand in {\tt
file1.c} through {\tt file5.c} as one group and {\tt file6.c} by itself. After
each handin you will be shown a list of all of the files you have handed in up
to that point.

\bigskip

\noindent{\bf Checking a previous handin}

\medskip

\noindent If you ever want to check the status of a previous handin (``Did I
really hand in those files?''), you can go to the class handin page and choose
``Check Status'' from the handin choices. After making that choice, filling in
your username and password, and choosing an assignment to check on, click the
Submit button at the bottom of the page. You will then be presented with a list
of all of the files you have handed in for that particular assignment, along
with their sizes and the time and day you handed them in.

\bigskip

\noindent{\bf Changing your password}

\medskip

\noindent Changing your password on occasion can be a good idea. To change your
password, choose the ``Password'' link from the menu on the left. Fill out the
``Change user password'' form with your username, current password, and the new
password you would like. The change will take effect immediately after you
submit it, and you will also be sent a piece of e-mail on CSE confirming the
change.

\bigskip

\noindent{\bf Forgotten password}

\medskip

\noindent If you forget your password, the handin system can send it to you at
your CSE e-mail address. To receive your password, choose the ``Password'' link
from the menu on the left and fill out the ``Send user password'' form with
your username. After you submit the form you will receive mail on CSE with your
handin password.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye