Problems

Implement the following in both ML and Java .

1. Develop an abstract data-type called $set$. Represent a set of integers as a list (there should be no duplications) and develop functions for
   1. Adding a new element to a set.
   2. Checking whether an element belongs to a set.
   3. Finding the intersection of two sets.
   4. Finding the union of two sets.
   Estimate the time complexity of each operation.
2. Represent a set as an ordered list of integers and develop functions for each of the above operations. The time complexity of each of the above functions should be linear.
3. Consider a representation of univariate polynomials as lists of pairs of the type (coefficient, exponent). For example, the polynomial $7x^8 + 3x^4 + x + 5$ may be represented as the list $[[7,8],[3,4],[1,1],[5,0]]$. Assume that the polynomials are in their canonical form, i.e, the exponents are in the decreasing order.
   1. Develop algorithms/functions for adding and multiplying two polynomials. Estimate the time complexities of your algorithms.
   2. Develop Java function/procedure for reading and printing a polynomial.