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

Homework #1

Introduction

The goal of this homework is to:
  • give you a feel for how to write efficient and robust code,
  • help you learn how to debug and profile Java programs, and
  • familiarize you with the Eclipse IDE.

Please keep track of how much time, in terms of number of hours, it takes you to solve each exercise, as we will ask you to provide us with this information.

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 October 1, 2010, at 23:59. Any assignments (or parts thereof) handed in late will not be considered.

Exercise 1 (35 points)

In this exercise, you will learn how to debug a Java program using Eclipse's integrated debugger.

To start, download the Test.java, PhDStudent.java, Office.java, and Laboratory.java files. These classes make up a program. The entry point of this program is the Test class. If you run the program, you will notice it throws an exception. Read the code of the program and infer what the program is supposed to do. Then, fix the program. A correct execution of the program should output:

Correct output

--PhD STUDENTS WORKING IN SWENG-1--

Silviu SWENG-1

Vitaly SWENG-1

moving Silviu to office #2

--PhD STUDENTS WORKING IN SWENG-1--

Vitaly SWENG-1

--PhD STUDENTS WORKING IN SWENG-2--

Silviu SWENG-2


You will use the Eclipse IDE, with its integrated debugging environment, to fix the bugs. During the lab session on Friday (24-Sep), we will offer tutorials on using Eclipse and debugging in Eclipse, for those students who are not familiar with the IDE.

The program has 3 bugs introduced there intentionally. Your task is to find these 3 bugs, using code reading and the debugger, and then fix them. The bugs have varying levels of difficulty, so you will get 5 points for finding and fixing the easiest one, 10 points for the medium-difficulty one, and 20 points for the most difficult one.

To fix the bugs, you are allowed to change only the implementations of existing methods. Do not change the Test class, do not try to make the program print the correct output without fixing the bugs (i.e., you must preserve the expected behavior of the program), and do not change/add fields/methods or alter the class hierarchy. Doing any of these will unfortunately lead to you receiving 0 points for Exercise 1.

Exercise 2 (15 points)

In this exercise, you will learn how to choose between two competing fixes of the same bug.

Consider the following Java method that computes the absolute value of an integer x:

The abs(int) method

int abs(int x) {

   if (x >= 0) {

      return x;

   }

   return -x;

}

2.1 (5 points)

The above method has a bug: it does not handle the case when x == Integer.MIN_VALUE.

What value does abs(Integer.MIN_VALUE) return? (1 point)

Why does abs(Integer.MIN_VALUE) not return the mathematically correct value of -Integer.MIN_VALUE? (4 points)

2.2 (10 points)

Consider the following two possible fixes:

A first fix

long abs(int x) {

   long longX = x;

   if (longX >= 0) {

      return longX;

   }

   return -longX;

}

A second fix

int abs(int x) {

   if (x >= 0) {

      return x;

   } 

   if (x == Integer.MIN_VALUE) {

      throw new ArithmeticException("cannot compute abs(Integer.MIN_VALUE)");

   }

   return -x;

}

Does the first fix return the mathematically correct value of -Integer.MIN_VALUE? Explain why. (2 points)

Can the first fix cause the program to terminate with failure or exception? Explain why/how. (2 points)

Say you have to replace the original (buggy) implementation of the abs function with one of the two fixes above. One of the concerns is how much other code (i.e., code that calls the abs function) needs to be changed. Which of the two fixes will require the fewest changes to code that has already been written? Explain why. (3 points)

If the program fails after a call to the abs function, which of the two fixes will be most helpful in debugging the problem? Explain why. (3 points)

Exercise 3 (30 points)

In this exercise, you will learn to use Eclipse's TPTP profiler and write efficient code.

Consider a function that computes the Fibonacci numbers:

Consider the recursive method Fibonacci.fib(int n) from the Fibonacci class, which computes F(n). The TestFibonacci class calls Fibonacci.fib(1000) and measures the execution time. Download these two classes.

3.1 (4 points)

Configure Eclipse's TPTP to profile not only the program itself, but also the calls into JDK classes. To find the bottlenecks, execute the TestFibonacci class in TPTP. Report the top 3 methods that have the highest base execution time, along with their percentages of total execution time, rounded to the nearest integer.

3.2 (15 points)

Write an iterative implementation (instead of the recursive one we gave you) of the Fibonacci function in the Fibonacci.iterativeFib() method. This implementation is supposed to run considerably faster, and has to correctly compute F(x) for F(x) <= Integer.MAX_VALUE. In other words, you do not have to worry about arithmetic overflows in this exercise; the implementation should only be logically correct.

Modify TestFibonacci.java to invoke Fibonacci.iterativeFib() and to use 100,000 instead of 1,000:

Modifications in TestFibonacci.java

public class TestFibonacci {

   public static void main(String[] args) {

       int n = 100000;

       ...

       System.out.println("F(" + n + ") = " + Fibonacci.iterativeFib(n));

       ...

   }

}

To test the performance of Fibonacci.iterativeFib(), run the new TestFibonacci class and report how long it takes to execute. The execution time has to be less than 2 milliseconds on the BC machines.

3.3 (5 points)

The problem with the previous implementation is that it uses a primitive integer type to store the result. Such a type is not sufficient to store the value of F(n), even for small values of n; for instance F(50) = 5* Integer.MAX_VALUE, and F(100) = 38* Long.MAX_VALUE. Write an iterative method Fibonacci.iterativeAllIntegersFib() that is capable of correctly computing F(n) for any value of n between 0 and Integer.MAX_VALUE. For instance, your new implementation should be able to compute the correct value of F(100000). Hint: use the java.math.BigInteger class.

3.4 (6 points)

Modify TestFibonacci.java to invoke Fibonacci.iterativeAllIntegersFib() and to use 1,000 instead of 100,000:

Modifications in TestFibonacci.java

public class TestFibonacci {

   public static void main(String[] args) {

       int n = 1000;

       ...

       System.out.println("F(" + n + ") = " + Fibonacci.iterativeAllIntegersFib(n));

       ...

   }

}

To find the bottlenecks of Fibonacci.iterativeAllIntegersFib(), execute again the TestFibonacci class in the TPTP profiler. Report the top 3 methods that have the highest base execution time, along with their percentages of total execution time. (2 points)

To test the performance of Fibonacci.iterativeAllIntegersFib(), run the program for n=100,000 and report the execution time. Is the call Fibonacci.iterativeAllIntegersFib(n) slower than the call Fibonacci.iterativeFib(n), for n=100,000? Explain why. (2 points)

Is it possible to make your implementation significantly (i.e., at least 2x) more efficient, without changing or replacing the java.math.BigInteger class? Explain why. (2 points)

Exercise 4 (20 points)

In this exercise, you will practice writing robust code.

The Ackermann function is defined as follows:

Helper formulas:

The Ackermann class contains prototypes for implementations of the Ackermann function. TestAckermann is a test class. Download these two classes.

4.1 (10 points)

Implement the Ackermann.ack() method (using the java.math.BigInteger class) such that it computes the correct values of
A(0, y), A(1, y), A(2, y), A(3, y), where 0 <= y <= Integer.MAX_VALUE - 3, and A(4, x), where 0 <= x <= 2. It is not necessary for the program to terminate in a reasonable amount of time for large values of y, but the code should be logically correct and always output the right value (perhaps after running for a very long time).

4.2 (5 points)

Is it possible to compute A(4, 3) using the java.math.BigInteger class? (1 point) Explain why. (4 points)

4.3 (5 points)

Implement the Ackermann.saferAck() method, such that it throws an ArithmeticException whenever it cannot compute the correct result.


Deliverables for Homework #1

To hand in your assignments, you will use your SVN account (create one according to these steps). Below, SVNAccount stands for the actual path to your SVN account (e.g., https://svn.epfl.ch/svn/sweng2010-candea).

  • You must place your answers in an SVNAccount/trunk/assignment1/answers.txt file.
  • You must provide your Java source files in the SVNAccount/trunk/assignment1 folder, including the sources of the test classes. Your code should successfully compile on the BC machines, by running "javac assignment1/*.java". If your files do not compile, you will lose all of the points for the code writing exercises (i.e., exercises 1, 3.2, 3.3, 4.1, 4.3) that are affected by the compilation errors.
  • You must write how much time (in hours) you spent solving each exercise in an SVNAccount/trunk/assignment1/timeSpent.txt file.

Frequently Asked Questions

We will post questions & answers of general interest here, as they appear on the discussion group.


Q: How do I install TPTP?

A: Use Eclipse's Update Manager and follow the steps described in this tutorial.


Q: In Exercise 1, can I fix more than 3 methods?

A: Yes.


Q: Can I use the helper formulas to compute Ackermann's function?

A: Yes. Additionally, you may use any other helper formulas, as long as you specify their source.


Q: What do I do if Eclipse crashes, or some plugin (e.g., TPTP) stops working properly?

A: Start Eclipse with "-clean" option, i.e., run "C:\eclipse\eclipse.exe -clean" from the command prompt.


Q: Where should I run the TestFibonacci class, to measure the execution time?

A: Run it on a BC machine, from a local folder, not a network folder. For instance, copy TestFibonacci.java and Fibonacci.java files into "C:\Documents and Settings\<user name>\workspace\Fibonacci" folder, then go to that folder, compile the two files (i.e., run "javac *.java") and run TestFibonacci class there (i.e., run "java TestFibonacci"). Alternatively, you can create an empty Java project in Eclipse, copy the two files into its "src" folder, refresh the workspace in Eclipse (i.e., press F5 after you click on the project name in Package Explorer view), then run the TestFibonacci class from Eclipse.


Q: What should I do if the TPTP profiler returns different results every time for the TestFibonacci class?

A: Run it a couple of times (e.g., 5 times), and choose the most frequent ranking of the top 3 methods. You can pick any percentages you see for the most frequent ranking.


Q: Where do I find the solutions?

A: You can find them here.