Spring 2026 CPS 2232
Data Structures
Wenzhou-Kean University April 8, 2026
Programming Assignment 1
Programming Assignment 1
The Programming Assignment 1 is due Sunday, April 26 at 23:59. Submit the “Polyno-
[Link]” and “[Your student ID] [your Name] PA1 [Link]” files to the Canvas under
“Projects” → “Project 1”.
Problem 1-1. [100 points] Univariate Polynomial Manipulation
Task description. Design, implement and test an ADT, Polynomial, that provides some of the
basic operations for univariate polynomials. For example, P (x) = 3x4 − 7x + 18 is such a
polynomial.
Your ADT Polynomial should have a data member belonging to the class MyLinkedList which
keeps the terms (term consists of coefficient and exponent) in the polynomial in a linked list . The
This can be a circular linked list
linked list representation of a polynomial has one node for each term that has non-zero coefficient.
The terms are in decreasing order of non-negative exponent and the head node has its coefficient
and exponent field equal to 0 and-1 respectively. The following figure gives some examples.
2 Programming Assignment 1
You must use the three classes MyLinkedList, Iterator, and Term to do the job: (should be modified to adapt the change to circular structure)
•You cannot modify the specific details of these three classes;
•You use Iterator for accessing the linked list instead of next pointer in class Node.
The ADT Polynomial should support the following operations, some of which are inherited from
the superclass BasePolynomial.
(a) Polynomial()
- Create the zero polynomial, that is P (x) = 0. Polynomial() is the class default constructor.
(b) Polynomial(int[] data)
- It is the class constructor to create a polynomial with the initial values of the coefficients and
exponents that stored in data. Given data = {c0 , e0 , c1 , e1 , . . . , cn , en }, create the polynomial
P (x) = c0 xe0 + c1 xe1 + . . . + cn xen . You can assume that each ci is a non-zero integer and
all ei are in decreasing order, i.e., e0 > e1 > . . . > en ≥ 0.
(c) String toString()
- Convert the Polynomial object this to a string in the format: “[c0 x ∧ e0 + c1 x ∧ e1 + . . . +
cn x ∧ en ]”.
(d) Polynomial add(Polynomial another)
- Add the two polynomials this and another, store the resulting polynomial into a new Poly-
nomial object out, and return out.
(e) Polynomial subtract(Polynomial another)
- Subtract the polynomial this from the polynomial another, store the resulting polynomial
into a new Polynomial object out, and return out.
(f) Polynomial multiply(Polynomial another)
- Multiply the two polynomials this and another, store the resulting polynomial into a new
Polynomial object out, and return out.
Tasks. You are given five files “[Link]”, “[Link]”, “[Link]”,
“[Link]”, and “[Link]”. The implementations of some methods are missing in the file
“[Link]”. You need to implement these missing methods (highlight by the “TODO” key-
word). You CANNOT modify the signatures of these methods. You CANNOT print any additional
message to the console in your final submission except those are already there in toString(). You
CANNOT modify the files “[Link]”, “[Link]” and “[Link]”. You
need to complete the following tasks.
•Implement the methods add(Polynomial another), subtract(Polynomial another), and multi-
ply(Polynomial another). You may add any other public/private methods and recursive solutions that you think are necessary.
•Write a report named “[Your student ID] [your Name] PA1 [Link]”, which includes
–a cover page with your name and your student ID;
Programming Assignment 1 3
–the design of test cases and the purpose of each test case;
A recursive solution; Possible extensions of this problem;
–the analysis of the running time of the methods add(...), subtract(...), and multiply(...)
with the explanation.
How to interpret and run
class Trie Remarks: You do not need to handle whether the input is in valid format. E.g., you can assume that the input string can always convert to a trie. You can assume that all characters in a message exist in the given trie. An encoded message can always be decoded by the given trie.
class Huffman Remarks: Huffman coding may not be unique, but the cost should be the same. If your Huffman coding is different from the sample one, it is fine as long as it is correct.
Interpret. Unzip the “[Link]”, and go to the folder “Assignment 1” in the command prompt.
Type “javac -d . assignment 1/*.java chapter 1/*.java”.
Run. Type “java assignment 1/PA1”.
Grading
Make sure that your java version is jdk 17.
Make sure that you can interpret your java files to the class files. Failing to interpret your submis-
sion results in zero score for the implementation.
The grading is based on running a list of test cases, and your report. Some sample test cases are
given in “[Link]”. Make sure that your program can pass the given sample test cases.
Make sure that you follow the Course Polices. Plagiarism can result in 0 point.