Dr. John Hopcroft: "Computer Science in the Information Age"The last forty years have seen computer science evolve as a major academic discipline. Today the field is undergoing a major change. Some of the drivers of this change are the internet, the world wide web, large sensor networks, large quantities of information in digital form and the wide spread use of computers for accessing information. This change is requiring universities to revise the content of computer science programs. This talk will cover the changes in the theoretical foundations needed to support information access in the coming years.

Professor Hopcroft is the 1986 Turing Award Winner and one of the most influential computer scientists in the world. The Turing Award in computer science is equivalent to the Nobel prize in physics or chemistry.

• I will not be in at all today (Monday).
• I am cancelling the extra session this evening; I'll talk more about the assignment in class.
• I'm extending the due date for Bugs Interpreter, Part II to midnight Sunday, April 27.
• I will give you one more (small!) assignment this Thursday.

Yet another oversight : I forgot to specify that your Bug constructor should have one parameter, the name of the bug (as a String). It's too late to require this, but it will ease our testing if you can provide such a constructor.

The ParserTest.java I provided uses DavesTreeParseMethod.parse in the makeTree method. You can replace this with your Tree.parse. I did this for grading your programs, so that if your parse method is broken it won't cause all my tests to fail.

Also, it uses a Token constructor with only one argument. Here's the code you need:

/**
 * Constructor for Tokens.
 * @param value The characters making up the token.
 */
public Token(String value) {
    this.type = determineTokenType(value);
    this.value = value;
}
 

private Type determineTokenType(String value) {
    char firstCharacter = value.charAt(0);
    
    if (firstCharacter == '\n') return Type.EOL;
    
    else if (Character.isLetter(firstCharacter)) {
        if (value.equals("EOF")) return Type.EOF;
        else if (isKeyword(value)) return Type.KEYWORD;
        else return Type.NAME;
    }
    
    else if (Character.isDigit(firstCharacter)) return Type.NUMBER;
    
    else if (firstCharacter == '.') {
        if (value.length() == 1) return Type.SYMBOL;
        else return Type.NUMBER;
    }
    
    else return Type.SYMBOL;
}

If you don't have an isKeyword method, it's not hard to write one.

Apparently, I also forgot to include numbers and variable names in the list of things that you need to evaluate. So:

• To evaluate a number, use Double.parseDouble(numeral).
• To evaluate a variable name, fetch it from your HashMap.

New postings:

• ParserTest.java -- still relevant to your Interpreter.
• Midterm exam answer key

Also, a couple of people have pointed out that I forgot to include block in the list of node types that need to be interpreted. I hope everyone realized that you can't do the rest of the assignment without interpreting blocks!

I've gotten a number of questions about whether certain children should be omitted from the AST. The rule is this: If a node has children of different kinds (for example, a function node has a name, a var parameter list, and a block body), then all children must be present. This is so that we know exactly where to find each kind of child (in this example, the body is always the third child).

If a node has a variable number of children, all of the same kind (list, var, block, and switch), then it may have zero children. Hence, a function with no parameters still has a var child, but that var child does not have children.

Addition to Tree API assignment: Also provide an @Override public boolean equals(Object obj) method. (It's really hard to do JUnit testing without this!)

Minor corrections:

• public Tree getChild(int index)   should be
  public Tree<V> getChild(int index)


• public Iterator iterator()   should be
  public Iterator<Tree<V>> iterator()


• public static Tree parse(String treeDescription)    should be
  public static Tree<String> parse(String treeDescription)

If you have started this assignment, you will have discovered that the parse(String) method is really difficult. It helps if you use the techniques you learned from the Bugs Recognizer assignment. I also recommend using a StringTokenizer and adding either a void pushBack(String token) method or a String peek() method to it. Don't be afraid to write several helper methods along the way.

Combined errata for the Recognizer assignment:

• Errata #1: isFactor(), color names, <do statement>, isParameterList(), <moveto action>.
• Errata #2: <turn action> and <turnto action>, <switch statement>, <initialization block>, and <bug definition>.
• Errata #3: createTokenizer() and isFollowedBy(Recognizer, String).
• Errata #4: <var declaration> needs <eol>, and isFactor() should handle unary operators.
• Errata #5: Remove the cast to int from Recognizer.nextToken().

Clarification #1: I asked you to try shuffling a ten element array 100 times by each of two shuffle methods, save the results in 10x10 arrays, and print and compare the results. This is not a JUnit test, it's one where you have to look at the results and make a judgment. JUnit tests should never print anything.

Clarification #2: I said you should write test methods for any helper methods you write. I did not mean this to include any helper methods in your JUnit test class. It may be a good idea to test such methods, but it's not required.

Warning: Once you call a sort method on an array, that array is sorted. So if you do something like

bubbleSort(shuffledArray);
insertionSort(shuffledArray);
selectionSort(shuffledArray);

then the latter two calls, despite the names, are not sorting a randomized array.

Suggestion: The easy way to get separate timings on the nine cases is to put each case into a separate method. Like so:

bubbleSortAlreadySortedArray(int[] array) {
 bubbleSort(array);
}
insertionSortAlreadySortedArray(int[] array) {
 insertionSort(array);
}
... // six methods omitted
selectionSortShuffledArray((int[] array) {
 selectionSort(array);
}

Correction: When testing the shuffling methods, I said to "shuffle the array ten thousand times, and see how often each element ends up in each location" Make that "one hundred thousand (100000) times," in order to get the expected value of approximately 1000 in each location of your 10x10 array.

(I had it right the first time; 10 numbers sorted 10000 times, distributed over 100 cells in a 10x10 array, gives an average of 1000 in each cell.)

I wrote the Fraction class for you--the only change you are supposed to make in it is to throw an exception for division by zero. This should be done in the constructor. (You could also do it in the divide method, but that would be redundant.) Also note that throwing an exception does not mean that you should catch the exception--if this isn't clear, you need to review exceptions and exception handling.

I did talk about factory methods in class, but I never meant to imply that you should replace the Fraction constructor with a factory method. Please leave all the method signatures the same! Otherwise you will make it much more difficult for us to test your JUnit methods.

You are expected to test the public String toString() method in the Fraction class. However, your test method cannot be public void toString()--do you see why? You must give the test method some other name, say, testToString.

NetBeans, it turns out, likes to keep its JUnit tests in a different package from the code being tested, and that is causing some problems. If you like, you can change the greatestCommonDivisor method to be public access instead of default (package) access.