Problem 1:  Circuits   (12 pts)

Build a circuit which computes following input/output table with at most three gates. You may only use 2-input AND, OR and 1-input NOT gates.  [Hint: What boolean expression represents this I/O table? If you are unable to find the solution with three gates, express it in as few gates as possible.] Use identities to your answer; do not guess and check.

Problem 3:  Algorithms   (10 pts)

Given the following algorithm:

Input: N, M (non-negative integers)

s := 0

a := N

b := M

while a > 0 and b > 0 do

b := b - 1

s := s + a + b

a := a - 1

end while

Output: s

Compute the trace table for the input N = 3, M = 4

Problem 4:  Counting   (12 pts)

(a)  (4 pts)  How many solutions are there to the equation

x1 + x2 + x3 + x4  = 25

where each xi  < 3 is an integer and x4  ≤ 7.

(b)  (4 pts)  How many integers between 1 and 2500 are multiples of 9, 11, or 16?

(c)  (4 pts)  How many integers between 1 and 50 do you have to select to ensure that at least one of the selected integers is prime?

Problem 5:  Greatest Common Divisor   (10 pts)

Apply the Euclidean Algorithm to compute the greatest common divisor of 3588 and 805. Use the format of the quotient-remainder theorem to display your work (i.e. do not build a trace table).

Problem 6:  Summation Formula   (12 pts)

Prove the following formula using Induction.

n

k=2

for all n < 2.

Problem 7:  Method of Iteration   (10 pts)

Solve the following recurrence relation by the method of iteration:

a1      =    1

an      =   an − 1 + n(n - 1) for all n < 2.

Problem 8:  Second Order Recursion   (12 pts)

Solve the following second order homogeneous recurrence relation with constant coefficients

a0      =   0

a1      =   3

an      =   6an − 1 - 4an −2     An < 2