Java

Programming Assignment 3: Logician

CECS 328

1 Deadline

Friday, October 29th, 2021 at 5 PM

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 contradic- tory 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