Archive‎ > ‎2010‎ > ‎Assignments‎ > ‎

Homework #5

Introduction

The goals of this homework are to:
  • familiarize you with design patterns
  • give you a feeling about the optimization opportunities that may arise in the code

Please keep track of how much time (in hours) it takes you to solve each exercise. Please download and complete the timeSpent.txt template (replace xxx with the number of hours you spent) and include this file with your deliverables.

You must use the provided answers.txt template to answer the questions.

The total number of points for this homework is 100. 

Please be mindful of the Collaboration Policy. If you have any questions regarding the assignment requirements, ask on the discussion group. If you have any doubts about whether it's appropriate to ask something, check with the course staff. You are allowed to use Web search to find answers to questions.

The deadline for this homework is December 24, 2010, at 12:00 CET (noon). Assignments (or parts thereof) handed in late will not be considered.


In this homework, you will implement an evaluator for mathematical expressions that operate on matrices and scalar values. Bold capital letters (M, A, B, ...) denote matrix values, and lower case italic letters (a, b, c, ...) denote scalar values.

An expression is recursively defined as:
  • A matrix of n values, or a scalar value (equivalent to a 1 x 1 matrix). The scalar values and the matrix elements are represented by the double Java type, which also includes the special values Infinity and NaN. In this homework, all the operations should accept these special values as inputs, but the corresponding outputs are undefined (however, the code should not crash or throw an exception).
  • An addition/subtraction of two expressions, corresponding to matrix or scalar operations (AB, ab, A - B, a - b)
  • A multiplication of two expressions. The expressions can be two matrices (A * B), a scalar and a matrix (c * A), or two scalars (a * b). Note that in the first two cases, the multiplication is not commutative; in particular, for the second case, it is required that the scalar coefficient be the first operand of the multiplication.
  • A division of two expressions. The expressions can be either two scalar values (a / b), or a matrix and a scalar (A / b). The latter is mathematically equivalent to (1/b) * A. In both cases, b cannot be 0.
In addition, an expression can also contain the following single-parameter functions:
  • The sine and cosine of an arbitrary scalar value: sin(c), cos(c)
  • The exponential of a scalar value, or of a square-matrix value: exp(c), exp(A). The exponential of a matrix X is mathematically defined as:
where X is a n x n matrix, and In represents the identity matrix (ones on the diagonal, and zeros in rest). Since this formula is an infinite series, the computation of the exponential will be only approximate, as we will see later on.

Here are some examples of valid expressions, according to our definition:



An expression is represented as a DAG (Directed Acyclic Graph), and each node represents an operation (binary operator, or function) or a constant value (and in this case it is a "terminal" node, having no descendants). This allows common subexpressions to appear only once in the DAG. For instance, the first example can be compactly represented as the following DAG:



A starting code skeleton can be found here. It contains the basic class infrastructure, and a basic set of test cases. The code comments may state specific interface requirements.

You are encouraged to write your own test cases, to test all the functional and performance requirements. In grading your submission, we will use the test cases provided in the skeleton, plus other, unpublished ones. All the performance requirements specified in this homework refer to the BC machines.

Note: You are not allowed to modify the public method and constructor signatures provided in the code skeleton (but you may add new methods and classes at will). Changing them will likely result in an incompatibility with our test suite at grading time, and you will lose all the points associated with the affected exercises.

Exercise 1 (40 points)

Take a look at the epfl.sweng.expr package. We represent the DAG nodes as general Expression objects, where each object has 0, 1, or 2 children nodes, depending on its type. ConstantExpression, BinaryExpression, and FunctionExpression implement the specific functionality of each node type.

Note: For this exercise, we are not concerned with the accept() methods of the Expression objects (you may implement them as empty methods).
  1. Take a look at the Expression.java and IExpressionVisitor.java files. Name two design patterns that are used in the code. (2 points)
  2. Implement the ConstantExpression class, which represents a constant value (matrix or scalar) and is a terminal node in an expression DAG. (5 points)
  3. Take a look at the epfl.sweng.expr.operators package. Name one design pattern used in the code. (2 points)
  4. Implement the operators in the Operators class, according to the expression rules defined above. (20 points)
    Note: The operations should throw a MismatchedExpressionsException whenever the operands are invalid for the given operation.
  5. Take a look at the epfl.sweng.expr.functions package. Implement the sin and cos functions (without the exponential). (5 points)
  6. Based on the functionality implemented in points 4 and 5, implement the BinaryExpression and FunctionExpression classes. (6 points)

Exercise 2 (20 points)

Review the matrix exponentiation formula shown in the introduction. Since the formula is an infinite series, we implement it by progressively computing partial sums, until we reach the point when adding one more terms does not increase the sum by more than a constant threshold value.

Use this formula to implement the matrix exponentiation (offered by the Functions class). For checking the approximation condition, you should use the ConstantExpression.approximate() method.

Your code needs to be as efficient as possible. Each computation should work for matrices up to 100 x 100 and exponent values up to 20.0*I(where In is the identity matrix), and the execution time for each exponentiation should always take less than 0.6 seconds. Failing to meet the performance requirements will result in losing 10 points for this exercise, even if the implementation is correct (that is, it gives the right answer).

Exercise 3 (40 points)

In this exercise you will make use of the IExpressionVisitor framework in order to evaluate and print expressions. The IExpressionVisitor methods are called according to the following rules:

  • The preVisit() method is called for each expression node, before it is visited. It returns true or false, depending whether the visitor allows the visiting framework to continue visiting that node and its descendants.
  • The visit() method is called for each visited node, after all its descendants are visited. When a node has two descendants, the left descendant will be visited first.
You need to perform the following tasks:
  1. Implement the accept() methods for ConstantExpression, BinaryExpression, and FunctionExpression, according to the visiting rules described. (10 points)
  2. Take a look at the epfl.sweng.expr.visitors package. Implement an expression printer (i.e., the PrinterVisitor class) that obtains a String representation of an Expression object accepting the printer as a visitor. (15 points)
    The format of the resulting string should be as follows:
    • The format for scalar values should be the one provided by the Double.toString() method.
    • For matrices, the values should appear row-by-row, in a format of the form: [[a,b,c],[d,e,f]] (no spaces between commas or brackets), where each letter stands for the string representation of the corresponding scalar. In this case, (a b c) and (d e f) are the two rows of the matrix.
    • For functions, the format is <functionName>(<parameter>) where <functionName> is the name of the function, and <parameter> is the String representation of the parameter expression. For example: exp(a)
    • For binary operators, there should be exactly one space before and after each operator. For example: a + b
    • You should add parentheses if and only if it is necessary, with no space between them and the inner expression. For example: (a + b) * c
  3. Implement an expression evaluator in the same manner (i.e. the EvaluatorVisitor class). The expression accepting the EvaluatorVisitor object should be evaluated by it to a ConstantExpression value, and is then retrieved using the EvaluatorVisitor.getFinalResult() method. (10 points)
    Note: You should avoid redundant computation and evaluate the nodes only when necessary. Failing to do so will result in losing 5 points for this subpoint, regardless of the correctness of your implementation.
  4. Finally, use the visitor objects in order to implement the epfl.sweng.ExpressionEvaluator class. Read the class comments for more details about the functional requirements. (5 points)

Deliverables for Homework #5

Hand in your assignment by committing all the required files to your SVN account. Below, SVNAccount stands for the actual path to your SVN account (e.g., https://svn.epfl.ch/svn/sweng2010-candea):

  • Place your answers in a file named SVNAccount/trunk/assignment5/answers.txt.
    You must use the provided answers.txt template.
  • Provide your Java source files in a directory named SVNAccount/trunk/assignment5 (the assignment directory). Failing to follow this file structure will result in losing all the points for this assignment. There will be no exceptions this time.
  • Your code must successfully compile on the BC machines, by running from the assignment directory bash -c "/usr/bin/find -name '*.java' | xargs javac -cp 'C:\eclipse\plugins\org.junit4_4.5.0.v20090824\junit.jar'". This command will search for all the Java files in the assignment directory and compile them with javac. If your files do not compile, you will lose all of the points for the code writing exercises that are affected by the compilation errors. 
  • You must write how much time (in hours) you spent solving each exercise in a file named SVNAccount/trunk/assignment5/timeSpent.txt file. You must use the provided template.
  • You are strongly encouraged to commit your homework deliverables from the BC machines, since occasional network connectivity problems may prevent you from submitting from other locations.

Frequently Asked Questions

We will post questions & answers of general interest here, as they are brought up by the students.

Q: Is it OK for the code skeleton not to compile out-of-the-box?

A: Yes, it is expected that compilation errors occur before implementing the requested functionality (for instance, errors in the constructors of the expression classes). Once you properly implement the functionality, the errors should be gone. If you still get any errors after you implement the homework, and believe it's because of the original skeleton, please let us know.


***

Q: What are we supposed to do in the accept() methods?

A: The accept() method is a standard method in one of the design patterns that you need to identify, as part of the homework requirements. You should be able to design its functionality based on the design pattern description and the additional information given in Exercise 3. Moreover, you can also study the test cases provided in the code skeleton, to see how it can be used in practice.


***

Q: How should we measure the execution time for performance-sensitive code?


A: First, in the case of JUnit test cases, you may find more convenient to look at the execution times reported by the JUnit view in Eclipse, next to each test case executed. However, if you want to measure execution times for other pieces of code, you can use "ad-hoc" methods based on recording the start time, end time, and then measuring the difference, and printing it on the screen.


Second, in order to enforce a test case to pass only if the execution time is under a certain value, you should use the "timeout" parameter of the @Test annotation, like this:


@Test(timeout=400)
public void myTest() {
  // ... do expensive operation, and then assert the result is correct
}


Here, "timeout" takes the maximum execution time, in milliseconds. This is the method used in the official test suite, as well.


*** 

Q: Should a scalar value behave like a 1 x 1 matrix, or vice-versa?

A: A scalar and a 1 x 1 matrix should be the same thing. In other words, a constant expression created as a 1 x 1 matrix, or resulted like this from a matrix operation should be accessible as a scalar. Conversely, a constant expression created as a scalar may also be accessed as a 1 x 1 matrix. You should look at the test cases provided in the code skeleton for examples of correct behaviors.

***

Q: How should the division operation deal with divison by zero?

A: As specified in the statement, whenever operands are invalid for a certain operation, the operation implementation should throw a MismatchedExpressionException. A division by zero is also included in this case.

***

Q: What does the remark in the PrinterVisitor code template mean? What are we allowed to use and what shouldn't we?

A: The remark in the code refers to operator implementations only. This means that your code should not explicitly deal with "+", "-", "*", ..., but only deal with the information that can be obtained via the IFunction or IBinaryOperator interface. In other words, if the staff tests your code with other operators that implement the IBinaryOperator interface, your implementation should also work and correctly print the expression.

Finally, you can and should use the specific functionality offered by BinaryExpression, FunctionExpression and ConstantExpression, since they are parameters passed to the overloaded visit() method.