[ANU] [DCS] [COMP2100/2500] [Description] [Schedule] [Lectures] [Labs] [Homework] [Assignments] [COMP2500] [Assessment] [PSP] [Java] [Reading] [Help]

COMP2100/2500
Midsemester Exam sample solutions

Question 1 [10 marks]

(a) What is the difference between static and dynamic code analysis? [1 mark]

Solution: Basically what I was looking for here was that in dynamic code analysis you run the code, while in static code analysis you don't.

(b) Name one strength and one weakness of static code analysis. [2 marks]

Solution:

Strength: any one of the following:

• It's more effective than dynamic code analysis.

• It's more efficient than dynamic code analysis.

• (You can start earlier because) You can work on incomplete code.

Weakness: any one of the following:

• It only deals with what you think the code should do.

• It only deals with what you think the code will do.

• It is expensive (in both time and money).

• It is difficult to do well.

(c) The Visitor pattern is not necessarily an improvement over the ‘Expression Version 3’ style of design for recursive data structures. When would you choose the Visitor pattern, and when is the other design more suitable? [2 marks]

Solution: The Visitor pattern design is good if you are going to need to add new operations to a data structure that is not going to change (or will only change a little). By change I mean adding new types of nodes.

The other design is better if you are more likely to add new types of nodes and less likely to add new operations.

(d) Explain the roles of the three components in the Model-View-Controller architecture for graphical user interfaces. [3 marks]

Solution:

The Model is the underlying data and functionality of the application. It registers its views and informs them when it changes. It responds to instructions from the Controller by changing its state.

The View is responsible for displaying data from the Model to the user. It responds to updates from the Model by requesting the data it needs from the Model. It responds to instructions from the Controller by changing its appearance.

The Controller is responsible for handling input from the user (and other events). It tells the Model to change its state. It tells the View to change its appearance.

(e) Explain the steps involved in adding a button to a Swing window and arranging that a message “Button pressed!” is printed on System.out every time the user clicks on it. You do not have to write code. [2 marks]

Solution:

1. Create a button object (an instance of class JButton or a subclass).

2. Add that button to the window (perhaps involving some layout manager).

3. Create a listener for the button. (This is really two steps, but they're often rolled into one. Really you have to create a class and then an instance of that class.)

4. In its actionPerformed() method, put the instruction System.out.println("Button pressed!");. (This could be part of the previous step, but I wanted to see it somewhere.)

5. Link the listener to the button. (You do this with the addActionListener() method, but you didn't have to remember this.

---

Question 2 [10 marks]

This question is about recursive tree data structures for representing algebraic expressions. We use the ‘Expression Version 4’ design (with the Visitor pattern) studied in lectures and in Lab 2. Your task here is to add the notion of variables to the system.

A variable has (a) a name, i.e. a textual representation, which is a single letter, represented in Java using the type char; and (b) a value, which is an integer, represented in Java using the type int. The set of variables used in evaluating an expression is stored in a Hashtable which maps variable names to variable values.

You may assume that the main class has a field:

Hashtable variables = new Hashtable();

which is initialized thus:

variables.put('a', 1);
variables.put('b', 2);
variables.put('c', 3);
variables.put('d', 4);

So, for example, the expression

System.out.println((Integer) variables.get('c'))

will print the number 3. (This uses the automatic boxing and unboxing features of Java 1.5, but not generics. We could implement the lookup table with a Hashtable<Character, Integer> but since we haven't used this in labs or assignments, we'll stick to the old form for now.)

The Expression class looks like this.

public abstract class Expression {
    public abstract void accept(Visitor v);
}

Operations on expressions are performed by visitors, which must all implement the following interface.

public interface Visitor {
    public abstract void visitConstant(Constant c);
    public abstract void visitAddition(Addition a);
    public abstract void visitVariable(Variable v);
}

Class Expression will have only three effective subclasses, representing constants, variables and sums of two expressions. Only one of these, class Constant, has been implemented:

public class Constant extends Expression {

    int value;

    public Constant(int v) { value = v; }

    public void accept(Visitor visitor) {
        visitor.visitConstant(this);
    }
}

(a) Write class Variable, which inherits from class Expression. Note the following:

• It must have a field of type char to store its name.

• The constructor must take one argument of type char and initialize the field appropriately.

• It must have an appropriate accept() method.

[2 marks]

Solution:

public class Variable extends Expression {

    char name;

    public Variable(char c) {
        name = c;
    }

    public void accept(Visitor v) {
        v.visitVariable(this);
    }
}

Many students gave the character argument (c above) a nice identifier (name), but then gave the field (which is part of the public interface of the class) a single-letter identifier. This is the wrong way round. The class interface needs to be carefully designed, while method arguments and locals can have single-letter identifiers without damaging usability and readability. This was even worse in part (b) where the two sub-expressions were getting names like e1 and e2. I didn't take marks off for this, which is lucky for many of you. I will take marks off in the final exam, so be warned!

(b) Write class Addition, which inherits from class Expression and represents sums of two sub-expressions. Note the following:

• Each object must store its two sub-expressions in fields of type Expression.

• The constructor must take two arguments of class Expression and initialize the fields appropriately.

• It must have an appropriate accept() method.

[2 marks]

Solution:

public class Addition extends Expression {

    Expression left, right;

    public Addition(Expression l, Expression r) {
        left = l;
        right = r;
    }

    public void accept(Visitor v) {
        v.visitAddition(this);
    }
}

(c) Write class Evaluator, which traverses a tree and calculates the value of the expression. Note the following:

• An expression evaluator must have a field result of type int for storing the result of its calculations.

• It must also store a lookup table with values for variables.

• The constructor must take one argument of type Hashtable and initialise its fields appropriately.

• Class Evaluator must implement the Visitor interface.

• The visitVariable() method must look up the value of the variable in the lookup table, and set the value of result accordingly.

• You may use Java 1.5 features such as automatic boxing and unboxing if you want.

[3 marks]

Solution:

public class Evaluator implements Visitor {

    public int result;
    private Hashtable variables;

    public Evaluator(Hashtable h) {
        variables = h;
    }

    public void visitConstant(Constant c) {
        result = c.value;
    }

    public void visitAddition(Addition a) {
        a.left.accept(this);
        int subtotal = result;
        a.right.accept(this);
        result += subtotal;
    }

    public void visitVariable(Variable v) {
        result = (Integer) variables.get(v.name);
    }
}

There's no need to initialise result since Java sets it to zero automatically.

In visitAddition() you could also spawn other evaluators to do the left and right sides, and then get their results back and add them together, as in the lecture notes. Either method works.

The cast to Integer in visitVariable() is necessary, even with automatic boxing and unboxing, since calling get() on an ordinary Hashtable just returns an Object. Java 1.5 can convert Integer to int and vice-versa, but it can't figure out that an object is really an integer. You have to help it there.

I've made result public but this probably isn't the best solution. Several students had it private and then provided an accessor method. That's better.

(d) Write code that assigns to e a reference to a structure corresponding to the expression (a + ((c + 5) + d)), then prints out the value of that expression. In addition to the declaration and initialisation of the Hashtable (on page 4), you may assume the following declarations:

Expression e;
Constant c;
Addition a, b;
Variable x, y, z;
Evaluator v;

You may use Java 1.5 features such as automatic boxing and unboxing if you want.

[3 marks]

Solution:

c = new Constant(5);
x = new Variable('a');
y = new Variable('c');
z = new Variable('d');
a = new Addition(y, c);
b = new Addition(a, z);
e = new Addition(x, b);

v = new Evaluator(variables);
e.accept(v);
System.out.println(v.result);

The declarations made it confusing; that was deliberate. Most students were able to sort it out.

The single quote marks around the names of the variables are necessary and very important.

You must create the Evaluator object and then get the top node of the expression to accept it.

Question 3 [10 marks]

In this question you have to do a code review. The code you are to review is an attempted solution to a slightly modified version of Homework 2. The requirements for the program are:

Write a Java program (in a class Factors) that repeatedly prompts the user for an integer and then prints out the complete prime factorisation of that integer, with the factors in ascending order.

The program must stop when it reads an integer that is less than or equal to 1. If the user types something other than an integer, your program must ignore it and wait until the user types an integer.

Here is a sample run of the program. User input is in boldface, system output in normal type. Your final output should be formatted exactly like this:

comp2100@partch$ java Factors
> 15
15 = 3 * 5
> 180
180 = 2 * 2 * 3 * 3 * 5
> 1999
1999 = 1999
> 2000
2000 = 2 * 2 * 2 * 2 * 5 * 5 * 5
> 2001
2001 = 3 * 23 * 29
> 2002
2002 = 2 * 7 * 11 * 13
> 2003
2003 = 2003
> 0
Goodbye

The attempted solution consists of one class called Factors.

 1 class Factors {
 2 
 3     public static void mane(String[] args) {
 4         Scanner s = new Scanner(System.in);     
 5 
 6         System.out.print("> ");
 7         if (s.hasNextInt()) {
 8             int n = s.nextInt();
 9         }
10         while (n > 1) {
11             printFactors(n);
12             System.out.print("> ");
13             if (s.hasNextInt())
14                 n = s.nextInt();
15             }
16         }
17         System.out.println("Goodbye");
18     }
19
20     public static void printFactors(int n) {
21         int p = 1;
22
23         System.out.print(n + " = "};
24         while (p < n) {
25             if (n % p == 0) {
26                 System.out.print(p + " * ");
27                 n = n / p;
28             }
29             p = p + 1;
30         }
31     }
32 }

(a) What will be printed on System.out by the call printFactors(4)? (What will actually be printed, not what should be printed.) [1 mark]

Solution: Of course as it stands, it wouldn't produce anything because the code for printFactors() contains a syntax error. But assuming that error is fixed and no other changes made, the call printFactors(4) will produce the following: 4_=_1_*_2_*_ (where I've used underscore characters to represent spaces).

(b) There are nine defects in this program. All are genuine defects in the code, that will either generate a compilation error or cause the program to crash or give wrong results. Ignore any errors of style or problems with comments etc.

Perform a careful review of this code and locate all defects. For each defect, write the number of the line on which it occurs, together with a clear, concise statement of what is wrong there. [9 marks]

Solution:

1. Line 1: Missing import of java.util.Scanner.

2. Line 3: The method name “mane” is wrong; it should be “main”. Contrary to what some students wrote, this isn't a syntax error. The program compiles just fine. It's when you try to run it that you get an error because the JVM can't find a main method to run. The error message is

   Exception in thread "main" java.lang.NoSuchMethodError: main

   But don't worry, I didn't take any marks off for that.

3. Line 8: The declaration of n is inside the if statement. This means that n will be out of scope outside there, so that references to it on lines 10, 11 and 14 will generate compiler errors. (I was happy to pay this as a defect at any or all of those lines too, but it was still only worth one mark.)

4. Line 13: There is a left bracket missing at the end of the line. (Or alternatively there is an extra right bracket at line 15. But not both.)

5. Lines 10–16 : A non-integer input from the user, once inside the loop, will cause an infinite loop.

6. Line 21: Need to initialise n to 2, not 1, since 1 is not a prime. You didn't need to know the maths for that, just look at the sample output.

7. Line 23: Syntax error — the } at the end of the line should be a ).

8. Line 29: We should only increment p if it wasn't a factor, so this should be inside an else part. As it stands, the program ignores the possibility of repeated factors.

9. Line 31: The program doesn't print the last factor. Adding a line System.out.println(p); here (between lines 30 and 31) will fix it. Several students reported other defects related to this: the lack of a newline character before prompts was one example. Some students saw it as a defect at line 24, where they thought the condition should have been p<=n. This gets the last factor, but then line 26 would also have to be changed so that it doesn't print an asterisk after the last factor. All of this was correct, and any of these observations earned you a mark, but only one mark. You couldn't get more marks for observing more consequences of this defect.

Question 4 [10 marks]

This question is about the PSP. A student has completed a PSP Project Plan Summary form for Program #1 and now starts working on Program #2.

Fill in the ‘Plan’ column of the PSP Project Plan Summary form based on a size estimate of 50 lines of code with maximum of 60 and minimum of 40. Take all other plan data from the completed form for Program #1.

The student takes 12 minutes to complete the Planning phase, 8 minutes to complete the Design phase, 28 minutes to complete the Code phase, 16 minutes to complete the Compile phase, 88 minutes to complete the Test phase, and 8 minutes to complete the Postmortem phase.

The student injects 4 defects in the Design phase, 8 in the Code phase, 2 in the Compile phase and 1 in the Test phase.

The student removes 3 defects in the Code phase, 7 in the Compile phase and 5 in the Test phase.

The finished program is 40 lines of code.

Record all this information on the form.

Now complete the rest of the form: all totals in the ‘Actual’ column, plus everything in the ‘To Date’ and ‘To Date %’ columns.

You do not have to fill in the ‘greyed-out’ parts of the form.

(Note that the numbers have been carefully chosen so that all the results come out as simple round numbers. You do not need a calculator.)

Here is the student's PSP Project Plan Summary form for Program #1, with all details completed.

Student	A. Student	Date	27/4
Program	Character Table	Program #	1
Instructor	I. Barnes	Language	Java

Summary	Plan	Actual	To Date
Minutes/LOC	2.0	2.0	2.0
LOC/Hour	30	30	30
Program Size (LOC):
Total new & changed	50	40	40
Maximum size	70
Minimum size	30

Time in phase (min)	Plan	Actual	To Date	To Date %
Planning	20	12	12	15%
Design	10	4	4	5%
Code	20	32	32	40%
Compile	10	8	8	10%
Test	20	8	8	10%
Postmortem	20	16	16	20%
Total	100	80	80	100%
Maximum Time	140
Minimum Time	60

Defects Injected	Actual	To Date	To Date %
Planning
Design	1	1	20%
Code	3	3	60%
Compile
Test	1	1	20%
Total	5	5	100%
Defects Removed	Actual	To Date	To Date %
Planning
Design
Code	1	1	20%
Compile	1	1	20%
Test	3	3	60%
Total	5	5	100%

Here is a new PSP Project Plan Summary form for Program #2 that you have to complete using data taken from the form for Program #1 and the description of events above.

Solution:

Student	A. Student>	Date	28/4
Program	Factors	Program #	2
Instructor	I. Barnes	Language	Java

Summary	Plan	Actual	To Date
Minutes/LOC	2.0	4.0	3.0
LOC/Hour	30	15	20
Program Size (LOC):
Total new & changed	50	40	80
Maximum size	60
Minimum size	40

Time in phase (min)	Plan	Actual	To Date	To Date %
Planning	15	12	24	10%
Design	5	8	12	5%
Code	40	28	60	25%
Compile	10	16	24	10%
Test	10	88	96	40%
Postmortem	20	8	24	10%
Total	100	160	240	100%
Maximum Time	120
Minimum Time	80

Defects Injected	Actual	To Date	To Date %
Planning
Design	4	5	25%
Code	8	11	55%
Compile	2		20%
Test	1	2	10%
Total	15	20	100%
Defects Removed	Actual	To Date	To Date %
Planning
Design
Code	3	4	20%
Compile	7	8	40%
Test	5	8	40%
Total	15	20	100%

[ANU] [DCS] [COMP2100/2500] [Description] [Schedule] [Lectures] [Labs] [Homework] [Assignments] [COMP2500] [Assessment] [PSP] [Java] [Reading] [Help]

Copyright © 2005, Ian Barnes, The Australian National University
Version 2005.1, Friday, 3 June 2005, 12:52:15 +1000
Feedback & Queries to comp2100@cs.anu.edu.au