On this page:
Practice Problems
Problem 1: XML Sameness
Problem 2: Pesky Polynomials

Assignment 4: Equality; Double-dispatch🔗

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


Be very, very careful with naming! Again, the solution files expect your submissions to be named a certain way, so that they can define their own Examples class with which to test your code. Therefore, whenever the assignment specifies:
  • the names of classes,

  • the names and types of the fields within classes,

  • the names, types and order of the arguments to the constructor,

  • the names, types and order of arguments to methods, or

  • filenames,

...be sure that your submission uses exactly those names.

Make sure you follow the style guidelines that Bottlenose 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 Bottlenose submission system. You may submit as many times as you wish. Be aware of the fact that close to the deadline the Bottlenose 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:

Due Dates:
  • Examplar: Sunday, February 4th, 9:00pm

  • Implementations: Wednesday, February 7th, 9:00pm

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.

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]

Related files:

We have given you Examplar stubs for these data definitions. Name your examples class ExamplesXml.

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: