oindent

Assume you are given an infinite supply of two$-$input, one$-$output gates,

most of which are OR gates and some of which are AND gates.

Unfortunately the OR and AND gates have been mixed together and you

can't tell them apart. For a given integer $k$\backslash$geq $0$$$,$ you would like

to construct a two$-$input, one$-$output combinational $``$$k$$-$OR$\text{'}\text{'}$ circuit

from your supply of two$-$input, one output gates such that the following

property holds: If at most $k$ of the gates are AND gates then the

circuit correctly implements OR$.$ Assume for simplicity that $k$ is a

power of two.

For a given integer $k $\backslash$geq $0$$$,$ you would like to design a $k$$-$OR

circuit that uses as few gates as possible.

$\backslash$begin$\{$enumerate$\}$

$\backslash$item Design a $$1$$$-$OR circuit with the smallest number of gates. That is$,$ your circuit should take two inputs, and always return the OR of the inputs, as long as at most one of the gates constituting the circuit is an AND gate, while the remainder are OR gates. Argue the correctness of your circuit.

$\backslash$item Using a $$1$$$-$OR circuit as a black box or making a new circuit from scratch, design a $$2$$$-$OR circuit. How many gates does your circuit have? Argue the correctness of your circuit.

$\backslash$item Generalizing the black box approach from part $($b$),$ or using a different approach, design the best possible $k$$-$OR circuit you can and derive a $$\backslash$Theta$$-$bound $($in terms of the parameter $k$$)$ for the number of gates in your $k$$-$OR circuit. Argue the correctness of your circuit. For full credit, the number of gates in your circuit must be a polynomial in $k$$.$

$\backslash$end$\{$enumerate$\}$