A group is a set equipped with a binary operator that satisfies the group axioms. An example of a group is the set of integers with the addition operation. It is a group because it satisfies the following group axioms.
x+(y+z) = (x+y)+z.
0 is
the identity element for addition.
x is invertible if there is some element
y in the set such that, when x is applied to y we get the identity element e
i.e. xy = yx = e.
All integers are invertible. The inverse of an integer is its negation. This follows since
x+(-x) = (-x) + x = 0 for all integers x.
A finite group is a group with a finite set. An example of a finite group is the set {0,1,2}
together with addition modulus 3. A cayley table
is a convenient way of representing a finite group. It is a table with rows and columns indexed by the elements of the group.
Given a group elements a, b and its binary operator *, the content of the cell indexed by row
a and column b is the group element a*b. It's like a multiplication table,
except that the binary operation is not necessarily multiplication.
The following is a cayley table for the group of integers mod 3.
|0|1|2| -------- 0|0|1|2| -------- 1|1|2|0| -------- 2|2|0|1| --------
A cayley table captures all the information of a Group. Given a table we can verify whether it is a Cayley table or not. We only need to verify it satisfies the four group axioms.
Write a C++ program that reads a table, then determines whether it is a cayley table or not.
Assume the input is a number n, followed sequence of n² space
separated characters in the set {0, ..., 9, a, ..., z}. Assume the input is always properly
formatted and that 0 < n < 36. The n² characters that follow n
are the rows of the cayley table, also assume the n numbers in the first row are distinct
(These are the elements of the group).
An input of this form encodes a cayley table whose
rows and columns are indexed by the fist row of the table. The following is an example.
Consider the following input
3 0 1 2 1 2 0 2 0 1
It encodes the following table.
|0|1|2| -------- 0|0|1|2| -------- 1|1|2|0| -------- 2|2|0|1| --------
Notice that the rows and columns are indexed by the first row (0,1, and 2) in the order they appear in the input.
If we rearranged the first row as in the following input then we get a different table.
3 2 1 0 1 2 0 2 0 1
It encodes the following table.
|2|1|0| -------- 2|2|1|0| -------- 1|1|2|0| -------- 0|2|0|1| --------
Suppose you have the following input in a file Test.txt.
3 0 1 2 1 2 0 2 0 1
If your executable is called run, then the command ./run < Test.txt
Should produce the following output.
Printing the table. |0|1|2| -------- 0|0|1|2| -------- 1|1|2|0| -------- 2|2|0|1| -------- It is a cayley table! The identity element is 0.
The following input file would produce the following output.
3 0 2 1 1 2 0 2 0 1
Output:
Printing the table. |0|2|1| -------- 0|0|2|1| -------- 2|1|2|0| -------- 1|2|0|1| -------- It is not a Cayley table! Not associative: (20)0 != 2(00).
In this case we see that the input isn't a cayley table since the operator isn't associative.
Since the elements of our groups are limited to single characters, we can denote the group
operation by juxtaposition without any ambiguity i.e. we use xy instead of
x * y.
In general, you program should behave as follows. It should first print the cayley table, then test to see if the table satisfies all the group axioms. It should test them in the order: closure, associativity, identity, then inverse. If the table fails any of these tests it should print a message saying that the table isn't a Cayley table. Then it should do ONE of the following. If the table doesn't satisfy closure, it should also print out an element that shouldn't be in that table. Then it should terminate. Otherwise, if the table doesn't satisfy associativity, it should print elements x,y,z such that (xy)z isn't equal to x(yz). As shown in the previous example. Then it should terminate. Otherwise, if the table doesn't satisfy identity, it should print out that the table has no identity element. Then it should terminate. Otherwise, if the table doesn't satisfy inverse, it should print an element without an inverse. Then it should terminate.
Your program should consist of the files: cayley.cc, cayley.h, driver.cc, Makefile.
cayley.cc: this file MUST include the following functions with the signature specified.
void read_table(char table[MAX][MAX], int table_size):
This function reads the table. It reads in n² (where n = table_size) numbers into the array table.
These are the n rows of the table.
void print_table(char table[MAX][MAX], int table_size):
This function prints table as a cayley table of size table_size.
It should be printed as presented in the examples above. It should have row
and column boundaries.
bool is_closed(char table[MAX][MAX], int table_size, char& outlier):
This function is meant to verify the closure axiom. It should return true if and only if
the table stored in table is closed i.e. every operation gives an element in the group.
If the group isn't closed, then outlier should be set to a character in the table that
doesn't belong. MAX is a constant integer that is set to 36 (the number of allowed characters). It
should be declared in cayley.h.
void is_associative(char table[MAX][MAX], int table_size, char& x, char& y, char& z, bool& ans).
This function is meant to verify the associativity axiom. It should set ans to true if and only if
the table's operation is associative. If it isn't it should set x, y, and z to elements that violate
associativity. They should be set such that (xy)z != x(yz).
void has_identity(char table[MAX][MAX], int table_size, char& identity):
This function is meant to verify the identity element axiom. It should set identity
to the integer constant ERROR (Should be declared in cayley.h and set to -1)
if the table has no identity element. Otherwise, identity is set to an identity element
in the table.
void all_have_inverse(char table[MAX][MAX], int table_size, char& ans)
This function is meant to verify the inverse element axiom. It should set ans
to the integer constant GOOD (Should be declared in cayley.h and set to -2.) if
every element in the group has an inverse. Otherwise, out out should be set
to an element in the table without an inverse.
These functions are required, you'll lose a lot of point if they aren't implement as I have specified.
They should also be implemented in the order they are presented above.
Don't make your functions over complicated, make helper functions to simplify your code. All helper functions
should be implemented in cayley.cc.
cayley.h: this file should contain the header/signature of all functions in cayley.cc. It should also include the constants ERROR (set to -1) and GOOD (set to -2). All your functions should have appropriate pre/post comments. You can omit pre/post comments in cayley.cc but they must be included in cayley.h.
driver.cc: this file should have the main function. The main function should read in the table, print it, then indicate whether the table is a cayley table or not.
Makefile: the make file should create an executable called run. In a folder with all your files, the make command should produce the executable run. It should be properly designed so that it always produces an up to date executable.
This project is due on Friday the 14th at 11:59:59 PM. The files driver.cc, cayley.cc, cayley.h, Makefile,
Test1.txt, Test2.txt, TestCases.txt (ONLY) should be placed in a folder named with your last name only. Compress the folder using zip
and upload it to Inquire. Test1.txt and Test2.txt are two test cases for you program. TestCases.txt is an explanation of each test case and
the expected output of your program.
Correctness: 60% Test cases: 10% Style: 10% (code alignment, comments, not using magic numbers, ...) Makefile: 10% Following submission guide lines: 10%