**Due Friday, Oct 8**

**Problem 1 - BigO**

Let us going to compare algorithms with different BigO runtimes. Consider the following algorithms:

- Fibonacci (recursive),
- Counting how many of the elements in an array are unique,
- Linear search, and
- Binary search

We want to see how much time these algorithms really need for different
values of *N*. To measure that, we will need to start a stop watch, then run an
algorithm numerous times for the same *N* value, e.g. 1000 or even 10000 times and
then stop the watch. We can plot the stopped time in the console. This will give
us the an output that looks similar to the following figure:

10 x 11 x 12 x 13 x 14 x 15 x 16 x

As you will see, some of the algorithms are so fast that such a picture looks
like a straight line and doesn't reveal the actual differences. Therefore, we
would like to run the algorithms not only for consecutive *N* - e.g, 10,
11, 12, 13, 14, ..., 28, 29 -, but also for *N* that grows faster - e.g.,
4, 9, 16, 25, ..., 361, 400.

Sounds very complicated? We can greatly simplify the challenge if we make good use of Java's object-oriented features:

Create an abstract class that does all the work that is common, runs an
algorithm for different values of *N*, starts and stops the "stop watch"
and plots the graph. Let's call the method that does all the work plot().

This class should have as a field an array of integers that define the values
of *N*. This field should be set in the constructor, together with the
name of the algorithm and with the number of times to run the algorithm.

But how does the plot() method run the different algorithms? It can do it because it can call an abstract method that represents an arbitrary algorithm. (This abstract class is very similar to the interface in Assignment 1 and the abstract method is the equivalent of the method the interface defined there!)

Now you can implement the four actual algorithms as four subclasses of our abstract class. Each of the subclasses needs only to provide an implementation of the abstract method. (Also, it will need a constructor to provide the info specific to this particular algorithm, e.g. its name.)

You'll need to plot eight graphs - we have four algorithms and we'd like to
see their performance with two different sets of of *N* values.
Therefore, your driver program can construct an array of the corresponding eight
versions of our algorithms. Then the program can go through a for loop to run
the eight graphs.

After comparing the eight sets of graphs, order them according to their Big O efficiency in the Javadoc of your driver class.

Hints:

- To make it simple to draw the graphs, adapt the following conventions: The vertical axis is
the input
*N*and the horizontal axis corresponds to the runtime of the algorithm. - Don't miss the labs - they will provide additional information that will help you with the coding!

**Problem 2 - ADT**

In computational mathematics, it is often important to be as exact as
possible. If your computations use only rational numbers - i.e., fractions - you
can be exact! Let's create the ADT `Fraction`

that allows you to compute with
fractions exactly.

Your ADT `Fraction `

will have two attributes: a numerator and a denominator,
both integers.

To support the typical arithmetic operations, `Fraction `

should
support the following behaviors: `add`

, `subtract`

, `multiply`

,
and
`divide`

. (Note that since each of these behaviors represent a binary
operation, your behaviors will have to accept another fraction.)

In addition, there should be a the following behaviors:

`simplify`

that will divide both attributes by their GCD,`changeSign`

that will convert a negative fraction to its counterpart and vice versa.`set`

that sets both attributes of the fraction,`value`

that delivers the fraction's value as a floating point number, and`toString`

that provides a textual representation of the fraction.

Create a driver program with a menu to allow the user to manipulate fractional numbers using the above behaviors.

**Due Friday, Sept 24**

**Problem 1**

Write a Java program that computes the *binomial coefficient* **(n over k)** using three
different methods:

- using factorial
- (n over k) = n! / (k! * (n - k)!)
- recursion:
- (n over 0) = (n over n) = 1
- (n over k) = (n - 1 over k - 1) + (n - 1 over k)

- iteration
- (n over k) = n * (n - 1) * ... * (n - k + 1) / (k * (k - 1) *... * 2 * 1)

A nicely formatted formulas are here.

Compare how much time each of these three alternatives need using `System.currentTimeMillis()`.

**Problem 2**

Write a Java program that computes the all the prime numbers that are less
than *n* using the *Sieve of Erasthothenes* algorithm. This an informal
description of the algorithm:

- Write down all integer numbers between 2 and
*n*. Color them blue. - Pick the first blue number (initially 2) - it is a prime, so color it green.
- Color red all multiples of this prime.
- Repeat from step 2 until the first blue number root is greater square root of n.
- When finished, all the green and blue numbers are prime.

Hint: You can use an array of `boolean` values, e.g. where `false` means
"it's red, i.e. a multiple, i.e. not prime" and `true` means
"it's green of blue, i.e. prime or possible prime". Whether it's blue
or green is simply a matter of where you are in the list of numbers.

**Due Friday, Sept 10**

**Problem 1. Tables of mathematical functions**

You have probably encountered tables of mathematical functions in high
school, for instance logarithmic tables. Such tables are important: for
instance, mathematical APIs such as `java.lang.Math`

often use such
tables internally because looking up a value in a table is typically more
efficient than computing the values.

In this assignment you will create a program that outputs FIVE different tables of mathematical functions. Each of these functions should be represented by a class and defines a method for computation. The output should be done in the main program with ONE output method that takes such function as its argument. (To be precise, it the argument will be an object of the class that represents the function.) This output function should write the table to the console, for instance like this:

x | sin(x) ------|------ 0.00 | 0.00 2.00 | 0.91 4.00 | -0.76 6.00 | -0.28 8.00 | 0.99

Notice that you will need to write the function's name (e.g. `sin(x)`

)
in the heading of the table. What is the best way to do that?

- 1a) Write the tables of two simple functions, e.g. f(x)=cos(x), f(x)=exp(x), f(x)=x^4, f(x)=log2(x).
- 1b) Write the tables of a linear function, i.e. f(x)=c
_{1}*x+c_{0}where c_{1}and c_{0}are arbitrary coefficients.

You'll need to store the coefficients when the object that represents such a linear function is constructed.*Hint:* - 1c) Now develop a class that represents an arbitrary
polynomial, i.e. f(x)=c
_{n}*x^{n}+c_{n-1}*x^{n-1}+..+c_{1}*x+c_{0 }The coefficients need to be stored in an array and you will again need to store them while the polynomial is constructed. You will need a for-loop that iterates through the coefficients to compute the f(x) values.*Hint:*

** Extra points:** Constructing the name of a polynomial
- even just of a linear function - in the customary way isn't quite trivial as
you need to skip coefficient that are 0, leave out the coefficients that are 1,
write only - if a coefficient is -1, etc. You get extra points if you get it
right.

**Due Friday, August 27**

(Extra Credit)

**Problem 1.**

Become familiar with all the pages at our course web site www2.hawaii.edu/~janst/211. Also, look at the TA's home page www2.hawaii.edu/~johnwu/ - that's where important information about homework assignments will be posted.

**Problem 2.**

Construct a web page that contains the following information and post it so
that it is available at ** http://www2.hawaii.edu/~youraccount/ics211/info_about_myself.htm**
(e.g. in case of our TA it would be at

- your name

- what you prefer to be called
- your recent photograph

- email address
- your UH ID
- your Skype name (if any)

- your year (Freshman, Sophomore, etc.)

- ICS courses you have completed

- where you are from

- when you plan to graduate

- what you are most looking forward to in this class

- your interests

- anything else you want to share that will help your instructor remember
you

Make sure your face is clearly visible in your photograph - this is to help the instructor and the TA learn who you are. If you do not have a clear photograph, have your picture taken in class by the instructor.

To protect your privacy, make sure that there is an ** index.html**
file in your

Doing this assignment earns you extra-credit points, which is much to your advantage.