#### Assignment 4: Equality; Double-dispatch

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

##### Instructions

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,

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:

Homework 4 Problem 1: The Building.java file

Homework 4 Problem 2: The CampusTour.java file

Homework 4 Problem 3: The Polynomial.java file

Due Date: Tuesday, February 15th, 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.

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:` `Building Equality

Download and complete the Building.java file (look for the // TODO: comments).

This one’s pretty simple, and is a wamup for...

### Problem 2:` `The Pru Is Like The North Star!

Download and complete the CampusTour.java file (look for the // TODO: comments). You may find some of your code from the last exercise helpful.

Sameness of tours is slightly subtler than structural sameness:

If a BranchingTour had arbitrarily many-choices instead of two, how would you implement sameness for an ISetOfTourLocation, where order doesn’t matter?

When a tour branches, the option1 and option2 destinations are arbitrary: one BranchingTour is the same as another BranchingTour if their two sub-tours are the same in either order, and their speeches are the same.

Two Quads are the same only when their names are the same and their locations are the same in the same order, as their ordering is specified in the data representation.

### Problem 3:` `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 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.

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. Like the Trigram problem from last week, you will likely want to implement a compareTo method to help out with the sorting.

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.)