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!

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:

  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
  2. recursion:
  3. iteration

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?

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:

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 public_html/ folder so that when someone is trying to look at your "home" page for ics211, they will not see the page info_about_myself.htm in the "index". In fact, you may opt to use another name instead of info_about_myself.htm and send the link to the TA.

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