CS-2510 Assignment 9

Due: December 5th @ 10:00 pm

Purpose:

To practice representing structures and writing interesting methods.

This is our last assignment (aside from the final project),

Programming Problem 1: (Arith.java)

Here's a class diagram for structures that represent simple arithmetic expressions. 

                             +-------------+
                             |     Exp     |<------------+
                             +=============+              \
                             +------+------+               \
                                   / \                      \
                                  +---+                      \
                                    |                         \
                    +---------------+------------------+       \
                    |                                  |        \
              +----------+                      +-------------+  \
              |   Num    |                      |     Bin     |  |
              +==========+                      +=============+  |
              | int  val |                 +----| Oper  op    |  |
              +----------+                 |    | Exp   left  |--+
                                           |    | Exp   right |--/
                                           |    +-------------+
                                           V  
                                      +---------+               
                                      |  Oper   |
                                      +=========+
                                      +----+----+
                                          / \
                                         +---+
                                           |
                         +-----------+-----+-----+-----------+
                         |           |           |           |
                     +-------+   +-------+   +-------+   +-------+
                     |  Add  |   |  Sub  |   |  Mul  |   |  Div  |
                     +=======+   +=======+   +=======+   +=======+
                     +-------+   +-------+   +-------+   +-------+
The classes are meant to allow us to represent a little math language. In my (mental) version, we would represent a simple math expression like: 
8 * ((1 + -2) - 9) = -80
Or in Prefix notation: 
(* 8 (- (+ 1 -2) 9) = -80
As the Exp instance: 
new Bin(new Mult(), new Num(8), 
    new Bin(new Sub(), new Bin(new Add(), new Num(1), new Num(-2)), 
        new Num(9)

  1. Translate the class diagram into class defintions. (Make sure Num can hold arbitrary numbers, including decimals and negative numbers). Make examples that represent the following "programs": 

    1. 2 * 2 + 7
      Remember order-of-operations!! 

    2. 20 / 2 - (5 + 3)

  2. Create a simple method apply for the classes that implement operations (i.e., Oper, Add, Sub, etc.) that does the appropriote operation when given two Num arguments.

    E.g., for Add the two arguments should be added... easy right? Make the method abstract in the Oper class.

  3. Create a recursive method eval() for the entire hierarchy that evaluates the "expression" to a single double.

    For Num, you should know what to do.

    For Bin you should recursively eval, then apply the operation.

  4. Test your methods by evaluating simple examples and the ones I asked you to create for Exercise #1. (Congratulations... you just made an interpreter in Java!!)



Programming Problem 2: (Complexity.java)

Download the Complexity.java code. In it you will find a few methods in the Algos class. For each one, I would like you to do the following tasks. Include your answers as block comments (/* Comment... */) above each method.

  1. Write a recurrence relation for the method (e.g. T(n) = 2T(n-1)).

  2. Describe the complexity of the method. I.e. Which of the following bounds best describes the method? Explain your reasoning.

    • O(lg(n))
    • O(n)
    • O(n*lg(n))
    • O(n^2)
    • O(2^n)

  3. Look at the ComplexityExamples class. In it you will find a test for each method. At the beginning of each test, there is a variable n, which represents the input size to the function.

    Play around with different values of n for each function, and examine the amount of time that each test takes to run (see the output in your console). Compare these results with your answers to (2).

    Note that it may seem to freeze if you choose numbers which are too large. You can either try to wait, or click the red square in the top right of the Console area to cancel execution, and try again with smaller numbers.

    Hint: think about the amount of time that should be added when you increase n by a certain factor. E.g. for an O(n) algorithm, the amount of time it should take if you double n should be twice as long, but for n^2 it should be 4 times as long ((2n)^2 = 4*n). But for some algorithms, you may only want to change n by a small number each time.