Hey Everyone, Post your solutions to the May 10, In-Class Exercise to this thread. Best, Chris

-- May 10 In-Class Exercise

Without @BT@MOD3@BT@ gates, we can calculate parity by tabulating all possible @BT@2^n@BT@ outputs and representing it as a CNF formula. As we allow unbounded fan-in, this circuit will be of depth 2. The first layer of fan-in AND will be of up to size @BT@1.5n*2^n@BT@ - every output is negated in half the inputs. Negation requires an additional circuit, leading to an average size of @BT@1.5n@BT@ for each AND. There are @BT@2^n@BT@ AND circuits OR'd together. I don't use @BT@MOD3@BT@ gates so far.

-- May 10 In-Class Exercise

• We can determine if there are an even or an odd number of inputs by hard- wiring a CNF or DNF formula. • For a K inputs, we can use a MOD-3 gate to reduce the number of gates by adding a MOD-3 gate for K inputs and a MOD-3 gate for K+1 inputs, with the +1 input being always on. Depending on our value for K, we can get our answer by applying a simple boolean function to the output of these gates.

-- May 10 In-Class Exercise

XOR operation which uses AND, OR and NOT gates could be used here. This would require 2^n - 1 number of gates and the maximum depth would be 2^n. This circuit family does not require mod 3 gates