1 Write three Scheme procedures to simulate these three gates: AND, OR, and NOT, shown in the diagram in Figure 1. Test your procedures using all possible input combinations. Hint: Lecture slides showed the implementation of a not-gate in Scheme.

2 Write a Scheme procedure to simulate the XOR gate, shown in the diagram in Figure 2. You must use AND, OR, and NOT gates that you defined in question 1 to implement XOR. In infix notation, c = ((NOT a) AND b) OR (a AND (Not b)))

3 Define Scheme procedures to simulate the logic design given in the diagram in Figure 3. The procedures must follow the design in Figure and call the gate procedures that you defined in the previous questions and must return a pair with two elements '(c . s), where s is the binary sum of a, b, and x, while c is the carry-out. You will implement the procedure in three steps using three procedures, as listed below.

3.1 Write a procedure (halfAdder x a b) to generate (return) the sum bit s. The upper half of Fig. 3 (5 points)

3.2 Write a procedure (carry-out x a b) to generate (return) the carryOut bit c. The lower half of Fig. 3 (5 points)

3.3 Write a procedure (fullAdder x a b) to generate the pair output (c . s), where s is the output of the halfAdder procedure and c is the output of the carry-out procedure. The fullAdder is also called a one-bit adder. (5 points)

4 The diagram in Figure 4 shows the design of an n-bit adder using n one-bit full adders, where n = 32 in the diagram. The carryOut of bit-i is the carryIn of bit i+1, where the carryIn of bit 0 is 0. The procedure should have three parameters: A, B, and n, where A and B are two lists representing two binary inputs numbers, and n is the length of A and B: (nbit-adder A B n). Two solutions are acceptable: (1) Follow the design in Figure 4, or (2) follow the binary addition algorithm given in the lecture slides. In both case, you must call at least one of the procedures that you defined in Question 3. You may define one or more helper procedures.

4.1 Define a procedure (tail lst), which returns the last element of lst. (4 points)

4.2 Define a procedure (rmtail lst), which returns the list without the last element of lst. For example, (rmtail (1 3 5 6 8)) should return (1 3 5 6). (4 points)

4.3 Follow the fantastic-four abstract approach to design your recursive solution to implement the diagram in Figure 4. You must also explain: (4 points)

(1) What is the size-n problem of your procedure?

(2) What are the stopping condition and its return value?

(3) What is the size-(n-1) problem?

(4) What are the steps to construct the size-n problem solution from the size-(n-1) solution.

Write the answers as comments in the program. 4.4 Following the fantastic-four steps that you have designed in the previous question, implement the n-bit adder, and design a test plan to test the program. (18 points) Note: your (n-bit-adder A B n) should call a recursive procedure, e.g., (recursiveAdd A B c), where c is a carry. You can follow the lecture slides to write these two procedures. However, you cannot use (quotient t 2) and (remainder t 2). Instead, you must call your (nbit-adder (tail A) (tail B) c). You can use (car (bit-adder (tail A) (tail B) c)) and (cdr (n-bitadder (tail A) (tail B) c)) to obtain the sum and carry, respectively.

Test your program using the given test cases and make sure they generate the output matching with the expected output.

In the output, the left-most element is the carry-out of the n-bit adder. If the carry-out is 1, it represents an overflow in the adder. The remaining elements of the list are the sum.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

;Q1 (3 points)

; Put your code here:

(define OR-GATE (lambda (a b)

(define AND-GATE (lambda (a b)

(define NOT-GATE (lambda (a)

; Q2 (2 points)

; Put your code here:

(define XOR-GATE (lambda (a b)

; Test cases and expected output. Do not edit or remove.

(newline)

(Display "AND-Gate Output ")

(AND-GATE 0 0)

(AND-GATE 0 1)

(AND-GATE 1 0)

(AND-GATE 1 1)

;0

;0

;0

;1

(newline)

(Display "OR-Gate Output ")

(OR-GATE 0 0)

(OR-GATE 0 1)

(OR-GATE 1 0)

(OR-GATE 1 1)

;0

;1

;1

;1

(newline)

(newline)

(Display "XOR-Gate Output ")

(XOR-GATE 0 0)

(XOR-GATE 0 1)

(XOR-GATE 1 0)

(XOR-GATE 1 1)

;0

;1

;1

;0

;Q3.1 (5 points)

(define halfAdder (lambda (x a b)

;Q3.2 (5 points)

(define carry-out (lambda (x a b)

;Q3.3 (5 points)

(define fullAdder (lambda (x a b)

; Test cases and expected output. Do not edit or remove.

(newline)

(Display "halfAdder Output ")

(halfAdder 0 0 0)

(halfAdder 0 0 1)

(halfAdder 0 1 0)

(halfAdder 0 1 1)

(halfAdder 1 0 0)

(halfAdder 1 0 1)

(halfAdder 1 1 0)

(halfAdder 1 1 1)

;halfAdder Output

;0

;1

;1

;0

;1

;0

;0

;1

(newline)

(Display "fullAdder Output ")

(fullAdder 0 0 0)

(fullAdder 0 0 1)

(fullAdder 0 1 0)

(fullAdder 0 1 1)

(fullAdder 1 0 0)

(fullAdder 1 0 1)

(fullAdder 1 1 0)

(fullAdder 1 1 1)

;(0 . 0)

;(0 . 1)

;(0 . 1)

;(1 . 0)

;(0 . 1)

;(1 . 0)

;(1 . 0)

;(1 . 1)

;Q4.1 (4 points)

(define tail (lambda (lst)

;Q4.2 (4 points)

(define rmtail (lambda (lst)

;Q4.3 (4 points)

; Write the answers in comments

;1) What is the size-n problem of your procedure?

;2) What are the stopping condition and its return value?

;3) What is the size-(n-1) problem?

;4) What are the steps to construct the size-n problem solution from the size-(n-1) solution?

;Q4.4 (18 points)

(define n-bit-adder (lambda (L1 L2 n)

; Test cases. Do not edit or remove.

(define X1 '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) )

(define X2 '(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) )

(define X3 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1) )

(define X4 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0) )

(define X5 '(1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1) )

(define X6 '(1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0) )

(Display "n-bit-adder Output ")

(newline)

(Display "n-bit-adder Output ")

(n-bit-adder1 X1 X2 32)

(n-bit-adder1 X3 X4 32)

(n-bit-adder1 X5 X6 32)

(n-bit-adder1 X2 X3 32)

(n-bit-adder1 X4 X5 32)

(n-bit-adder1 X1 X6 32)

;(0 (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1))

;(0 (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1))

;(1 (1 0 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1))

;(1 (0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0))

;(1 (1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1))

;(0 (1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0))