CSE 240 Homework 12, Spring 2018 (50 points)
Due Saturday, November 10, 2018 at 11:59PM, plus a 24-Hour grace period
Introduction
The aim of this assignment is to make sure that you understand and are familiar with the concepts covered in the lectures. By the end of the assignment, you should have
- ● strong concept of functional paradigm.
- ● strong concept of pairs and list.
- ● understood the use of let-form and unnamed procedure.
- ● applied recursion to solve complex problems.
Reading: chapter 4 and course notes (slides).
You are expected to do the majority of the assignment outside the class meetings.
need assistance, or have questions about the assignment, please contact the instructor or the TA during their office hours.Preparation: Complete the multiple choice questions in the textbook exercise section. The answer keys can be found in the course Web site. These exercises can help you prepare for your weekly quiz and the exam. You are encourage to read the other exercise questions and make sure you understand these questions in the textbook exercise section, which can help you better understand what materials are expected to understand after the lectures and homework on each chapter.
You are expected to do the majority of the assignment outside the class meetings. Should you need assistance, or have questions about the assignment, please contact the instructor or the TA during their office hours.
You are encouraged to ask and answer questions on the course discussion board. (However, do not share your answers in the course discussion board.)
Practice Exercises (no submission required)
- 1 What is the major difference between a while-loop and a recursive procedure? What is tail- recursion?
- 2 What are the major steps of developing a recursive procedure?
- 3 Given the following Scheme program:
CSE240 – Introduction to Programming Language 1 | Page Homework 12
Should you
3 Given the following program:
(define mymax1 (lambda (lst) (if (= (length lst) 1)
))
3.1
3.2
3.3
3.4 4
4.1 4.2 4.3 5
6
6.1 6.2 6.3
(car lst)
(let ((m (mymax1 (cdr lst))))
(if (> (car lst) m) (car lst)
m)))
Add a procedure to handle the case of empty list, that is, if the given list is empty, the program should return “error: list empty”.
Describe the four design steps used to solve the recursive problem and give the solution obtained in each step.
Compare and contrast the algorithm (approach) used in this program and the divide-and- conquer algorithm.
Use C to re implement the program.
Follow the four design steps to solve each of the following recursive problems, using Scheme and using C, respectively.
Count the number of the elements in a list
Sum a list
Reverse a list
For each recursive procedure you write, describe the four design steps that you use to solve the recursive problem and give the solution obtained in each step.
Fibonacci Numbers are defined by
Follow the four design steps to write a recursive procedure to implement the function Define the size-n problem
Define the stopping conditions and the return values.
Define the size-m problems
CSE240 – Introduction to Programming Language 2 | Page Homework 12
- 6.4 Construct the size-n solution from the hypothetic size-m solutions.
- 6.5 Give the complete procedure that computes Fibonacci Numbers for any given integer n >= 0.
Programming Exercise (50 points)
Logic gates and adder are basic components of building a processor. All high-level language programs will be translated into instructions that can be executed on these basic components. The correctness and performance of these components are extremely important.
A computer system consists of hardware and software. Before we implement a hardware component, the design is normally simulated by a program first, so that we can verify its correctness and evaluate its performance. In this project, you will write Scheme programs to simulate an n-bit Adder.
If you did not take CSE/EEE120, or CSE/EEE230 and are not familiar with logic gates, you can ignore the physical meaning of the components. Simply consider each component as a pure math/logic function that does something, and you are asked to combine a more complex function using a few simpler functions in a specific way.
- 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. (3 points)
Figure 1. Logic gates AND, OR, and NOT
The test cases and expected outputs are given in the code template file hw12.rkt. Do not remove or edit these lines.
- 2 Write a Scheme procedure to simulate the XOR gate, shown in the diagram in Figure 2. You must use AN
Figure 2. Logic gate XOR, where 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.
CSE240 – Introduction to Programming Language 3 | Page Homework 12
D
- 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)
Figure 3. The logic design of a one-bit full adder
Verify your procedure by exhaustive testing: Use all valid inputs to test the procedure. There are eight valid inputs:
(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)
The test cases and expected outputs are given in the code template file hw12.rkt. Do not remove or edit these lines.
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: (n- bit-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.
CSE240 – Introduction to Programming Language 4 | Page Homework 12
result31
a31 b31
result30
result1
result0
a0 b0
Adder 31
Adder 30
Adder 1
Adder 0
Carry-out
0
a30 b30 a1 b1
Figure 4. The design of a 32-bit adder 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 (fulladder (tail A) (tail B) c). You can use (car (fulladder (tail A) (tail B) c)) and (cdr (n-bit- adder (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.
CSE240 – Introduction to Programming Language 5 | Page Homework 12
Grading of Programming Assignment
The TA will grade your program following these steps: The TA will grade your program following these steps:
(1) Compile the code. If it does not compile, 20% of the points given will be deducted. For example, if there are 20 points possible, you will earn 16 points if the program fails to compile.
(2) The TA will read your program and give points based on the points allocated to each component, the readability of your code (organization of the code and comments), logic, inclusion of the required functions, and correctness of the implementations of each function.
What to Submit?
You are required to submit your solutions in a compressed format (.zip). Zip all files into a single
zip file. Make sure your compressed file is labeled correctly: lastname_firstname12.zip. For this home assignment, the compressed file MUST contain the following:
hw12.rkt (Scheme program)
No other files should be in the compressed folder.
If multiple submissions are made, the most recent submission will be graded, even if the assignment is submitted late.
Where to Submit?
All submissions must be electronically submitted to the respected homework link in the course web page where you downloaded the assignment.
Late submission deduction policy
● No penalty for late submissions that are received within 24 hours after the deadline;
CSE240 – Introduction to Programming Language 6 | Page Homework 12
- ● 10% grade deduction for every day it is late after the grace period;
- ● No late submission after Tuesday at 11:59PM.
Academic Integrity and Honor Code.
You are encouraged to cooperate in study group on learning the course materials. However, you may not cooperate on preparing the individual assignments. Anything that you turn in must be your own work: You must write up your own solution with your own understanding. If you use an idea that is found in a book or from other sources, or that was developed by someone else or jointly with some group, make sure you acknowledge the source and/or the names of the persons in the write-up for each problem. When you help your peers, you should never show your work to them. All assignment questions must be asked in the course discussion board. Asking assignment questions or making your assignment available in the public websites before the assignment due will be considered cheating.
The instructor and the TA will CAREFULLY check any possible proliferation or plagiarism. We will use the document/program comparison tools like MOSS (Measure Of Software Similarity: http://moss.stanford.edu/) to check any assignment that you submitted for grading. The Ira A. Fulton Schools of Engineering expect all students to adhere to ASU’s policy on Academic Dishonesty. These policies can be found in the Code of Student Conduct:http://www.asu.edu/studentaffairs/studentlife/judicial/academic_integrity.htm
ALL cases of cheating or plagiarism will be handed to the Dean’s office. Penalties include a failing grade in the class, a note on your official transcript that shows you were punished for cheating, suspension, expulsion and revocation of already awarded degrees.
CSE240 – Introduction to Programming Language 7 | Page Homework 12