Assignment 4: Equality; Double-dispatch🔗

Goals: To reason about structual and non-structural equality.

Instructions🔗

Make sure you follow the style guidelines that Handins enforces. For now the most important ones are: using spaces instead of tabs, indenting by 2 characters, following the naming conventions (data type names start with a capital letter, names of fields and methods start with a lower case letter), and having spaces before curly braces.

You will submit this assignment by the deadline using the Handins submission system. You may submit as many times as you wish. Be aware of the fact that close to the deadline the Handins system may slow down to handle many submissions - so try to finish early.

There will be a separate submission for each problem - it makes it easier to grade each problem, and to provide you with the feedback for each problem you work on.

The submissions will be organized as follows:

• Homework 4 Problem 1: The XML.java file

• Homework 4 Problem 2: The Polynomial.java file

Practice Problems🔗

Work out these problems on your own. Save them in an electronic portfolio, so you can show them to your instructor, review them before the exam, use them as a reference when working on the homework assignments.

• Problems 18.1 - 18.4 on page 225

• Problem 18.5 on page 229

• Problem 18.6 on page 234

• Problem 19.4 on page 263

Problem 1: XML Sameness🔗

XML, the eXtensible Markup Language, is a format for defining tree-shaped data. In BSL, we’d write the data definition as follows:

;; A XML is one of

;; - Text

;; - Tag

;; A Text is a (make-text String)

(define-struct text [content])

;; A Tag is a (make-tag String Attrs Content)

(define-struct tag [name attrs content])

;; An Attrs is a [List-of Attr]

;; An Attr is a (make-attr String String)

(define-struct attr [name value])

;; NOTE: attribute names within an individual tag must be unique.

;; A Content is a [List-of XML]

• Design the method boolean sameDocument(IXML doc), that determines if this XML document and the given document have exactly the same shape: the same tags, the same tree-structure, the same attributes in the same order with the same values, and the same content.

• Typically, the attributes of a given element are considered as a set: the order among the attributes does not matter. Design the method boolean sameXML(IXML doc), that determines if this XML document and the given document have equivalent shape, when attribute-ordering is irrelevant.

• Often, the tags in XML are used to indicate formatting. Design the method boolean sameText(IXML doc), that ignores all the tags and attributes and determines if this document and the given document contain the same plain text content.

Since we are designing three different—but related!—notions of sameness, the quality of your test suite is especially important on this problem. There is therefore an Examplar submission for you to refine your test suite. The wheats and chaffs are not guaranteed to be exhaustive (though there is at least one chaff associated with each method above), but if your test suite cannot catch all our chaffs, we will grade your submitted tests accordingly. Note: Next to each test case (whether that’s a particular data example or a particular check-expect), leave a comment explaining why that example is interesting, distinctive, or necessary: what scenario is it trying to test for?

Hint and Note: One of the ways examples may fail to run is if the input data themselves are somehow bogus when they shouldn’t be, or incorrectly not bogus when they should be. (Recall the Date example from lecture.) For your Examplar tests, instead of defining all your example data as fields of your examples class, define them as local variables within each testSomething method. You may also need to use the various exception-checking testing methods to detect some of the chaffs.

Problem 2: Pesky Polynomials🔗

To learn about polynomials in much greater depth, consider taking the Rings and Fields course offered by the math department.

Mathematically, polynomials are written as: \(a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x^1 + a_0 x^0\)

Each expression of the form \(a_i x^i\) is called a Monomial. Every monomial has a degree, a non-negative integer that \(x\) is raised to (\(i\)), as well as a coefficient, which \(x^i\) is multipled by (\(a_i\)). For this problem, our polynomials will be over the integers, which means all of the coefficients must also be integers; you do not have to worry about doubles in this problem. Make sure that only monomials with non-negative degrees can be constructed. (The coefficients can be any integer.)

Note: To make the uses of your constructors more readable, and make them match the math notation more closely, your constructor should have the signature Monomial(int coefficient, int degree) – and our tests will expect this order of the arguments.

This problem focuses on polynomials in a single variable. As a challenge, consider how you might extend the reasoning in this problem to work with polynomials in multiple variables – what additional simplifications might you need, to make this feasible?

A Polynomial has just one field, monomials, which is a ILoMonomial. You should ensure that a Polynomial cannot be constructed if any of the monomials given to it have the same degree. However, the monomials can be in any order, e.g. \(3x^2 + 5\) is the same polynomial as \(5 + 3x^2\). Finally, monomials might be present with coefficients of zero, and these should not affect sameness: both the polynomials in the previous sentence are the same as \(5 + 0x + 3x^2\).

You will design two contructors for the Polynomial class and several methods for it, which are described below:

• Warmup: Design a method evaluate that evaluates a polynomial at a given integer value. For instance, evaluating \(3x^2 + 5\) at \(4\) should yield 53. You may want to use the Math.pow method, and coerce its result from a double to an int. (We’ll limit ourselves to integers rather than doubles, just for simplicity of testing.)

• The subsequent methods in this problem can be made much easier if you normalize the list of monomials given to the Polynomial constructor. For instance, instead of tolerating both \(5 + 2x + 3x^4\) and also \(2x + 3x^4 + 0x^2 + 5\), you should prefer the first one: it’s sorted, and there are no zero-coefficients anywhere. You will likely want to implement a compareTo method somewhere to help out with the sorting. It should obey the same purpose statement as compareTo on strings: it should return a negative number if this thing-being-compared is less than the given thing-being-compared, it should return a positive number if this thing-being-compared is greater than the given thing-being-compared, and zero otherwise.

  Design a method normalize on ILoMonomial that provides this normalization step. By normalizing your data and keeping it normalized, (almost all of) the methods below should each be quite short to implement. Use this method in your primary constructor of Polynomial to ensure that polynomials only ever contain normalized lists of monomials.

• Design another convenience constructor for Polynomial that takes in no arguments at all, and simply initializes the monomials field to represent the zero polynomial.

• Design a method add that adds two polynomials together. Polynomials are added one monomial at a time: if their degrees are the same, you add the coefficients, otherwise you just include both monomials. For example, \(3x^2 + 4x^2\) simplifies to \(7x^2\), but \(2x + 3x^2\) does not simplify any further. (Hints: start by designing a method to add a single monomial to a list of monomials (“add” in the mathematical sense, not just “cons onto a list” – and be careful about preserving normalization). Then use that as a helper for the overall add method in this problem.)

• Design a method samePolynomial which determines if two Polynomials represent the same polynomial. (Hint: you can solve this problem two different ways, using structural comparisons as we’ve done in class, or using some of the mathematical methods defined above.)

• Extra credit: Design a method multiply that multiplies two polynomials together. Two polynomials are multiplied by taking each monomial in the first polynomial and multiplying it by each monomial in the second, and then adding up all the results. Two monomials are multiplied by multiplying their coefficients and adding their degrees: \(3x^2 * 4x^3\) simplifies to \(12x^5\). (Hints: there are at least two ways to think about solving this problem, and both of them should use methods you’ve already written earlier in this problem as helpers to finish this multiply method. Again consider starting from a method to multiply by a single monomial. Again, be careful about preserving normalization in this helper.)