CSCI2041: Advanced Programming Principles
Programming Project 1
O. Introduction.
Polynomial arithmetic is a classic application of linked data structures like those used internally
Copyright By PowCoder代写 加微信 powcoder
by OCaml. For this project, you must write OCaml functions that make, add, and negate
univariate polynomials.
1. Theory.
For the purposes of this project, a polynomial is a finite sum of zero or more terms, like this.
Each term has a coefficient, shown as a subscripted a. It also has a variable, shown as y, with an
exponent, shown as a subscripted e. A polynomial is well formed if its coefficients are nonzero
integers, its exponents are nonnegative integers, and its terms appear in decreasing order of their
exponents. A polynomial with no terms is also well formed, and is assumed to be 0. Now
suppose that we have two well formed polynomials, p and q, like this.
= 3r° +21* +213-p2+:
= 7,4+12 – 10-3
To find the sum of p and q, we write one polynomial above the other, so that terms with equal
exponents appear in the same columns, and draw a line under them. Then, moving left to right
we visit the terms in each column. If two terms appear in a column, then we add their
coefficients. If the sum of the coefficients is O, then we do nothing. Otherwise, we write a new
term below the line in the same column, whose coefficient is the sum, and whose exponent is
that of the two terms. For example, the result of p + q is the well formed polynomial
3,5 + 9×4 + 2,3 – 4r +2
2,5 + 74+713-112
+ 112 – 11_2
318 + 91° +213
– 4r’ +21°
To find the difference of p and a, we first find – a, and then compute p + (- g) according to the
sum algorithm. The negation – q is obtained by simply reversing the signs of q’s coefficients
– (7x* +112-411 -319
-7×4 – 1,2 + 4×1 + 310
If there are two polvnomials with at most n terms, then we can add them in O(n) time. We can
also negate a polynomial with n terms in O(n) time.
Polynomials like these can be represented efficiently using singly linked linear lists, which
we will implement using OCaml user-defined types. We will represent polynomials as instances
of the OCaml type poly, which is defined like this.
= PolyEmpty PolyTerm of int
The type poly has two constructors, PolyEmpty and PolyTerm. The constructor PolyEmpty
makes a polynomial with no terms: it represents O. The constructor
To find the sum of p and q, we write one polynomial above the other, so that terms with equal
exponents appear in the same columns, and draw a line under them. Then, moving left to right
we visit the terms in each column. If two terms appear in a column, then we add their
coefficients. If the sum of the coefficients is O, then we do nothing. Otherwise, we write a new
term below the line in the same column, whose coefficient is the sum, and whose exponent is
that of the two terms. For example, the result of p + q is the well formed polynomial
3,5 + 9×4 + 2,3 – 4r +2
2,5 + 74+713-112
+ 112 – 11_2
318 + 91° +213
– 4r’ +21°
To find the difference of p and a, we first find – a, and then compute p + (- g) according to the
sum algorithm. The negation – q is obtained by simply reversing the signs of q’s coefficients
– (7x* +112-411 -319
-7×4 – 1,2 + 4×1 + 310
If there are two polvnomials with at most n terms, then we can add them in O(n) time. We can
also negate a polynomial with n terms in O(n) time.
Polynomials like these can be represented efficiently using singly linked linear lists, which
we will implement using OCaml user-defined types. We will represent polynomials as instances
of the OCaml type poly, which is defined like this.
= PolyEmpty PolyTerm of int
The type poly has two constructors, PolyEmpty and PolyTerm. The constructor PolyEmpty
makes a polynomial with no terms: it represents O. The constructor PolvTerm makes a
polynomial whose first term has a coefficient and an exponent, represented by the two int’s. It
is followed by zero or more remaining terms, represented by another instance of poly. For
example, we can construct the well formed polynomial 3r° + 97 + 2,3
– 4x + 2. using nested
constructors. like this.
(PolvTerm (3,
(PolyTerm (2,
(PolyTerm (-4,
(PolyTerm (2, 0, PolyEmpty)) )) ) ) ) ) ) !
And yes, OCaml really does require all those annoying parentheses @
And yes, OCaml really does require all those annoying parentheses @
2. Implementation.
You must write at least the following OCaml functions.
isPolyok p
(10 points.) Here p is an instance of the type poly. Test if p is well formed, so it has
no zero coefficients, no negative exponents, and so its terms appear in decreasing
order of their exponents. Return true if p is well formed, and false otherwise
makePoly i
(10 points.) Here i is a list of zero or more integers that looks like this. The a’s are
the coefficients of a polynomial, and the e’s are its exponents.
[al;er; an ; en …; an; en ]
Using the constructors PolyEmpty and PolyTerm, construct an instance of the type
poly that represents the following polynomial, and return it.
If the polynomial resulting from i is not well formed (so isPoly0k is false), then
raise the exception MakePolyError.
(20 points.) Here 1 and r are well formed instances of the type poly. Using the
constructors PolyEmpty and PolyTerm, construct a new well formed polynomial
that represents the sum of 1 and r, and return it.
polyMinus r
(5 points.) Here r is a well formed instance of the type poly. Using the constructors
PolyEmpty and PolyTerm, construct a new well formed polynomial that represents
-r and return it.
Here are some hints and threats.
• You are not allowed to use loops, mutable data structures, or variables in your functions. If
you do that, then you will receive ZERO POINTS for this project.
• Some of these functions might use tail recursions. Others might use a mixture of tail
recursions and non-tail recursions. Still others might not use tail recursions at all
• Some of these functions are most easily written using helpers. Any function can use
external helpers, internal helpers, or both. However, one kind of helper might be better than
another. You can write as many helpers as you need.
• Because poly’s are immutable, the function polyAdd might work by copying parts of
existing poly’s. For best efficiency, it must do as little copying as possible. Also, the
exponents of a well formed poly appear in decreasing order. The function polyAdd might
use this to avoid visiting all the terms of a poly.
• The function po1vAdd can use tuples to match more than one object at once. For example,
suppose that 1 and r are poly’s. Then something like this can match on both of them.
(20 points.) Here 1 and r are well formed instances of the type poly. Using the
constructors PolyEmpty and PolyTerm, construct a new well formed polynomial
that represents the sum of 1 and r, and return it.
polyMinus r
(5 points.) Here r is a well formed instance of the type poly. Using the constructors
PolyEmpty and PolyTerm, construct a new well formed polynomial that represents
-r and return it.
Here are some hints and threats.
• You are not allowed to use loops, mutable data structures, or variables in your functions. If
you do that, then you will receive ZERO POINTS for this project.
• Some of these functions might use tail recursions. Others might use a mixture of tail
recursions and non-tail recursions. Still others might not use tail recursions at all
• Some of these functions are most easily written using helpers. Any function can use
external helpers, internal helpers, or both. However, one kind of helper might be better than
another. You can write as many helpers as you need.
• Because poly’s are immutable, the function polyAdd might work by copying parts of
existing poly’s. For best efficiency, it must do as little copying as possible. Also, the
exponents of a well formed poly appear in decreasing order. The function polyAdd might
use this to avoid visiting all the terms of a poly.
• The function polyAdd can use tuples to match more than one object at once. For example
suppose that 1 and r are poly’s. Then something like this can match on both of them.
with (PolyEmpty, PolyEmpty)
(PolyTerm (1Coef, Expo, 10ther),
PolyTerm (rCoef, rExpo, rother))
The three dots «…” stand for additional OCaml code. This is onlv an example-it is no
necessarily what you will write.
• The file printpoly.ml defines a function called printoly that prints a poly so it is
somewhat easy to read. This may help with debugging. For example, suppose that p is the
poly that was constructed above using nested constructors. Then the call printpoly p wil
print this
3 x^5 + 9 x^4 + 2 ×^3
You need not know how printPoly works internally.
You can use the function makepoly to construct test cases for your functions, and you car
use the function printPoly to print their results. You can invent any test cases you like
they are not provided here.
3. Deliverables.
Unlike the lab assignments, YOU ARE NOT ALLOWED TO WORK WITH A PARTNER ON THIS
PROJECT. Although you may discuss the project with others in a general way, IT MUST BE
WRITTEN ENTIRELY BY YOURSELF. Also unlike the lab assignments, your grade will not be
based on test cases. The TA’s will grade your project by reading your OCaml code in detail.
The project will be due in two weeks, at 11:55 PM on October 10, 2022. It is worth 45
points. You must submit only one file. It must contain all your OCaml code and the results o
any test cases that you invented. Any output, resulting from running test cases, must appear in
comment (* -* *) at the end of your file. If you do not know how to turn in your work, ther
please ask vour lab TA’s.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com