## Assignments

### Assignment 3

Due Friday, Oct 8

Problem 1 - BigO

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

1. Fibonacci (recursive),
2. Counting how many of the elements in an array are unique,
3. Linear search, and
4. 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:

1. 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.
2. Don't miss the labs - they will provide additional information that will help you with the coding!

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:

1. `simplify` that will divide both attributes by their GCD,
2. `changeSign` that will convert a negative fraction to its counterpart and vice versa.
3. `set` that sets both attributes of the fraction,
4. `value` that delivers the fraction's value as a floating point number, and
5. `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.

### Assignment 2

Due Friday, Sept 24

Problem 1

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

1. using factorial
• (n over k) = n! / (k! * (n - k)!)
2. recursion:
• (n over 0) = (n over n) = 1
• (n over k) = (n - 1 over k - 1) + (n - 1 over k)
3. 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:

1. Write down all integer numbers between 2 and n. Color them blue.
2. Pick the first blue number (initially 2) - it is a prime, so color it green.
3. Color red all multiples of this prime.
4. Repeat from step 2 until the first blue number root is greater square root of n.
5. 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.

### Assignment 1

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)=c1*x+c0 where c1 and c0 are arbitrary coefficients.
Hint: You'll need to store the coefficients when the object that represents such a linear function is constructed.
• 1c)    Now develop a class that represents an arbitrary polynomial, i.e. f(x)=cn*xn+cn-1*xn-1+..+c1*x+c0
Hint: 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.

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.

### Assignment 0

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 http://www2.hawaii.edu/~johnwu/ics211/info_about_myself.htm:

• what you prefer to be called
• 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