Due Friday, Oct 8
Problem 1 - BigO
Let us going to compare algorithms with different BigO runtimes. Consider the following algorithms:
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.
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
Fraction will have two attributes: a numerator and a denominator,
To support the typical arithmetic operations,
support the following behaviors:
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:
simplifythat will divide both attributes by their GCD,
changeSignthat will convert a negative fraction to its counterpart and vice versa.
setthat sets both attributes of the fraction,
valuethat delivers the fraction's value as a floating point number, and
toStringthat 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
Write a Java program that computes the binomial coefficient (n over k) using three different methods:
A nicely formatted formulas are here.
Compare how much time each of these three alternatives need using System.currentTimeMillis().
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:
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.
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.
Due Friday, August 27
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.
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.