CSE 240 Homework 13, Spring 2021 (50 points)
Due Saturday, April 24 at 11:59PM
No grace period and no Monday-Tuesday late submission for this final homework. The submission link will be disable on Saturday at 11:59pm!
Introduction
The aim of this assignment is to make sure that you understand and are familiar with the concepts covered in the lectures on Prolog. By the end of the assignment, you should have exercised
• Compared and contrasted the programming C++, Scheme, and Prolog.
• Prolog list operations and manipulations
• Prolog recursive rules with multiple nested calls
Reading: Textbook Chapter 5 and lecture slides.
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.)
Programming Assignment (50 points)
1 You will reimplement the Quicksort given in textbook and lecture slides. In the given example, the first (left-most) element of the given list is selected as the pivot. In this question, you must choose the second element of the list as the pivot. Hint: You can represent the input list into pairs: [First | [Pivot | Tail]]. You must write comments to indicate the size-n problem, stopping condition and its return value, size m-problems, and construction of the size-n problem from size-m problems. [20 points]
Test case:
| ?- qsort2([8, 3, 4, 12, 25, 4, 6, 1, 9, 22, 6], Sorted). It returns: Sorted = [1,3,4,4,6,6,8,9,12,22,25]
2 A premium pizza is comprised of exactly 40 ounces of toppings. The available toppings are listed below with their corresponding weight (in ounces). There can be multiple entries of each topping, as long as the total weight is equal to 40 ounces. [20 points]
CSE240 – Introduction to Programming Languages 1 | P a g e Homework 14
Topping
Weight (ounces)
Pepperoni
4
Sausage Bacon Onion Mushroom
10 6 5 7
For example, a pizza can contain 1 topping of pepperoni, 2 toppings of sausage, 1 topping of bacon, and 2 toppings of onion : 1*4 + 2*10 + 1*6 + 2*5 = 40 (ounces)
A pizza cannot contain 7 toppings of bacon : 7 * 6 = 42 > 40
A pizza cannot contain only 3 toppings of sausage : 3*10 = 30 < 40
2.1 Define a rule pizza(P, S, B, O, M) to find out how many of each topping can be contained on a pizza, where P, S, B, O, and M are the weight (in ounces) of the Pepperoni, Sausage,
Bacon, Onion, and Mushroom toppings, respectively.
2.2 Use your pizza rule to find all possible outputs to the following question (goal).
| ?- pizza(1, S, 1, O, M). Put all answers of the question in a comment in the file.
2.3 Use your pizza rule to find all possible outputs to the following question (goal).
| ?- pizza(P, S, B, O, 1). Put all answers of the question in a comment in the file.
𝑓𝑜𝑜(𝑥, 𝑦) = {𝑦
Assume that both x and y are originally non-negative integers greater than 0
For example: foo(5, 6) = 6 + foo(5, 3) 5 + foo(3, 3) 3 + foo(1, 3) 3 + foo(1,0) 1
= 6 + 5 + 3 + 3 + 1 = 18
Solve the problem in Prolog: Define a rule foo(X, Y, Z), where Z is used for the return value. You may also use foo(X, Y) and use Y to hold the return value. [10 points]
Note, you must use recursion. Follow the Fantastic Four-Step Abstract approach. You must indicate the steps in the comments for all parts. (Note, a Prolog rule does not return a value. You need to use an additional parameter to hold the return value.)
What to Submit?
CSE240 – Introduction to Programming Languages 2 | P a g e Homework 14
3 Complete the code for the following problem in Prolog. 𝑥
[15] [2]
[3]
[10 points]
𝑖𝑓 𝑦 ≤ 0 𝑖𝑓 𝑥 ≤ 0 𝑥+𝑓𝑜𝑜(𝑥−2,𝑦) 𝑖𝑓𝑥≥𝑦 𝑦+𝑓𝑜𝑜(𝑥,𝑦−3) 𝑖𝑓𝑥<𝑦
You are required to submit your solutions in a compressed format (.zip). Make sure your compressed file is label correctly - lastname_firstname13.zip.
The compressed file MUST contain the following:
question1Sort.pl
question2Pizza.pl question3Math.pl
You must submit in three separate .pl file. Submitting one file with all three programs are NOT acceptable. 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.
Submission preparation notice: The assignment may consist of multiple files. You must copy these files into a single folder for canvas submission. To make sure that you have all the files included in the zip file and they work after unzip operation, you must test them before submission. You must also download your own submission from the canvas. Unzip the file on a different machine and test your assignment and see if you can open and test the files in a different location, because the TA will test your application on a different machine. If you submitted an empty project folder, an incomplete project folder, or a wrong folder, you cannot resubmit after the submission linked is closed! We grade only what you submitted in the canvas. We cannot grade the assignment on your computer or any other storage, even if the modification date indicated that the files were created before the submission due dates. The canvas submission may take a few minutes. Be patient and wait for it to complete.
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 grace period;
● No late submission.
Grading Rubrics
Each sub-question (programming tasks) has been assigned certain points. We will grade your programs following these steps:
(1) Compile the code. If it does not compile, 50% of the points given for the code under compilation will be deducted. Then, we will read the code and give points between 50% and 0, as shown in right part of the rubric table.
(2) If the code passes the compilation, we will execute and test the code using test cases. We will assign points based on the left part of the rubric table.
(3) In both cases (passing compilation and failed compilation), we will read your program and give points based on the points allocated to each sub-question, the readability of your code
CSE240 – Introduction to Programming Languages 3 | P a g e Homework 14
(organization of the code and comments), logic, inclusion of the required functions, and
correctness of the implementations of each function.
(4) Please notice that we will not debug your program to figure out how big or how small the
error is. You may lose 50% of your points for a small error such missing a comma or a
space!
(5) We will apply the following rubrics to each sub-question listed in the assignment. Assume
that points assigned to a sub-question is pts:
Major
Code passed compilation
Code failed compilation
Points
Pts * 100%
Pts * 90%
Pts * 80%
Pts * 60%-70%
Pts * 40%- 50%
Pts * 10%- 30%
0
Each Sub- question
Meeting all requirements, well commented, and working correctly in all test cases
Working correctly in all test cases. Comments not provided to explain what each part of code does.
Working with minor problem, such as not writing comments, code not working in certain uncommon boundary conditions.
Working in most test cases, but with major problem, such as the code fail a common test case
Failed compilation or not working correctly but showing serious effort in addressing the problem.
Failed compilation, showing some effort, but the code does not implement the required work.
No attempt
Please read the FAQ file in the Course Information folder:
Q: For some reason, my assignment submission did not go through, but I thought it went through. I can show you on my local disk or in my Dropbox that I completed the assignment before the due date. Can my assignment be graded?
A: You should always download your own submission from the blackboard after submission and test if the submission contains all the required files. We will grade the assignment submitted to Canvas only. We cannot grade the assignment sent from email or stored in any other places, regardless its last-modified-time. If you submitted your assignment into the blackboard, it cannot be downloaded from the instructor side, but it can download from your side, we can download from your blackboard and grade the assignment. Please meet the instructor or TA in this case.
CSE240 – Introduction to Programming Languages 4 | P a g e Homework 14