Programming Assignment 3: Logician

Programming Assignment 3: Logician
CECS 328
1 Deadline
Friday, October 29th
2 Introduction
A logician is examining a sequence of logical statements in order to create an
example of an algorithm for one of his classes. The statements are numbered
from 0 to N −1, and for any given pair of statements, they are either contradictory or non-contradictory. For the purposes of his example, he requires a subset
S of statements (taken from his original list of N) such that each statement in
S has at least k1 other statements in S that are non-contradictory and k2 other
statements in S that are contradictory. (You should not think of a statement
as being contradictory nor non-contradictory to itself.) The logicians goal is to
determine, among all possible sets S, the largest.
3 Your code
Input will be a matrix of boolean values, a value for k1, and a value for k2. If
the value [i][j] in the matrix is true (resp. false), then statement i is not (resp.
is) contradictory to statement j.
Your output will be a set of integers that represent the set S of statements
that you have chosen. It should be the largest among all possible sets that
satisfy the professor’s requirements.
The Java header for the function in StudentSolver.java is:
public static HashSet<Integer> solve(boolean[][] m, int k1x, int k2x)
The Python header for the function is:
def solve(m, k1x, k2x)
The C++ header for the function is:
static std::set<int> solve(bool** m, int matrixSize, int k1x, int k2x);
1
Figure 1: Robert Smullyan- inventor of knights and knaves puzzles and improver
of Godel’s incompleteness theorem
4 Example
Assume that the matrix is the following:


0 0 1 1 1
0 1 1 1 1
1 1 0 1 1
1 1 1 0 0
1 1 1 0 0


where 0 is false and 1 is true, and assume that k1 = 2 and k2 = 1.
The largest set of statements that is consistent with the restrictions is
{0, 1, 3, 4}. 0 does not contradict 3 and 4 but does contradict 1. 1 does not
contradict 3 and 4 but does contradict 0. 3 does not contradict 0 and 1 but
does contradict 4. 4 does not contradict 0 and 1 but does contradict 3.
Important note: The diagonal entries in the matrix can essentially be ignored
for the purposes of this problem.
2