Assignments

Assignment 3

Due Wednesday, February 22

Problem 1 – Expressions

Construct a program that evaluates algebraic expressions in the infix format, such as "((5 + (2 * a)) - (35 % b))". The program should first prompt the user for the expression and convert the expression into the the postfix format. The program should then repeatedly prompt the user for the values of all the variables in the expression, evaluate the expression and output the result.

You can assume that the infix form is fully parenthesized, i.e. you don't need to worry about the precedence

Example:

Expression> ((5 + (2 * a)) - (35 % b))
a>5
b>3
Result=13
New values, new expression or quit (v/e/q)>v
a>3
b>5
Result=11
New values, new expression or quit (v/e/q)>q

Problem 2 –Circular Doubly-Linked List

Write a generic class that implements a circular doubly-linked list. Write a generic driver class that allows the user to 1) insert an item at the beginning of the list, 2) insert an item at the end of the list, 2) remove the first item from the list, 3) remove the last item from the list, and 4) print all the items in the list to the console. Then write two programs: one that uses the driver program for manipulating floating point numbers as items and another that manipulates string items.

Your program should 1) use a for-each loop to print all the items, and 2) make an appropriate use of the double links and circularity of the list.

Assignment 2

Due Wednesday, February 8

Problem 1 – ADTs & Inheritance

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 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. 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.

In addition, create a Decimal class (also with its own driver program) that performs its operations through the behaviors of the above Fraction class, this time converting all results to decimal.

Problem 2 – Sieve of Eratosthenes

Write a Java program that computes the all the prime numbers that are less than n using the Sieve of Eratosthenes algorithm. This is 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.

Extra Credit – Recursive Sequential Search

Using the random integer array from Assignment 1, accept another integer (between 2 and 999) from the user, and implement a recursive sequential search to locate and print it to the screen. If not found, print the appropriate message. Iterative solutions will not receive any credit, so make sure that you solves the problem recursively.

Assignment 1

Due Wednesday, January 25

Problem 1. Java Arrays and Loops

Fill an array of size N (read N from the console) with integer random numbers between 2 and 999. Then fill an array of exact size with all of the numbers that are greater than 499, and another array of exact size with those numbers that are less than 500. Now overwrite the original array with the numbers so that all the numbers less than 500 are followed by all the numbers that are greater than 499. Finally write out the first N/2 prime numbers in the array.

Hints:

  1. Use System.arraycopy() to write the numbers back into the original array.
  2. Use the fact that if a number N is not a prime, it can be expressed as a product where one of the factors in the product is less than the square root of N (but greater or equal 2). To find out whether N is prime, you can simply test whether there is such a factor that divides N.

Example:

Assignment 0

Due Wednesday, January 25

(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 pageswww2.hawaii.edu/~motookaj/211 and www2.hawaii.edu/~achriste/211 - 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 Julie Motooka, it would be at http://www2.hawaii.edu/~motookaj/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.

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.